tests.py - django-treebeard

‹r98

r100

Source path: svn/ trunk/ treebeard/ tests.py

# -*- coding: utf-8 -*-
"""

    treebeard.tests
    ---------------

    Unit tests.

    :copyright: 2008 by Gustavo Picon
    :license: Apache License 2.0

"""

import os, functools
from django.test import TestCase
from django.db import models, transaction
from django.contrib.auth.models import User, AnonymousUser
from django.db.models import Q
from django.conf import settings

from treebeard import numconv
from treebeard.exceptions import InvalidPosition, InvalidMoveToDescendant, \
    PathOverflow, MissingNodeOrderBy
from treebeard.mp_tree import MP_Node
from treebeard.al_tree import AL_Node
from treebeard.ns_tree import NS_Node

# ghetto app detection, there is probably some introspection method,
# but meh, this works
HAS_DJANGO_AUTH = 'django.contrib.auth' in settings.INSTALLED_APPS

BASE_DATA = [
  {'data':{'desc':'1'}},
  {'data':{'desc':'2'}, 'children':[
    {'data':{'desc':'21'}},
    {'data':{'desc':'22'}},
    {'data':{'desc':'23'}, 'children':[
      {'data':{'desc':'231'}},
    ]},
    {'data':{'desc':'24'}},
  ]},
  {'data':{'desc':'3'}},
  {'data':{'desc':'4'}, 'children':[
    {'data':{'desc':'41'}},
  ]},
]


class MP_TestNode(MP_Node):
    steplen = 3

    desc = models.CharField(max_length=255)


class MP_TestNodeSomeDep(models.Model):
    node = models.ForeignKey(MP_TestNode)


class NS_TestNode(NS_Node):
    desc = models.CharField(max_length=255)


class NS_TestNodeSomeDep(models.Model):
    node = models.ForeignKey(NS_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']
    val1 = models.IntegerField()
    val2 = models.IntegerField()
    desc = models.CharField(max_length=255)


class NS_TestNodeSorted(NS_Node):
    node_order_by = ['val1', 'val2', 'desc']
    val1 = models.IntegerField()
    val2 = models.IntegerField()
    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

    numval = models.IntegerField()


class MP_TestNodeSmallStep(MP_Node):
    steplen = 1
    alphabet = '0123456789'


class MP_TestNodeSortedAutoNow(MP_Node):
    desc = models.CharField(max_length=255)
    created = models.DateTimeField(auto_now_add=True)

    node_order_by = ['created']


class MP_TestNodeShortPath(MP_Node):
    steplen = 1
    alphabet = '01234'
    desc = models.CharField(max_length=255)

# This is how you change the default fields defined in a Django abstract class
# (in this case, MP_Node), since Django doesn't allow overriding fields, only
# mehods and attributes
MP_TestNodeShortPath._meta.get_field('path').max_length = 4


class MP_TestSortedNodeShortPath(MP_Node):
    steplen = 1
    alphabet = '01234'
    desc = models.CharField(max_length=255)

    node_order_by = ['desc']
MP_TestSortedNodeShortPath._meta.get_field('path').max_length = 4


if HAS_DJANGO_AUTH:
    class MP_TestIssue14(MP_Node):
        name = models.CharField(max_length=255)
        users = models.ManyToManyField(User)


def multi_test():
    def decorator(f):

        @functools.wraps(f)
        def _multi_test(self):
            try:

                try:
                    self.set_MP() ; f(self)
                finally:
                    transaction.rollback()

                try:
                    self.set_AL() ; f(self)
                finally:
                    transaction.rollback()

                try:
                    self.set_NS() ; f(self)
                finally:
                    transaction.rollback()

            finally:
                self.model = None
                self.sorted_model = None
                self.dep_model = None
        return _multi_test
    return decorator


class TestTreeBase(TestCase):

    def setUp(self):
        self.set_MP()
        self.unchanged = [(u'1', 1, 0),
                          (u'2', 1, 4),
                          (u'21', 2, 0),
                          (u'22', 2, 0),
                          (u'23', 2, 1),
                          (u'231', 3, 0),
                          (u'24', 2, 0),
                          (u'3', 1, 0),
                          (u'4', 1, 1),
                          (u'41', 2, 0)]


    def set_MP(self):
        self.model = MP_TestNode
        self.sorted_model = MP_TestNodeSorted
        self.dep_model = MP_TestNodeSomeDep
    
        
    def set_NS(self):
        self.model = NS_TestNode
        self.sorted_model = NS_TestNodeSorted
        self.dep_model = NS_TestNodeSomeDep



    def set_AL(self):
        self.model = AL_TestNode
        self.sorted_model = AL_TestNodeSorted
        self.dep_model = AL_TestNodeSomeDep


    def got(self):
        if self.model == NS_TestNode:
            # this slows down nested sets tests quite a bit, but it has the
            # advantage that we'll check the node edges are correct
            d = {}
            for tree_id, lft, rgt in self.model.objects.values_list('tree_id', 'lft', 'rgt'):
                d.setdefault(tree_id, []).extend([lft, rgt])
            for tree_id, got_edges in d.items():
                self.assertEqual(len(got_edges), max(got_edges))
                good_edges = range(1, len(got_edges)+1)
                self.assertEqual(sorted(got_edges), good_edges)

        return [(o.desc, o.get_depth(), o.get_children_count())
                for o in self.model.get_tree()]



class TestEmptyTree(TestTreeBase):

    @multi_test()
    def test_load_bulk_empty(self):
        ids = self.model.load_bulk(BASE_DATA)
        got_descs = [obj.desc
                     for obj in self.model.objects.filter(id__in=ids)]
        expected_descs = [x[0] for x in self.unchanged]
        self.assertEqual(sorted(got_descs), sorted(expected_descs))
        self.assertEqual(self.got(), self.unchanged)

    
    @multi_test()
    def test_dump_bulk_empty(self):
        self.assertEqual(self.model.dump_bulk(), [])


    @multi_test()
    def test_add_root_empty(self):
        obj = self.model.add_root(desc='1')
        expected = [(u'1', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_get_root_nodes_empty(self):
        got = self.model.get_root_nodes()
        expected = []
        self.assertEqual([node.desc for node in got], expected)


    @multi_test()
    def test_get_first_root_node_empty(self):
        got = self.model.get_first_root_node()
        self.assertEqual(got, None)


    @multi_test()
    def test_get_last_root_node_empty(self):
        got = self.model.get_last_root_node()
        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)
        NS_TestNode.load_bulk(BASE_DATA)


class TestClassMethods(TestNonEmptyTree):

    def setUp(self):
        super(TestClassMethods, self).setUp()


    @multi_test()
    def test_load_bulk_existing(self):

        # inserting on an existing node

        node = self.model.objects.get(desc=u'231')
        ids = self.model.load_bulk(BASE_DATA, node)
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (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),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        expected_descs = [u'1', u'2', u'21', u'22', u'23', u'231', u'24', u'3',
                          u'4', u'41']
        got_descs = [obj.desc
                     for obj in self.model.objects.filter(id__in=ids)]
        self.assertEqual(sorted(got_descs), sorted(expected_descs))
        self.assertEqual(self.got(), expected)


    @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):
        node = self.model.objects.get(desc=u'231')
        self.model.load_bulk(BASE_DATA, node)

        # this is ONLY needed by the nested set tree model, the rgt value of
        # the node was updated in a raw query, and it must be updated in
        # django's object
        if self.model == NS_TestNode:
            node = self.model.objects.get(pk=node.id)


        got = [(o.desc, o.get_depth(), o.get_children_count())
                for o in self.model.get_tree(node)]
        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):
        node = self.model.objects.get(desc=u'231')
        self.model.load_bulk(BASE_DATA, node)
        
        # this is ONLY needed by the nested set tree model, the rgt value of
        # the node was updated in a raw query, and it must be updated in
        # django's object
        if self.model == NS_TestNode:
            node = self.model.objects.get(pk=node.id)

        got = self.model.dump_bulk(node, False)
        expected = [{'data':{'desc':u'231'}, 'children':BASE_DATA}]
        self.assertEqual(got, expected)


    @multi_test()
    def test_load_and_dump_bulk_keeping_ids(self):
        exp = self.model.dump_bulk(keep_ids=True)
        self.model.objects.all().delete()
        self.model.load_bulk(exp, None, True)
        got = self.model.dump_bulk(keep_ids=True)
        self.assertEqual(got, exp)


    @multi_test()
    def test_get_root_nodes(self):
        got = self.model.get_root_nodes()
        expected = ['1', '2', '3', '4']
        self.assertEqual([node.desc for node in got], expected)


    @multi_test()
    def test_get_first_root_node(self):
        got = self.model.get_first_root_node()
        self.assertEqual(got.desc, '1')



    @multi_test()
    def test_get_last_root_node(self):
        got = self.model.get_last_root_node()
        self.assertEqual(got.desc, '4')


    @multi_test()
    def test_add_root(self):
        obj = self.model.add_root(desc='5')
        self.assertEqual(obj.get_depth(), 1)
        self.assertEqual(self.model.get_last_root_node().desc, '5')



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'),
            ('1', '1'),
            ('4', '4'),
            ('21', '2'),
            ('24', '2'),
            ('22', '2'),
            ('231', '2'),
        ]
        for desc, expected in data:
            node = self.model.objects.get(desc=desc).get_root()
            self.assertEqual(node.desc, expected)


    @multi_test()
    def test_get_parent(self):
        data = [
            ('2', None),
            ('1', None),
            ('4', None),
            ('21', '2'),
            ('24', '2'),
            ('22', '2'),
            ('231', '23'),
        ]
        data = dict(data)
        objs = {}
        for desc, expected in data.items():
            node = self.model.objects.get(desc=desc)
            parent = node.get_parent()
            if expected:
                self.assertEqual(parent.desc, expected)
            else:
                self.assertEqual(parent, None)
            objs[desc] = node
            # corrupt the objects' parent cache
            node._parent_obj = 'CORRUPTED!!!'

        for desc, expected in data.items():
            node = objs[desc]
            # asking get_parent to not use the parent cache (since we corrupted
            # it in the previous loop)
            parent = node.get_parent(True)
            if expected:
                self.assertEqual(parent.desc, expected)
            else:
                self.assertEqual(parent, None)

    
    @multi_test()
    def test_get_children(self):
        data = [
            ('2', ['21', '22', '23', '24']),
            ('23', ['231']),
            ('231', []),
        ]
        for desc, expected in data:
            children = self.model.objects.get(desc=desc).get_children()
            self.assertEqual([node.desc for node in children], expected)

    
    @multi_test()
    def test_get_children_count(self):
        data = [
            ('2', 4),
            ('23', 1),
            ('231', 0),
        ]
        for desc, expected in data:
            got = self.model.objects.get(desc=desc).get_children_count()
            self.assertEqual(got, expected)


    @multi_test()
    def test_get_siblings(self):
        data = [
            ('2', ['1', '2', '3', '4']),
            ('21', ['21', '22', '23', '24']),
            ('231', ['231']),
        ]
        for desc, expected in data:
            siblings = self.model.objects.get(desc=desc).get_siblings()
            self.assertEqual([node.desc for node in siblings], expected)


    @multi_test()
    def test_get_first_sibling(self):
        data = [
            ('2', '1'),
            ('1', '1'),
            ('4', '1'),
            ('21', '21'),
            ('24', '21'),
            ('22', '21'),
            ('231', '231'),
        ]
        for desc, expected in data:
            node = self.model.objects.get(desc=desc).get_first_sibling()
            self.assertEqual(node.desc, expected)
    

    @multi_test()
    def test_get_prev_sibling(self):
        data = [
            ('2', '1'),
            ('1', None),
            ('4', '3'),
            ('21', None),
            ('24', '23'),
            ('22', '21'),
            ('231', None),
        ]
        for desc, expected in data:
            node = self.model.objects.get(desc=desc).get_prev_sibling()
            if expected is None:
                self.assertEqual(node, None)
            else:
                self.assertEqual(node.desc, expected)
    
    
    @multi_test()
    def test_get_next_sibling(self):
        data = [
            ('2', '3'),
            ('1', '2'),
            ('4', None),
            ('21', '22'),
            ('24', None),
            ('22', '23'),
            ('231', None),
        ]
        for desc, expected in data:
            node = self.model.objects.get(desc=desc).get_next_sibling()
            if expected is None:
                self.assertEqual(node, None)
            else:
                self.assertEqual(node.desc, expected)


    @multi_test()
    def test_get_last_sibling(self):
        data = [
            ('2', '4'),
            ('1', '4'),
            ('4', '4'),
            ('21', '24'),
            ('24', '24'),
            ('22', '24'),
            ('231', '231'),
        ]
        for desc, expected in data:
            node = self.model.objects.get(desc=desc).get_last_sibling()
            self.assertEqual(node.desc, expected)



    @multi_test()
    def test_get_first_child(self):
        data = [
            ('2', '21'),
            ('21', None),
            ('23', '231'),
            ('231', None),
        ]
        for desc, expected in data:
            node = self.model.objects.get(desc=desc).get_first_child()
            if expected is None:
                self.assertEqual(node, None)
            else:
                self.assertEqual(node.desc, expected)


    @multi_test()
    def test_get_last_child(self):
        data = [
            ('2', '24'),
            ('21', None),
            ('23', '231'),
            ('231', None),
        ]
        for desc, expected in data:
            node = self.model.objects.get(desc=desc).get_last_child()
            if expected is None:
                self.assertEqual(node, None)
            else:
                self.assertEqual(node.desc, expected)


    @multi_test()
    def test_get_ancestors(self):
        data = [
            ('2', []),
            ('21', ['2']),
            ('231', ['2', '23']),
        ]
        for desc, expected in data:
            nodes = self.model.objects.get(desc=desc).get_ancestors()
            self.assertEqual([node.desc for node in nodes], expected)


    @multi_test()
    def test_get_descendants(self):
        data = [
            ('2', ['21', '22', '23', '231', '24']),
            ('23', ['231']),
            ('231', []),
            ('1', []),
            ('4', ['41']),
        ]
        for desc, expected in data:
            nodes = self.model.objects.get(desc=desc).get_descendants()
            self.assertEqual([node.desc for node in nodes], expected)


    @multi_test()
    def test_get_descendant_count(self):
        data = [
            ('2', 5),
            ('23', 1),
            ('231', 0),
            ('1', 0),
            ('4', 1),
        ]
        for desc, expected in data:
            got = self.model.objects.get(desc=desc).get_descendant_count()
            self.assertEqual(got, expected)


    @multi_test()
    def test_is_sibling_of(self):
        data = [
            ('2', '2', True),
            ('2', '1', True),
            ('21', '2', False),
            ('231', '2', False),
            ('22', '23', True),
            ('231', '23', False),
            ('231', '231', True),
        ]
        for desc1, desc2, expected in data:
            node1 = self.model.objects.get(desc=desc1)
            node2 = self.model.objects.get(desc=desc2)
            self.assertEqual(node1.is_sibling_of(node2), expected)



    @multi_test()
    def test_is_child_of(self):
        data = [
            ('2', '2', False),
            ('2', '1', False),
            ('21', '2', True),
            ('231', '2', False),
            ('231', '23', True),
            ('231', '231', False),
        ]
        for desc1, desc2, expected in data:
            node1 = self.model.objects.get(desc=desc1)
            node2 = self.model.objects.get(desc=desc2)
            self.assertEqual(node1.is_child_of(node2), expected)


    @multi_test()
    def test_is_descendant_of(self):
        data = [
            ('2', '2', False),
            ('2', '1', False),
            ('21', '2', True),
            ('231', '2', True),
            ('231', '23', True),
            ('231', '231', False),
        ]
        for desc1, desc2, expected in data:
            node1 = self.model.objects.get(desc=desc1)
            node2 = self.model.objects.get(desc=desc2)
            self.assertEqual(node1.is_descendant_of(node2), expected)


