Commits

Gustavo Picon committed c1e2ede

Added an adjacency list tree library, also more tests, methods, docstrings,
etc...

Comments (0)

Files changed (7)

 setup.py
 treebeard/__init__.py
 treebeard/models.py
+treebeard/al_tree.py
+treebeard/mp_tree.py
 treebeard/numconv.py
 treebeard/tests.py
 docs/conf.py
       .. automethod:: add_child
       .. automethod:: add_sibling
       .. automethod:: delete
+      .. automethod:: get_tree
       .. automethod:: get_depth
       .. automethod:: get_ancestors
       .. automethod:: get_children
       .. automethod:: is_child_of
       .. automethod:: is_descendant_of
       .. automethod:: is_sibling_of
+      .. automethod:: is_root
+      .. automethod:: is_leaf
       .. automethod:: move
       .. automethod:: save
 
       .. automethod:: add_sibling
       .. automethod:: move
 
+      .. automethod:: get_tree
+
       .. automethod:: find_problems
       .. automethod:: fix_tree
 
 
+:mod:`treebeard.al_tree` --- Adjacency List tree implementation for Django
+==========================================================================
+
+.. automodule:: treebeard.al_tree
+
+   .. autoclass:: AL_Node
+
+      .. automethod:: get_depth
+
+
 :mod:`tbbench` --- tree
 =======================
 

treebeard/__init__.py

 
 VERSION = (0, 9, 'svn')
 
-from treebeard.models import Node
+from treebeard.models import Node, InvalidPosition, InvalidMoveToDescendant, \
+    MissingNodeOrderBy, PathOverflow
 
 
-class InvalidPosition(Exception):
-    """
-    Raised when passing an invalid pos value
-    """
 
-class InvalidMoveToDescendant(Exception):
-    """
-    Raised when attemping to move a node to one of it's descendants.
-    """
-
-class MissingNodeOrderBy(Exception):
-    """
-    Raised when an operation needs a missing
-    :attr:`~treebeard.MP_Node.node_order_by` attribute
-    """
-
-class PathOverflow(Exception):
-    """
-    Raised when trying to add or move a node to a position where no more nodes
-    can be added (see :attr:`~treebeard.MP_Node.path` and
-    :attr:`~treebeard.MP_Node.alphabet` for more info)
-    """
-
-

treebeard/al_tree.py

