from django.db import models
from django.contrib.contenttypes.models import ContentType
from django.contrib.contenttypes import generic
from django.db import models
from django.contrib.contenttypes.models import ContentType
from django.contrib.contenttypes import generic
from philo.exceptions import AncestorDoesNotExist
from philo.models.fields import JSONField
from philo.utils import ContentTypeRegistryLimiter, ContentTypeSubclassLimiter
from philo.signals import entity_class_prepared
from philo.validators import json_validator
from UserDict import DictMixin
from philo.exceptions import AncestorDoesNotExist
from philo.models.fields import JSONField
from philo.utils import ContentTypeRegistryLimiter, ContentTypeSubclassLimiter
from philo.signals import entity_class_prepared
from philo.validators import json_validator
from UserDict import DictMixin
def value_formfield(self, **kwargs):
kwargs['initial'] = self.value_json
def value_formfield(self, **kwargs):
kwargs['initial'] = self.value_json
value_object_id = models.PositiveIntegerField(verbose_name='Value ID', null=True, blank=True)
value = generic.GenericForeignKey('value_content_type', 'value_object_id')
value_object_id = models.PositiveIntegerField(verbose_name='Value ID', null=True, blank=True)
value = generic.GenericForeignKey('value_content_type', 'value_object_id')
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 get_path(self, root=None, pathsep='/', field='slug'):
def get_path(self, root=None, pathsep='/', field='slug'):
- 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]])
+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