class TestAddChild(TestNonEmptyTree):

    @multi_test()
    def test_add_child_to_leaf(self):
        obj = self.model.objects.get(desc=u'231').add_child(desc='2311')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 1),
                    (u'2311', 4, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_child_to_node(self):
        obj = self.model.objects.get(desc=u'2').add_child(desc='25')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'25', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)



class TestAddSibling(TestNonEmptyTree):


    @multi_test()
    def test_add_sibling_invalid_pos(self):
        method =  self.model.objects.get(desc=u'231').add_sibling
        self.assertRaises(InvalidPosition, method, 'invalid_pos')


    @multi_test()
    def test_add_sibling_missing_nodeorderby(self):
        node_wchildren = self.model.objects.get(desc=u'2')
        method = node_wchildren.add_sibling
        self.assertRaises(MissingNodeOrderBy, method, 'sorted-sibling',
                          desc='aaa')
    
    
    @multi_test()
    def test_add_sibling_last_root(self):
        node_wchildren = self.model.objects.get(desc=u'2')
        obj = node_wchildren.add_sibling('last-sibling', desc='5')
        self.assertEqual(obj.get_depth(), 1)
        self.assertEqual(node_wchildren.get_last_sibling().desc, u'5')

    
    @multi_test()
    def test_add_sibling_last(self):
        node = self.model.objects.get(desc=u'231')
        obj = node.add_sibling('last-sibling', desc='232')
        self.assertEqual(obj.get_depth(), 3)
        self.assertEqual(node.get_last_sibling().desc, u'232')

    
    @multi_test()
    def test_add_sibling_first_root(self):
        node_wchildren = self.model.objects.get(desc=u'2')
        obj = node_wchildren.add_sibling('first-sibling', desc='new')
        self.assertEqual(obj.get_depth(), 1)
        expected = [(u'new', 1, 0),
                    (u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)



    @multi_test()
    def test_add_sibling_first(self):
        node_wchildren = self.model.objects.get(desc=u'23')
        obj = node_wchildren.add_sibling('first-sibling', desc='new')
        self.assertEqual(obj.get_depth(), 2)
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'new', 2, 0),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_sibling_left_root(self):
        node_wchildren = self.model.objects.get(desc=u'2')
        obj = node_wchildren.add_sibling('left', desc='new')
        self.assertEqual(obj.get_depth(), 1)
        expected = [(u'1', 1, 0),
                    (u'new', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_sibling_left(self):
        node_wchildren = self.model.objects.get(desc=u'23')
        obj = node_wchildren.add_sibling('left', desc='new')
        self.assertEqual(obj.get_depth(), 2)
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'new', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_sibling_left_noleft_root(self):
        node = self.model.objects.get(desc=u'1')
        obj = node.add_sibling('left', desc='new')
        self.assertEqual(obj.get_depth(), 1)
        expected = [(u'new', 1, 0),
                    (u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_sibling_left_noleft(self):
        node = self.model.objects.get(desc=u'231')
        obj = node.add_sibling('left', desc='new')
        self.assertEqual(obj.get_depth(), 3)
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 2),
                    (u'new', 3, 0),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_sibling_right_root(self):
        node_wchildren = self.model.objects.get(desc=u'2')
        obj = node_wchildren.add_sibling('right', desc='new')
        self.assertEqual(obj.get_depth(), 1)
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'new', 1, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_sibling_right(self):
        node_wchildren = self.model.objects.get(desc=u'23')
        obj = node_wchildren.add_sibling('right', desc='new')
        self.assertEqual(obj.get_depth(), 2)
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'new', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_sibling_right_noright_root(self):
        node = self.model.objects.get(desc=u'4')
        obj = node.add_sibling('right', desc='new')
        self.assertEqual(obj.get_depth(), 1)
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0),
                    (u'new', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_sibling_right_noright(self):
        node = self.model.objects.get(desc=u'231')
        obj = node.add_sibling('right', desc='new')
        self.assertEqual(obj.get_depth(), 3)
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 2),
                    (u'231', 3, 0),
                    (u'new', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)



class TestDelete(TestNonEmptyTree):

    def setUp(self):
        super(TestDelete, self).setUp()
        for node in self.model.objects.all():
            self.dep_model(node=node).save()

    @multi_test()
    def test_delete_leaf(self):
        self.model.objects.get(desc=u'231').delete()
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_delete_node(self):
        self.model.objects.get(desc=u'23').delete()
        expected = [(u'1', 1, 0),
                    (u'2', 1, 3),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)



    @multi_test()
    def test_delete_root(self):
        self.model.objects.get(desc=u'2').delete()
        expected = [(u'1', 1, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_delete_filter_root_nodes(self):
        self.model.objects.filter(desc__in=('2', '3')).delete()
        expected = [(u'1', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_delete_filter_children(self):
        self.model.objects.filter(
            desc__in=('2', '23', '231')).delete()
        expected = [(u'1', 1, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_delete_nonexistant_nodes(self):
        self.model.objects.filter(desc__in=('ZZZ', 'XXX')).delete()
        self.assertEqual(self.got(), self.unchanged)


    @multi_test()
    def test_delete_same_node_twice(self):
        self.model.objects.filter(
            desc__in=('2', '2')).delete()
        expected = [(u'1', 1, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_delete_all_root_nodes(self):
        self.model.get_root_nodes().delete()
        count = self.model.objects.count()
        self.assertEqual(count, 0)


    @multi_test()
    def test_delete_all_nodes(self):
        self.model.objects.all().delete()
        count = self.model.objects.count()
        self.assertEqual(count, 0)



class TestMoveErrors(TestNonEmptyTree):

    @multi_test()
    def test_move_invalid_pos(self):
        node = self.model.objects.get(desc=u'231')
        self.assertRaises(InvalidPosition, node.move, node, 'invalid_pos')


    @multi_test()
    def test_move_to_descendant(self):
        node = self.model.objects.get(desc=u'2')
        target = self.model.objects.get(desc=u'231')
        self.assertRaises(InvalidMoveToDescendant, node.move, target,
            'first-sibling')

    @multi_test()
    def test_nonsorted_move_in_sorted(self):
        node = self.sorted_model.add_root(val1=3, val2=3, desc='zxy')
        self.assertRaises(InvalidPosition, node.move, node, 'left')


    @multi_test()
    def test_move_missing_nodeorderby(self):
        node = self.model.objects.get(desc=u'231')
        self.assertRaises(MissingNodeOrderBy, node.move, node,
                          'sorted-child')
        self.assertRaises(MissingNodeOrderBy, node.move, node,
                          'sorted-sibling')




class TestMoveLeafRoot(TestNonEmptyTree):

    @multi_test()
    def test_move_leaf_last_sibling_root(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'2'), 'last-sibling')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0),
                    (u'231', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_leaf_first_sibling_root(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'2'), 'first-sibling')
        expected = [(u'231', 1, 0),
                    (u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_leaf_left_sibling_root(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'2'), 'left')
        expected = [(u'1', 1, 0),
                    (u'231', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_leaf_right_sibling_root(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'2'), 'right')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'231', 1, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_leaf_last_child_root(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'2'), 'last-child')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'231', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_leaf_first_child_root(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'2'), 'first-child')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'231', 2, 0),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)] 
        self.assertEqual(self.got(), expected)



class TestMoveLeaf(TestNonEmptyTree):

    @multi_test()
    def test_move_leaf_last_sibling(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'22'), 'last-sibling')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'231', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)



    @multi_test()
    def test_move_leaf_first_sibling(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'22'), 'first-sibling')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'231', 2, 0),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_leaf_left_sibling(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'22'), 'left')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'21', 2, 0),
                    (u'231', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_leaf_right_sibling(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'22'), 'right')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'231', 2, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_leaf_left_sibling_itself(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'231'), 'left')
        self.assertEqual(self.got(), self.unchanged)


    @multi_test()
    def test_move_leaf_last_child(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'22'), 'last-child')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 1),
                    (u'231', 3, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_leaf_first_child(self):
        self.model.objects.get(desc=u'231').move(self.model.objects.get(desc=u'22'), 'first-child')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 1),
                    (u'231', 3, 0),
                    (u'23', 2, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)



