Author: reinhard
Date: 2009-10-08 05:31:18 -0500 (Thu, 08 Oct 2009)
New Revision: 9946
Added:
trunk/gnue-common/src/base/tree.py
Removed:
trunk/gnue-common/src/utils/tree.py
Log:
Completed implementation of Node and NamedNode.
Copied: trunk/gnue-common/src/base/tree.py (from rev 9928, trunk/gnue-common/src/utils/tree.py)
===================================================================
--- trunk/gnue-common/src/base/tree.py (rev 0)
+++ trunk/gnue-common/src/base/tree.py 2009-10-08 10:31:18 UTC (rev 9946)
@@ -0,0 +1,1101 @@
+# GNU Enterprise Common Library - Tree structure classes
+#
+# Copyright 2001-2009 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$
+
+"""
+Classes representing a node in a tree structure.
+
+TODO: This module is work in progress.
+"""
+
+from gnue.common.base import errors, i18n
+from gnue.common.base.i18n import utranslate as u_ # for epydoc
+
+__all__ = ['Node', 'NamedNode', 'AttribNode',
+ 'ChildNotAllowedError', 'DuplicateSingletonError',
+ 'CircularReferenceError', 'DuplicateChildNameError',
+ 'DuplicateDescendantNameError', 'NodeDictNotAvailableError']
+
+
+# =============================================================================
+# 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 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
+ 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.
+
+ Instances of this class support searching L{ancestors
+ <__find_ancestor_of_class__>} and L{descendants
+ <__find_descendant_of_class__>} of a given class.
+
+ @cvar _allowed_children_: Dictionary with valid child node classes, where
+ the key is the class and the value is a dictionary in the form
+ {'singleton': True/False (defaults to False)}.
+ """
+
+ _allowed_children_ = {}
+
+
+ # -------------------------------------------------------------------------
+ # Constructor
+ # -------------------------------------------------------------------------
+
+ def __init__(self, parent=None, children=None):
+ """
+ Initialize a new node.
+
+ @param parent: Parent node.
+ @type parent: Node
+ @param children: Children to add to this node after initalization.
+ @type children: list
+ """
+
+ #: Parent node or C{None} if this is the root node
+ self.__parent = None
+
+ #: List of child nodes
+ self.__children = []
+
+ self.__parent__ = parent
+
+ if children is not None:
+ for child in children:
+ child.__parent__ = self
+
+
+ # -------------------------------------------------------------------------
+ # Property "parent"
+ # -------------------------------------------------------------------------
+
+ def __get_parent(self):
+
+ return self.__parent
+
+ # -------------------------------------------------------------------------
+
+ def __set_parent(self, value):
+
+ checktype(value, [Node, None])
+
+ self._set_parent_(value)
+
+ # -------------------------------------------------------------------------
+
+ __parent__ = property(__get_parent, __set_parent, None,
+ """
+ Parent node, or C{None} if this is the root of the tree.
+
+ @type: Node or None
+ """)
+
+
+ # -------------------------------------------------------------------------
+ # 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 C{__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)
+
+
+ # -------------------------------------------------------------------------
+ # Find first parent of a given class
+ # -------------------------------------------------------------------------
+
+ def __find_ancestor_of_class__(self, ancestor_class):
+ """
+ Return the nearest ancestor with the given class.
+
+ This function searches through all ancestors (parent, parent of the
+ parent, etc.) of this node until it finds a node of the given class.
+ If none of the ancestors is of the given class, None is returned.
+
+ @param ancestor_class: Node class to search for.
+ @type ancestor_class: type
+
+ @return: Ancestor node of the given class.
+ @rtype: Node or None
+ """
+
+ checktype(ancestor_class, type)
+
+ parent = self.__parent__
+ while parent is not None:
+ if isinstance(parent, ancestor_class):
+ return parent
+ parent = parent.__parent__
+ return None
+
+
+ # -------------------------------------------------------------------------
+ # Find first descendant of a given class
+ # -------------------------------------------------------------------------
+
+ def __find_descendant_of_class__(self, descendant_class):
+ """
+ Return the first descendant with the given class.
+
+ This function searches through all descendants (children, children of
+ children, etc.) of this node until it finds a node of the given class.
+ If none of the descendants is of the given class, None is returned.
+
+ 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 descendant_class: Node class to search for.
+ @type descendant_class: type
+
+ @return: Descendant node of the given node type.
+ @rtype: Node or None
+ """
+
+ checktype(descendant_class, type)
+
+ for child in self.__children__:
+ if isinstance(child, descendant_class):
+ return child
+ found = child.__find_descendant_of_class__(descendant_class)
+ if found is not None:
+ return found
+
+
+ # -------------------------------------------------------------------------
+ # 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 the new parent will accept us as a child.
+ if parent is not None:
+ for allowed_class, info in parent._allowed_children_.items():
+ # Must test with isinstance to also match descendant classes.
+ if isinstance(self, allowed_class):
+ if info.get('singleton', False):
+ if parent.__find_descendant_of_class__(allowed_class):
+ raise DuplicateSingletonError(parent,
+ allowed_class)
+ break
+ else:
+ raise ChildNotAllowedError(parent, self)
+
+ # 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)
+
+
+# -----------------------------------------------------------------------------
+# By default, allow all kinds of children
+# -----------------------------------------------------------------------------
+
+# This has to be put here since in the declaration of the Node class, the
+# identifier "Node" is not yet defined.
+Node._allowed_children_ = {Node: {}}
+
+
+# =============================================================================
+# NamedNode class
+# =============================================================================
+
+class NamedNode(Node):
+ """
+ A node in an n-ary tree with a name.
+
+ C{NamedNode}s introduce a L{I{node name} <node_name>}.
+
+ Children of C{NamedNode}s that are also C{NamedNode}s can be accessed
+ with their name by using the L{__get_child__} function. At the same time,
+ all children look like a read-only property of the direct parent, so to
+ access the child 'bar' of the node 'foo', just write C{foo.bar}.
+
+ To delete a child from the list of children, you can use 'C{del
+ node.childname}'.
+
+ Instances of this class support searching descendants for a given node
+ name with the method L{__find_descendant__}.
+
+ Every C{NamedNode} instance can define a list of node classes it is
+ interested in. Descendants of each of these classes will be hashed in a
+ L{dictionary <__get_node_dict__>} (a separate dictionary per class).
+
+ @cvar _node_dicts_: List of classes for which descendants should be hashed.
+ Defined by subclasses.
+ @type _node_dicts_: [str]
+ """
+
+ # -------------------------------------------------------------------------
+ # Class variables
+ # -------------------------------------------------------------------------
+
+ _node_dicts_ = []
+
+
+ # -------------------------------------------------------------------------
+ # Constructor
+ # -------------------------------------------------------------------------
+
+ def __init__(self, parent=None, children=None):
+ """
+ Initialize a new named node.
+
+ @param parent: Parent node.
+ @type parent: Node
+ """
+
+ # The following 3 variables must be set before __init__, because
+ # setting the parent or attaching the children already needs them.
+
+ #: Node name
+ self.__node_name = None
+
+ #: Dictionary with all named children
+ self.__named_children = {}
+
+ #: Dictionaries with descendants of interesting classes
+ self.__node_dicts = dict.fromkeys(self._node_dicts_, {})
+
+ Node.__init__(self, parent=parent, children=children)
+
+
+ # -------------------------------------------------------------------------
+ # Nice string representation
+ # -------------------------------------------------------------------------
+
+ def __unicode__(self):
+ """
+ Return the node name as unicode string.
+
+ If there is no node name defined, a string saying C{"<unnamed
+ I{classname}>"} is returned.
+ """
+
+ if self.__node_name is None:
+ return "<unnamed " + self.__class__.__name__ + ">"
+ else:
+ return unicode(self.__node_name)
+
+ # -------------------------------------------------------------------------
+
+ def __str__(self):
+ """
+ Return a 8 bit string representation of the node.
+
+ If there is no node name defined, a string saying C{"<unnamed
+ I{classname}>"} is returned.
+
+ The string is encoded in the current system encoding.
+ """
+
+ return i18n.outconv(self.__unicode__())
+
+ # -------------------------------------------------------------------------
+
+ def __repr__(self):
+ """
+ Return a verbose string representation of the node.
+ """
+
+ if self.__node_name is None:
+ return "<unnamed " + self.__class__.__name__ + ">"
+ else:
+ return "<%(class)s \"%(name)s\">" % {
+ 'class': self.__class__.__name__,
+ 'name': self.__str__()}
+
+
+ # -------------------------------------------------------------------------
+ # Attribute access
+ # -------------------------------------------------------------------------
+
+ def __getattr__(self, name):
+ """
+ Allow direct access to children by name.
+ """
+
+ if self.__named_children.has_key(name):
+ return self.__named_children[name]
+ else:
+ raise AttributeError
+
+ # -------------------------------------------------------------------------
+
+ def __delattr__(self, name):
+ """
+ Allow removal of children with C{del node.child}.
+ """
+
+ if self.__named_children.has_key(name):
+ self.__named_children[name].__parent__ = None
+ else:
+ Node.__delattr__(self, name)
+
+
+ # -------------------------------------------------------------------------
+ # 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_named_children()
+ self.__unregister_node_dict(self.__parent__)
+
+ self.__node_name = unicode(value)
+
+ if self.__node_name is not None:
+ self.__register_named_children()
+ self.__register_node_dict(self.__parent__)
+
+
+ # -------------------------------------------------------------------------
+
+ __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_named_children()
+ # We also have to unregister all our descendants from our old
+ # ancestors' node dicts.
+ def maybe_unregister(node, parent):
+ if isinstance(node, NamedNode):
+ node.__unregister_node_dict(parent)
+ self.__walk__(maybe_unregister, self.__parent__)
+
+ Node._set_parent_(self, parent)
+
+ if self.__node_name is not None:
+ self.__register_named_children()
+ # We also have to register all our descendants with our new
+ # ancestors' node dicts.
+ def maybe_register(node, parent):
+ if isinstance(node, NamedNode):
+ node.__register_node_dict(parent)
+ self.__walk__(maybe_register, self.__parent__)
+
+
+ # -------------------------------------------------------------------------
+ # Helper methods to register/unregister with parent and ancestors
+ # -------------------------------------------------------------------------
+
+ def __register_named_children(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
+
+ # -------------------------------------------------------------------------
+
+ def __register_node_dict(self, parent):
+
+ # register with all ancestors that have a node_dict for this class
+ ancestor = parent
+ while ancestor is not None:
+ if isinstance(ancestor, NamedNode):
+ if ancestor.__node_dicts.has_key(self.__class__):
+ node_dict = ancestor.__node_dicts[self.__class__]
+ if node_dict.has_key(self.__node_name):
+ raise DuplicateDescendantNameError, (self.__node_name,
+ self.__class__, ancestor)
+ node_dict[self.__node_name] = self
+ ancestor = ancestor.__parent__
+
+ # -------------------------------------------------------------------------
+
+ def __unregister_named_children(self):
+
+ # unregister with parent
+ if isinstance(self.__parent__, NamedNode):
+ del self.__parent__.__named_children[self.__node_name]
+
+ # -------------------------------------------------------------------------
+
+ def __unregister_node_dict(self, parent):
+
+ # unregister with all ancestors that have a node_dict for this class
+ ancestor = parent
+ while ancestor is not None:
+ if isinstance(ancestor, NamedNode):
+ node_dicts = ancestor.__node_dicts
+ if node_dicts.has_key(self.__class__):
+ del ancestor.__node_dicts[self.__class__]\
+ [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 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 name, 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 with the given name.
+ @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
+
+ # -------------------------------------------------------------------------
+ # Get node dictionary with all descendant nodes of a given class
+ # -------------------------------------------------------------------------
+
+ def __get_node_dict__(self, descendant_class):
+ """
+ Return a dictionary with all descendant nodes of the given class.
+
+ 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 classes that have been registered in
+ the L{_node_dicts_} list of the class of this node.
+ """
+
+ if descendant_class not in self.__node_dicts:
+ raise NodeDictNotAvailableError, (self.__node_name, self.__class__,
+ descendant_class)
+ return self.__node_dicts[descendant_class]
+
+
+# =============================================================================
+# AttribNode class
+# =============================================================================
+
+class AttribNode(NamedNode):
+ """
+ A node in an n-ary tree with node attributes.
+
+ Every subclass of this class can define a set of valid attributes that
+ nodes of this subclass will have, of what type the attributes are, and what
+ default value these attributes will have.
+
+ TODO: document structure of _node_attribs_ dictionary, and give examples
+ how to use it (especially how to extend the inherited dictionary in
+ subclasses).
+
+ Instances of this class expose their attributes through dictionary access.
+ The attribute 'my_attr' of the object instance 'my_node' can be read and
+ written as C{my_node['my_attr']}.
+
+ On creation of new instances, attributes are initialized with their default
+ value, or with C{None} if no default value is defined.
+
+ Whenever an attribute value is set, it is typecast to the defined type. If
+ this typecast fails, the value is not changed, and an exception is raised.
+
+ Attribute types can not only be ordinary data types (like C{unicode},
+ C{str}, or C{int}, but they can also be subclasses of L{NamedNode}. In this
+ case, both C{my_node['my_attr'] = other_node} and
+ C{my_node['my_attr'] = 'other_node_name'} are valid, and will cause
+ C{my_node['my_attr']} to evaluate to other_node, provided that other_node
+ has a name of 'other_node_name', both my_node and other_node are in the
+ same tree, and the type of other_node is registered in the root node's
+ C{_node_dicts_} list.
+ """
+
+ # -------------------------------------------------------------------------
+ # Class variables
+ # -------------------------------------------------------------------------
+
+ _node_attribs_ = {
+ 'name': {
+ 'type': str,
+ 'label': u_("name"),
+ 'description': u_("Name of this element"),
+ 'default': None}}
+
+
+ # -------------------------------------------------------------------------
+ # Constructor
+ # -------------------------------------------------------------------------
+
+ def __init__(self, parent=None, children=None):
+ """
+ Initialize a new attributed node.
+
+ @param parent: Parent node.
+ @type parent: Node
+ """
+
+ NamedNode.__init__(self, parent=parent, children=children)
+
+ #: Attributes
+ self.__attribs = {}
+
+ for (name, definition) in self._node_attribs_:
+ self.__attribs[name] = definition.get('default')
+
+
+ # -------------------------------------------------------------------------
+ # Dictionary style attribute access
+ # -------------------------------------------------------------------------
+
+ def __getitem__(self, name):
+
+ try:
+ definition = self._node_attribs_[name]
+ except KeyError:
+ raise InvalidAttributeError(self, name)
+
+ # if this is a reference to another node, look for it in the parent's
+ # node dictionary
+ target_type = definition['type']
+
+ # TODO: find node type for wanted class, look up name in root's node
+ # dictionary.
+
+ return self.__attribs[name]
+
+ # -------------------------------------------------------------------------
+
+ def __setitem__(self, name, value):
+
+ try:
+ definition = self._node_attribs_[name]
+ except KeyError:
+ raise InvalidAttributeError(self, name)
+
+ # typecast if necessary
+ target_type = definition['type']
+
+ # if this is a reference to another node, we need to store the name
+ if issubclass(target_type, NamedNode):
+ target_type = unicode
+
+ if not isinstance(value, target_type):
+ try:
+ value = target_type(value)
+ except Exception, e:
+ raise InvalidAttributeValueError(self, name, value, e)
+
+ # TODO: check if value is in list of allowed values if defined in
+ # _node_attribs_
+ self.__attribs[name] = value
+
+
+# =============================================================================
+# Exceptions
+# =============================================================================
+
+class ChildNotAllowedError(errors.ApplicationError):
+ """
+ Children of this class are not allowed for this parent.
+
+ The requested parent for this node can't be set because the parent does not
+ allow for children of this class.
+ """
+ def __init__(self, parent_node, child_node):
+ message = u_(
+ "Parent node '%(parent_node)s' does not allow children of "
+ "class '%(child_class)s'")
+ errors.ApplicationError.__init__(self, message % {
+ 'parent_node': parent_node,
+ 'child_class': child_node.__class__.__name__})
+
+
+# =============================================================================
+
+class DuplicateSingletonError(errors.ApplicationError):
+ """
+ Only one child of this class allowed.
+
+ The requested parent for this node can't be set because the parent already
+ has a child of this class, but only one is allowed.
+ """
+ def __init__(self, parent_node, child_class):
+ message = u_(
+ "Parent node '%(parent_node)s' already has a child of class "
+ "'%(child_class)s'")
+ errors.ApplicationError.__init__(self, message % {
+ 'parent_node': parent_node,
+ 'child_class': child_class.__name__})
+
+
+# =============================================================================
+
+class CircularReferenceError(errors.ApplicationError):
+ """
+ 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.ApplicationError.__init__(self, message)
+
+
+# =============================================================================
+
+class DuplicateChildNameError(errors.ApplicationError):
+ """
+ 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.ApplicationError.__init__(self, message % {
+ 'child_name': child_name,
+ 'parent_node': parent_node})
+
+
+# =============================================================================
+
+class DuplicateDescendantNameError(errors.ApplicationError):
+ """
+ Duplicate descendant name for node class.
+
+ 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 class
+ with the same name. This is only a problem if this ancestor maintains a
+ dictionary of the descendants of this class.
+
+ Note that after this exception has happened, the tree is in an inconsistent
+ state.
+ """
+ def __init__(self, descendant_name, descendant_class, ancestor_node):
+ message = u_(
+ "Duplicate node name '%(descendant_name)s' with class "
+ "'%(descendant_class)s' in descendants of node "
+ "'%(ancestor_node)s'")
+ errors.ApplicationError.__init__(self, message % {
+ 'descendant_name': descendant_name,
+ 'descendant_class': descendant_class.__name__,
+ 'ancestor_node': ancestor_node})
+
+
+# =============================================================================
+
+class NodeDictNotAvailableError(errors.SystemError):
+ """
+ Node Dictionary not available for this class.
+
+ This node class does not maintain a node dictionary for the requested class.
+ """
+ def __init__(self, node_name, parent_class, child_class):
+ message = u_(
+ "Node '%(node_name)s' of class '%(parent_class)s' does not "
+ "maintain a node dictionary for node class '%(child_class)s'")
+ errors.SystemError.__init__(self, message % {
+ 'node_name': node_name,
+ 'parent_class': parent_class.__module__ + '.' \
+ + parent_class.__name__,
+ 'child_class': child_class.__name__})
+
+
+# =============================================================================
+# Self test code
+# =============================================================================
+
+# -----------------------------------------------------------------------------
+# Node class
+# -----------------------------------------------------------------------------
+
+def test_node_class():
+
+ # Descendant of Node used in test code
+ class TestNode(Node):
+ def __init__(self, parent=None, children=None, text=None):
+ Node.__init__(self, parent=parent, children=children)
+ self.__text = text
+ def __str__(self):
+ return self.__text
+
+ # Build up our tree
+ root = TestNode(text='People')
+ monty_python = TestNode(parent=root, text='Monty Python')
+ john_cleese = TestNode(parent=monty_python, text='John Cleese')
+ TestNode(parent=monty_python, text='Michael Palin')
+ TestNode(parent=monty_python, text='Graham Chapman')
+ TestNode(parent=monty_python, text='Terry Jones')
+ TestNode(parent=monty_python, text='Terry Gilliam')
+ star_trek = TestNode(parent=root, text='Star Trek', children=[
+ TestNode(text='James T. Kirk'),
+ TestNode(text='Mr. Spock'),
+ TestNode(text='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__
+
+
+# -----------------------------------------------------------------------------
+# NamedNode class
+# -----------------------------------------------------------------------------
+
+def test_named_node_class():
+
+ # Descendants of Node and NamedNode used in test code
+ class TextNode(NamedNode):
+ def __init__(self, parent, text):
+ NamedNode.__init__(self, parent)
+ self.__node_name__ = text
+ class Man(TextNode):
+ pass
+ class Woman(TextNode):
+ pass
+ class Captain(TextNode):
+ pass
+ class Group(TextNode):
+ _node_dicts_ = [Man, Captain]
+ Group._allowed_children_ = {
+ Group: {},
+ Man: {},
+ Woman: {},
+ # There can only be one captain!
+ Captain: {'singleton': True}}
+
+ # Build up our tree
+ root = Group(None, 'People')
+ monty_python = Group(root, 'Monty Python')
+ john_cleese = Man(monty_python, 'John Cleese')
+ Man(monty_python, 'Michael Palin')
+ Man(monty_python, 'Graham Chapman')
+ Man(monty_python, 'Terry Jones')
+ Man(monty_python, 'Terry Gilliam')
+ Woman(monty_python, None) # The woman whose name I can't remember
+ star_trek = Group(root, 'Star Trek')
+ james_kirk = Captain(star_trek, 'James T. Kirk')
+ Man(star_trek, 'Spock')
+ Man(star_trek, 'Leonard McCoy')
+ Woman(star_trek, 'Nyota Uhura')
+ Man(star_trek, None) # The nameless security officer
+ wife = Node(james_kirk) # Kirk's wife - unnamed by intention
+ peter_kirk = Man(wife, 'Peter Kirk') # Kirk's son
+
+ # Test direct child access
+ print "Spock can be directly accessed:",
+ print star_trek.Spock
+
+ # Test "__node_name__" property
+ print james_kirk, "has node name", james_kirk.__node_name__
+
+ # Test "__get_child__" method
+ print "Terry Jones can be found:",
+ print monty_python.__get_child__('Terry Jones')
+
+ # Test "__find_ancestor_of_class__" method
+ print peter_kirk, "belongs to",
+ print peter_kirk.__find_ancestor_of_class__(Group)
+
+ # Test "__find_descendant__" method
+ print "Peter Kirk can be found:",
+ print star_trek.__find_descendant__('Peter Kirk')
+
+ # Test "__find_descendant_of_class__" method
+ print "Nyota Uhura can be found:",
+ print star_trek.__find_descendant_of_class__(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:
+ james_kirk.__node_name__ = 'James Tiberius Kirk'
+ print "Now Kirk's node name has changed to", james_kirk.__node_name__
+ print "Now he can be found under the new name with __get_child__:", \
+ star_trek.__get_child__('James Tiberius Kirk')
+ print "Now he can be found under the new name with __find_descendant__:", \
+ root.__find_descendant__('James Tiberius Kirk')
+ print "He cannot be found under the old name any more:", \
+ star_trek.__get_child__('James T. Kirk'), "-", \
+ root.__find_descendant__('James T. Kirk')
+ print "He is in root's node_dict as 'James Tiberius Kirk':", \
+ 'James Tiberius Kirk' in root.__get_node_dict__(Captain)
+ print "He is in root's node_dict as 'James T. Kirk':", \
+ 'James T. Kirk' in root.__get_node_dict__(Captain)
+
+ # Test changing parent: __get_child__, __get_node_dict__ for old and new
+ print "Making James Kirk a son of John Cleese (ugh!)"
+ james_kirk.__parent__ = john_cleese
+ print "Now he can be found under Monty Python with __find_descendant__:", \
+ monty_python.__find_descendant__('James Tiberius Kirk')
+ print "He cannot be found under Star Trek any more:", \
+ star_trek.__get_child__('James Tiberius Kirk'), "-", \
+ star_trek.__find_descendant__('James Tiberius Kirk')
+ print "He is in Star Trek's node_dict:", \
+ 'James Tiberius Kirk' in star_trek.__get_node_dict__(Man)
+ print "He is in Monty Python's node_dict:", \
+ 'James Tiberius Kirk' in monty_python.__get_node_dict__(Man)
+ print "Peter Kirk is in Star Trek's node_dict:", \
+ 'Peter Kirk' in star_trek.__get_node_dict__(Man)
+ print "Peter Kirk is in Monty Python's node_dict:", \
+ 'Peter Kirk' in monty_python.__get_node_dict__(Man)
+
+ # Test deletion of child
+ print "Deleting Spock"
+ del star_trek.Spock
+ print "Now he cannot be found any more:", \
+ star_trek.__get_child__('Spock'), "-", \
+ root.__find_descendant__('Spock')
+
+ # Test ChildNotAllowedError
+ try:
+ TextNode(star_trek, 'Nibble')
+ except ChildNotAllowedError, error:
+ print "Correctly got an exception:", error
+
+ # Test DuplicateSingletonError
+ try:
+ Captain(star_trek, 'Second Captain')
+ except DuplicateSingletonError, error:
+ print "Correctly got an exception:", error
+
+ # Test DuplicateChildNameError
+ try:
+ Woman(star_trek, 'Nyota Uhura')
+ except DuplicateChildNameError, error:
+ print "Correctly got an exception:", error
+ new_uhura = Woman(wife, 'Nyota Uhura') # this may not fail...
+ try:
+ new_uhura.__parent__ = star_trek # ...but this must fail
+ except DuplicateChildNameError, error:
+ print "Correctly got an exception:", error
+
+ # Test DuplicateDescendantNameError
+ try:
+ Man(peter_kirk, 'Terry Jones')
+ except DuplicateDescendantNameError, error:
+ print "Correctly got an exception:", error
+
+ # Test NodeDictNotAvailableError
+ try:
+ root.__get_node_dict__(Woman)
+ except NodeDictNotAvailableError, error:
+ print "Correctly got an exception:", error
+
+
+# -----------------------------------------------------------------------------
+# Run tests
+# -----------------------------------------------------------------------------
+
+if __name__ == '__main__':
+
+ test_node_class()
+ print
+ test_named_node_class()
+ # TODO: test_attrib_node_class()
Deleted: trunk/gnue-common/src/utils/tree.py
===================================================================
--- trunk/gnue-common/src/utils/tree.py 2009-10-08 06:51:58 UTC (rev 9945)
+++ trunk/gnue-common/src/utils/tree.py 2009-10-08 10:31:18 UTC (rev 9946)
@@ -1,965 +0,0 @@
-# GNU Enterprise Common Library - Tree structure classes
-#
-# Copyright 2001-2009 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$
-
-"""
-Classes representing a node in a tree structure.
-
-TODO: This module is work in progress.
-"""
-
-from gnue.common.base import errors, i18n
-from gnue.common.base.i18n import utranslate as u_ # for epydoc
-
-__all__ = ['CircularReferenceError', 'DuplicateChildNameError',
- 'DuplicateDescendantNameError', 'NodeDictNotAvailableError',
- 'Node', 'NamedNode', 'AttribNode']
-
-
-# =============================================================================
-# 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)
-
-
-# =============================================================================
-
-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.__module__ + '.' + node_class.__name__,
- 'node_type': node_type})
-
-
-# =============================================================================
-# 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 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
- 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
- """
-
- #: Parent node or C{None} if this is the root node
- self.__parent = None
-
- #: List of child nodes
- self.__children = []
-
- self.parent = parent
-
-
- # -------------------------------------------------------------------------
- # Property "parent"
- # -------------------------------------------------------------------------
-
- def __get_parent(self):
-
- return self.__parent
-
- # -------------------------------------------------------------------------
-
- def __set_parent(self, value):
-
- checktype(value, [Node, None])
-
- self._set_parent_(value)
-
- # -------------------------------------------------------------------------
-
- parent = property(__get_parent, __set_parent, None,
- """
- Parent node, or C{None} if this is the root of the tree.
-
- @type: Node or None
- """)
-
-
- # -------------------------------------------------------------------------
- # 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 C{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)
-
-
- # -------------------------------------------------------------------------
- # 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.
-
- Children of C{NamedNode}s that are also C{NamedNode}s can be L{accessed
- with their name <get_child>}.
-
- Instances of this class support searching ancestors L{for a given node type
- <find_ancestor_of_type>} and 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
- L{dictionary <get_node_dict>} (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 i18n.outconv(self.__node_name)
-
- 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.
- """
-
- if node_type not in self.__node_dicts:
- raise NodeDictNotAvailableError, (self.__node_name, self.__class__,
- node_type)
- return self.__node_dicts[node_type]
-
-
-# =============================================================================
-# AttribNode class
-# =============================================================================
-
-class AttribNode(NamedNode):
- """
- A node in an n-ary tree with node attributes.
-
- Every subclass of this class can define a set of valid attributes that
- nodes of this subclass will have, of what type the attributes are, and what
- default value these attributes will have.
-
- TODO: document structure of _node_attribs_ dictionary, and give examples
- how to use it (especially how to extend the inherited dictionary in
- subclasses).
-
- Instances of this class expose their attributes through dictionary access.
- The attribute 'my_attr' of the object instance 'my_node' can be read and
- written as C{my_node['my_attr']}.
-
- On creation of new instances, attributes are initialized with their default
- value, or with C{None} if no default value is defined.
-
- Whenever an attribute value is set, it is typecast to the defined type. If
- this typecast fails, the value is not changed, and an exception is raised.
-
- Attribute types can not only be ordinary data types (like C{unicode},
- C{str}, or C{int}, but they can also be subclasses of L{NamedNode}. In this
- case, both C{my_node['my_attr'] = other_node} and
- C{my_node['my_attr'] = 'other_node_name'} are valid, and will cause
- C{my_node['my_attr']} to evaluate to other_node, provided that other_node
- has a name of 'other_node_name', both my_node and other_node are in the
- same tree, and the type of other_node is registered in the root node's
- C{_node_dicts_} list.
- """
-
- # -------------------------------------------------------------------------
- # Class variables
- # -------------------------------------------------------------------------
-
- _node_attribs_ = {
- 'name': {
- 'type': str,
- 'label': u_("name"),
- 'description': u_("Name of this element"),
- 'default': None}}
-
-
- # -------------------------------------------------------------------------
- # Constructor
- # -------------------------------------------------------------------------
-
- def __init__(self, parent):
- """
- Initialize a new attributed node.
-
- @param parent: Parent node.
- @type parent: Node
- """
-
- NamedNode.__init__(self, parent)
-
- #: Attributes
- self.__attribs = {}
-
- for (name, definition) in self._node_attribs_:
- self.__attribs[name] = definition.get('default')
-
-
- # -------------------------------------------------------------------------
- # Dictionary style attribute access
- # -------------------------------------------------------------------------
-
- def __getitem__(self, name):
-
- try:
- definition = self._node_attribs_[name]
- except KeyError:
- raise InvalidAttributeError(self, name)
-
- # if this is a reference to another node, look for it in the parent's
- # node dictionary
- target_type = definition['type']
-
- # TODO: find node type for wanted class, look up name in root's node
- # dictionary.
-
- return self.__attribs[name]
-
- # -------------------------------------------------------------------------
-
- def __setitem__(self, name, value):
-
- try:
- definition = self._node_attribs_[name]
- except KeyError:
- raise InvalidAttributeError(self, name)
-
- # typecast if necessary
- target_type = definition['type']
-
- # if this is a reference to another node, we need to store the name
- if issubclass(target_type, NamedNode):
- target_type = unicode
-
- if not isinstance(value, target_type):
- try:
- value = target_type(value)
- except Exception, e:
- raise InvalidAttributeValueError(self, name, value, e)
-
- # TODO: check if value is in list of allowed values if defined in
- # _node_attribs_
- self.__attribs[name] = value
-
-
-# =============================================================================
-# Self test code
-# =============================================================================
-
-# -----------------------------------------------------------------------------
-# Node class
-# -----------------------------------------------------------------------------
-
-def test_node_class():
-
- # 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
-
-
-# -----------------------------------------------------------------------------
-# NamedNode class
-# -----------------------------------------------------------------------------
-
-def test_named_node_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
- wife = Node(james_kirk) # Kirk's wife - unnamed node by intention
- peter_kirk = ManNode(wife, '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
-
- # 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:
- james_kirk.node_name = 'James Tiberius Kirk'
- print "Now Kirk's node name has changed to", james_kirk.node_name
- print "Now he can be found under the new name with get_child:", \
- star_trek.get_child('James Tiberius Kirk')
- print "Now he can be found under the new name with find_descendant:", \
- root.find_descendant('James Tiberius Kirk')
- print "He cannot be found under the old name any more:", \
- star_trek.get_child('James T. Kirk'), "-", \
- root.find_descendant('James T. Kirk')
- print "He is in root's node_dict as 'James Tiberius Kirk':", \
- 'James Tiberius Kirk' in root.get_node_dict('man')
- print "He is in root's node_dict as 'James T. Kirk':", \
- 'James T. Kirk' in root.get_node_dict('man')
-
- # Test changing parent: get_child, get_node_dict for old and new
- print "Making John Cleese a son of James Kirk's wife (ugh!)"
- john_cleese.parent = wife
- print "Now he can be found under Star Trek with find_descendant:", \
- star_trek.find_descendant('John Cleese')
- print "He cannot be found under Monty Python any more:", \
- monty_python.get_child('John Cleese'), "-", \
- monty_python.find_descendant('John Cleese')
- print "He is in Star Trek's node_dict:", \
- 'John Cleese' in star_trek.get_node_dict('man')
- print "He is in Monty Python's node_dict:", \
- 'John Cleese' in monty_python.get_node_dict('man')
-
- # Test DuplicateChildNameError
- try:
- TextNode(star_trek, 'Nyota Uhura')
- except DuplicateChildNameError, error:
- print "Correctly got an exception:", error
- new_uhura = WomanNode(wife, 'Nyota Uhura') # this may not fail...
- try:
- new_uhura.parent = star_trek # ...but this must fail
- except DuplicateChildNameError, error:
- print "Correctly got an exception:", error
-
- # Test DuplicateDescendantNameError
- try:
- TextNode(peter_kirk, 'Terry Jones')
- except DuplicateDescendantNameError, error:
- print "Correctly got an exception:", error
-
- # Test NodeDictNotAvailableError
- try:
- root.get_node_dict('woman')
- except NodeDictNotAvailableError, error:
- print "Correctly got an exception:", error
-
-
-# -----------------------------------------------------------------------------
-# Run tests
-# -----------------------------------------------------------------------------
-
-if __name__ == '__main__':
-
- test_node_class()
- test_named_node_class()
- # TODO: test_attrib_node_class()
lmpx.com only provides a reader for public news (NNTP) servers. It is not
affiliated with the servers or forums shown here and is not responsible for
the content of articles, which is written by their respective authors.