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'])