+# -*- coding: utf-8 -*-
+"""
+
+    treebeard.al_tree
+    -----------------
+
+    Adjacency List Tree.
+
+
+    :copyright: 2008 by Gustavo Picon
+    :license: Apache License 2.0
+
+    This is a simple implementation of the traditional Adjacency List Model for
+    storing trees in relational databases.
+
+    In the adjacency list model, every node will have a
+    ":attr:`~AL_Node.parent`" key, that will be NULL for root nodes.
+
+    Since ``django-treebeard`` must return trees ordered in a predictable way,
+    the ordering for models without the :attr:`~AL_Node.node_order_by`
+    attribute will have an extra attribute that will store the relative
+    position of a node between it's siblings: :attr:`~AL_Node.sib_order`.
+
+    The adjacency list model has the advantage of fast writes at the cost of
+    slow reads. If you read more than you write, use
+    :class:`~treebeard.mp_tree.MP_Node` instead.
+
+"""
+
+from django.core import serializers
+from django.db import models, transaction, connection
+
+from treebeard.models import Node, InvalidMoveToDescendant
+
+
+
+class AL_NodeManager(models.Manager):
+    """ Custom manager for nodes.
+    """
+
+    def get_query_set(self):
+        """
+        Sets the custom queryset as the default.
+        """
+        qset = super(AL_NodeManager, self).get_query_set()
+        if self.model.node_order_by:
+            order_by = ['parent']+self.model.node_order_by
+        else:
+            order_by = ['parent', 'sib_order']
+        return qset.order_by(*order_by)
+
+
+class AL_Node(Node):
+    """
+    Abstract model to create your own Adjacency List Trees.
+
+
+    .. attribute:: node_order_by
+
+       Attribute: a list of model fields that will be used for node
+       ordering. When enabled, all tree operations will assume this ordering.
+
+       Example::
+
+          node_order_by = ['field1', 'field2', 'field3']
+
+
+    .. attribute:: parent
+
+       ``ForeignKey`` to itself. This attribute **MUST** be defined in the
+       subclass (sadly, this isn't inherited correctly from the ABC in
+       `Django 1.0`). Just copy&paste these lines to your model::
+
+                parent = models.ForeignKey('self',
+                                           related_name='children_set',
+                                           null=True,
+                                           db_index=True)
+
+    .. attribute:: sib_order
+
+       ``PositiveIntegerField`` used to store the relative position of a node
+       between it's siblings. This attribute is mandatory *ONLY* if you don't
+       set a :attr:`node_order_by` field. You can define it copy&pasting this
+       line in your model::
+
+               sib_order = models.PositiveIntegerField()
+
+    Examples::
+
+            class AL_TestNode(AL_Node):
+                parent = models.ForeignKey('self',
+                                           related_name='children_set',
+                                           null=True,
+                                           db_index=True)
+                sib_order = models.PositiveIntegerField()
+                desc = models.CharField(max_length=255)
+
+            class AL_TestNodeSorted(AL_Node):
+                parent = models.ForeignKey('self',
+                                           related_name='children_set',
+                                           null=True,
+                                           db_index=True)
+                node_order_by = ['val1', 'val2', 'desc']
+                val1 = models.IntegerField()
+                val2 = models.IntegerField()
+                desc = models.CharField(max_length=255)
+
+
+    Read the API reference of :class:`treebeard.Node` for info on methods
+    available in this class, or read the following section for methods with
+    particular arguments or exceptions.
+    """
+
+    #parent = models.ForeignKey('self',
+    #                           null=True)
+    objects = AL_NodeManager()
+    node_order_by = None
+
+    @classmethod
+    def add_root(cls, **kwargs):
+        """
+        Adds a root node to the tree.
+
+        See: :meth:`treebeard.Node.add_root`
+
+        :raise PathOverflow: when no more root objects can be added
+        """
+        newobj = cls(**kwargs)
+        newobj._cached_depth = 1
+
+        if not cls.node_order_by:
+            try:
+                max = cls.objects.filter(parent__isnull=True).order_by(
+                        'sib_order').reverse()[0].sib_order
+            except IndexError:
+                max = 0
+            newobj.sib_order = max + 1
+
+        # saving the instance before returning it
+        newobj.save()
+        transaction.commit_unless_managed()
+        return newobj
+
+
+    @classmethod
+    def get_root_nodes(cls):
+        """
+        :returns: A queryset containing the root nodes in the tree.
+
+        See: :meth:`treebeard.Node.get_root_nodes`
+        """
+        return cls.objects.filter(parent__isnull=True)
+
+
+    def get_depth(self, update=False):
+        """
+        :returns: the depth (level) of the node
+            Caches the result in the object itself to help in loops.
+
+        :param update: Updates de cached value.
+
+        See: :meth:`treebeard.Node.get_depth`
+        """
+
+        if self.parent_id is None:
+            return 1
+
+        try:
+            if update:
+                del self._cached_depth
+            else:
+                return self._cached_depth
+        except AttributeError:
+            pass
+
+        depth = 0
+        node = self
+        while node:
+            node = node.parent
+            depth += 1
+        self._cached_depth = depth
+        return depth
+
+
+    def get_children(self):
+        """
+        :returns: A queryset of all the node's children
+
+        See: :meth:`treebeard.Node.get_children`
+        """
+        return self.__class__.objects.filter(parent=self)
+
+
+    def get_parent(self, update=False):
+        """
+        :returns: the parent node of the current node object.
+
+        See: :meth:`treebeard.Node.get_parent`
+        """
+        return self.parent
+
+
+    def get_ancestors(self):
+        """
+        :returns: A *list* containing the current node object's ancestors,
+            starting by the root node and descending to the parent.
+
+        See: :meth:`treebeard.Node.get_ancestors`
+        """
+        ancestors = []
+        node = self.parent
+        while node:
+            ancestors.append(node)
+            node = node.parent
+        ancestors.reverse()
+        return ancestors
+
+
+    def get_root(self):
+        """
+        :returns: the root node for the current node object.
+
+        See: :meth:`treebeard.Node.get_root`
+        """
+        ancestors = self.get_ancestors()
+        if ancestors:
+            return ancestors[0]
+        return self
+
+        
+    def is_descendant_of(self, node):
+        """
+        :returns: ``True`` if the node if a descendant of another node given
+            as an argument, else, returns ``False``
+
+        See: :meth:`treebeard.Node.is_descendant_of`
+        """
+        return self.pk in [obj.pk for obj in node.get_descendants()]
+
+
+    @classmethod
+    def dump_bulk(cls, parent=None, keep_ids=True):
+        """
+        Dumps a tree branch to a python data structure.
+
+        See: :meth:`treebeard.Node.dump_bulk`
+        """
+
+        # not really a queryset, but it works
+        qset = cls.get_tree(parent)
+
+        ret, lnk = [], {}
+        pos = 0
+        for pyobj in serializers.serialize('python', qset):
+            node = qset[pos]
+            depth = node.get_depth()
+            # django's serializer stores the attributes in 'fields'
+            fields = pyobj['fields']
+            del fields['parent']
+            del fields['sib_order']
+            if 'id' in fields:
+                del fields['id']
+
+            newobj = {'data': fields}
+            if keep_ids:
+                newobj['id'] = pyobj['pk']
+
+            if (not parent and depth == 1) or \
+                    (parent and depth == parent.get_depth()):
+                ret.append(newobj)
+            else:
+                parentobj = lnk[node.parent_id]
+                if 'children' not in parentobj:
+                    parentobj['children'] = []
+                parentobj['children'].append(newobj)
+            lnk[node.id] = newobj
+            pos += 1
+        return ret
+
+        
+
+
+    def add_child(self, **kwargs):
+        """
+        Adds a child to the node.
+
+        See: :meth:`treebeard.Node.add_child`
+        """
+        newobj = self.__class__(**kwargs)
+        try:
+            newobj._cached_depth = self._cached_depth + 1
+        except AttributeError:
+            pass
+
+        if not self.__class__.node_order_by:
+            try:
+                max = self.__class__.objects.filter(parent=self).reverse(
+                    )[0].sib_order
+            except IndexError:
+                max = 0
+            newobj.sib_order = max + 1
+
+        # saving the instance before returning it
+        newobj.parent = self
+        newobj.save()
+        transaction.commit_unless_managed()
+        return newobj
+
+
+    @classmethod
+    def _get_tree_recur(cls, ret, parent, depth):
+        if parent:
+            qset = cls.objects.filter(parent=parent)
+        else:
+            qset = cls.get_root_nodes()
+        for node in qset:
+            node._cached_depth = depth
+            ret.append(node)
+            cls._get_tree_recur(ret, node, depth+1)
+
+
+    @classmethod
+    def get_tree(cls, parent=None):
+        """
+        :returns: A list of nodes ordered as DFS, including the parent. If
+                  no parent is given, the entire tree is returned.
+
+        See: :meth:`treebeard.Node.get_tree`
+        """
+        if parent:
+            depth = parent.get_depth() + 1
+            ret = [parent]
+        else:
+            depth = 1
+            ret = []
+        cls._get_tree_recur(ret, parent, depth)
+        return ret
+
+
+    def get_descendants(self):
+        """
+        :returns: A *list* of all the node's descendants, doesn't
+            include the node itself
+
+        See: :meth:`treebeard.Node.get_descendants`
+        """
+        return self.__class__.get_tree(parent=self)[1:]
+
+
+    def get_descendant_count(self):
+        """
+        :returns: the number of descendants of a node.
+
+        See: :meth:`treebeard.Node.get_descendant_count`
+        """
+        return len(self.get_descendants())
+
+
+    def get_siblings(self):
+        """
+        :returns: A queryset of all the node's siblings, including the node
+            itself.
+
+        See: :meth:`treebeard.Node.get_siblings`
+        """
+        if self.parent:
+            return self.__class__.objects.filter(parent=self.parent)
+        return self.__class__.get_root_nodes()
+
+
+    def add_sibling(self, pos=None, **kwargs):
+        """
+        Adds a new node as a sibling to the current node object.
+
+        See: :meth:`treebeard.Node.add_sibling`
+        """
+
+        pos = self._fix_add_sibling_opts(pos)
+
+        stmts = []
+
+        # creating a new object
+        newobj = self.__class__(**kwargs)
+
+        if not self.node_order_by:
+            siblings = self.get_siblings()
+
+            max = self.get_siblings().order_by(
+                      'sib_order').reverse()[0].sib_order
+            newobj.sib_order = self.__class__._move_add_sibling_aux(pos,
+                                   self, stmts)
+
+        if self.parent_id:
+            newobj.parent_id = self.parent_id
+
+        cursor = connection.cursor()
+        for sql, vals in stmts:
+            cursor.execute(sql, vals)
+
+        # saving the instance before returning it
+        newobj.save()
+        transaction.commit_unless_managed()
+        return newobj
+
+
+    @classmethod
+    def _move_add_sibling_aux(cls, pos, target, stmts):
+        """
+        helper that makes a hole between siblings for a new node (only for not
+        sorted trees)
+        """
+
+        sib_order = target.sib_order
+        if pos == 'last-sibling' \
+                or (pos == 'right' and target == target.get_last_sibling()):
+            sib_order = target.get_last_sibling().sib_order + 1
+        else:
+            siblings = target.get_siblings()
+            siblings = {'left': siblings.filter(
+                                     sib_order__gte=target.sib_order),
+                        'right': siblings.filter(
+                                     sib_order__gt=target.sib_order),
+                        'first-sibling': siblings}[pos]
+            sib_order = {'left': sib_order,
+                         'right': sib_order+1,
+                         'first-sibling': 1}[pos]
+            try:
+                min = siblings.order_by('sib_order')[0].sib_order
+            except IndexError:
+                min = 0
+            if min:
+                sql = 'UPDATE %(table)s' \
+                      ' SET sib_order=sib_order+1' \
+                      ' WHERE sib_order >= %%s' \
+                      ' AND ' % {'table': cls._meta.db_table}
+                params = [min]
+                if target.is_root():
+                    sql += 'parent_id IS NULL'
+                else:
+                    sql += 'parent_id=%s'
+                    params.append(target.parent_id)
+                stmts.append((sql, params))
+        return sib_order
+
+
+    def move(self, target, pos=None):
+        """
+        Moves the current node and all it's descendants to a new position
+        relative to another node.
+
+        See: :meth:`treebeard.Node.move`
+        """
+
+        pos = self._fix_move_opts(pos)
+
+        stmts = []
+        sib_order = None
+        parent = None
+
+        if pos in ('first-child', 'last-child', 'sorted-child'):
+            # moving to a child
+            if target.get_children_count():
+                target = target.get_last_child()
+                pos = {'first-child': 'first-sibling',
+                       'last-child': 'last-sibling',
+                       'sorted-child': 'sorted-sibling'}[pos]
+            else:
+                parent = target
+                if pos == 'sorted-child':
+                    pos = 'sorted-sibling'
+                else:
+                    pos = 'first-sibling'
+                    sib_order = 1
+
+        if target.is_descendant_of(self):
+            raise InvalidMoveToDescendant("Can't move node to a descendant.")
+
+        if self == target and (
+              (pos == 'left') or \
+              (pos in ('right', 'last-sibling') and \
+                target == target.get_last_sibling()) or \
+              (pos == 'first-sibling' and \
+                target == target.get_first_sibling())):
+            # special cases, not actually moving the node so no need to UPDATE
+            return
+
+        if pos == 'sorted-sibling':
+            # easy, just change the parent
+            if parent:
+                self.parent = parent
+            else:
+                self.parent = target.parent
+        else:
+            if sib_order:
+                self.sib_order = sib_order
+            else:
+                self.sib_order = self.__class__._move_add_sibling_aux(pos,
+                                        target, stmts)
+            if parent:
+                self.parent = parent
+            else:
+                self.parent = target.parent
+
+        if stmts:
+            cursor = connection.cursor()
+            for sql, vals in stmts:
+                cursor.execute(sql, vals)
+
+        self.save()
+        transaction.commit_unless_managed()
+
+
+        
+    class Meta:
+        """
+        Abstract model.
+        """
+        abstract = True

