diff options
Diffstat (limited to 'webapp/django/utils/tree.py')
| -rw-r--r-- | webapp/django/utils/tree.py | 153 |
1 files changed, 153 insertions, 0 deletions
diff --git a/webapp/django/utils/tree.py b/webapp/django/utils/tree.py new file mode 100644 index 0000000000..a9028b834b --- /dev/null +++ b/webapp/django/utils/tree.py @@ -0,0 +1,153 @@ +""" +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 + + # We need this because of django.db.models.query_utils.Q. Q. __init__() is + # problematic, but it is a natural Node subclass in all other respects. + def _new_instance(cls, children=None, connector=None, negated=False): + """ + This is called to create a new instance of this class when we need new + Nodes (or subclasses) in the internal code in this class. Normally, it + just shadows __init__(). However, subclasses with an __init__ signature + that is not an extension of Node.__init__ might need to implement this + method to allow a Node to create a new instance of them (if they have + any extra setting up to do). + """ + obj = Node(children, connector, negated) + obj.__class__ = cls + return obj + _new_instance = classmethod(_new_instance) + + 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 and conn_type == self.connector: + 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 = self._new_instance(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 = [self._new_instance(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 = [self._new_instance(self.children, self.connector, + self.negated)] + self.connector = conn_type + self.negated = False + + self.subtree_parents.append(self.__class__(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 = self.__class__(self.children, self.connector) + self.connector = obj.connector + self.negated = obj.negated + self.children = obj.children + self.children.append(node) + |