doc/generate-hooke-txt.py

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