class TestMoveBranchRoot(TestNonEmptyTree):

    @multi_test()
    def test_move_branch_first_sibling_root(self):
        self.model.objects.get(desc='4').move(self.model.objects.get(desc='2'), 'first-sibling')
        expected =  [(u'4', 1, 1),
                     (u'41', 2, 0),
                     (u'1', 1, 0),
                     (u'2', 1, 4),
                     (u'21', 2, 0),
                     (u'22', 2, 0),
                     (u'23', 2, 1),
                     (u'231', 3, 0),
                     (u'24', 2, 0),
                     (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_last_sibling_root(self):
        self.model.objects.get(desc='4').move(self.model.objects.get(desc='2'), 'last-sibling')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_left_sibling_root(self):
        self.model.objects.get(desc='4').move(self.model.objects.get(desc='2'), 'left')
        expected = [(u'1', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_right_sibling_root(self):
        self.model.objects.get(desc='4').move(self.model.objects.get(desc='2'), 'right')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_left_noleft_sibling_root(self):
        self.model.objects.get(desc='4').move(self.model.objects.get(desc='2').get_first_sibling(), 'left')
        expected = [(u'4', 1, 1),
                    (u'41', 2, 0),
                    (u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_right_noright_sibling_root(self):
        self.model.objects.get(desc='4').move(self.model.objects.get(desc='2').get_last_sibling(), 'right')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 4),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0),
                    (u'4', 1, 1),
                    (u'41', 2, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_first_child_root(self):
        self.model.objects.get(desc='4').move(self.model.objects.get(desc='2'), 'first-child')
        expected = [(u'1', 1, 0),
                   (u'2', 1, 5),
                   (u'4', 2, 1),
                   (u'41', 3, 0),
                   (u'21', 2, 0),
                   (u'22', 2, 0),
                   (u'23', 2, 1),
                   (u'231', 3, 0),
                   (u'24', 2, 0),
                   (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)



    @multi_test()
    def test_move_branch_last_child_root(self):
        self.model.objects.get(desc='4').move(self.model.objects.get(desc='2'), 'last-child')
        expected = [(u'1', 1, 0),
                    (u'2', 1, 5),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'4', 2, 1),
                    (u'41', 3, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)



class TestMoveBranch(TestNonEmptyTree):

    @multi_test()
    def test_move_branch_first_sibling(self):
        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),
                    (u'41', 3, 0),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_last_sibling(self):
        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),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'4', 2, 1),
                    (u'41', 3, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_left_sibling(self):
        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),
                    (u'22', 2, 0),
                    (u'4', 2, 1),
                    (u'41', 3, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_right_sibling(self):
        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),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'4', 2, 1),
                    (u'41', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_left_noleft_sibling(self):
        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),
                    (u'41', 3, 0),
                    (u'21', 2, 0),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_right_noright_sibling(self):
        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),
                    (u'22', 2, 0),
                    (u'23', 2, 1),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'4', 2, 1),
                    (u'41', 3, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_left_itself_sibling(self):
        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):
        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),
                    (u'22', 2, 0),
                    (u'23', 2, 2),
                    (u'4', 3, 1),
                    (u'41', 4, 0),
                    (u'231', 3, 0),
                    (u'24', 2, 0),
                    (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_move_branch_last_child(self):
        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),
                     (u'22', 2, 0),
                     (u'23', 2, 2),
                     (u'231', 3, 0),
                     (u'4', 3, 1),
                     (u'41', 4, 0),
                     (u'24', 2, 0),
                     (u'3', 1, 0)]
        self.assertEqual(self.got(), expected)



