--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/app/django/utils/tree.py	Fri Jul 18 18:22:23 2008 +0000
@@ -0,0 +1,134 @@
+"""
+A class for storing a tree graph. Primarily used for filter constructs in the
+ORM.
+"""
+
+from copy import deepcopy
+
+class Node(object):
+    """
+    A single internal node in the tree graph. A Node should be viewed as a
+    connection (the root) with the children being either leaf nodes or other
+    Node instances.
+    """
+    # Standard connector type. Clients usually won't use this at all and
+    # subclasses will usually override the value.
+    default = 'DEFAULT'
+
+    def __init__(self, children=None, connector=None, negated=False):
+        """
+        Constructs a new Node. If no connector is given, the default will be
+        used.
+
+        Warning: You probably don't want to pass in the 'negated' parameter. It
+        is NOT the same as constructing a node and calling negate() on the
+        result.
+        """
+        self.children = children and children[:] or []
+        self.connector = connector or self.default
+        self.subtree_parents = []
+        self.negated = negated
+
+    def __str__(self):
+        if self.negated:
+            return '(NOT (%s: %s))' % (self.connector, ', '.join([str(c) for c
+                    in self.children]))
+        return '(%s: %s)' % (self.connector, ', '.join([str(c) for c in
+                self.children]))
+
+    def __deepcopy__(self, memodict):
+        """
+        Utility method used by copy.deepcopy().
+        """
+        obj = Node(connector=self.connector, negated=self.negated)
+        obj.__class__ = self.__class__
+        obj.children = deepcopy(self.children, memodict)
+        obj.subtree_parents = deepcopy(self.subtree_parents, memodict)
+        return obj
+
+    def __len__(self):
+        """
+        The size of a node if the number of children it has.
+        """
+        return len(self.children)
+
+    def __nonzero__(self):
+        """
+        For truth value testing.
+        """
+        return bool(self.children)
+
+    def __contains__(self, other):
+        """
+        Returns True is 'other' is a direct child of this instance.
+        """
+        return other in self.children
+
+    def add(self, node, conn_type):
+        """
+        Adds a new node to the tree. If the conn_type is the same as the root's
+        current connector type, the node is added to the first level.
+        Otherwise, the whole tree is pushed down one level and a new root
+        connector is created, connecting the existing tree and the new node.
+        """
+        if node in self.children:
+            return
+        if len(self.children) < 2:
+            self.connector = conn_type
+        if self.connector == conn_type:
+            if isinstance(node, Node) and (node.connector == conn_type or
+                    len(node) == 1):
+                self.children.extend(node.children)
+            else:
+                self.children.append(node)
+        else:
+            obj = Node(self.children, self.connector, self.negated)
+            self.connector = conn_type
+            self.children = [obj, node]
+
+    def negate(self):
+        """
+        Negate the sense of the root connector. This reorganises the children
+        so that the current node has a single child: a negated node containing
+        all the previous children. This slightly odd construction makes adding
+        new children behave more intuitively.
+
+        Interpreting the meaning of this negate is up to client code. This
+        method is useful for implementing "not" arrangements.
+        """
+        self.children = [Node(self.children, self.connector, not self.negated)]
+        self.connector = self.default
+
+    def start_subtree(self, conn_type):
+        """
+        Sets up internal state so that new nodes are added to a subtree of the
+        current node. The conn_type specifies how the sub-tree is joined to the
+        existing children.
+        """
+        if len(self.children) == 1:
+            self.connector = conn_type
+        elif self.connector != conn_type:
+            self.children = [Node(self.children, self.connector, self.negated)]
+            self.connector = conn_type
+            self.negated = False
+
+        self.subtree_parents.append(Node(self.children, self.connector,
+                self.negated))
+        self.connector = self.default
+        self.negated = False
+        self.children = []
+
+    def end_subtree(self):
+        """
+        Closes off the most recently unmatched start_subtree() call.
+
+        This puts the current state into a node of the parent tree and returns
+        the current instances state to be the parent.
+        """
+        obj = self.subtree_parents.pop()
+        node = Node(self.children, self.connector)
+        self.connector = obj.connector
+        self.negated = obj.negated
+        self.children = obj.children
+        self.children.append(node)
+