py_tasks_melange: app/django/utils/tree.py@e076aee6e90f (annotated)

54 03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	1	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	2	A class for storing a tree graph. Primarily used for filter constructs in the
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	3	ORM.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	4	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	5
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	6	from copy import deepcopy
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	7
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	8	class Node(object):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	9	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	10	A single internal node in the tree graph. A Node should be viewed as a
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	11	connection (the root) with the children being either leaf nodes or other
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	12	Node instances.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	13	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	14	# Standard connector type. Clients usually won't use this at all and
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	15	# subclasses will usually override the value.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	16	default = 'DEFAULT'
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	17
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	18	def __init__(self, children=None, connector=None, negated=False):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	19	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	20	Constructs a new Node. If no connector is given, the default will be
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	21	used.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	22
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	23	Warning: You probably don't want to pass in the 'negated' parameter. It
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	24	is NOT the same as constructing a node and calling negate() on the
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	25	result.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	26	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	27	self.children = children and children[:] or []
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	28	self.connector = connector or self.default
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	29	self.subtree_parents = []
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	30	self.negated = negated
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	31
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	32	def __str__(self):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	33	if self.negated:
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	34	return '(NOT (%s: %s))' % (self.connector, ', '.join([str(c) for c
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	35	in self.children]))
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	36	return '(%s: %s)' % (self.connector, ', '.join([str(c) for c in
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	37	self.children]))
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	38
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	39	def __deepcopy__(self, memodict):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	40	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	41	Utility method used by copy.deepcopy().
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	42	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	43	obj = Node(connector=self.connector, negated=self.negated)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	44	obj.__class__ = self.__class__
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	45	obj.children = deepcopy(self.children, memodict)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	46	obj.subtree_parents = deepcopy(self.subtree_parents, memodict)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	47	return obj
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	48
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	49	def __len__(self):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	50	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	51	The size of a node if the number of children it has.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	52	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	53	return len(self.children)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	54
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	55	def __nonzero__(self):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	56	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	57	For truth value testing.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	58	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	59	return bool(self.children)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	60
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	61	def __contains__(self, other):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	62	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	63	Returns True is 'other' is a direct child of this instance.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	64	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	65	return other in self.children
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	66
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	67	def add(self, node, conn_type):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	68	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	69	Adds a new node to the tree. If the conn_type is the same as the root's
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	70	current connector type, the node is added to the first level.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	71	Otherwise, the whole tree is pushed down one level and a new root
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	72	connector is created, connecting the existing tree and the new node.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	73	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	74	if node in self.children:
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	75	return
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	76	if len(self.children) < 2:
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	77	self.connector = conn_type
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	78	if self.connector == conn_type:
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	79	if isinstance(node, Node) and (node.connector == conn_type or
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	80	len(node) == 1):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	81	self.children.extend(node.children)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	82	else:
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	83	self.children.append(node)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	84	else:
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	85	obj = Node(self.children, self.connector, self.negated)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	86	self.connector = conn_type
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	87	self.children = [obj, node]
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	88
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	89	def negate(self):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	90	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	91	Negate the sense of the root connector. This reorganises the children
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	92	so that the current node has a single child: a negated node containing
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	93	all the previous children. This slightly odd construction makes adding
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	94	new children behave more intuitively.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	95
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	96	Interpreting the meaning of this negate is up to client code. This
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	97	method is useful for implementing "not" arrangements.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	98	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	99	self.children = [Node(self.children, self.connector, not self.negated)]
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	100	self.connector = self.default
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	101
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	102	def start_subtree(self, conn_type):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	103	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	104	Sets up internal state so that new nodes are added to a subtree of the
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	105	current node. The conn_type specifies how the sub-tree is joined to the
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	106	existing children.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	107	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	108	if len(self.children) == 1:
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	109	self.connector = conn_type
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	110	elif self.connector != conn_type:
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	111	self.children = [Node(self.children, self.connector, self.negated)]
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	112	self.connector = conn_type
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	113	self.negated = False
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	114
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	115	self.subtree_parents.append(Node(self.children, self.connector,
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	116	self.negated))
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	117	self.connector = self.default
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	118	self.negated = False
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	119	self.children = []
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	120
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	121	def end_subtree(self):
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	122	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	123	Closes off the most recently unmatched start_subtree() call.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	124
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	125	This puts the current state into a node of the parent tree and returns
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	126	the current instances state to be the parent.
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	127	"""
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	128	obj = self.subtree_parents.pop()
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	129	node = Node(self.children, self.connector)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	130	self.connector = obj.connector
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	131	self.negated = obj.negated
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	132	self.children = obj.children
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	133	self.children.append(node)
03e267d67478 Major reorganization of the soc svn repo, to merge into a single App Engine Todd Larsen <tlarsen@google.com> parents: diff changeset	134

author	Todd Larsen <tlarsen@google.com>
	Mon, 29 Sep 2008 15:46:42 +0000
changeset 208	e076aee6e90f
parent 54	03e267d67478
child 323	ff1a9aa48cfd
permissions	-rw-r--r--