from philo.signals import entity_class_prepared
from philo.validators import json_validator
from UserDict import DictMixin
from philo.signals import entity_class_prepared
from philo.validators import json_validator
from UserDict import DictMixin
def get_with_path(self, path, root=None, absolute_result=True, pathsep='/', field='slug'):
"""
Returns the object with the path, unless absolute_result is set to False, in which
case it returns a tuple containing the deepest object found along the path, and the
remainder of the path after that object as a string (or None if there is no remaining
path). Raises a DoesNotExist exception if no object is found with the given path.
def get_with_path(self, path, root=None, absolute_result=True, pathsep='/', field='slug'):
"""
Returns the object with the path, unless absolute_result is set to False, in which
case it returns a tuple containing the deepest object found along the path, and the
remainder of the path after that object as a string (or None if there is no remaining
path). Raises a DoesNotExist exception if no object is found with the given path.
+
+ If the path you're searching for is known to exist, it is always faster to use
+ absolute_result=True - unless the path depth is over ~40, in which case the high cost
+ of the absolute query makes a binary search (i.e. non-absolute) faster.
+ # Note: SQLite allows max of 64 tables in one join. That means the binary search will
+ # only work on paths with a max depth of 127 and the absolute fetch will only work
+ # to a max depth of (surprise!) 63. Although this could be handled, chances are your
+ # tree structure won't be that deep.
- def find_obj(segments, depth, deepest_found):
+ def find_obj(segments, depth, deepest_found=None):
+ if deepest_found is None:
+ deepest_level = 0
+ elif root is None:
+ deepest_level = deepest_found.get_level() + 1
+ else:
+ deepest_level = deepest_found.get_level() - root.get_level()
- # Yay! Found one! Could there be a deeper one?
- if absolute_result:
- return obj
+ # Yay! Found one!
+ if root is None:
+ deepest_level = obj.get_level() + 1
+ else:
+ deepest_level = obj.get_level() - root.get_level()
+
+ # Could there be a deeper one?
+ if obj.is_leaf_node():
+ return obj, build_path(segments[deepest_level:]) or None
- if deepest_found == depth:
- return obj, build_path(segments[deepest_found:]) or None
+ if depth > deepest_level + obj.get_descendant_count():
+ depth = deepest_level + obj.get_descendant_count()
+
+ if deepest_level == depth:
+ return obj, build_path(segments[deepest_level:]) or None
- # Then the deepest one was already found.
- return obj, build_path(segments[deepest_found:])
+ # Then this was the deepest.
+ return obj, build_path(segments[deepest_level:])
+
+ if absolute_result:
+ return self.get(**make_query_kwargs(segments, root))
- return find_obj(segments, len(segments), 0)
+ # Try a modified binary search algorithm. Feed the root in so that query complexity
+ # can be reduced. It might be possible to weight the search towards the beginning
+ # of the path, since short paths are more likely, but how far forward? It would
+ # need to shift depending on len(segments) - perhaps logarithmically?
+ return find_obj(segments, len(segments)/2 or len(segments))
objects = TreeManager()
parent = models.ForeignKey('self', related_name='children', null=True, blank=True)
slug = models.SlugField(max_length=255)
objects = TreeManager()
parent = models.ForeignKey('self', related_name='children', null=True, blank=True)
slug = models.SlugField(max_length=255)
- def has_ancestor(self, ancestor, inclusive=False):
- if inclusive:
- parent = self
- else:
- parent = self.parent
-
- parents = []
-
- while parent:
- if parent == ancestor:
- return True
- # If we've found this parent before, the path is recursive and ancestor wasn't on it.
- if parent in parents:
- return False
- parents.append(parent)
- parent = parent.parent
- # If ancestor is None, catch it here.
- if parent == ancestor:
- return True
- return False
-
def get_path(self, root=None, pathsep='/', field='slug'):
def get_path(self, root=None, pathsep='/', field='slug'):
- def compile_path(parents):
- return pathsep.join([getattr(parent, field, '?') for parent in parents])
+ if root is not None and not self.is_descendant_of(root):
+ raise AncestorDoesNotExist(root)
- while parent and parent != root:
- if parent in parents:
- if root is not None:
- raise AncestorDoesNotExist(root)
- parents.append(parent)
- return u"\u2026%s%s" % (pathsep, compile_path(parents[::-1]))
- parents.append(parent)
- parent = parent.parent
+ qs = self.get_ancestors()
+class TreeEntityBase(MPTTModelBase, EntityBase):
+ def __new__(meta, name, bases, attrs):
+ attrs['_mptt_meta'] = MPTTOptions(attrs.pop('MPTTMeta', None))
+ cls = EntityBase.__new__(meta, name, bases, attrs)
+
+ return meta.register(cls)
+
+
git.ithinksw.org / philo.git / blobdiff