1 """
2 treeutil
3 ========
4 Contains all sort of utilities to search and manipulate nested lists as trees.
5
6 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
7 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
8 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
9 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
10 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
11 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
12 THE SOFTWARE.
13
14 @author: by Mehdi Khoury
15 @version: 1.20
16 @copyright: (c) 2009 Mehdi Khoury under the mit license
17 http://www.opensource.org/licenses/mit-license.html
18 """
19
20 from collections import deque
21 import psyco
22 import pickle
23 import copy
24 import array
25 import string
26
27
28
34
35
38
39 psyco.profile()
40
42 """
43 Function: listGetRootNode
44 ==========================
45 get the root node of a nested list
46
47 @param myTree: the nested list representing a tree
48
49 @return: the root node of a nested list
50
51 """
52 if type(myTree)is not list:
53 raise NotAList, "Tree should be a (nested) list."
54 if not myTree:
55 raise EmptyList, "Tree should not be empty."
56 if type(myTree[0])is list:
57 raise NestedHeadNode, "Head node should not be a list."
58 exit
59 return myTree[0]
60
61
63 """
64
65 Function: BFS_Search
66 =====================
67 Traverse the nodes of a tree in breadth-first order.
68
69 @param myTree: the nested list representing a tree
70
71 @return: an generator for a list of nodes in Breath First Search order
72
73 """
74
75 queue = deque(myTree)
76 while queue:
77 node = queue.popleft()
78 if type(node) is list:
79 yield node[0]
80 for elem in node[1:]:
81 queue.append(elem)
82 else: yield node
83
84
85
87 """
88 Function: walk
89 ===============
90 Walk over a sequence of items, printing each one in turn, and
91 recursively walking over sub-sequences.
92
93 @param seq: the nested list representing a tree
94
95 """
96 print seq
97 if isinstance(seq, list):
98 for item in seq:
99 walk(item)
100
101
103 """
104
105 Function: getChildrenNodes2
106 ============================
107 Get the children nodes in a nested list for a specific depth
108
109 @param lst: the nested list representing a tree
110 @param depth: the nested list representing a tree
111
112 @return: a flat list of children nodes for a specific depth
113
114 """
115 result=[]
116 if depth>0:
117 for elem in getChildrenNodes2(lst,depth-1):
118 if isinstance(elem, list):
119 result.extend(elem[1:])
120 else:
121 result =lst
122 return result
123
124
125
126
127
128
129
130 -def PostOrder_Search(myTree):
131 """
132 Function: PostOrder_Search
133 ===========================
134 Traverse the nodes of a tree by getting the leafs
135 first and the branches after. Finishes with the root.
136 e.g. [1,[2,[3,4,[5,6,7]]],[8,[9,10,11]],[12,13,14]]
137 gives : [7, 6, 5, 4, 3, 2, 11, 10, 9, 8, 14, 13, 12, 1]
138
139 @param myTree: the nested list representing a tree
140
141 @return: a flat list of nodes in PostOrder Search
142
143 """
144 queue = deque(myTree)
145
146 node = queue.popleft()
147 queue.append(node)
148
149 while queue:
150 node = queue.popleft()
151 if type(node) is list:
152 for elem in node:
153 queue.appendleft(elem)
154 else: yield node
155
156
157
159 """
160 Function: DFS_Search
161 =====================
162 a recursive generator that flatten a nested list
163 gives a list of all nodes in the tree in Depth First Search order
164
165 @param seq: the nested list representing a tree
166
167 @return: a flat list of nodes in Depth First Search order
168
169 """
170 for x in seq:
171 if type(x) is list:
172 for y in DFS_Search(x):
173 yield y
174 else:
175 yield x
176
177
179 """
180 Function: BranchNodes_Search
181 =============================
182 a generator to iterate through branch nodes only in BFS order.
183
184 @param myTree: the nested list representing a tree
185
186 @return: a flat list of branch nodes nodes in BFS order.
187
188 """
189 queue = deque(myTree)
190 node = queue.popleft()
191 yield node
192 while queue:
193 node = queue.popleft()
194 if type(node) is list:
195 yield node[0]
196 for elem in node:
197 queue.append(elem)
198
199
201 """
202 Function: LeafNodes_Search
203 ===========================
204 a generator to iterate through leaf nodes
205 only in right-to-left BFS preorder.
206
207 @param myTree: the nested list representing a tree
208
209 @return: a flat list of leaf nodes nodes in BFS preorder.
210
211 """
212 queue = deque(myTree)
213
214 queue.popleft()
215 while queue:
216 node = queue.popleft()
217 if type(node) is list:
218 for elem in node[1:]:
219 queue.appendleft(elem)
220 else: yield node
221
222
223
224
225
226
228 """
229 Function: isNested
230 ===================
231 Check if a list is nested
232
233 @param myList: the nested list representing a tree
234
235 @return: 1 if nested , 0 if not.
236
237 """
238 for elem in myList:
239 if type(elem) is list:
240 return 1
241 else:
242 return 0
243
244
245
246
247
248
250 """
251 Function: list_getTail
252 =======================
253 get the tail of a 'node'
254 e.g. [1,2]->[2]
255 e.g. [1,[2,4],5]->[2,5]
256
257 @param myList: the nested list representing a tree
258
259 @return: the tail of the list
260
261 """
262 value =[]
263 if type(myList) is list:
264 for elem in myList[1:]:
265 if type(elem) is not list :
266 value.append(elem)
267 else:
268 value.append(elem[0])
269 return value
270
271
273 """
274 Function: getSubLists
275 ======================
276 get a list of all sub lists in a nested list
277
278 @param myList: the nested list representing a tree
279
280 @return: a list of all sub lists in a nested list
281
282 """
283 temp = myList
284 result=[]
285 while temp:
286 elem = temp.pop(0)
287 if type(elem) is list:
288 result.append(elem)
289 temp.extend(elem)
290 return result
291
292
294 """
295 Function: nestedListToDict
296 ===========================
297 get a dictionnary from a nested list
298
299 @param myList: the nested list representing a tree
300
301 @return: a dictionary
302
303 """
304 if not myList:
305 raise EmptyList, "Tree should not be empty."
306 exit
307 result={}
308 result[myList[0]]=list_getTail(myList)
309 temp = getSubLists(myList)
310 for elem in temp: result[elem[0]]=list_getTail(elem)
311 return result
312
313
315 """
316 Function: dictFindRootNode
317 ===========================
318 find the root node of a tree
319 in a dictionary (assumption is that
320 a root node is a key never found in
321 any of all values)
322
323 @param myDict: the dictionary representing a tree
324
325 @return: a dictionary
326
327 """
328 result=None
329 temp=[]
330 for elem in myDict.itervalues():
331 temp.extend(elem)
332 for key in myDict.iterkeys():
333 if key not in temp:
334 result = key
335 return result
336 return result
337
338
340 """
341 Function: dictGetRootList
342 ==========================
343 get the list coresponding to the root node
344
345 @param myDict: the dictionary representing a tree
346
347 @return: the list coresponding to the root node
348
349 """
350 result=[]
351 root = dictFindRootNode(myDict)
352 atom = [root]
353 atom.extend(myDict[root])
354 result.extend(atom)
355 return result
356
357
358
360 """
361 Function: dictToSubLists
362 =========================
363 get a list version of the dictionary
364
365 @param myDict: the dictionary representing a tree
366
367 @return: the list corresponding to the dictionary
368
369 """
370 result =[]
371 for k, v in myDict.iteritems():
372 atom=[k]
373 atom.extend(v)
374 result.append(atom)
375 return result
376
377
379 """
380 Function: nestedInsert
381 =======================
382 nest a list inside another one if the
383 first one has elements which are head of
384 lists or sub lists in list 2
385
386 @param list1: flat list 1
387 @param list1: flat list 2
388
389 @return: resulting nested list
390
391 """
392 temp = list1
393 for i in xrange(1,len(temp)):
394 for elem in list2:
395 if temp[i]== elem[0]:
396 temp[i]=nestedInsert(elem,list2)
397 return temp
398
399
401 """
402 Function: dictToNestedList
403 ===========================
404 finally, transform the dictionary
405 into a nested list
406
407 @param myDict: the dictionary representing a tree
408
409 @return: the nested list corresponding to the dictionary
410
411 """
412 if not myDict:
413 raise EmptyDict, "Dictionary should not be empty."
414 exit
415 root = dictGetRootList(myDict)
416 sublists = dictToSubLists(myDict)
417 sublists.remove(root)
418 return nestedInsert(root,sublists)
419