X-Git-Url: http://git.ithinksw.org/philo.git/blobdiff_plain/bce7b7c4d0308a1d9a2e450b83ba1dac99e57d5b..e095f691f243784f8c8d0a9773270b9dbead18e9:/models/base.py diff --git a/models/base.py b/models/base.py index dabe491..c7b1c26 100644 --- a/models/base.py +++ b/models/base.py @@ -10,6 +10,7 @@ from philo.utils import ContentTypeRegistryLimiter, ContentTypeSubclassLimiter from philo.signals import entity_class_prepared from philo.validators import json_validator from UserDict import DictMixin +from mptt.models import MPTTModel, MPTTModelBase, MPTTOptions class Tag(models.Model): @@ -279,18 +280,28 @@ class Entity(models.Model): class TreeManager(models.Manager): use_for_related_fields = True - def roots(self): - return self.filter(parent__isnull=True) - 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. segments = path.split(pathsep) + # Check for a trailing pathsep so we can restore it later. + trailing_pathsep = False + if segments[-1] == '': + trailing_pathsep = True + # Clean out blank segments. Handles multiple consecutive pathseps. while True: try: @@ -301,11 +312,13 @@ class TreeManager(models.Manager): # Special-case a lack of segments. No queries necessary. if not segments: if root is not None: + if absolute_result: + return root return root, None else: raise self.model.DoesNotExist('%s matching query does not exist.' % self.model._meta.object_name) - def make_query_kwargs(segments): + def make_query_kwargs(segments, root): kwargs = {} prefix = "" revsegs = list(segments) @@ -315,66 +328,94 @@ class TreeManager(models.Manager): kwargs["%s%s__exact" % (prefix, field)] = segment prefix += "parent__" - kwargs[prefix[:-2]] = root + if prefix: + kwargs[prefix[:-2]] = root + return kwargs - def find_obj(segments, depth, deepest_found): + def build_path(segments): + path = pathsep.join(segments) + if trailing_pathsep and segments and segments[-1] != '': + path += pathsep + return path + + 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() try: - obj = self.get(**make_query_kwargs(segments[:depth])) + obj = self.get(**make_query_kwargs(segments[deepest_level:depth], deepest_found or root)) except self.model.DoesNotExist: - if absolute_result: - raise + if not deepest_level and depth > 1: + # make sure there's a root node... + depth = 1 + else: + # Try finding one with half the path since the deepest find. + depth = (deepest_level + depth)/2 - depth = (deepest_found + depth)/2 - if deepest_found == depth: + if deepest_level == depth: # This should happen if nothing is found with any part of the given path. + if root is not None and deepest_found is None: + return root, build_path(segments) raise - # Try finding one with half the path since the deepest find. return find_obj(segments, depth, deepest_found) else: - # 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 - deepest_found = depth - depth = (len(segments) + depth)/2 + depth += (len(segments) - depth)/2 or len(segments) - depth - if deepest_found == depth: - return obj, pathsep.join(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 try: - return find_obj(segments, depth, deepest_found) + return find_obj(segments, depth, obj) except self.model.DoesNotExist: - # Then the deepest one was already found. - return obj, pathsep.join(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)) -class TreeModel(models.Model): +class TreeModel(MPTTModel): objects = TreeManager() parent = models.ForeignKey('self', related_name='children', null=True, blank=True) slug = models.SlugField(max_length=255) - def has_ancestor(self, ancestor): - parent = self - while parent: - if parent == ancestor: - return True - parent = parent.parent - return False - def get_path(self, root=None, pathsep='/', field='slug'): - if root is not None and not self.has_ancestor(root): + if root == self: + return '' + + if root is not None and not self.is_descendant_of(root): raise AncestorDoesNotExist(root) - path = getattr(self, field, '?') - parent = self.parent - while parent and parent != root: - path = getattr(parent, field, '?') + pathsep + path - parent = parent.parent - return path + qs = self.get_ancestors() + + if root is not None: + qs = qs.filter(**{'%s__gt' % self._mptt_meta.level_attr: root.get_level()}) + + return pathsep.join([getattr(parent, field, '?') for parent in list(qs) + [self]]) path = property(get_path) def __unicode__(self): @@ -385,7 +426,17 @@ class TreeModel(models.Model): abstract = True +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) + + class TreeEntity(Entity, TreeModel): + __metaclass__ = TreeEntityBase + @property def attributes(self): if self.parent: