5 """Auto-generate reStructuredText of the hooke module tree for Sphinx.
7 This script is adapted from one written for `Bugs Everywhere`_.
9 .. _Bugs Everywhere: http://bugseverywhere.org/
16 sys.path.insert(0, os.path.abspath('..'))
20 t = ':mod:`%s`' % modname
22 return '\n'.join([delim, t, delim, '', ''])
24 def automodule(modname):
26 '.. automodule:: %s' % modname,
31 def toctree(children):
32 if len(children) == 0:
39 ' %s.txt' % c for c in sorted(children)
42 def make_module_txt(modname, children):
43 filename = os.path.join('hooke', '%s.txt' % modname)
44 if not os.path.exists('hooke'):
46 if os.path.exists(filename):
47 return None # don't overwrite potentially hand-written files.
48 f = file(filename, 'w')
49 f.write(title(modname))
50 f.write(automodule(modname))
51 f.write(toctree(children))
57 """A traversable tree structure.
70 >>> i = Tree(); i.n = "i"
71 >>> h = Tree([i]); h.n = "h"
72 >>> f = Tree([h]); f.n = "f"
73 >>> e = Tree(); e.n = "e"
74 >>> c = Tree([f,e]); c.n = "c"
75 >>> g = Tree(); g.n = "g"
76 >>> d = Tree([g]); d.n = "d"
77 >>> b = Tree([d]); b.n = "b"
78 >>> a = Tree(); a.n = "a"
82 Get the longest branch length with
87 Sort the tree recursively. Here we sort longest branch length
90 >>> a.sort(key=lambda node : -node.branch_len())
91 >>> "".join([node.n for node in a.traverse()])
94 And here we sort shortest branch length first.
96 >>> a.sort(key=lambda node : node.branch_len())
97 >>> "".join([node.n for node in a.traverse()])
100 We can also do breadth-first traverses.
102 >>> "".join([node.n for node in a.traverse(depth_first=False)])
105 Serialize the tree with depth marking branches.
107 >>> for depth,node in a.thread():
108 ... print "%*s" % (2*depth+1, node.n)
119 Flattening the thread disables depth increases except at
122 >>> for depth,node in a.thread(flatten=True):
123 ... print "%*s" % (2*depth+1, node.n)
134 We can also check if a node is contained in a tree.
136 >>> a.has_descendant(g)
138 >>> c.has_descendant(g)
140 >>> a.has_descendant(a)
142 >>> a.has_descendant(a, match_self=True)
145 def __cmp__(self, other):
146 return cmp(id(self), id(other))
148 def __eq__(self, other):
149 return self.__cmp__(other) == 0
151 def __ne__(self, other):
152 return self.__cmp__(other) != 0
154 def branch_len(self):
155 """Return the largest number of nodes from root to leaf (inclusive).
163 this method returns 5.
167 Exhaustive search every time == *slow*.
169 Use only on small trees, or reimplement by overriding
170 child-addition methods to allow accurate caching.
175 return 1 + max([child.branch_len() for child in self])
177 def sort(self, *args, **kwargs):
178 """Sort the tree recursively.
180 This method extends :meth:`list.sort` to Trees.
184 This method can be slow, e.g. on a :meth:`branch_len` sort,
185 since a node at depth `N` from the root has it's
186 :meth:`branch_len` method called `N` times.
188 list.sort(self, *args, **kwargs)
190 child.sort(*args, **kwargs)
192 def traverse(self, depth_first=True):
193 """Generate all the nodes in a tree, starting with the root node.
198 Depth first by default, but you can set `depth_first` to
199 `False` for breadth first ordering. Siblings are returned
200 in the order they are stored, so you might want to
201 :meth:`sort` your tree first.
203 if depth_first == True:
206 for descendant in child.traverse():
208 else: # breadth first, Wikipedia algorithm
209 # http://en.wikipedia.org/wiki/Breadth-first_search
211 while len(queue) > 0:
216 def thread(self, flatten=False):
217 """Generate a (depth, node) tuple for every node in the tree.
219 When `flatten` is `False`, the depth of any node is one
220 greater than the depth of its parent. That way the
221 inheritance is explicit, but you can end up with highly
224 When `flatten` is `True`, the depth of any node is only
225 greater than the depth of its parent when there is a branch,
226 and the node is not the last child. This can lead to ancestry
227 ambiguity, but keeps the total indentation down. For example::
233 would both produce (after sorting by :meth:`branch_len`)::
243 stack = [] # ancestry of the current node
247 for node in self.traverse(depth_first=True):
248 while len(stack) > 0 \
249 and id(node) not in [id(c) for c in stack[-1]]:
258 depth = depthDict[id(parent)]
259 if len(parent) > 1 and node != parent[-1]:
261 depthDict[id(node)] = depth
265 def has_descendant(self, descendant, depth_first=True, match_self=False):
266 """Check if a node is contained in a tree.
271 The potential descendant.
273 The search order. Set this if you feel depth/breadth would
278 x.has_descendant(x, match_self=True) -> True
280 if descendant == self:
282 for d in self.traverse(depth_first):
288 def python_tree(root_path='hooke', root_modname='hooke'):
290 tree.path = root_path
293 while len(stack) > 0:
295 if f.path.endswith('.py'):
296 f.name = os.path.basename(f.path)[:-len('.py')]
297 elif os.path.isdir(f.path) \
298 and os.path.exists(os.path.join(f.path, '__init__.py')):
299 f.name = os.path.basename(f.path)
301 for child in os.listdir(f.path):
302 if child == '__init__.py':
305 c.path = os.path.join(f.path, child)
311 f.modname = root_modname
313 f.modname = f.parent.modname + '.' + f.name
317 if __name__ == '__main__':
318 pt = python_tree(root_path='../hooke', root_modname='hooke')
319 for node in pt.traverse():
321 make_module_txt(node.modname, [c.modname for c in node])