--- /dev/null
+# 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']
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):
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 <pathsep>-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.
# 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)
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):
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):
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:
git.ithinksw.org / philo.git / commitdiff