1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
|
# -*- coding: iso-8859-1 -*-
# GNU Solfege - free ear training software
# Copyright (C) 2005, 2006, 2007, 2008 Tom Cato Amundsen
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
import weakref
class NodeNotFound(Exception):
pass
class Cursor(object):
def __init__(self, node):
"""
node -- The node the cursor will be pointing to when created.
"""
self.m_tree = node
self.m_pos = []
while 1:
try:
self.m_tree = self.m_tree.parent()
except AttributeError:
break
def new_point_to_node(node):
c = Cursor(node)
c.goto_node(node)
return c
new_point_to_node = staticmethod(new_point_to_node)
def _find_node(self):
"""
Return the node for self.m_pos. Will raise IndexError if
self.m_pos points to a node that does not exist.
"""
if self.m_pos == []:
return self.m_tree
node = self.m_tree.m_children[self.m_pos[0]]
for x in self.m_pos[1:]:
node = node.m_children[x]
return node
def get(self):
return self._find_node()
def get_prev(self):
"""
Return the prev node, without changing the cursor.
Return None if we are on the first node.
"""
c = self.copy()
if c.go_prev():
return c.get()
def get_parent(self):
"""
Return the parent node, without changing the cursor.
Return None if we are on the first node.
"""
c = self.copy()
if c.go_parent():
return c.get()
def goto_last_child(self):
"""
Go to the last child in m_children.
"""
assert self._find_node().m_children
self.m_pos.append(len(self._find_node().m_children)-1)
def goto_node(self, node):
"""
Move the pointer to the node "node".
Return True if successful.
Raise NodeNotFound if we cannot find the node
"""
while self.go_next():
if self.get() == node:
return True
raise NodeNotFound(node)
def go_next(self):
"""
Go to the next node.
Return True if we can go next.
Return False without changing the cursor if we are on the last node.
"""
p = self.get()
if p.m_children:
self.m_pos.append(0)
return True
else:
# Check if the m_children we are in has more lements.
# If so return True
# Go up one level
# until []
# First go from [0,0,0] to [0,0,1]
try:
c = self.copy()
c.m_pos[-1] += 1
c._find_node()
self.m_pos[-1] += 1
return True
except IndexError:
# Then try [0, 1]
while len(c.m_pos) > 0:
try:
c.m_pos = c.m_pos[:-1]
c.m_pos[-1] += 1
c._find_node()
self.m_pos = c.m_pos[:]
return True
except:
pass
return False
def go_prev(self):
"""
Go to the previous node.
Return True if sucessful.
Return False without changing the cursor if we are on the first node.
"""
if not self.m_pos:
return False
if self.m_pos[-1] > 0:
self.m_pos[-1] -= 1
if self._find_node().m_children:
# go to last node of child
while self._find_node().m_children:
self.m_pos.append(len(self._find_node().m_children)-1)
else:
self.m_pos = self.m_pos[:-1]
return True
def go_parent(self):
"""
Go to the parent node.
Return True if sucessfull.
Return False if we have no parent node to move to.
"""
if self.m_pos != []:
self.m_pos = self.m_pos[:-1]
return True
return False
def goto(self, pos):
"""
Go to pos.
Don't change, and raise IndexError if pos is not valid.
"""
c = self.copy()
c.m_pos = pos
c._find_node()
self.m_pos = pos
def go_prev_sibling(self):
"""
Given the tree
A
B
C
D
E
and we are at pos D, go_prev_sibling will move the cursor to B
Return True on success.
Return False if there is no prev sibling
"""
level = len(self.m_pos)
c = self.copy()
while c.go_prev():
if len(c.m_pos) == level:
self.m_pos = c.m_pos[:]
return True
return False
def get_prev_sibling(self):
c = self.copy()
if c.go_prev_sibling():
return c.get()
def go_next_sibling(self):
"""
Given the tree
A
B
C
D
E
and we are at pos B, go_prev_sibling will move the cursor to D
Return True on success.
Return False if there is no prev sibling
"""
level = len(self.m_pos)
c = self.copy()
while c.go_next():
if len(c.m_pos) == level:
self.m_pos = c.m_pos[:]
return True
return False
def get_next_sibling(self):
c = self.copy()
if c.go_next_sibling():
return c.get()
def is_child_of(self, *names):
"""
names -- the names to test for
Return the name of the found parent.
Return None if not ancestor.
"""
if type(names[0]) == tuple:
names = names[0]
c = self.copy()
while c.go_parent():
if c.get().m_name in names:
return c.get().m_name
return None
def copy(self):
"""Return a copy of ourselves."""
c = Cursor(self.m_tree)
c.m_pos = self.m_pos[:]
return c
def insert(self, node):
"""
Insert the node before the node we are pointing to. Self will
point to the newly inserted node.
"""
c = self.copy()
c.go_parent()
c.get().m_children.insert(self.m_pos[-1], node)
def pop(self):
"""
Remove the element pointed at, and return it.
The cursor will move to the node before the deleted node.
"""
node = self.get()
c = self.copy()
c.go_parent()
del_idx = self.m_pos[-1]
self.go_prev()
del c.get().m_children[del_idx]
return node
def delete(self):
"""
Delete the node we are pointing too.
The node should have no children.
We will move to the node before the deleted node.
Raise IndexError if we try to delete the toplevel node.
"""
node = self.get()
assert not node.m_children
c = self.copy()
if c.go_parent():
del_idx = self.m_pos[-1]
self.go_prev()
del c.get().m_children[del_idx]
else:
# We are on the top level
raise IndexError("We cannot delete the toplevel node.")
pass
def last(self):
"""
return the last node in the tree.
raise IndexError if the tree is empty.
"""
self.m_pos = []
node = self.m_tree
while node.m_children:
self.m_pos.append(len(node.m_children)-1)
node = node.m_children[-1]
class TreeNode(object):
def __init__(self, name='noname'):
self.m_name = name
self.m_children = []
def add(self, child):
child.parent = weakref.ref(self)
self.m_children.append(child)
def show(self, level=0):
print " "*level, self, self.m_name
for n in self.m_children:
n.show(level + 1)
def iterate_tree(self):
yield self
for n in self.m_children:
for x in n.iterate_tree():
yield x
def iterate_children(self):
for n in self.m_children:
for x in n.iterate_tree():
yield x
|