doc/generate-hooke-txt.py

   1 #!/usr/bin/python
   2 #
   3 # COPYRIGHT
   4
   5 """Auto-generate reStructuredText of the hooke module tree for Sphinx.
   6
   7 This script is adapted from one written for `Bugs Everywhere`_.
   8
   9 .. _Bugs Everywhere: http://bugseverywhere.org/
  10 """
  11
  12 import sys
  13 import os, os.path
  14
  15
  16 sys.path.insert(0, os.path.abspath('..'))
  17
  18
  19 def title(modname):
  20     t = ':mod:`%s`' % modname
  21     delim = '*'*len(t)
  22     return '\n'.join([delim, t, delim, '', ''])
  23
  24 def automodule(modname):
  25     return '\n'.join([
  26             '.. automodule:: %s' % modname,
  27             '   :members:',
  28             '   :undoc-members:',
  29             '', ''])
  30
  31 def toctree(children):
  32     if len(children) == 0:
  33         return ''
  34     return '\n'.join([
  35             '.. toctree::',
  36             '   :maxdepth: 2',
  37             '',
  38             ] + [
  39             '   %s.txt' % c for c in sorted(children)
  40             ] + ['', ''])
  41
  42 def make_module_txt(modname, children):
  43     filename = os.path.join('hooke', '%s.txt' % modname)
  44     if not os.path.exists('hooke'):
  45         os.mkdir('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))
  52     f.close()
  53
  54
  55
  56 class Tree(list):
  57     """A traversable tree structure.
  58
  59     Examples
  60     --------
  61
  62     Construct::
  63
  64                +-b---d-g
  65              a-+   +-e
  66                +-c-+-f-h-i
  67
  68     with
  69
  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"
  79     >>> a.append(c)
  80     >>> a.append(b)
  81
  82     Get the longest branch length with
  83
  84     >>> a.branch_len()
  85     5
  86
  87     Sort the tree recursively.  Here we sort longest branch length
  88     first.
  89
  90     >>> a.sort(key=lambda node : -node.branch_len())
  91     >>> "".join([node.n for node in a.traverse()])
  92     'acfhiebdg'
  93
  94     And here we sort shortest branch length first.
  95
  96     >>> a.sort(key=lambda node : node.branch_len())
  97     >>> "".join([node.n for node in a.traverse()])
  98     'abdgcefhi'
  99
 100     We can also do breadth-first traverses.
 101
 102     >>> "".join([node.n for node in a.traverse(depth_first=False)])
 103     'abcdefghi'
 104
 105     Serialize the tree with depth marking branches.
 106
 107     >>> for depth,node in a.thread():
 108     ...     print "%*s" % (2*depth+1, node.n)
 109     a
 110       b
 111         d
 112           g
 113       c
 114         e
 115         f
 116           h
 117             i
 118
 119     Flattening the thread disables depth increases except at
 120     branch splits.
 121
 122     >>> for depth,node in a.thread(flatten=True):
 123     ...     print "%*s" % (2*depth+1, node.n)
 124     a
 125       b
 126       d
 127       g
 128     c
 129       e
 130     f
 131     h
 132     i
 133
 134     We can also check if a node is contained in a tree.
 135
 136     >>> a.has_descendant(g)
 137     True
 138     >>> c.has_descendant(g)
 139     False
 140     >>> a.has_descendant(a)
 141     False
 142     >>> a.has_descendant(a, match_self=True)
 143     True
 144     """
 145     def __cmp__(self, other):
 146         return cmp(id(self), id(other))
 147
 148     def __eq__(self, other):
 149         return self.__cmp__(other) == 0
 150
 151     def __ne__(self, other):
 152         return self.__cmp__(other) != 0
 153
 154     def branch_len(self):
 155         """Return the largest number of nodes from root to leaf (inclusive).
 156
 157         For the tree::
 158
 159                +-b---d-g
 160              a-+   +-e
 161                +-c-+-f-h-i
 162
 163         this method returns 5.
 164
 165         Notes
 166         -----
 167         Exhaustive search every time == *slow*.
 168
 169         Use only on small trees, or reimplement by overriding
 170         child-addition methods to allow accurate caching.
 171         """
 172         if len(self) == 0:
 173             return 1
 174         else:
 175             return 1 + max([child.branch_len() for child in self])
 176
 177     def sort(self, *args, **kwargs):
 178         """Sort the tree recursively.
 179
 180         This method extends :meth:`list.sort` to Trees.
 181
 182         Notes
 183         -----
 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.
 187         """
 188         list.sort(self, *args, **kwargs)
 189         for child in self:
 190             child.sort(*args, **kwargs)
 191
 192     def traverse(self, depth_first=True):
 193         """Generate all the nodes in a tree, starting with the root node.
 194
 195         Parameters
 196         ----------
 197         depth_first : bool
 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.
 202         """
 203         if depth_first == True:
 204             yield self
 205             for child in self:
 206                 for descendant in child.traverse():
 207                     yield descendant
 208         else: # breadth first, Wikipedia algorithm
 209             # http://en.wikipedia.org/wiki/Breadth-first_search
 210             queue = [self]
 211             while len(queue) > 0:
 212                 node = queue.pop(0)
 213                 yield node
 214                 queue.extend(node)
 215
 216     def thread(self, flatten=False):
 217         """Generate a (depth, node) tuple for every node in the tree.
 218
 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
 222         indented threads.
 223
 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::
 228
 229                       +-b                  +-b-c
 230                     a-+-c        and     a-+
 231                       +-d-e-f              +-d-e-f
 232
 233         would both produce (after sorting by :meth:`branch_len`)::
 234
 235             (0, a)
 236             (1, b)
 237             (1, c)
 238             (0, d)
 239             (0, e)
 240             (0, f)
 241
 242         """
 243         stack = [] # ancestry of the current node
 244         if flatten == True:
 245             depthDict = {}
 246
 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]]:
 250                 stack.pop(-1)
 251             if flatten == False:
 252                 depth = len(stack)
 253             else:
 254                 if len(stack) == 0:
 255                     depth = 0
 256                 else:
 257                     parent = stack[-1]
 258                     depth = depthDict[id(parent)]
 259                     if len(parent) > 1 and node != parent[-1]:
 260                         depth += 1
 261                 depthDict[id(node)] = depth
 262             yield (depth,node)
 263             stack.append(node)
 264
 265     def has_descendant(self, descendant, depth_first=True, match_self=False):
 266         """Check if a node is contained in a tree.
 267
 268         Parameters
 269         ----------
 270         descendant : Tree
 271           The potential descendant.
 272         depth_first : bool
 273           The search order.  Set this if you feel depth/breadth would
 274           be a faster search.
 275         match_self : bool
 276           Set to `True` for::
 277
 278               x.has_descendant(x, match_self=True) -> True
 279         """
 280         if descendant == self:
 281             return match_self
 282         for d in self.traverse(depth_first):
 283             if descendant == d:
 284                 return True
 285         return False
 286
 287
 288 def python_tree(root_path='hooke', root_modname='hooke'):
 289     tree = Tree()
 290     tree.path = root_path
 291     tree.parent = None
 292     stack = [tree]
 293     while len(stack) > 0:
 294         f = stack.pop(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)
 300             f.is_module = True
 301             for child in os.listdir(f.path):
 302                 if child == '__init__.py':
 303                     continue
 304                 c = Tree()
 305                 c.path = os.path.join(f.path, child)
 306                 c.parent = f
 307                 stack.append(c)
 308         else:
 309             continue
 310         if f.parent == None:
 311             f.modname = root_modname
 312         else:
 313             f.modname = f.parent.modname + '.' + f.name
 314             f.parent.append(f)
 315     return tree
 316
 317 if __name__ == '__main__':
 318     pt = python_tree(root_path='../hooke', root_modname='hooke')
 319     for node in pt.traverse():
 320         print node.modname
 321         make_module_txt(node.modname, [c.modname for c in node])