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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186 | """
New instance methods for Django models which are set up for Modified
Preorder Tree Traversal.
"""
def get_ancestors(self, ascending=False):
"""
Creates a ``QuerySet`` containing the ancestors of this model
instance.
This defaults to being in descending order (root ancestor first,
immediate parent last); passing ``True`` for the ``ascending``
argument will reverse the ordering (immediate parent first, root
ancestor last).
"""
if self.is_root_node():
return self._tree_manager.none()
opts = self._meta
return self._default_manager.filter(**{
'%s__lt' % opts.left_attr: getattr(self, opts.left_attr),
'%s__gt' % opts.right_attr: getattr(self, opts.right_attr),
opts.tree_id_attr: getattr(self, opts.tree_id_attr),
}).order_by('%s%s' % ({True: '-', False: ''}[ascending], opts.left_attr))
def get_children(self):
"""
Creates a ``QuerySet`` containing the immediate children of this
model instance, in tree order.
The benefit of using this method over the reverse relation
provided by the ORM to the instance's children is that a
database query can be avoided in the case where the instance is
a leaf node (it has no children).
"""
if self.is_leaf_node():
return self._tree_manager.none()
return self._tree_manager.filter(**{
self._meta.parent_attr: self,
})
def get_descendants(self, include_self=False):
"""
Creates a ``QuerySet`` containing descendants of this model
instance, in tree order.
If ``include_self`` is ``True``, the ``QuerySet`` will also
include this model instance.
"""
if not include_self and self.is_leaf_node():
return self._tree_manager.none()
opts = self._meta
filters = {opts.tree_id_attr: getattr(self, opts.tree_id_attr)}
if include_self:
filters['%s__range' % opts.left_attr] = (getattr(self, opts.left_attr),
getattr(self, opts.right_attr))
else:
filters['%s__gt' % opts.left_attr] = getattr(self, opts.left_attr)
filters['%s__lt' % opts.left_attr] = getattr(self, opts.right_attr)
return self._tree_manager.filter(**filters)
def get_descendant_count(self):
"""
Returns the number of descendants this model instance has.
"""
return (getattr(self, self._meta.right_attr) -
getattr(self, self._meta.left_attr) - 1) / 2
def get_next_sibling(self):
"""
Returns this model instance's next sibling in the tree, or
``None`` if it doesn't have a next sibling.
"""
opts = self._meta
if self.is_root_node():
filters = {
'%s__isnull' % opts.parent_attr: True,
'%s__gt' % opts.tree_id_attr: getattr(self, opts.tree_id_attr),
}
else:
filters = {
opts.parent_attr: getattr(self, '%s_id' % opts.parent_attr),
'%s__gt' % opts.left_attr: getattr(self, opts.right_attr),
}
sibling = None
try:
sibling = self._tree_manager.filter(**filters)[0]
except IndexError:
pass
return sibling
def get_previous_sibling(self):
"""
Returns this model instance's previous sibling in the tree, or
``None`` if it doesn't have a previous sibling.
"""
opts = self._meta
if self.is_root_node():
filters = {
'%s__isnull' % opts.parent_attr: True,
'%s__lt' % opts.tree_id_attr: getattr(self, opts.tree_id_attr),
}
order_by = '-%s' % opts.tree_id_attr
else:
filters = {
opts.parent_attr: getattr(self, '%s_id' % opts.parent_attr),
'%s__lt' % opts.right_attr: getattr(self, opts.left_attr),
}
order_by = '-%s' % opts.right_attr
sibling = None
try:
sibling = self._tree_manager.filter(**filters).order_by(order_by)[0]
except IndexError:
pass
return sibling
def get_root(self):
"""
Returns the root node of this model instance's tree.
"""
if self.is_root_node():
return self
opts = self._meta
return self._default_manager.get(**{
opts.tree_id_attr: getattr(self, opts.tree_id_attr),
'%s__isnull' % opts.parent_attr: True,
})
def get_siblings(self, include_self=False):
"""
Creates a ``QuerySet`` containing siblings of this model
instance. Root nodes are considered to be siblings of other root
nodes.
If ``include_self`` is ``True``, the ``QuerySet`` will also
include this model instance.
"""
opts = self._meta
if self.is_root_node():
filters = {'%s__isnull' % opts.parent_attr: True}
else:
filters = {opts.parent_attr: getattr(self, '%s_id' % opts.parent_attr)}
queryset = self._tree_manager.filter(**filters)
if not include_self:
queryset = queryset.exclude(pk=self.pk)
return queryset
def insert_at(self, target, position='first-child', commit=False):
"""
Convenience method for calling ``TreeManager.insert_node`` with this
model instance.
"""
self._tree_manager.insert_node(self, target, position, commit)
def is_child_node(self):
"""
Returns ``True`` if this model instance is a child node, ``False``
otherwise.
"""
return not self.is_root_node()
def is_leaf_node(self):
"""
Returns ``True`` if this model instance is a leaf node (it has no
children), ``False`` otherwise.
"""
return not self.get_descendant_count()
def is_root_node(self):
"""
Returns ``True`` if this model instance is a root node,
``False`` otherwise.
"""
return getattr(self, '%s_id' % self._meta.parent_attr) is None
def move_to(self, target, position='first-child'):
"""
Convenience method for calling ``TreeManager.move_node`` with this
model instance.
"""
self._tree_manager.move_node(self, target, position)
|
