- Author:
- lars.yencken
- Posted:
- May 9, 2008
- Language:
- Python
- Version:
- .96
- Score:
- 0 (after 0 ratings)
The nested set abstraction is a very nice way to store hierarchical data, for example places, in a database. It provides an easy way to say that Melbourne is within Victoria, which is within Australia, etc.</p>
The calls to addChild() are expensive, so this model is slow to build, and bad if you do frequent updates. If you're building a read-only model though, it's much faster than ForeignKey('self') for determining ancestor/descendent relationships.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | class HierarchicalModel(models.Model):
"A generic hierarchical database model."
left_visit = models.IntegerField(primary_key=True)
right_visit = models.IntegerField(db_index=True)
class Meta:
abstract = True
@classmethod
def getRoot(cls):
"Get the unique root node for this table."
return cls.objects.get(left_visit=1)
@classmethod
def initRoot(cls, **kwargs):
"Set the unique root object. Call only once."
kwargs['left_visit'] = 1
kwargs['right_visit'] = 2
rootObj = cls(**kwargs)
rootObj.save()
return rootObj
def getAncestors(self):
"Returns all ancesters of this node."
return self.objects.filter(
left_visit__lte=self.left_visit,
right_visit__gte=self.right_visit,
).order_by('left_visit')
def getSubtree(self):
"Returns the subtree under (and including) this node."
return self.objects.filter(
left_visit__gte=self.left_visit,
right_visit__lte=self.right_visit,
).order_by('left_visit')
def addChild(self, **kwargs):
"Adds a child node under this node."
cls = self.__class__
nodeCount = cls.getRoot().right_visit
parent_left_visit = self.left_visit
parent_right_visit = self.right_visit
cursor = connection.cursor()
cursor.execute("""
UPDATE %s SET right_visit = right_visit + 2
WHERE right_visit >= %s
""", (cls._meta.db_table, parent_right_visit))
cursor.execute("""
UPDATE %s SET left_visit = left_visit + 2
WHERE left_visit > %s
""", (cls._meta.db_table, parent_right_visit))
kwargs['left_visit'] = parent_right_visit
kwargs['right_visit'] = parent_right_visit + 1
newNode = cls(**kwargs)
newNode.save()
self.right_visit += 2
return newNode
def __cmp__(self, rhs):
return cmp(self.left_visit, self.right_visit)
def leaves(self):
"Returns all leaf nodes under this node."
return self.getSubtree().extra(where=['left_visit + 1 = right_visit'])
|
More like this
- Template tag - list punctuation for a list of items by shapiromatron 10 months, 3 weeks ago
- JSONRequestMiddleware adds a .json() method to your HttpRequests by cdcarter 11 months ago
- Serializer factory with Django Rest Framework by julio 1 year, 5 months ago
- Image compression before saving the new model / work with JPG, PNG by Schleidens 1 year, 6 months ago
- Help text hyperlinks by sa2812 1 year, 7 months ago
Comments
Ah, ok, it looks like they've done a very thorough job. I just pulled this out of my code after I'd cleaned it up to use model inheritance. Perhaps it's still useful as a very small subset of what django-mptt does. Thanks for the link.
#
Please login first before commenting.