From: Stephen Burrows Date: Fri, 12 Nov 2010 19:10:01 +0000 (-0500) Subject: Initial mptt commit. Implements a much more efficient get_with_path method for TreeMa... X-Git-Tag: philo-0.9~25^2~1^2~4 X-Git-Url: http://git.ithinksw.org/philo.git/commitdiff_plain/beb034eda30e8af8a169c4d43c5aba83812337e4?ds=inline;hp=d6479a69e07aa3b6756228159d80693aa619b6f8 Initial mptt commit. Implements a much more efficient get_with_path method for TreeManager, optimized with mptt features. Also increases efficiency of TreeModel.get_path(). mptt admin features to come. --- diff --git a/migrations/0009_auto__add_field_node_lft__add_field_node_rght__add_field_node_tree_id_.py b/migrations/0009_auto__add_field_node_lft__add_field_node_rght__add_field_node_tree_id_.py new file mode 100644 index 0000000..a6f58fd --- /dev/null +++ b/migrations/0009_auto__add_field_node_lft__add_field_node_rght__add_field_node_tree_id_.py @@ -0,0 +1,178 @@ +# encoding: utf-8 +import datetime +from south.db import db +from south.v2 import SchemaMigration +from django.db import models + +class Migration(SchemaMigration): + + def forwards(self, orm): + + # Adding field 'Node.lft' + db.add_column('philo_node', 'lft', self.gf('django.db.models.fields.PositiveIntegerField')(default=0, db_index=True), keep_default=False) + + # Adding field 'Node.rght' + db.add_column('philo_node', 'rght', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False) + + # Adding field 'Node.tree_id' + db.add_column('philo_node', 'tree_id', self.gf('django.db.models.fields.PositiveIntegerField')(default=0, db_index=True), keep_default=False) + + # Adding field 'Node.level' + db.add_column('philo_node', 'level', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False) + + # Adding field 'Template.lft' + db.add_column('philo_template', 'lft', self.gf('django.db.models.fields.PositiveIntegerField')(default=0, db_index=True), keep_default=False) + + # Adding field 'Template.rght' + db.add_column('philo_template', 'rght', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False) + + # Adding field 'Template.tree_id' + db.add_column('philo_template', 'tree_id', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False) + + # Adding field 'Template.level' + db.add_column('philo_template', 'level', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False) + + + def backwards(self, orm): + + # Deleting field 'Node.lft' + db.delete_column('philo_node', 'lft') + + # Deleting field 'Node.rght' + db.delete_column('philo_node', 'rght') + + # Deleting field 'Node.tree_id' + db.delete_column('philo_node', 'tree_id') + + # Deleting field 'Node.level' + db.delete_column('philo_node', 'level') + + # Deleting field 'Template.lft' + db.delete_column('philo_template', 'lft') + + # Deleting field 'Template.rght' + db.delete_column('philo_template', 'rght') + + # Deleting field 'Template.tree_id' + db.delete_column('philo_template', 'tree_id') + + # Deleting field 'Template.level' + db.delete_column('philo_template', 'level') + + + models = { + 'contenttypes.contenttype': { + 'Meta': {'unique_together': "(('app_label', 'model'),)", 'object_name': 'ContentType', 'db_table': "'django_content_type'"}, + 'app_label': ('django.db.models.fields.CharField', [], {'max_length': '100'}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'model': ('django.db.models.fields.CharField', [], {'max_length': '100'}), + 'name': ('django.db.models.fields.CharField', [], {'max_length': '100'}) + }, + 'philo.attribute': { + 'Meta': {'unique_together': "(('key', 'entity_content_type', 'entity_object_id'), ('value_content_type', 'value_object_id'))", 'object_name': 'Attribute'}, + 'entity_content_type': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'attribute_entity_set'", 'to': "orm['contenttypes.ContentType']"}), + 'entity_object_id': ('django.db.models.fields.PositiveIntegerField', [], {}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'key': ('django.db.models.fields.CharField', [], {'max_length': '255'}), + 'value_content_type': ('django.db.models.fields.related.ForeignKey', [], {'blank': 'True', 'related_name': "'attribute_value_set'", 'null': 'True', 'to': "orm['contenttypes.ContentType']"}), + 'value_object_id': ('django.db.models.fields.PositiveIntegerField', [], {'null': 'True', 'blank': 'True'}) + }, + 'philo.collection': { + 'Meta': {'object_name': 'Collection'}, + 'description': ('django.db.models.fields.TextField', [], {'null': 'True', 'blank': 'True'}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'name': ('django.db.models.fields.CharField', [], {'max_length': '255'}) + }, + 'philo.collectionmember': { + 'Meta': {'object_name': 'CollectionMember'}, + 'collection': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'members'", 'to': "orm['philo.Collection']"}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'index': ('django.db.models.fields.PositiveIntegerField', [], {'null': 'True', 'blank': 'True'}), + 'member_content_type': ('django.db.models.fields.related.ForeignKey', [], {'to': "orm['contenttypes.ContentType']"}), + 'member_object_id': ('django.db.models.fields.PositiveIntegerField', [], {}) + }, + 'philo.contentlet': { + 'Meta': {'object_name': 'Contentlet'}, + 'content': ('philo.models.fields.TemplateField', [], {}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'name': ('django.db.models.fields.CharField', [], {'max_length': '255'}), + 'page': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'contentlets'", 'to': "orm['philo.Page']"}) + }, + 'philo.contentreference': { + 'Meta': {'object_name': 'ContentReference'}, + 'content_id': ('django.db.models.fields.PositiveIntegerField', [], {'null': 'True', 'blank': 'True'}), + 'content_type': ('django.db.models.fields.related.ForeignKey', [], {'to': "orm['contenttypes.ContentType']"}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'name': ('django.db.models.fields.CharField', [], {'max_length': '255'}), + 'page': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'contentreferences'", 'to': "orm['philo.Page']"}) + }, + 'philo.file': { + 'Meta': {'object_name': 'File'}, + 'file': ('django.db.models.fields.files.FileField', [], {'max_length': '100'}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'mimetype': ('django.db.models.fields.CharField', [], {'max_length': '255'}) + }, + 'philo.foreignkeyvalue': { + 'Meta': {'object_name': 'ForeignKeyValue'}, + 'content_type': ('django.db.models.fields.related.ForeignKey', [], {'to': "orm['contenttypes.ContentType']", 'null': 'True', 'blank': 'True'}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'object_id': ('django.db.models.fields.PositiveIntegerField', [], {'null': 'True', 'blank': 'True'}) + }, + 'philo.jsonvalue': { + 'Meta': {'object_name': 'JSONValue'}, + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'value': ('philo.models.fields.JSONField', [], {}) + }, + 'philo.manytomanyvalue': { + 'Meta': {'object_name': 'ManyToManyValue'}, + 'content_type': ('django.db.models.fields.related.ForeignKey', [], {'to': "orm['contenttypes.ContentType']", 'null': 'True', 'blank': 'True'}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'values': ('django.db.models.fields.related.ManyToManyField', [], {'symmetrical': 'False', 'to': "orm['philo.ForeignKeyValue']", 'null': 'True', 'blank': 'True'}) + }, + 'philo.node': { + 'Meta': {'object_name': 'Node'}, + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'level': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}), + 'lft': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}), + 'parent': ('django.db.models.fields.related.ForeignKey', [], {'blank': 'True', 'related_name': "'children'", 'null': 'True', 'to': "orm['philo.Node']"}), + 'rght': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}), + 'slug': ('django.db.models.fields.SlugField', [], {'max_length': '255', 'db_index': 'True'}), + 'tree_id': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}), + 'view_content_type': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'node_view_set'", 'to': "orm['contenttypes.ContentType']"}), + 'view_object_id': ('django.db.models.fields.PositiveIntegerField', [], {}) + }, + 'philo.page': { + 'Meta': {'object_name': 'Page'}, + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'template': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'pages'", 'to': "orm['philo.Template']"}), + 'title': ('django.db.models.fields.CharField', [], {'max_length': '255'}) + }, + 'philo.redirect': { + 'Meta': {'object_name': 'Redirect'}, + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'status_code': ('django.db.models.fields.IntegerField', [], {'default': '302'}), + 'target': ('django.db.models.fields.CharField', [], {'max_length': '200'}) + }, + 'philo.tag': { + 'Meta': {'object_name': 'Tag'}, + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'name': ('django.db.models.fields.CharField', [], {'max_length': '255'}), + 'slug': ('django.db.models.fields.SlugField', [], {'unique': 'True', 'max_length': '255', 'db_index': 'True'}) + }, + 'philo.template': { + 'Meta': {'object_name': 'Template'}, + 'code': ('philo.models.fields.TemplateField', [], {}), + 'documentation': ('django.db.models.fields.TextField', [], {'null': 'True', 'blank': 'True'}), + 'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}), + 'level': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}), + 'lft': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}), + 'mimetype': ('django.db.models.fields.CharField', [], {'default': "'text/html'", 'max_length': '255'}), + 'name': ('django.db.models.fields.CharField', [], {'max_length': '255'}), + 'parent': ('django.db.models.fields.related.ForeignKey', [], {'blank': 'True', 'related_name': "'children'", 'null': 'True', 'to': "orm['philo.Template']"}), + 'rght': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}), + 'slug': ('django.db.models.fields.SlugField', [], {'max_length': '255', 'db_index': 'True'}), + 'tree_id': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}) + } + } + + complete_apps = ['philo'] diff --git a/models/base.py b/models/base.py index 03b9b54..c2c12ad 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,36 +280,17 @@ class Entity(models.Model): class TreeManager(models.Manager): use_for_related_fields = True - def roots(self): - return self.filter(parent__isnull=True) - - def get_branch_pks(self, root, depth=5, inclusive=True): - branch_pks = [] - parent_pks = [root.pk] - - if inclusive: - branch_pks.append(root.pk) - - for i in xrange(depth): - child_pks = list(self.filter(parent__pk__in=parent_pks).exclude(pk__in=branch_pks).values_list('pk', flat=True)) - if not child_pks: - break - - branch_pks += child_pks - parent_pks = child_pks - - return branch_pks - - def get_branch(self, root, depth=5, inclusive=True): - return self.filter(pk__in=self.get_branch_pks(root, depth, inclusive)) - 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. + Given a -separated path, fetch the matching model of this type. 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. @@ -326,11 +308,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) @@ -340,7 +324,12 @@ class TreeManager(models.Manager): kwargs["%s%s__exact" % (prefix, field)] = segment prefix += "parent__" - kwargs[prefix[:-2]] = root + if not prefix and root is not None: + prefix = "parent__" + + if prefix: + kwargs[prefix[:-2]] = root + return kwargs def build_path(segments): @@ -350,85 +339,67 @@ class TreeManager(models.Manager): return path def find_obj(segments, depth, deepest_found): + if deepest_found is None: + deepest_level = 0 + else: + deepest_level = deepest_found.get_level() + 1 try: - obj = self.get(**make_query_kwargs(segments[:depth])) + obj = self.get(**make_query_kwargs(segments[deepest_level:depth], deepest_found)) 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. 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! + deepest_level = obj.get_level() + 1 - deepest_found = depth - depth = (len(segments) + depth)/2 + # 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 + depth += (len(segments) - depth)/2 or len(segments) - depth + + 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, build_path(segments[deepest_found:]) + # Then this was the deepest. + return obj, build_path(segments[deepest_level:]) - return find_obj(segments, len(segments), 0) + if absolute_result: + return self.get(**make_query_kwargs(segments, root)) + + # 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), root) -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, 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'): - parent = self.parent - parents = [self] - - def compile_path(parents): - return pathsep.join([getattr(parent, field, '?') for parent in parents]) - - 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 - - if root is not None and parent is None: + if root is not None and not self.is_descendant_of(root): raise AncestorDoesNotExist(root) - return compile_path(parents[::-1]) + return pathsep.join([getattr(parent, field, '?') for parent in list(self.get_ancestors()) + [self]]) path = property(get_path) def __unicode__(self): @@ -439,7 +410,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: