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

[reinhard]

Author: reinhard
Date: 2006-05-18 04:36:28 -0500 (Thu, 18 May 2006)
New Revision: 8467

Modified:
   trunk/gnue-common/src/utils/tree.py
Log:
Added NamedNode class.


Modified: trunk/gnue-common/src/utils/tree.py
===================================================================
--- trunk/gnue-common/src/utils/tree.py 2006-05-15 13:55:36 UTC (rev 8466)
+++ trunk/gnue-common/src/utils/tree.py 2006-05-18 09:36:28 UTC (rev 8467)
@@ -25,9 +25,13 @@
 Classes representing a node in a tree structure.
 """
 
+import locale
+
 from gnue.common.apps import errors
 
-__all__ = ['CircularReferenceError', 'Node']
+__all__ = ['CircularReferenceError', 'DuplicateChildNameError',
+        'DuplicateDescendantNameError', 'NodeDictNotAvailableError',
+        'Node', 'NamedNode']
 
 
 # =============================================================================
@@ -48,6 +52,69 @@
 
 
 # =============================================================================
+
+class DuplicateChildNameError(errors.SystemError):
+    """
+    Duplicate child name.
+
+    Changing the node name or the parent of this node as requested would result
+    in the (new) parent having two children with the same node name.
+
+    Note that after this exception has happened, the tree is in an inconsistent
+    state.
+    """
+    def __init__(self, child_name, parent_node):
+        message = u_(
+                "Duplicate child name '%(child_name)s' for parent node "
+                "'%(parent_node)s'")
+        errors.SystemError.__init(self, message % {
+                'child_name': child_name,
+                'parent_node': repr(parent_node)})
+
+
+# =============================================================================
+
+class DuplicateDescendantNameError(errors.SystemError):
+    """
+    Duplicate descendant name for node type.
+
+    Changing the node name or the parent of this node as requested would result
+    in a (new) ancestor of this node having two descendants of the same type
+    with the same name. This is only a problem if this ancestor maintains a
+    dictionary of the descendants of this type.
+
+    Note that after this exception has happened, the tree is in an inconsistent
+    state.
+    """
+    def __init__(self, descendant_name, descendant_type, ancestor_node):
+        message = u_(
+                "Duplicate node name '%(descendant_name)s' in descendants of "
+                "node type %(descendant_type)s of node '%(ancestor_node)s'")
+        errors.SystemError.__init(self, message % {
+                'descendant_name': descendant_name,
+                'descendant_type': descendant_type,
+                'ancestor_node': ancestor_node})
+
+
+# =============================================================================
+
+class NodeDictNotAvailableError(errors.SystemError):
+    """
+    Node Dictionary not available for this type.
+
+    This node class does not maintain a node dictionary for the requested type.
+    """
+    def __init__(self, node_name, node_class, node_type):
+        message = u_(
+                "Node '%(node_name)s' of class '%(node_class)s does not "
+                "maintain a node dictionary for node type %(node_type)s")
+        errors.SystemError.__init(self, message % {
+                'node_name': node_name,
+                'node_class': node_class,
+                'node_type': node_type})
+
+
+# =============================================================================
 # Node class
 # =============================================================================
 
@@ -56,8 +123,8 @@
     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.
+    node can have one parent (a node with a parent of C{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
@@ -79,7 +146,11 @@
         @param parent: Parent node.
         @type parent: Node
         """
+
+        #: Parent node or C{None} if this is the root node
         self.__parent = None
+
+        #: List of child nodes
         self.__children = []
 
         self.parent = parent
@@ -99,26 +170,15 @@
 
         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
+        self._set_parent_(value)
 
-        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.
+            Parent node, or C{None} if this is the root of the tree.
 