treebeard/models.py

     def get_tree(cls, parent=None):
         """
         :returns: A list of nodes ordered as DFS, including the parent. If
-        no parent is given, the entire tree is returned.
+                  no parent is given, the entire tree is returned.
         """
         raise NotImplementedError
 
                 print '%s by %s (%d replies)' % (node.comment, node.author,
                                                  node.descendants_count)
         """
-        raise NotImplementedError
+
+        # this is the slowest possible implementation, subclasses should do
+        # better
+        if parent is None:
+            qset = cls.get_root_nodes()
+        else:
+            qset = parent.children_set.all()
+        nodes = list(qset)
+        for node in nodes:
+            node.descendants_count = node.get_descendant_count()
+        return nodes
 
 
     def get_depth(self):
 
         Example::
 
-           node.get_root()
+          node.get_root()
         """
         raise NotImplementedError
 
 
+    def is_root(self):
+        """
+        :returns: True if the node is a root node (else, returns False)
+
+        Example::
+
+           node.is_root()
+        """
+        return self.get_root() == self
+
+
+    def is_leaf(self):
+        """
+        :returns: True if the node is a leaf node (else, returns False)
+
+        Example::
+
+           node.is_leaf()
+        """
+        return self.get_children_count() == 0
+
+
     def get_ancestors(self):
         """
         :returns: A queryset containing the current node object's ancestors,
             starting by the root node and descending to the parent.
+            (some subclasses may return a list)
 
         Example::
 
         self.__class__.objects.filter(id=self.id).delete()
 
 
+    def _fix_add_sibling_opts(self, pos):
+        """
+        prepare the pos variable for the add_sibling method
+        """
+        if pos is None:
+            if self.node_order_by:
+                pos = 'sorted-sibling'
+            else:
+                pos = 'last-sibling'
+        if pos not in ('first-sibling', 'left', 'right', 'last-sibling', 'sorted-sibling'):
+            raise InvalidPosition('Invalid relative position: %s' % (pos,))
+        if self.node_order_by and pos != 'sorted-sibling':
+            raise InvalidPosition('Must use %s in add_sibling when'
+                                  ' node_order_by is enabled' % ('sorted-sibling',))
+        if pos == 'sorted-sibling' and not self.node_order_by:
+            raise MissingNodeOrderBy('Missing node_order_by attribute.')
+        return pos
+
+
+    def _fix_move_opts(self, pos):
+        """
+        prepare the pos var for the move method
+        """
+        if pos is None:
+            if self.node_order_by:
+                pos = 'sorted-sibling'
+            else:
+                pos = 'last-sibling'
+        if pos not in ('first-sibling', 'left', 'right', 'last-sibling', 'sorted-sibling',
+                       'first-child', 'last-child', 'sorted-child'):
+            raise InvalidPosition('Invalid relative position: %s' % (pos,))
+        if self.node_order_by and pos not in ('sorted-child', 'sorted-sibling'):
+            raise InvalidPosition('Must use %s or %s in add_sibling when'
+                                  ' node_order_by is enabled' % ('sorted-sibling',
+                                  'sorted-child'))
+        if pos in ('sorted-child', 'sorted-sibling') and not self.node_order_by:
+            raise MissingNodeOrderBy('Missing node_order_by attribute.')
+        return pos
+
+
     class Meta:
         """
         Abstract model.
         """
         abstract = True
 
+
+class InvalidPosition(Exception):
+    """
+    Raised when passing an invalid pos value
+    """
+
+class InvalidMoveToDescendant(Exception):
+    """
+    Raised when attemping to move a node to one of it's descendants.
+    """
+
+class MissingNodeOrderBy(Exception):
+    """
+    Raised when an operation needs a missing
+    :attr:`~treebeard.MP_Node.node_order_by` attribute
+    """
+
+class PathOverflow(Exception):
+    """
+    Raised when trying to add or move a node to a position where no more nodes
+    can be added (see :attr:`~treebeard.MP_Node.path` and
+    :attr:`~treebeard.MP_Node.alphabet` for more info)
+    """

treebeard/mp_tree.py

 
     ``django-treebeard`` uses a particular approach: every step in the path has
     a fixed width and has no separators. This makes queries predictable and
-    faster at the cost of using more characters to store a step. To attack this
+    faster at the cost of using more characters to store a step. To address this
     problem, every step number is encoded.
 
     Also, two extra fields are stored in every node:
 from django.db.models import Q
 from django.conf import settings
 
-from treebeard import Node, InvalidPosition, InvalidMoveToDescendant, \
-    PathOverflow, MissingNodeOrderBy
+from treebeard.models import Node, InvalidMoveToDescendant, PathOverflow
 
 
 class MP_NodeQuerySet(models.query.QuerySet):
 
 class MP_Node(Node):
     """
