from django.db import models, connection
import operator

qn = connection.ops.quote_name

class Node(models.Model):
    parent    = models.ForeignKey('self', related_name="children", blank=True, null=True)
    position  = models.IntegerField(default=0)
    lft       = models.PositiveIntegerField(editable=False,default=1)
    rgt       = models.PositiveIntegerField(editable=False,default=1)

        
    def rebuild_tree(self, left):
        right = left+1
        for c in Node.objects.filter(parent=self).order_by('position'):
            right = c.rebuild_tree(right)
        self.lft = left
        self.rgt = right
        super(Node, self).save()
        return right+1

    def ancestors(self):
        query = """
        SELECT id FROM %s
        WHERE lft <= %s AND rgt >= %s
        ORDER BY lft;
        """ % (qn(self._meta.db_table), self.lft, self.rgt)
         
        cursor = connection.cursor()
        cursor.execute(query)
        results = cursor.fetchall()
        return map(operator.itemgetter(0), results)

    def save(self):
        super(Node, self).save()
        
        root = Node.objects.filter(parent__isnull=True)[0]
        root.rebuild_tree(1)