class TestTreeSorted(TestTreeBase):

    def got(self):
        return [(o.val1, o.val2, o.desc, o.get_depth(), o.get_children_count())
                 for o in self.sorted_model.get_tree()]


    @multi_test()
    def test_add_root_sorted(self):
        self.sorted_model.add_root(val1=3, val2=3, desc='zxy')
        self.sorted_model.add_root(val1=1, val2=4, desc='bcd')
        self.sorted_model.add_root(val1=2, val2=5, desc='zxy')
        self.sorted_model.add_root(val1=3, val2=3, desc='abc')
        self.sorted_model.add_root(val1=4, val2=1, desc='fgh')
        self.sorted_model.add_root(val1=3, val2=3, desc='abc')
        self.sorted_model.add_root(val1=2, val2=2, desc='qwe')
        self.sorted_model.add_root(val1=3, val2=2, desc='vcx')
        expected = [(1, 4, u'bcd', 1, 0),
                    (2, 2, u'qwe', 1, 0),
                    (2, 5, u'zxy', 1, 0),
                    (3, 2, u'vcx', 1, 0),
                    (3, 3, u'abc', 1, 0),
                    (3, 3, u'abc', 1, 0),
                    (3, 3, u'zxy', 1, 0),
                    (4, 1, u'fgh', 1, 0)]
        self.assertEqual(self.got(), expected)


    @multi_test()
    def test_add_child_sorted(self):
        root = self.sorted_model.add_root(val1=0, val2=0, desc='aaa')
        root.add_child(val1=3, val2=3, desc='zxy')
        root.add_child(val1=1, val2=4, desc='bcd')
        root.add_child(val1=2, val2=5, desc='zxy')
        root.add_child(val1=3, val2=3, desc='abc')
        root.add_child(val1=4, val2=1, desc='fgh')
        root.add_child(val1=3, val2=3, desc='abc')
        root.add_child(val1=2, val2=2, desc='qwe')
        root.add_child(val1=3, val2=2, desc='vcx')
        expected = [(0, 0, u'aaa', 1, 8),
                    (1, 4, u'bcd', 2, 0),
                    (2, 2, u'qwe', 2, 0),
                    (2, 5, u'zxy', 2, 0),
                    (3, 2, u'vcx', 2, 0),
                    (3, 3, u'abc', 2, 0),
                    (3, 3, u'abc', 2, 0),
                    (3, 3, u'zxy', 2, 0),
                    (4, 1, u'fgh', 2, 0)]
        self.assertEqual(self.got(), expected)



    @multi_test()
    def test_move_sorted(self):
        self.sorted_model.add_root(val1=3, val2=3, desc='zxy')
        self.sorted_model.add_root(val1=1, val2=4, desc='bcd')
        self.sorted_model.add_root(val1=2, val2=5, desc='zxy')
        self.sorted_model.add_root(val1=3, val2=3, desc='abc')
        self.sorted_model.add_root(val1=4, val2=1, desc='fgh')
        self.sorted_model.add_root(val1=3, val2=3, desc='abc')
        self.sorted_model.add_root(val1=2, val2=2, desc='qwe')
        self.sorted_model.add_root(val1=3, val2=2, desc='vcx')
        root_nodes = self.sorted_model.get_root_nodes()
        target = root_nodes[0]
        for node in root_nodes[1:]:

            # because raw queries don't update django objects
            if self.sorted_model == NS_TestNodeSorted:
                node = self.sorted_model.objects.get(pk=node.id)
                target = self.sorted_model.objects.get(pk=target.id)

            node.move(target, 'sorted-child')
        expected = [(1, 4, u'bcd', 1, 7),
                    (2, 2, u'qwe', 2, 0),
                    (2, 5, u'zxy', 2, 0),
                    (3, 2, u'vcx', 2, 0),
                    (3, 3, u'abc', 2, 0),
                    (3, 3, u'abc', 2, 0),
                    (3, 3, u'zxy', 2, 0),
                    (4, 1, u'fgh', 2, 0)]
        self.assertEqual(self.got(), expected)


