3 # Copyright (C) 2010 W. Trevor King <wking@drexel.edu>
5 # This file is part of Hooke.
7 # Hooke is free software: you can redistribute it and/or modify it
8 # under the terms of the GNU Lesser General Public License as
9 # published by the Free Software Foundation, either version 3 of the
10 # License, or (at your option) any later version.
12 # Hooke is distributed in the hope that it will be useful, but WITHOUT
13 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
15 # Public License for more details.
17 # You should have received a copy of the GNU Lesser General Public
18 # License along with Hooke. If not, see
19 # <http://www.gnu.org/licenses/>.
21 """Auto-generate reStructuredText of the hooke module tree for Sphinx.
23 This script is adapted from one written for `Bugs Everywhere`_.
25 .. _Bugs Everywhere: http://bugseverywhere.org/
32 sys.path.insert(0, os.path.abspath('..'))
36 t = ':mod:`%s`' % modname
38 return '\n'.join([delim, t, delim, '', ''])
40 def automodule(modname):
42 '.. automodule:: %s' % modname,
47 def toctree(children):
48 if len(children) == 0:
55 ' %s.txt' % c for c in sorted(children)
58 def make_module_txt(modname, children):
59 filename = os.path.join('hooke', '%s.txt' % modname)
60 if not os.path.exists('hooke'):
62 if os.path.exists(filename):
63 return None # don't overwrite potentially hand-written files.
64 f = file(filename, 'w')
65 f.write(title(modname))
66 f.write(automodule(modname))
67 f.write(toctree(children))
73 """A traversable tree structure.
86 >>> i = Tree(); i.n = "i"
87 >>> h = Tree([i]); h.n = "h"
88 >>> f = Tree([h]); f.n = "f"
89 >>> e = Tree(); e.n = "e"
90 >>> c = Tree([f,e]); c.n = "c"
91 >>> g = Tree(); g.n = "g"
92 >>> d = Tree([g]); d.n = "d"
93 >>> b = Tree([d]); b.n = "b"
94 >>> a = Tree(); a.n = "a"
98 Get the longest branch length with
103 Sort the tree recursively. Here we sort longest branch length
106 >>> a.sort(key=lambda node : -node.branch_len())
107 >>> "".join([node.n for node in a.traverse()])
110 And here we sort shortest branch length first.
112 >>> a.sort(key=lambda node : node.branch_len())
113 >>> "".join([node.n for node in a.traverse()])
116 We can also do breadth-first traverses.
118 >>> "".join([node.n for node in a.traverse(depth_first=False)])
121 Serialize the tree with depth marking branches.
123 >>> for depth,node in a.thread():
124 ... print "%*s" % (2*depth+1, node.n)
135 Flattening the thread disables depth increases except at
138 >>> for depth,node in a.thread(flatten=True):
139 ... print "%*s" % (2*depth+1, node.n)
150 We can also check if a node is contained in a tree.
152 >>> a.has_descendant(g)
154 >>> c.has_descendant(g)
156 >>> a.has_descendant(a)
158 >>> a.has_descendant(a, match_self=True)
161 def __cmp__(self, other):
162 return cmp(id(self), id(other))
164 def __eq__(self, other):
165 return self.__cmp__(other) == 0
167 def __ne__(self, other):
168 return self.__cmp__(other) != 0
170 def branch_len(self):
171 """Return the largest number of nodes from root to leaf (inclusive).
179 this method returns 5.
183 Exhaustive search every time == *slow*.
185 Use only on small trees, or reimplement by overriding
186 child-addition methods to allow accurate caching.
191 return 1 + max([child.branch_len() for child in self])
193 def sort(self, *args, **kwargs):
194 """Sort the tree recursively.
196 This method extends :meth:`list.sort` to Trees.
200 This method can be slow, e.g. on a :meth:`branch_len` sort,
201 since a node at depth `N` from the root has it's
202 :meth:`branch_len` method called `N` times.
204 list.sort(self, *args, **kwargs)
206 child.sort(*args, **kwargs)
208 def traverse(self, depth_first=True):
209 """Generate all the nodes in a tree, starting with the root node.
214 Depth first by default, but you can set `depth_first` to
215 `False` for breadth first ordering. Siblings are returned
216 in the order they are stored, so you might want to
217 :meth:`sort` your tree first.
219 if depth_first == True:
222 for descendant in child.traverse():
224 else: # breadth first, Wikipedia algorithm
225 # http://en.wikipedia.org/wiki/Breadth-first_search
227 while len(queue) > 0:
232 def thread(self, flatten=False):
233 """Generate a (depth, node) tuple for every node in the tree.
235 When `flatten` is `False`, the depth of any node is one
236 greater than the depth of its parent. That way the
237 inheritance is explicit, but you can end up with highly
240 When `flatten` is `True`, the depth of any node is only
241 greater than the depth of its parent when there is a branch,
242 and the node is not the last child. This can lead to ancestry
243 ambiguity, but keeps the total indentation down. For example::
249 would both produce (after sorting by :meth:`branch_len`)::
259 stack = [] # ancestry of the current node
263 for node in self.traverse(depth_first=True):
264 while len(stack) > 0 \
265 and id(node) not in [id(c) for c in stack[-1]]:
274 depth = depthDict[id(parent)]
275 if len(parent) > 1 and node != parent[-1]:
277 depthDict[id(node)] = depth
281 def has_descendant(self, descendant, depth_first=True, match_self=False):
282 """Check if a node is contained in a tree.
287 The potential descendant.
289 The search order. Set this if you feel depth/breadth would
294 x.has_descendant(x, match_self=True) -> True
296 if descendant == self:
298 for d in self.traverse(depth_first):
304 def python_tree(root_path='hooke', root_modname='hooke'):
306 tree.path = root_path
309 while len(stack) > 0:
311 if f.path.endswith('.py'):
312 f.name = os.path.basename(f.path)[:-len('.py')]
313 elif os.path.isdir(f.path) \
314 and os.path.exists(os.path.join(f.path, '__init__.py')):
315 f.name = os.path.basename(f.path)
317 for child in os.listdir(f.path):
318 if child == '__init__.py':
321 c.path = os.path.join(f.path, child)
327 f.modname = root_modname
329 f.modname = f.parent.modname + '.' + f.name
333 if __name__ == '__main__':
334 pt = python_tree(root_path='../hooke', root_modname='hooke')
335 for node in pt.traverse():
337 make_module_txt(node.modname, [c.modname for c in node])