-    Abstract model to create your own tree models.
+    Abstract model to create your own Materialized Path Trees.
 
     .. attribute:: steplen
        
           numval = models.IntegerField()
           strval = models.CharField(max_length=255)
 
+    Read the API reference of :class:`treebeard.Node` for info on methods
+    available in this class, or read the following section for methods with
+    particular arguments or exceptions.
     """
 
     steplen = 4
     @classmethod
     def get_tree(cls, parent=None):
         """
-        :returns: A queryset of nodes ordered as DFS, including the parent. If
-        no parent is given, the entire tree is returned.
+        :returns: A *queryset* of nodes ordered as DFS, including the parent. If
+                  no parent is given, the entire tree is returned.
+
+        See: :meth:`treebeard.Node.get_tree`
+
+        .. note::
+
+            This metod returns a queryset.
         """
         if parent is None:
             # return the entire tree
            node's new position
         """
 
-        if pos is None:
-            if self.node_order_by:
-                pos = 'sorted-sibling'
-            else:
-                pos = 'last-sibling'
-        if pos not in ('first-sibling', 'left', 'right', 'last-sibling', 'sorted-sibling'):
-            raise InvalidPosition('Invalid relative position: %s' % (pos,))
-        if self.node_order_by and pos != 'sorted-sibling':
-            raise InvalidPosition('Must use %s in add_sibling when'
-                                  ' node_order_by is enabled' % ('sorted-sibling',))
-        if pos == 'sorted-sibling' and not self.node_order_by:
-            raise MissingNodeOrderBy('Missing node_order_by attribute.')
+        pos = self._fix_add_sibling_opts(pos)
 
         # creating a new object
         newobj = self.__class__(**kwargs)
         :raise PathOverflow: when the library can't make room for the
            node's new position
         """
-        if pos is None:
-            if self.node_order_by:
-                pos = 'sorted-sibling'
-            else:
-                pos = 'last-sibling'
-        if pos not in ('first-sibling', 'left', 'right', 'last-sibling', 'sorted-sibling',
-                       'first-child', 'last-child', 'sorted-child'):
-            raise InvalidPosition('Invalid relative position: %s' % (pos,))
-        if self.node_order_by and pos not in ('sorted-child', 'sorted-sibling'):
-            raise InvalidPosition('Must use %s or %s in add_sibling when'
-                                  ' node_order_by is enabled' % ('sorted-sibling',
-                                  'sorted-child'))
-        if pos in ('sorted-child', 'sorted-sibling') and not self.node_order_by:
-            raise MissingNodeOrderBy('Missing node_order_by attribute.')
+
+        pos = self._fix_move_opts(pos)
 
         oldpath = self.path
 
 
             if newpos is None:
                 siblings = target.get_siblings()
-                siblings = {'left':siblings.filter(path__gte=target.path),
-                            'right':siblings.filter(path__gt=target.path),
-                            'first-sibling':siblings}[pos]
+                siblings = {'left': siblings.filter(path__gte=target.path),
+                            'right': siblings.filter(path__gt=target.path),
+                            'first-sibling': siblings}[pos]
                 basenum = cls._get_lastpos_in_path(target.path)
-                newpos = {'first-sibling':1, 'left':basenum, 'right':basenum+1}[pos]
+                newpos = {'first-sibling': 1,
+                          'left': basenum,
+                          'right': basenum+1}[pos]
 
             newpath = cls._get_path(target.path, newdepth, newpos)
 
             newdepth += 1
             if target.numchild:
                 target = target.get_last_child()
-                pos = {'first-child':'first-sibling', 'last-child':'last-sibling', 'sorted-child':'sorted-sibling'}[pos]
+                pos = {'first-child': 'first-sibling',
+                       'last-child': 'last-sibling',
+                       'sorted-child': 'sorted-sibling'}[pos]
             else:
                 # moving as a target's first child
                 newpos = 1

treebeard/tests.py

 from treebeard import InvalidPosition, InvalidMoveToDescendant, \
     PathOverflow, MissingNodeOrderBy, numconv
 from treebeard.mp_tree import MP_Node
+from treebeard.al_tree import AL_Node
 
 BASE_DATA = [
   {'data':{'desc':'1'}},
     node = models.ForeignKey(MP_TestNode)
 
 
+class AL_TestNode(AL_Node):
+    parent = models.ForeignKey('self',
+                               related_name='children_set',
+                               null=True,
+                               db_index=True)
+    sib_order = models.PositiveIntegerField()
+    desc = models.CharField(max_length=255)
+
+
+class AL_TestNodeSomeDep(models.Model):
+    node = models.ForeignKey(AL_TestNode)
+
+
 class MP_TestNodeSorted(MP_Node):
     steplen = 1
     node_order_by = ['val1', 'val2', 'desc']
     desc = models.CharField(max_length=255)
 
 
+class AL_TestNodeSorted(AL_Node):
+    parent = models.ForeignKey('self',
+                               related_name='children_set',
+                               null=True,
+                               db_index=True)
+    node_order_by = ['val1', 'val2', 'desc']
+    val1 = models.IntegerField()
+    val2 = models.IntegerField()
+    desc = models.CharField(max_length=255)
+
+
 class MP_TestNodeAlphabet(MP_Node):
     steplen = 2
 
 MP_TestNodeShortPath._meta.get_field('path').max_length = 4
 
 
-class TestSortedNodeShortPath(MP_Node):
+class MP_TestSortedNodeShortPath(MP_Node):
     steplen = 1
     alphabet = '01234'
     desc = models.CharField(max_length=255)
 
     node_order_by = ['desc']
-TestSortedNodeShortPath._meta.get_field('path').max_length = 4
+MP_TestSortedNodeShortPath._meta.get_field('path').max_length = 4
 
 
 def multi_test():
                 finally:
                     transaction.rollback()
 
+                try:
+                    self.set_AL() ; f(self)
+                finally:
+                    transaction.rollback()
+
             finally:
                 self.model = None
                 self.sorted_model = None
         self.dep_model = MP_TestNodeSomeDep
 
 
+    def set_AL(self):
+        self.model = AL_TestNode
+        self.sorted_model = AL_TestNodeSorted
+        self.dep_model = AL_TestNodeSomeDep
+
+
     def got(self):
         return [(o.desc, o.get_depth(), o.get_children_count())
                 for o in self.model.get_tree()]
         self.assertEqual(got, None)
 
 
+    @multi_test()
+    def test_get_tree(self):
+        got = list(self.model.get_tree())
+        self.assertEqual(got, [])
+
+
 
 class TestNonEmptyTree(TestTreeBase):
 
     def setUp(self):
         super(TestNonEmptyTree, self).setUp()
         MP_TestNode.load_bulk(BASE_DATA)
+        AL_TestNode.load_bulk(BASE_DATA)
 
 
 class TestClassMethods(TestNonEmptyTree):
 
 
     @multi_test()
+    def test_get_tree_all(self):
+        got = [(o.desc, o.get_depth(), o.get_children_count())
+                for o in self.model.get_tree()]
+        self.assertEqual(got, self.unchanged)
+
+
+    @multi_test()
     def test_dump_bulk_all(self):
         self.assertEqual(self.model.dump_bulk(keep_ids=False), BASE_DATA)
 
 
     @multi_test()
+    def test_get_tree_node(self):
+        leafnode = self.model.objects.get(desc=u'231')
+        self.model.load_bulk(BASE_DATA, leafnode)
+
+        got = [(o.desc, o.get_depth(), o.get_children_count())
+                for o in self.model.get_tree(leafnode)]
+        expected = [(u'231', 3, 4),
+                    (u'1', 4, 0),
+                    (u'2', 4, 4),
+                    (u'21', 5, 0),
+                    (u'22', 5, 0),
+                    (u'23', 5, 1),
+                    (u'231', 6, 0),
+                    (u'24', 5, 0),
+                    (u'3', 4, 0),
+                    (u'4', 4, 1),
+                    (u'41', 5, 0)]
+        self.assertEqual(got, expected)
+
+
+    @multi_test()
     def test_dump_bulk_node(self):
         leafnode = self.model.objects.get(desc=u'231')
         self.model.load_bulk(BASE_DATA, leafnode)
+
+        got = self.model.dump_bulk(leafnode, False)
         expected = [{'data':{'desc':u'231'}, 'children':BASE_DATA}]
-        self.assertEqual(self.model.dump_bulk(leafnode, False), expected)
+        self.assertEqual(got, expected)
 
 
     @multi_test()
 class TestSimpleNodeMethods(TestNonEmptyTree):
 
     @multi_test()
+    def test_is_root(self):
+        data = [
+            ('2', True),
+            ('1', True),
+            ('4', True),
+            ('21', False),
+            ('24', False),
+            ('22', False),
+            ('231', False),
+        ]
+        for desc, expected in data:
+            got = self.model.objects.get(desc=desc).is_root()
+            self.assertEqual(got, expected)
+
+
+    @multi_test()
+    def test_is_leaf(self):
+        data = [
+            ('2', False),
+            ('23', False),
+            ('231', True),
+        ]
+        for desc, expected in data:
+            got = self.model.objects.get(desc=desc).is_leaf()
+            self.assertEqual(got, expected)
+
+
+    @multi_test()
     def test_get_root(self):
         data = [
             ('2', '2'),
 
     @multi_test()
     def test_move_branch_first_sibling(self):
-        MP_TestNode.objects.get(desc='4').move(MP_TestNode.objects.get(desc='23'), 'first-sibling')
+        self.model.objects.get(desc='4').move(self.model.objects.get(desc='23'), 'first-sibling')
         expected = [(u'1', 1, 0),
                     (u'2', 1, 5),
                     (u'4', 2, 1),
 
     @multi_test()
     def test_move_branch_last_sibling(self):
-        MP_TestNode.objects.get(desc='4').move(MP_TestNode.objects.get(desc='23'), 'last-sibling')
+        self.model.objects.get(desc='4').move(self.model.objects.get(desc='23'), 'last-sibling')
         expected = [(u'1', 1, 0),
                     (u'2', 1, 5),
                     (u'21', 2, 0),
 
     @multi_test()
     def test_move_branch_left_sibling(self):
-        MP_TestNode.objects.get(desc='4').move(MP_TestNode.objects.get(desc='23'), 'left')
+        self.model.objects.get(desc='4').move(self.model.objects.get(desc='23'), 'left')
         expected = [(u'1', 1, 0),
                     (u'2', 1, 5),
                     (u'21', 2, 0),
 
     @multi_test()
     def test_move_branch_right_sibling(self):
-        MP_TestNode.objects.get(desc='4').move(MP_TestNode.objects.get(desc='23'), 'right')
+        self.model.objects.get(desc='4').move(self.model.objects.get(desc='23'), 'right')
         expected = [(u'1', 1, 0),
                     (u'2', 1, 5),
                     (u'21', 2, 0),
 
     @multi_test()
     def test_move_branch_left_noleft_sibling(self):
-        MP_TestNode.objects.get(desc='4').move(MP_TestNode.objects.get(desc='23').get_first_sibling(), 'left')
+        self.model.objects.get(desc='4').move(self.model.objects.get(desc='23').get_first_sibling(), 'left')
         expected = [(u'1', 1, 0),
                     (u'2', 1, 5),
                     (u'4', 2, 1),
 
     @multi_test()
     def test_move_branch_right_noright_sibling(self):
-        MP_TestNode.objects.get(desc='4').move(MP_TestNode.objects.get(desc='23').get_last_sibling(), 'right')
+        self.model.objects.get(desc='4').move(self.model.objects.get(desc='23').get_last_sibling(), 'right')
         expected = [(u'1', 1, 0),
                     (u'2', 1, 5),
                     (u'21', 2, 0),
 
     @multi_test()
     def test_move_branch_left_itself_sibling(self):
-        MP_TestNode.objects.get(desc='4').move(MP_TestNode.objects.get(desc='4'), 'left')
+        self.model.objects.get(desc='4').move(self.model.objects.get(desc='4'), 'left')
         self.assertEqual(self.got(), self.unchanged)
 
 
     @multi_test()
     def test_move_branch_first_child(self):
-        MP_TestNode.objects.get(desc='4').move(MP_TestNode.objects.get(desc='23'), 'first-child')
+        self.model.objects.get(desc='4').move(self.model.objects.get(desc='23'), 'first-child')
         expected = [(u'1', 1, 0),
                     (u'2', 1, 4),
                     (u'21', 2, 0),
 
     @multi_test()
     def test_move_branch_last_child(self):
-        MP_TestNode.objects.get(desc='4').move(MP_TestNode.objects.get(desc='23'), 'last-child')
+        self.model.objects.get(desc='4').move(self.model.objects.get(desc='23'), 'last-child')
         expected =  [(u'1', 1, 0),
                      (u'2', 1, 4),
                      (u'21', 2, 0),
 class TestHelpers(TestTreeBase):
 
     def setUp(self):
-        for model in (MP_TestNode, ):
+        for model in (MP_TestNode, AL_TestNode):
             model.load_bulk(BASE_DATA)
             for node in model.get_root_nodes():
                 model.load_bulk(BASE_DATA, node)
                              (u'431', u'i', 3, 1),
                              (u'4311', u'e', 4, 0),
                              (u'44', u'o', 2, 0)],
-            TestSortedNodeShortPath: [(u'1', u'a', 1, 4),
+            MP_TestSortedNodeShortPath: [(u'1', u'a', 1, 4),
                            (u'11', u'a', 2, 0),
                            (u'12', u'a', 2, 0),
                            (u'13', u'o', 2, 0),
                            (u'3', u'd', 1, 0),
                            (u'4', u'g', 1, 0)]}
 
-        for model in (MP_TestNodeShortPath, TestSortedNodeShortPath):
+        for model in (MP_TestNodeShortPath, MP_TestSortedNodeShortPath):
             model(path='4', depth=2, numchild=2, desc='a').save()
             model(path='13', depth=1000, numchild=0, desc='u').save()
             model(path='14', depth=4, numchild=500, desc='o').save()