/usr/lib/python2.7/dist-packages/treebeard/al_tree.py is in python-django-treebeard 2.0~beta1-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 | """Adjacency List"""
from django.core import serializers
from django.db import connection, models, transaction
from django.utils.translation import ugettext_noop as _
from treebeard.exceptions import InvalidMoveToDescendant
from treebeard.models import Node
class AL_NodeManager(models.Manager):
"""Custom manager for nodes."""
def get_query_set(self):
"""Sets the custom queryset as the default."""
if self.model.node_order_by:
order_by = ['parent'] + list(self.model.node_order_by)
else:
order_by = ['parent', 'sib_order']
return super(AL_NodeManager, self).get_query_set().order_by(*order_by)
class AL_Node(Node):
"""Abstract model to create your own Adjacency List Trees."""
objects = AL_NodeManager()
node_order_by = None
@classmethod
def add_root(cls, **kwargs):
"""Adds a root node to the tree."""
newobj = cls(**kwargs)
newobj._cached_depth = 1
if not cls.node_order_by:
try:
max = cls.objects.filter(parent__isnull=True).order_by(
'sib_order').reverse()[0].sib_order
except IndexError:
max = 0
newobj.sib_order = max + 1
newobj.save()
transaction.commit_unless_managed()
return newobj
@classmethod
def get_root_nodes(cls):
""":returns: A queryset containing the root nodes in the tree."""
return cls.objects.filter(parent__isnull=True)
def get_depth(self, update=False):
"""
:returns: the depth (level) of the node
Caches the result in the object itself to help in loops.
:param update: Updates the cached value.
"""
if self.parent_id is None:
return 1
try:
if update:
del self._cached_depth
else:
return self._cached_depth
except AttributeError:
pass
depth = 0
node = self
while node:
node = node.parent
depth += 1
self._cached_depth = depth
return depth
def get_children(self):
""":returns: A queryset of all the node's children"""
return self.__class__.objects.filter(parent=self)
def get_parent(self, update=False):
""":returns: the parent node of the current node object."""
return self.parent
def get_ancestors(self):
"""
:returns: A *list* containing the current node object's ancestors,
starting by the root node and descending to the parent.
"""
ancestors = []
node = self.parent
while node:
ancestors.insert(0, node)
node = node.parent
return ancestors
def get_root(self):
""":returns: the root node for the current node object."""
ancestors = self.get_ancestors()
if ancestors:
return ancestors[0]
return self
def is_descendant_of(self, node):
"""
:returns: ``True`` if the node if a descendant of another node given
as an argument, else, returns ``False``
"""
return self.pk in [obj.pk for obj in node.get_descendants()]
@classmethod
def dump_bulk(cls, parent=None, keep_ids=True):
"""Dumps a tree branch to a python data structure."""
serializable_cls = cls._get_serializable_model()
if (
parent and serializable_cls != cls and
parent.__class__ != serializable_cls
):
parent = serializable_cls.objects.get(pk=parent.pk)
# a list of nodes: not really a queryset, but it works
objs = serializable_cls.get_tree(parent)
ret, lnk = [], {}
for node, pyobj in zip(objs, serializers.serialize('python', objs)):
depth = node.get_depth()
# django's serializer stores the attributes in 'fields'
fields = pyobj['fields']
del fields['parent']
# non-sorted trees have this
if 'sib_order' in fields:
del fields['sib_order']
if 'id' in fields:
del fields['id']
newobj = {'data': fields}
if keep_ids:
newobj['id'] = pyobj['pk']
if (not parent and depth == 1) or\
(parent and depth == parent.get_depth()):
ret.append(newobj)
else:
parentobj = lnk[node.parent_id]
if 'children' not in parentobj:
parentobj['children'] = []
parentobj['children'].append(newobj)
lnk[node.pk] = newobj
return ret
def add_child(self, **kwargs):
"""Adds a child to the node."""
newobj = self.__class__(**kwargs)
try:
newobj._cached_depth = self._cached_depth + 1
except AttributeError:
pass
if not self.__class__.node_order_by:
try:
max = self.__class__.objects.filter(parent=self).reverse(
)[0].sib_order
except IndexError:
max = 0
newobj.sib_order = max + 1
newobj.parent = self
newobj.save()
transaction.commit_unless_managed()
return newobj
@classmethod
def _get_tree_recursively(cls, results, parent, depth):
if parent:
nodes = parent.get_children()
else:
nodes = cls.get_root_nodes()
for node in nodes:
node._cached_depth = depth
results.append(node)
cls._get_tree_recursively(results, node, depth + 1)
@classmethod
def get_tree(cls, parent=None):
"""
:returns: A list of nodes ordered as DFS, including the parent. If
no parent is given, the entire tree is returned.
"""
if parent:
depth = parent.get_depth() + 1
results = [parent]
else:
depth = 1
results = []
cls._get_tree_recursively(results, parent, depth)
return results
def get_descendants(self):
"""
:returns: A *list* of all the node's descendants, doesn't
include the node itself
"""
return self.__class__.get_tree(parent=self)[1:]
def get_descendant_count(self):
""":returns: the number of descendants of a nodee"""
return len(self.get_descendants())
def get_siblings(self):
"""
:returns: A queryset of all the node's siblings, including the node
itself.
"""
if self.parent:
return self.__class__.objects.filter(parent=self.parent)
return self.__class__.get_root_nodes()
def add_sibling(self, pos=None, **kwargs):
"""Adds a new node as a sibling to the current node object."""
pos = self._prepare_pos_var_for_add_sibling(pos)
newobj = self.__class__(**kwargs)
if not self.node_order_by:
newobj.sib_order = self.__class__._get_new_sibling_order(pos,
self)
newobj.parent_id = self.parent_id
newobj.save()
transaction.commit_unless_managed()
return newobj
@classmethod
def _is_target_pos_the_last_sibling(cls, pos, target):
return pos == 'last-sibling' or (
pos == 'right' and target == target.get_last_sibling())
@classmethod
def _make_hole_in_db(cls, min, target_node):
qset = cls.objects.filter(sib_order__gte=min)
if target_node.is_root():
qset = qset.filter(parent__isnull=True)
else:
qset = qset.filter(parent=target_node.parent)
qset.update(sib_order=models.F('sib_order') + 1)
@classmethod
def _make_hole_and_get_sibling_order(cls, pos, target_node):
siblings = target_node.get_siblings()
siblings = {
'left': siblings.filter(sib_order__gte=target_node.sib_order),
'right': siblings.filter(sib_order__gt=target_node.sib_order),
'first-sibling': siblings
}[pos]
sib_order = {
'left': target_node.sib_order,
'right': target_node.sib_order + 1,
'first-sibling': 1
}[pos]
try:
min = siblings.order_by('sib_order')[0].sib_order
except IndexError:
min = 0
if min:
cls._make_hole_in_db(min, target_node)
return sib_order
@classmethod
def _get_new_sibling_order(cls, pos, target_node):
if cls._is_target_pos_the_last_sibling(pos, target_node):
sib_order = target_node.get_last_sibling().sib_order + 1
else:
sib_order = cls._make_hole_and_get_sibling_order(pos, target_node)
return sib_order
def move(self, target, pos=None):
"""
Moves the current node and all it's descendants to a new position
relative to another node.
"""
pos = self._prepare_pos_var_for_move(pos)
sib_order = None
parent = None
if pos in ('first-child', 'last-child', 'sorted-child'):
# moving to a child
if not target.is_leaf():
target = target.get_last_child()
pos = {'first-child': 'first-sibling',
'last-child': 'last-sibling',
'sorted-child': 'sorted-sibling'}[pos]
else:
parent = target
if pos == 'sorted-child':
pos = 'sorted-sibling'
else:
pos = 'first-sibling'
sib_order = 1
if target.is_descendant_of(self):
raise InvalidMoveToDescendant(
_("Can't move node to a descendant."))
if self == target and (
(pos == 'left') or
(pos in ('right', 'last-sibling') and
target == target.get_last_sibling()) or
(pos == 'first-sibling' and
target == target.get_first_sibling())):
# special cases, not actually moving the node so no need to UPDATE
return
if pos == 'sorted-sibling':
if parent:
self.parent = parent
else:
self.parent = target.parent
else:
if sib_order:
self.sib_order = sib_order
else:
self.sib_order = self.__class__._get_new_sibling_order(pos,
target)
if parent:
self.parent = parent
else:
self.parent = target.parent
self.save()
transaction.commit_unless_managed()
class Meta:
"""Abstract model."""
abstract = True
|