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, 2007, 2008  Guillaume Chazarain <guichaz@yahoo.fr>
  18
  19 from pysize.core import compute_size
  20 from pysize.core.pysize_fs_node import create_node
  21 from pysize.core.exception_propagation import unexpect
  22
  23 # http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/231503
  24 # By David Eppstein
  25 def _breadth_first(tree, children=iter):
  26     """Traverse the nodes of a tree in breadth-first order.
  27     The first argument should be the tree root; children
  28     should be a function taking as argument a tree node and
  29     returning an iterator of the node's children.
  30     """
  31     yield tree
  32     last = tree
  33     for node in _breadth_first(tree, children):
  34         for child in children(node):
  35             yield child
  36             last = child
  37         if last is node:
  38             return
  39
  40 class pysize_tree(object):
  41     """The entry point to a tree of pysize_node.
  42     min_size < 1.0 => ratio to total size."""
  43     @unexpect(OSError)
  44     def __init__(self, paths, max_depth, min_size, options):
  45         self.fullpaths = paths
  46         auto_min_size = min_size <= 1.0
  47         estimated_size = compute_size.slow_sum(paths, options.cross_device)
  48         if auto_min_size:
  49             min_size_ratio = min_size
  50             min_size = estimated_size * min_size_ratio
  51         self.root = create_node(None, paths, paths, max_depth, min_size,
  52                                 options)
  53         if auto_min_size and estimated_size != self.root.size:
  54             estimated_size = self.root.size
  55             min_size = estimated_size * min_size_ratio
  56             self.root = create_node(None, paths, paths, max_depth, min_size,
  57                                     options)
  58         self.height = self.root.compute_height()
  59
  60     def get_next_sibling(self, node):
  61         """Return the next pysize_node in node's level."""
  62         is_next = False
  63         for child in self.breadth_first():
  64             if is_next:
  65                 if child.compute_depth() == node.compute_depth():
  66                     return child
  67                 return
  68             is_next = child is node
  69
  70     def get_previous_sibling(self, node):
  71         """Return the previous pysize_node in node's level."""
  72         prev = None
  73         for child in self.breadth_first():
  74             if child == node:
  75                 if prev.compute_depth() == node.compute_depth():
  76                     return prev
  77                 return
  78             prev = child
  79
  80     def get_first_child(self, node):
  81         """Return the first pysize_node in node's children."""
  82         if node.children:
  83             return node.children[0]
  84
  85     def get_parent(self, node):
  86         """Return the saved parent of node."""
  87         return node.parent
  88
  89     def breadth_first(self):
  90         """Iterate over the nodes in breadth first order."""
  91         return _breadth_first(self.root, lambda c: c.children)