class TestMP_TreeAlphabet(TestCase):

    def test_alphabet(self):
        if not os.getenv('TREEBEARD_TEST_ALPHABET', False):
            # run this test only if the enviroment variable is set
            return
        basealpha = numconv.BASE85
        got_err = False
        last_good = None
        for alphabetlen in range(35, len(basealpha)+1):
            alphabet = basealpha[0:alphabetlen]
            expected = [alphabet[0]+char for char in alphabet[1:]]
            expected.extend([alphabet[1]+char for char in alphabet])
            expected.append(alphabet[2]+alphabet[0])

            # remove all nodes
            MP_TestNodeAlphabet.objects.all().delete()

            # change the model's alphabet
            MP_TestNodeAlphabet.alphabet = alphabet

            # insert root nodes
            for pos in range(len(alphabet)*2):
                try:
                    MP_TestNodeAlphabet.add_root(numval=pos)
                except:
                    got_err = True
                    break
            if not got_err:
                got = [obj.path for obj in MP_TestNodeAlphabet.objects.all()]
                if got != expected:
                    got_err = True
            if got_err:
                break
            else:
                last_good = alphabet
        if last_good:
            print '\nThe best BASE85 based alphabet for your setup is: %s' \
                % (last_good,)
        else:
            # this should never happen
            self.fail("Couldn't find a default working alphabet for your setup!")



class TestHelpers(TestTreeBase):

    def setUp(self):
        for model in (MP_TestNode, AL_TestNode, NS_TestNode):
            model.load_bulk(BASE_DATA)
            for node in model.get_root_nodes():
                model.load_bulk(BASE_DATA, node)
            model.add_root(desc='5')

    @multi_test()
    def test_descendants_group_count_root(self):
        expected = [(o.desc, o.get_descendant_count())
                    for o in self.model.get_root_nodes()]
        got = [(o.desc, o.descendants_count)
               for o in self.model.get_descendants_group_count()]
        self.assertEqual(got, expected)


    @multi_test()
    def test_descendants_group_count_node(self):
        parent = self.model.get_root_nodes().get(desc='2')
        expected = [(o.desc, o.get_descendant_count())
                    for o in parent.get_children()]
        got = [(o.desc, o.descendants_count)
               for o in self.model.get_descendants_group_count(parent)]
        self.assertEqual(got, expected)



