# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU Library General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
#
# See the COPYING file for license information.
#
# Copyright (c) 2006, 2007 Guillaume Chazarain
from pysize.core import compute_size
from pysize.core.pysize_fs_node import create_node
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/231503
# By David Eppstein
def _breadth_first(tree, children=iter):
"""Traverse the nodes of a tree in breadth-first order.
The first argument should be the tree root; children
should be a function taking as argument a tree node and
returning an iterator of the node's children.
"""
yield tree
last = tree
for node in _breadth_first(tree, children):
for child in children(node):
yield child
last = child
if last is node:
return
class pysize_tree(object):
"""The entry point to a tree of pysize_node.
min_size < 1.0 => ratio to total size."""
def __init__(self, paths, max_depth, min_size, options):
self.fullpaths = paths
auto_min_size = min_size <= 1.0
estimated_size = compute_size.slow_sum(paths, options.cross_device)
if auto_min_size:
min_size_ratio = min_size
min_size = estimated_size * min_size_ratio
self.root = create_node(None, paths, max_depth, min_size, options)
if auto_min_size and estimated_size != self.root.size:
estimated_size = self.root.size
min_size = estimated_size * min_size_ratio
self.root = create_node(None, paths, max_depth, min_size, options)
self.height = self.root.compute_height()
def get_next_sibling(self, node):
"""Return the next pysize_node in node's level."""
is_next = False
for child in self.breadth_first():
if is_next:
if child.compute_depth() == node.compute_depth():
return child
return
is_next = child is node
def get_previous_sibling(self, node):
"""Return the previous pysize_node in node's level."""
prev = None
for child in self.breadth_first():
if child == node:
if prev.compute_depth() == node.compute_depth():
return prev
return
prev = child
def get_first_child(self, node):
"""Return the first pysize_node in node's children."""
if node.children:
return node.children[0]
def get_parent(self, node):
"""Return the saved parent of node."""
return node.parent
def breadth_first(self):
"""Iterate over the nodes in breadth first order."""
return _breadth_first(self.root, lambda c: c.children)