1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
"""
A class for storing a tree graph. Primarily used for filter constructs in the
ORM.
"""
import copy
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 connection type. Clients usually won't use this at all and
# subclasses will usually override the value.
default = 'DEFAULT'
def __init__(self, children=None, connection=None):
self.children = children and children[:] or []
self.connection = connection or self.default
self.subtree_parents = []
self.negated = False
def __str__(self):
return '(%s: %s)' % (self.connection, ', '.join([str(c) for c in
self.children]))
def __deepcopy__(self, memodict):
"""
Utility method used by copy.deepcopy().
"""
obj = self.__class__(connection=self.connection)
obj.children = copy.deepcopy(self.children, memodict)
obj.subtree_parents = copy.deepcopy(self.subtree_parents, memodict)
obj.negated = self.negated
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 connection type, the node is added to the first level.
Otherwise, the whole tree is pushed down one level and a new root
connection is created, connecting the existing tree and the new node.
"""
if len(self.children) < 2:
self.connection = conn_type
if self.connection == conn_type:
if isinstance(node, Node) and (node.connection == conn_type
or len(node) == 1):
self.children.extend(node.children)
else:
self.children.append(node)
else:
obj = Node(self.children, self.connection)
self.connection = conn_type
self.children = [obj, node]
def negate(self):
"""
Negate the sense of the root connection.
Interpreting the meaning of this negate is up to client code. This
method is useful for implementing "not" arrangements.
"""
self.children = [NegatedNode(self.children, self.connection,
old_state=self.negated)]
self.connection = 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 is required so that the new subtree is
connected correctly to any existing nodes in the tree.
"""
if len(self.children) == 1:
self.connection = conn_type
elif self.connection != conn_type:
self.children = [Node(self.children, self.connection)]
self.connection = conn_type
self.subtree_parents.append(Node(self.children, self.connection))
self.connection = self.default
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.connection)
self.connection = obj.connection
self.children = obj.children
self.children.append(node)
class NegatedNode(Node):
"""
A class that indicates the connection type should be negated (whatever that
means -- it's up to the client) when used by the client code.
"""
def __init__(self, children=None, connection=None, old_state=True):
super(NegatedNode, self).__init__(children, connection)
self.negated = not old_state
|