class TestMP_TreeSortedAutoNow(TestCase):
    """
    The sorting mechanism used by treebeard when adding a node can fail if the
    ordering is using an "auto_now" field
    """

    def test_sorted_by_autonow_workaround(self):
        """
        workaround
        """
        import datetime
        for i in range(1, 5):
            MP_TestNodeSortedAutoNow.add_root(desc='node%d' % (i,),
                                             created=datetime.datetime.now())

    def test_sorted_by_autonow_FAIL(self):
        """
        This test asserts that we have a problem.
        fix this, somehow
        """
        MP_TestNodeSortedAutoNow.add_root(desc='node1')
        self.assertRaises(ValueError, MP_TestNodeSortedAutoNow.add_root,
                          desc='node2')



class TestMP_TreeStepOverflow(TestCase):
    
    def test_add_root(self):
        method = MP_TestNodeSmallStep.add_root
        for i in range(1, 10):
            method()
        self.assertRaises(PathOverflow, method)

    def test_add_child(self):
        root = MP_TestNodeSmallStep.add_root()
        method = root.add_child
        for i in range(1, 10):
            method()
        self.assertRaises(PathOverflow, method)

    def test_add_sibling(self):
        root = MP_TestNodeSmallStep.add_root()
        for i in range(1, 10):
            root.add_child()
        method = root.get_last_child().add_sibling
        positions = ('first-sibling', 'left', 'right', 'last-sibling')
        for pos in positions:
            self.assertRaises(PathOverflow, method, pos)

    def test_move(self):
        root = MP_TestNodeSmallStep.add_root()
        for i in range(1, 10):
            root.add_child()
        newroot = MP_TestNodeSmallStep.add_root()
        targets = [(root, ['first-child', 'last-child']),
                   (root.get_first_child(), ['first-sibling',
                                            'left',
                                            'right',
                                            'last-sibling'])]
        for target, positions in targets:
            for pos in positions:
                self.assertRaises(PathOverflow, newroot.move, target, pos)



class TestMP_TreeShortPath(TestCase):
    """
    Here we test a tree with a very small path field (max_length=4) and a
    steplen of 1
    """
    def test_short_path(self):
        obj = MP_TestNodeShortPath.add_root().add_child().add_child().add_child()
        self.assertRaises(PathOverflow, obj.add_child)



class TestMP_TreeFindProblems(TestTreeBase):

    def test_find_problems(self):
        model = MP_TestNodeAlphabet
        model.alphabet = '01234'
        model(path='01', depth=1, numchild=0, numval=0).save()
        model(path='1', depth=1, numchild=0, numval=0).save()
        model(path='111', depth=1, numchild=0, numval=0).save()
        model(path='abcd', depth=1, numchild=0, numval=0).save()
        model(path='qa#$%!', depth=1, numchild=0, numval=0).save()
        model(path='0201', depth=2, numchild=0, numval=0).save()
        model(path='020201', depth=3, numchild=0, numval=0).save()
        model(path='03', depth=1, numchild=2, numval=0).save()
        model(path='0301', depth=2, numchild=0, numval=0).save()
        model(path='030102', depth=3, numchild=10, numval=0).save()
        model(path='04', depth=10, numchild=1, numval=0).save()
        model(path='0401', depth=20, numchild=0, numval=0).save()


        evil_chars, bad_steplen, orphans, wrong_depth, wrong_numchild = \
                                                        model.find_problems()
        self.assertEqual(['abcd', 'qa#$%!'],
            [o.path for o in model.objects.filter(id__in=evil_chars)])
        self.assertEqual(['1', '111'],
            [o.path for o in model.objects.filter(id__in=bad_steplen)])
        self.assertEqual(['0201', '020201'],
            [o.path for o in model.objects.filter(id__in=orphans)])
        self.assertEqual(['03', '0301', '030102'],
            [o.path for o in model.objects.filter(id__in=wrong_numchild)])
        self.assertEqual(['04', '0401'],
            [o.path for o in model.objects.filter(id__in=wrong_depth)])



