[gnue] r8445 - trunk/gnue-common/src/utils

[reinhard]

Author: reinhard
Date: 2006-04-20 16:27:31 -0500 (Thu, 20 Apr 2006)
New Revision: 8445

Added:
   trunk/gnue-common/src/utils/tree.py
Log:
Added a very basic tree structure handling library.


Added: trunk/gnue-common/src/utils/tree.py
===================================================================
--- trunk/gnue-common/src/utils/tree.py 2006-04-20 13:39:50 UTC (rev 8444)
+++ trunk/gnue-common/src/utils/tree.py 2006-04-20 21:27:31 UTC (rev 8445)
@@ -0,0 +1,242 @@
+# GNU Enterprise Common Library - Tree structure classes
+#
+# Copyright 2001-2006 Free Software Foundation
+#
+# This file is part of GNU Enterprise
+#
+# GNU Enterprise 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, or (at your option) any later version.
+#
+# GNU Enterprise 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 General Public License for more details.
+#
+# You should have received a copy of the GNU General Public
+# License along with program; see the file COPYING. If not,
+# write to the Free Software Foundation, Inc., 59 Temple Place
+# - Suite 330, Boston, MA 02111-1307, USA.
+#
+# $Id: http.py 8129 2006-01-18 21:25:44Z jcater $
+
+"""
+Classes representing a node in a tree structure.
+"""
+
+from gnue.common.apps import errors
+
+__all__ = ['CircularReferenceError', 'Node']
+
+
+# =============================================================================
+# Exceptions
+# =============================================================================
+
+class CircularReferenceError(errors.SystemError):
+    """
+    Setting parent would create a circular reference.
+
+    Setting the requested parent for this node would create a circular
+    reference in the tree, like A is the parent of B, B is the parent of C, and
+    C is the parent of A.
+    """
+    def __init__(self):
+        message = u_("Setting parent would create a circular reference")
+        errors.SystemError.__init__(self, message)
+
+
+# =============================================================================
+# Node class
+# =============================================================================
+
+class Node(object):
+    """
+    A node in a n-ary tree.
+
+    Instances of this class represent nodes that make up a tree structure. Each
+    node can have one parent (a node with a parent of None is a root node) and
+    an arbitary number of children.
+
+    The parent of a node is defined on creation of the node, but can be changed
+    later. Nodes keep track of their children automatically, so changing the
+    parent of a node from A to B will automatically remove the node from A's
+    list of children and add it to B's list of children.
+
+    Children of a node are sorted in the order in which they were attached to
+    the parent.
+    """
+
+    # -------------------------------------------------------------------------
+    # Constructor
+    # -------------------------------------------------------------------------
+
+    def __init__(self, parent):
+        """
+        Initialize a new node.
+
+        @param parent: Parent node.
+        @type parent: Node
+        """
+        self.__parent = None
+        self.__children = []
+
+        self.parent = parent
+
+
+    # -------------------------------------------------------------------------
+    # Property "parent"
+    # -------------------------------------------------------------------------
+
+    def __get_parent(self):
+
+        return self.__parent
+
+    # -------------------------------------------------------------------------
+
+    def __set_parent(self, value):
+
+        checktype(value, [Node, None])
+
+        # Make sure that we don't create a circular reference
+        node = value
+        while node is not None:
+            if node is self:
+                raise CircularReferenceError
+            node = node.__parent
+
+        if self.__parent is not None:
+            self.__parent.__children.remove(self)
+        self.__parent = value
+        if self.__parent is not None:
+            self.__parent.__children.append(self)
+
+    # -------------------------------------------------------------------------
+
+    parent = property(__get_parent, __set_parent, None,
+            """
+            Parent node, or None if this is the root of the tree.
+
+            @type: Node
+            """)
+
+
+    # -------------------------------------------------------------------------
+    # Property "children"
+    # -------------------------------------------------------------------------
+
+    # This is a property because we want to make it readonly
+
+    def __get_children(self):
+
+        return self.__children
+
+    # -------------------------------------------------------------------------
+
+    children = property(__get_children, None, None,
+            """
+            List of child nodes. (readonly)
+
+            @type: [Node]
+            """)
+
+
+    # -------------------------------------------------------------------------
+    # Property "root"
+    # -------------------------------------------------------------------------
+
+    def __get_root(self):
+
+        result = self
+        while result.__parent is not None:
+            result = result.__parent
+        return result
+
+    # -------------------------------------------------------------------------
+
+    root = property(__get_root, None, None,
+            """
+            Root node of the tree this node is a member of. (readonly)
+
+            @type: Node
+            """)
+
+
+    # -------------------------------------------------------------------------
+    # Apply a function to every element in the tree
+    # -------------------------------------------------------------------------
+
+    def walk(self, function, *args, **kwargs):
+        """
+        Apply a function to all nodes of the (sub)tree rooted at this node.
+
+        The function is first applied to this node, then to the first child
+        node, then to all children of the first child node recursively, then to
+        the next child node, etc.
+
+        The function is called with the repective node as the first argument,
+        followed by the positional arguments and keyword arguments provided in
+        the call to "walk".
+
+        @param function: Function to call on every node.
+        @type function: callable
+        @param args: Positional arguments
+        @type args: tuple
+        @param kwargs: Keyword arguments
+        @type kwargs: dict
+        """
+
+        function(self, *args, **kwargs)
+        for child in self.__children:
+            child.walk(function, *args, **kwargs)
+
+
+# =============================================================================
+# Self test code
+# =============================================================================
+
+if __name__ == '__main__':
+
+    # Descendant of Node used in test code
+    class TestNode(Node):
+        def __init__(self, parent, text):
+            Node.__init__(self, parent)
+            self.__text = text
+        def __str__(self):
+            return self.__text
+
+    # Build up our tree
+    root = TestNode(None, 'People')
+    monty_python = TestNode(root, 'Monty Python')
+    john_cleese = TestNode(monty_python, 'John Cleese')
+    TestNode(monty_python, 'Michael Palin')
+    TestNode(monty_python, 'Graham Chapman')
+    TestNode(monty_python, 'Terry Jones')
+    TestNode(monty_python, 'Terry Gilliam')
+    star_trek = TestNode(root, 'Star Trek')
+    TestNode(star_trek, 'James T. Kirk')
+    TestNode(star_trek, 'Mr. Spock')
+    TestNode(star_trek, 'Leonard McCoy')
+
+    # Test "children" property
+    print "The Monty Python group:"
+    for child in monty_python.children:
+        print "   ", child
+
+    # Test "parent" and "root" property
+    print john_cleese, "is a member of", john_cleese.parent
+    print "    and all are", john_cleese.root
+
+    # Test "walk" function
+    def printout(self, prefix):
+        print prefix, self
+    print "All nodes:"
+    root.walk(printout, "   ")
+
+    # Test "CircularReferenceError" exception
+    try:
+        monty_python.parent = john_cleese
+    except CircularReferenceError, error:
+        print "Correctly got an exception:", error
+    print monty_python, "has now a parent of", monty_python.parent