pysize/core/pysize_fs_tree.py

   1 # This program is free software; you can redistribute it and/or modify
   2 # it under the terms of the GNU General Public License as published by
   3 # the Free Software Foundation; either version 2 of the License, or
   4 # (at your option) any later version.
   5 #
   6 # This program is distributed in the hope that it will be useful,
   7 # but WITHOUT ANY WARRANTY; without even the implied warranty of
   8 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   9 # GNU Library General Public License for more details.
  10 #
  11 # You should have received a copy of the GNU General Public License
  12 # along with this program; if not, write to the Free Software
  13 # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  14 #
  15 # See the COPYING file for license information.
  16 #
  17 # Copyright (c) 2006 Guillaume Chazarain <guichaz@yahoo.fr>
  18
  19 from pysize.core import compute_size
  20 from pysize.core.pysize_fs_node import create_node
  21
  22 # http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/231503
  23 # By David Eppstein
  24 def _breadth_first(tree, children=iter):
  25     """Traverse the nodes of a tree in breadth-first order.
  26     The first argument should be the tree root; children
  27     should be a function taking as argument a tree node and
  28     returning an iterator of the node's children.
  29     """
  30     yield tree
  31     last = tree
  32     for node in _breadth_first(tree, children):
  33         for child in children(node):
  34             yield child
  35             last = child
  36         if last is node:
  37             return
  38
  39 class pysize_tree(object):
  40     """The entry point to a tree of pysize_node.
  41     min_size < 1.0 => ratio to total size."""
  42     def __init__(self, paths, max_depth=1, min_size=0.0):
  43         self.fullpaths = paths
  44         if paths and min_size <= 1.0:
  45             min_size *= sum(map(compute_size.slow, paths))
  46         self.root = create_node(None, paths, max_depth, min_size)
  47         self.height = self.root.compute_height()
  48
  49     def get_next_sibling(self, node):
  50         """Return the next pysize_node in node's level."""
  51         is_next = False
  52         for child in _breadth_first(self.root, lambda c: c.children):
  53             if is_next:
  54                 if child.compute_depth() == node.compute_depth():
  55                     return child
  56                 return
  57             is_next = child is node
  58
  59     def get_previous_sibling(self, node):
  60         """Return the previous pysize_node in node's level."""
  61         prev = None
  62         for child in _breadth_first(self.root, lambda c: c.children):
  63             if child == node:
  64                 if prev.compute_depth() == node.compute_depth():
  65                     return prev
  66                 return
  67             prev = child
  68
  69     def get_first_child(self, node):
  70         """Return the first pysize_node in node's children."""
  71         if node.children:
  72             return node.children[0]
  73
  74     def get_parent(self, node):
  75         """Return the saved parent of node."""
  76         return node.parent