class TestMP_TreeFix(TestTreeBase):
    
    def setUp(self):
        super(TestMP_TreeFix, self).setUp()
        self.expected_no_holes = {
            MP_TestNodeShortPath: [
                (u'1', u'b', 1, 2),
                (u'11', u'u', 2, 1),
                (u'111', u'i', 3, 1),
                (u'1111', u'e', 4, 0),
                (u'12', u'o', 2, 0),
                (u'2', u'd', 1, 0),
                (u'3', u'g', 1, 0),
                (u'4', u'a', 1, 4),
                (u'41', u'a', 2, 0),
                (u'42', u'a', 2, 0),
                (u'43', u'u', 2, 1),
                (u'431', u'i', 3, 1),
                (u'4311', u'e', 4, 0),
                (u'44', u'o', 2, 0)],
            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'14', u'u', 2, 1),
                (u'141', u'i', 3, 1), 
                (u'1411', u'e', 4, 0),
                (u'2', u'b', 1, 2),
                (u'21', u'o', 2, 0),
                (u'22', u'u', 2, 1),
                (u'221', u'i', 3, 1),
                (u'2211', u'e', 4, 0),
                (u'3', u'd', 1, 0),
                (u'4', u'g', 1, 0)]}
        self.expected_with_holes = {
            MP_TestNodeShortPath: [
                (u'1', u'b', 1L, 2L),
                (u'13', u'u', 2L, 1L),
                (u'134', u'i', 3L, 1L),
                (u'1343', u'e', 4L, 0L),
                (u'14', u'o', 2L, 0L),
                (u'2', u'd', 1L, 0L),
                (u'3', u'g', 1L, 0L),
                (u'4', u'a', 1L, 4L),
                (u'41', u'a', 2L, 0L),
                (u'42', u'a', 2L, 0L),
                (u'43', u'u', 2L, 1L),
                (u'434', u'i', 3L, 1L),
                (u'4343', u'e', 4L, 0L),
                (u'44', u'o', 2L, 0L)],
            MP_TestSortedNodeShortPath: [
                (u'1', u'b', 1L, 2L),
                (u'13', u'u', 2L, 1L),
                (u'134', u'i', 3L, 1L),
                (u'1343', u'e', 4L, 0L),
                (u'14', u'o', 2L, 0L),
                (u'2', u'd', 1L, 0L),
                (u'3', u'g', 1L, 0L),
                (u'4', u'a', 1L, 4L),
                (u'41', u'a', 2L, 0L),
                (u'42', u'a', 2L, 0L),
                (u'43', u'u', 2L, 1L),
                (u'434', u'i', 3L, 1L),
                (u'4343', u'e', 4L, 0L),
                (u'44', u'o', 2L, 0L)]}

    def got(self, model):
        return [(o.path, o.desc, o.get_depth(), o.get_children_count())
                for o in model.get_tree()]
    
    def add_broken_test_data(self, model):
        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()
        model(path='134', depth=321, numchild=543, desc='i').save()
        model(path='1343', depth=321, numchild=543, desc='e').save()
        model(path='42', depth=1, numchild=1, desc='a').save()
        model(path='43', depth=1000, numchild=0, desc='u').save()
        model(path='44', depth=4, numchild=500, desc='o').save()
        model(path='434', depth=321, numchild=543, desc='i').save()
        model(path='4343', depth=321, numchild=543, desc='e').save()
        model(path='41', depth=1, numchild=1, desc='a').save()
        model(path='3', depth=221, numchild=322, desc='g').save()
        model(path='1', depth=10, numchild=3, desc='b').save()
        model(path='2', depth=10, numchild=3, desc='d').save()

    def test_fix_tree_non_destructive(self):

        for model in (MP_TestNodeShortPath, MP_TestSortedNodeShortPath):
            self.add_broken_test_data(model)
            model.fix_tree(destructive=False)
            self.assertEqual(self.got(model), self.expected_with_holes[model])
            model.find_problems()

    def test_fix_tree_destructive(self):

        for model in (MP_TestNodeShortPath, MP_TestSortedNodeShortPath):
            self.add_broken_test_data(model)
            model.fix_tree(destructive=True)
            self.assertEqual(self.got(model), self.expected_no_holes[model])
            model.find_problems()


class TestIssue14(TestCase):
    # http://code.google.com/p/django-treebeard/issues/detail?id=14

    def test_issue_14(self):
        if not HAS_DJANGO_AUTH:
            self.fail('this test needs django.contrib.auth in INSTALLED_APPS')

        # Using AnonymousUser() in the querysets will expose non-treebeard
        # related problems in Django 1.0
        #
        # Postgres:
        #   ProgrammingError: can't adapt
        # SQLite:
        #   InterfaceError: Error binding parameter 4 - probably unsupported
        #   type.
        # MySQL compared a string to an integer field:
        #   `treebeard_mp_testissue14_users`.`user_id` = 'AnonymousUser'
        #
        # Using a None field instead works (will be translated to IS NULL).
        #
        # anonuserobj = AnonymousUser()
        anonuserobj = None

        def qs_check(qs, expected):
            self.assertEqual(
                [o.name for o in qs],
                expected
            )

        user = User.objects.create_user('test_user', 'test@example.com',
                                        'testpasswd')
        user.save()
        root = MP_TestIssue14.add_root(name="the root node")

        first = root.add_child(name="first")
        second = root.add_child(name="second")

        qs_check(root.get_children(), ['first', 'second'])
        qs_check(root.get_children().filter(Q(name="first")), ['first'])
        qs_check(root.get_children().filter(Q(users=user)), [])
        qs_check(
            root.get_children().filter(Q(name="first") | Q(users=user)),
            ['first'])
        
        user = anonuserobj
        qs_check(
            root.get_children().filter(Q(name="first") | Q(users=user)),
            ['first', 'second'])

        user = User.objects.get(username="test_user")
        second.users.add(user)

        qs_check(
            root.get_children().filter(Q(name="first") | Q(users=user)),
            ['first', 'second'])

        user = anonuserobj
        qs_check(
            root.get_children().filter(Q(name="first") | Q(users=user)),
            ['first'])

#~

Show details Hide details

Change log

r99 by gpicon on Jun 14, 2009 Diff

Added a new (safer and faster but less
comprehensive) MP_Node.fix_tree()
approach.

Updated tests and docs.

Go to:

Project members, sign in to write a code review

Older revisions

r98 by gpicon on Jun 14, 2009 Diff

Added 2 new checks in
MP_Node.find_problems():

                  4. a list of ids of
nodes with the wrong depth value for
...

r97 by gpicon on Jun 14, 2009 Diff

Removing unnecesary debugging junk in
test model MP_TestIssue14

r96 by gpicon on Jun 14, 2009 Diff

Added test to expose a problem
reported in  Issue 14 . The test
confirmed that there is no bug in
treebeard triggering the problem.

...

All revisions of this file

File info

Size: 66060 bytes, 2026 lines

View raw file