160 lines
5.0 KiB
Python
160 lines
5.0 KiB
Python
# -*- coding: utf-8 -*-
|
|
|
|
import nilmdb
|
|
from nilmdb.utils.printf import *
|
|
|
|
from nose.tools import *
|
|
from nose.tools import assert_raises
|
|
|
|
from nilmdb.rbtree import RBTree, RBNode
|
|
|
|
from testutil.helpers import *
|
|
import unittest
|
|
|
|
# set to False to skip live renders
|
|
do_live_renders = False
|
|
def render(tree, description = "", live = True):
|
|
import testutil.renderdot as renderdot
|
|
r = renderdot.RBTreeRenderer(tree)
|
|
return r.render(description, live and do_live_renders)
|
|
|
|
class TestRBTree:
|
|
def test_rbtree(self):
|
|
rb = RBTree()
|
|
rb.insert(RBNode(10000, 10001))
|
|
rb.insert(RBNode(10004, 10007))
|
|
rb.insert(RBNode(10001, 10002))
|
|
# There was a typo that gave the RBTree a loop in this case.
|
|
# Verify that the dot isn't too big.
|
|
s = render(rb, live = False)
|
|
assert(len(s.splitlines()) < 30)
|
|
|
|
def test_rbtree_big(self):
|
|
import random
|
|
random.seed(1234)
|
|
|
|
# make a set of 100 intervals, inserted in order
|
|
rb = RBTree()
|
|
j = 100
|
|
for i in xrange(j):
|
|
rb.insert(RBNode(i, i+1))
|
|
render(rb, "in-order insert")
|
|
|
|
# remove about half of them
|
|
for i in random.sample(xrange(j),j):
|
|
if random.randint(0,1):
|
|
rb.delete(rb.find(i, i+1))
|
|
render(rb, "in-order insert, random delete")
|
|
|
|
# make a set of 100 intervals, inserted at random
|
|
rb = RBTree()
|
|
j = 100
|
|
for i in random.sample(xrange(j),j):
|
|
rb.insert(RBNode(i, i+1))
|
|
render(rb, "random insert")
|
|
|
|
# remove about half of them
|
|
for i in random.sample(xrange(j),j):
|
|
if random.randint(0,1):
|
|
rb.delete(rb.find(i, i+1))
|
|
render(rb, "random insert, random delete")
|
|
|
|
# in-order insert of 50 more
|
|
for i in xrange(50):
|
|
rb.insert(RBNode(i+500, i+501))
|
|
render(rb, "random insert, random delete, in-order insert")
|
|
|
|
def test_rbtree_basics(self):
|
|
rb = RBTree()
|
|
vals = [ 7, 14, 1, 2, 8, 11, 5, 15, 4]
|
|
for n in vals:
|
|
rb.insert(RBNode(n, n))
|
|
|
|
# stringify
|
|
s = ""
|
|
for node in rb:
|
|
s += str(node)
|
|
in_("[node (None) 1", s)
|
|
eq_(str(rb.nil), "[node nil]")
|
|
|
|
# inorder traversal, successor and predecessor
|
|
last = 0
|
|
for node in rb:
|
|
assert(node.start > last)
|
|
last = node.start
|
|
successor = rb.successor(node)
|
|
if successor:
|
|
assert(rb.predecessor(successor) is node)
|
|
predecessor = rb.predecessor(node)
|
|
if predecessor:
|
|
assert(rb.successor(predecessor) is node)
|
|
|
|
# Delete node not in the tree
|
|
with assert_raises(AttributeError):
|
|
rb.delete(RBNode(1,2))
|
|
|
|
# Delete all nodes!
|
|
for node in rb:
|
|
rb.delete(node)
|
|
|
|
# Build it up again, make sure it matches
|
|
for n in vals:
|
|
rb.insert(RBNode(n, n))
|
|
s2 = ""
|
|
for node in rb:
|
|
s2 += str(node)
|
|
assert(s == s2)
|
|
|
|
def test_rbtree_find(self):
|
|
# Get a little bit of coverage for some overlapping cases,
|
|
# even though the class doesn't fully support it.
|
|
rb = RBTree()
|
|
nodes = [ RBNode(1, 5), RBNode(1, 10), RBNode(1, 15) ]
|
|
for n in nodes:
|
|
rb.insert(n)
|
|
assert(rb.find(1, 5) is nodes[0])
|
|
assert(rb.find(1, 10) is nodes[1])
|
|
assert(rb.find(1, 15) is nodes[2])
|
|
|
|
def test_rbtree_find_leftright(self):
|
|
# Now let's get some ranges in there
|
|
rb = RBTree()
|
|
vals = [ 7, 14, 1, 2, 8, 11, 5, 15, 4]
|
|
for n in vals:
|
|
rb.insert(RBNode(n*10, n*10+5))
|
|
|
|
# Check find_end_left, find_right_start
|
|
for i in range(160):
|
|
left = rb.find_left_end(i)
|
|
right = rb.find_right_start(i)
|
|
if left:
|
|
# endpoint should be more than i
|
|
assert(left.end >= i)
|
|
# all earlier nodes should have a lower endpoint
|
|
for node in rb:
|
|
if node is left:
|
|
break
|
|
assert(node.end < i)
|
|
if right:
|
|
# startpoint should be less than i
|
|
assert(right.start <= i)
|
|
# all later nodes should have a higher startpoint
|
|
for node in reversed(list(rb)):
|
|
if node is right:
|
|
break
|
|
assert(node.start > i)
|
|
|
|
def test_rbtree_intersect(self):
|
|
# Fill with some ranges
|
|
rb = RBTree()
|
|
rb.insert(RBNode(10,20))
|
|
rb.insert(RBNode(20,25))
|
|
rb.insert(RBNode(30,40))
|
|
# Just a quick test; test_interval will do better.
|
|
eq_(len(list(rb.intersect(1,100))), 3)
|
|
eq_(len(list(rb.intersect(10,20))), 1)
|
|
eq_(len(list(rb.intersect(5,15))), 1)
|
|
eq_(len(list(rb.intersect(15,15))), 1)
|
|
eq_(len(list(rb.intersect(20,21))), 1)
|
|
eq_(len(list(rb.intersect(19,21))), 2)
|