-            @type: Node
+            @type: Node or None
             """)
 
 
@@ -177,7 +237,7 @@
 
         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".
+        the call to C{walk}.
 
         @param function: Function to call on every node.
         @type function: callable
@@ -192,22 +252,417 @@
             child.walk(function, *args, **kwargs)
 
 
+    # -------------------------------------------------------------------------
+    # Abstract functions
+    # -------------------------------------------------------------------------
+
+    def _set_parent_(self, parent):
+        """
+        Hook for subclasses to register a parent change.
+
+        Subclasses can implement this method to execute stuff that has to be
+        done whenever a node gets a new parent.
+        """
+
+        # Make sure that we don't create a circular reference
+        node = parent
+        while node is not None:
+            if node is self:
+                raise CircularReferenceError
+            node = node.__parent
+
+        # Unregister with old parent
+        if self.__parent is not None:
+            self.__parent.__children.remove(self)
+
+        # Set new parent
+        self.__parent = parent
+
+        # Register with new parent
+        if self.__parent is not None:
+            self.__parent.__children.append(self)
+
+
 # =============================================================================
+# NamedNode class
+# =============================================================================
+
+class NamedNode(Node):
+    """
+    A Node in an n-ary tree with a node type and a name.
+
+    C{NamedNode}s introduce a L{I{node type} <node_type>} and a L{I{node name}
+    <node_name>}. While for a given subclass of C{NamedNode}, all instances
+    share the same node type, each instance has a different node name.
+
+    Instances of this class support searching descendants L{for a given node
+    name <find_descendant>} or L{for a given node type
+    <find_descendant_of_type>}.
+
+    Every C{NamedNode} instance can define a list of node types it is
+    interested in. Descendants of each of these types will be hashed in a
+    dictionary (a separate dictionary per type).
+
+    @cvar _node_type_: Type of this node. Defined by subclasses.
+    @type _node_type_: str
+
+    @cvar _node_dicts_: List of types for which descendants should be hashed.
+        Defined by subclasses.
+    @type _node_dicts_: [str]
+    """
+
+    # -------------------------------------------------------------------------
+    # Class variables
+    # -------------------------------------------------------------------------
+
+    _node_type_ = None
+    _node_dicts_ = []
+
+
+    # -------------------------------------------------------------------------
+    # Constructor
+    # -------------------------------------------------------------------------
+
+    def __init__(self, parent):
+        """
+        Initialize a new named node.
+
+        @param parent: Parent node.
+        @type parent: Node
+        """
+
+        #: Node name
+        # Must be set before __init__, because setting the parent already needs
+        # this variable.
+        self.__node_name = None
+
+        Node.__init__(self, parent)
+
+        #: Dictionary with all named children
+        self.__named_children = {}
+
+        #: Dictionaries with descendants of interesting node types
+        self.__node_dicts = dict.fromkeys(self._node_dicts_, {})
+
+
+    # -------------------------------------------------------------------------
+    # Nice string representation
+    # -------------------------------------------------------------------------
+
+    def __repr__(self):
+        """
+        Return a string representation of the node.
+
+        The string representation is either the node name, or, if there is no
+        node name defined, a string saying C{"<unnamed I{node_type}>"}.
+
+        If the node name is a unicode string, it is converted to the encoding
+        as defined in the current locale.
+        """
+
+        if self.__node_name is None:
+            if self._node_type_ is None:
+                return "<unnamed untyped node>"
+            else:
+                return "<unnamed " + self._node_type_ + ">"
+
+        elif isinstance(self.__node_name, unicode):
+            return self.__node_name.encode(locale.getlocale()[0], 'replace')
+
+        else:
+            return self.__node_name
+
+
+    # -------------------------------------------------------------------------
+    # Property "node_type"
+    # -------------------------------------------------------------------------
+
+    def __get_node_type(self):
+
+        return self._node_type_
+
+    # -------------------------------------------------------------------------
+
+    node_type = property(__get_node_type, None, None,
+            """
+            Node type.
+
+            The node type is defined in the class definition of descendant
+            classes of L{NamedNode}. All nodes of the same class have the same
+            type. You can think of the node type as a "nice name for the class
+            of the node".
+
+            @type: basestring
+            """)
+
+    # -------------------------------------------------------------------------
+    # Property "node_name"
+    # -------------------------------------------------------------------------
+
+    def __get_node_name(self):
+
+        return self.__node_name
+
+    # -------------------------------------------------------------------------
+
+    def __set_node_name(self, value):
+
+        checktype(value, [basestring, None])
+
+        if self.__node_name is not None:
+            self.__unregister()
+
+        self.__node_name = value
+
+        if self.__node_name is not None:
+            self.__register()
+
+
+    # -------------------------------------------------------------------------
+
+    node_name = property(__get_node_name, __set_node_name, None,
+            """
+            Name of the node.
+
+            Usually, every node in a tree has a different name. Nodes may also
+            be unnamed (meaning a name of None).
+
+            @type: basestring
+            """)
+
+
+    # -------------------------------------------------------------------------
+    # Register with parents and ancestors if parent is changed
+    # -------------------------------------------------------------------------
+
+    def _set_parent_(self, parent):
+
+        if self.__node_name is not None:
+            self.__unregister()
+
+        Node._set_parent_(self, parent)
+
+        if self.__node_name is not None:
+            self.__register()
+
+
+    # -------------------------------------------------------------------------
+    # Helper methods to register/unregister with parent and ancestors
+    # -------------------------------------------------------------------------
+
+    def __register(self):
+
+        # register with parent
+        if isinstance(self.parent, NamedNode):
+            child_dict = self.parent.__named_children
+            if child_dict.has_key(self.__node_name):
+                raise DuplicateChildNameError, (self.__node_name, self.parent)
+            child_dict[self.__node_name] = self
+
+        # register with all ancestors that have a node_dict for this node type
+        ancestor = self.parent
+        while ancestor is not None:
+            if isinstance(ancestor, NamedNode):
+                if ancestor.__node_dicts.has_key(self._node_type_):
+                    node_dict = ancestor.__node_dicts[self._node_type_]
+                    if node_dict.has_key(self.__node_name):
+                        raise DuplicateDescendantNameError, (self.__node_name,
+                                self._node_type_, ancestor)
+                    node_dict[self.__node_name] = self
+            ancestor = ancestor.parent
+
+    # -------------------------------------------------------------------------
+
+    def __unregister(self):
+
+        # unregister with parent
+        if isinstance(self.parent, NamedNode):
+            del self.parent.__named_children[self.__node_name]
+
+        # unregister with all ancestors that have a node_dict for this node 
type
+        ancestor = self.parent
+        while ancestor is not None:
+            if isinstance(ancestor, NamedNode):
+                node_dicts = ancestor.__node_dicts
+                if node_dicts.has_key(self._node_type_):
+                    del ancestor.__node_dicts[self._node_type_]\
+                            [self.__node_name]
+            ancestor = ancestor.parent
+
+
+    # -------------------------------------------------------------------------
+    # Get child with the given node name
+    # -------------------------------------------------------------------------
+
+    def get_child(self, node_name):
+        """
+        Return the child node with the given node name
+
+        @param node_name: The node name of the desired child
+        @type node_name: basestring
+
+        @return: The child node with that node name, or C{None} if there is
+            no such child node.
+        @rtype: NamedNode or None
+        """
+
+        return self.__named_children.get(node_name)
+
+
+    # -------------------------------------------------------------------------
+    # Find first parent of a given node type
+    # -------------------------------------------------------------------------
+
+    def find_ancestor_of_type(self, node_type):
+        """
+        Return the nearest ancestor with the given node type.
+
+        This function searches through all ancestors (parent, parent of the
+        parent, etc.) of this node until it finds a node of the given node
+        type. If none of the ancestors is of the given type, None is returned.
+        
+        If a node isn't an instance of a subclass of L{NamedNode}, it is
+        ignored, however the search is continued by its parent.
+
+        @param node_type: Node type to search for.
+        @type node_type: str
+
+        @return: Ancestor node of the given node type.
+        @rtype: NamedNode or None
+        """
+
+        checktype(node_type, str)
+
+        parent = self.parent
+        while parent is not None:
+            if isinstance(parent, NamedNode):
+                if parent._node_type_ == node_type:
+                    return parent
+            parent = parent.parent
+        return None
+
+
+    # -------------------------------------------------------------------------
+    # Find first descendant with a given node name
+    # -------------------------------------------------------------------------
+
+    def find_descendant(self, node_name):
+        """
+        Return the first descendant with the given node name.
+
+        This function searches through all descendants (children, children of
+        children, etc.) of this node until it finds a node with the given node
+        name. If none of the descendants has the given type, None is returned.
+        
+        If a node isn't an instance of a subclass of L{NamedNode}, it is
+        ignored, however the search is continued by its children.
+
+        The search is first applied to the first child node, then to all
+        children of the first child node recursively, then to the next child
+        node, etc.
+
+        @param node_name: Node name to search for.
+        @type node_name: basestring
+
+        @return: Descendant node of the given node type.
+        @rtype: NamedNode or None
+        """
+
+        checktype(node_name, basestring)
+
+        # We need a helper function so we can traverse nodes not derived from
+        # NamedNode.
+        return self.__find_descendant(self, node_name)
+
+
+    # -------------------------------------------------------------------------
+    # Helper function for searching recursively through descendants
+    # -------------------------------------------------------------------------
+
+    def __find_descendant(self, node, node_name):
+
+        for child in node.children:
+            if isinstance(child, NamedNode):
+                if child.__node_name == node_name:
+                    return child
+            found = self.__find_descendant(child, node_name)
+            if found is not None:
+                return found
+
+    # -------------------------------------------------------------------------
+    # Find first descendant of a given node type
+    # -------------------------------------------------------------------------
+
+    def find_descendant_of_type(self, node_type):
+        """
+        Return the first descendant with the given node type.
+
+        This function searches through all descendants (children, children of
+        children, etc.) of this node until it finds a node of the given node
+        type. If none of the descendants is of the given type, None is
+        returned.
+        
+        If a node isn't an instance of a subclass of L{NamedNode}, it is
+        ignored, however the search is continued by its children.
+
+        The search is first applied to the first child node, then to all
+        children of the first child node recursively, then to the next child
+        node, etc.
+
+        @param node_type: Node type to search for.
+        @type node_type: str
+
+        @return: Descendant node of the given node type.
+        @rtype: NamedNode or None
+        """
+
+        checktype(node_type, str)
+
+        # We need a helper function so we can traverse nodes not derived from
+        # NamedNode.
+        return self.__find_descendant_of_type(self, node_type)
+
+
+    # -------------------------------------------------------------------------
+    # Helper function for searching recursively through descendants
+    # -------------------------------------------------------------------------
+
+    def __find_descendant_of_type(self, node, node_type):
+
+        for child in node.children:
+            if isinstance(child, NamedNode):
+                if child._node_type_ == node_type:
+                    return child
+            found = self.__find_descendant_of_type(child, node_type)
+            if found is not None:
+                return found
+
+
+    # -------------------------------------------------------------------------
+    # Get node dictionary with all descendant nodes of a given type
+    # -------------------------------------------------------------------------
+
+    def get_node_dict(self, node_type):
+        """
+        Return a dictionary with all descendant nodes of the given node type.
+
+        The node names are the keys of the dictionary, and the node objects
+        are the values. Nodes without a node name aren't included in the
+        dictionary.
+
+        This function only works for node types that have been registered in
+        the L{_node_dicts_} list of the class of this node.
+        """
+
+        return self.__node_dicts[node_type]
+
+
+# =============================================================================
 # Notes
 # =============================================================================
 
 # Some quick notes on descendant classes so I don't forget it:
 # 
-# TypedNode has a class attribute _type_ that is defined for every
-# descendant, will contain strings like "form", "entry", "block", etc.
-# Implements get_parent_of_type(), get_children_of_type().
-# 
-# NamedNode has a virtual method _get_name_() that descendants implement to
-# return a nice name of the node, like "blkPerson" or "fldName" or
-# "<unnamed button>". Implements a method for the root node to find a node with
-# a given type and a given name, to replace trigger/datasource/etc dictionaries
-# in GFForm.
-# 
 # AttributeNode adds handling of [XML] attributes. Descendants of this class
 # defined in a self-contained way details about the valid attributes (what is
 # now defined in those getXMLelements() functions). Initializes default
@@ -224,6 +679,10 @@
 
 if __name__ == '__main__':
 
+    # -------------------------------------------------------------------------
+    # Node class
+    # -------------------------------------------------------------------------
+
     # Descendant of Node used in test code
     class TestNode(Node):
         def __init__(self, parent, text):
@@ -266,3 +725,81 @@
     except CircularReferenceError, error:
         print "Correctly got an exception:", error
     print monty_python, "has now a parent of", monty_python.parent
+
+
+    # -------------------------------------------------------------------------
+    # NamedNode class
+    # -------------------------------------------------------------------------
+
+    # Descendants of NamedNode used in test code
+    class TextNode(NamedNode):
+        def __init__(self, parent, text):
+            NamedNode.__init__(self, parent)
+            self.node_name = text
+    class GroupNode(TextNode):
+        _node_type_ = 'group'
+        _node_dicts_ = ['man']
+    class ManNode(TextNode):
+        _node_type_ = 'man'
+    class WomanNode(TextNode):
+        _node_type_ = 'woman'
+
+    # Build up our tree
+    root = GroupNode(None, 'People')
+    monty_python = GroupNode(root, 'Monty Python')
+    john_cleese = ManNode(monty_python, 'John Cleese')
+    ManNode(monty_python, 'Michael Palin')
+    ManNode(monty_python, 'Graham Chapman')
+    ManNode(monty_python, 'Terry Jones')
+    ManNode(monty_python, 'Terry Gilliam')
+    WomanNode(monty_python, None)       # The woman whose name I can't remember
+    star_trek = GroupNode(root, 'Star Trek')
+    james_kirk = ManNode(star_trek, 'James T. Kirk')
+    ManNode(star_trek, 'Mr. Spock')
+    ManNode(star_trek, 'Leonard McCoy')
+    WomanNode(star_trek, 'Nyota Uhura')
+    ManNode(star_trek, None)    # The nameless security officer
+    woman = Node(james_kirk)    # Kirk's spouse - unnamed node by intention
+    peter_kirk = ManNode(woman, 'Peter Kirk')   # Kirk's son
+
+    # Test "node_type" property
+    print james_kirk, "is node type", james_kirk.node_type
+
+    # Test "node_name" property
+    print james_kirk, "is node name", james_kirk.node_name
+    james_kirk.node_name = 'James Tiberius Kirk'
+    print "Now his node name has changed to", james_kirk.node_name
+
+    # Test "get_child" method
+    print "Terry Jones can be found:", monty_python.get_child('Terry Jones')
+
+    # Test "find_ancestor_of_type" method
+    print peter_kirk, "belongs to", peter_kirk.find_ancestor_of_type('group')
+
+    # Test "find_descendant" method
+    print "Peter Kirk can be found:", star_trek.find_descendant('Peter Kirk')
+
+    # Test "find_descendant_of_type" method
+    print "Nyota Uhura can be found:", \
+            star_trek.find_descendant_of_type('woman')
+
+    # Test "get_node_dict" method
+    print "All men of the Monty Python group:"
+    for (key, value) in monty_python.get_node_dict('man').items():
+        print "   ", key, "=", value
+    print "All men of the Star Trek group:"
+    for (key, value) in star_trek.get_node_dict('man').items():
+        print "   ", key, "=", value
+    print "All men of all groups:"
+    for (key, value) in root.get_node_dict('man').items():
+        print "   ", key, "=", value
+
+    # Test changing node name: get_child, get_node_dict for old and new
+
+    # Test changing parent: get_child, get_node_dict for old and new
+
+    # Test DuplicateChildNameError
+
+    # Test DuplicateDescendantNameError
+
+    # Test NodeDictNotAvailableError