<filename>algo/redblack_test.py<gh_stars>1-10
import unittest
import redblack


def _create_tree():
    root = redblack.RedBlackNode(500, 'e', redblack.BLACK)

    redblack._insert_at_node(root, 200, 'b', redblack.RED)
    redblack._insert_at_node(root.left, 100, 'a', redblack.BLACK)
    redblack._insert_at_node(root.left, 300, 'c', redblack.BLACK)

    redblack._insert_at_node(root, 800, 'g', redblack.RED)
    redblack._insert_at_node(root.right, 700, 'f', redblack.BLACK)
    redblack._insert_at_node(root.right, 900, 'h', redblack.BLACK)

    return root


def _insert_tree():
    tree = redblack.RedBlackTree()
    tree.insert(100, 'a')
    tree.insert(200, 'b')
    tree.insert(300, 'c')
    tree.insert(500, 'e')
    tree.insert(700, 'f')
    tree.insert(800, 'g')
    tree.insert(900, 'h')

    return tree


class TestRedBlack(unittest.TestCase):
    def test_create_tree_and(self):
        tree = _create_tree()
        self.assertEqual(tree.key, 500)
        self.assertEqual(tree.left.left.key, 100)
        self.assertEqual(tree.right.right.key, 900)

    def test_validate_redblack_tree(self):
        tree = _create_tree()
        self.assertTrue(redblack._validate_redblack_tree(tree))

    def test_find_closest_ancestor_by_key(self):
        tree = _create_tree()
        found = redblack._find_closest_ancestor_by_key(tree, 750)
        self.assertEqual(found.key, 700)

    def test_find_sibling(self):
        tree = _create_tree()
        self.assertEqual(redblack._find_sibling(tree.left.right).key, 100)
        self.assertEqual(redblack._find_sibling(tree), None)

    def test_get_node_color(self):
        tree = _create_tree()
        self.assertEqual(redblack._get_node_color(tree.left.right),
                         redblack.BLACK)

    def test_flip_color(self):
        node = redblack.RedBlackNode(1)
        redblack._flip_color(node)
        self.assertEqual(node.color, redblack.BLACK)

    def test_left_rotation(self):
        tree = _create_tree()
        redblack._left_rotation(tree.left)
        self.assertEqual(tree.left.left.left.key, 100)  # rotated

        tree = _create_tree()
        redblack._left_rotation(tree)
        self.assertEqual(tree.parent.parent, None)  # rotated, top of the tree
        self.assertEqual(tree.parent.key, 800)
        self.assertEqual(tree.left.key, 200)

        tree = _create_tree()
        self.assertRaises(redblack.NullNodeError,
                          redblack._left_rotation,
                          tree.left.right)  # not possible

    def test_right_rotation(self):
        tree = _create_tree()
        redblack._right_rotation(tree.left)
        self.assertEqual(tree.left.right.right.key, 300)  # rotated

        tree = _create_tree()
        redblack._right_rotation(tree)
        self.assertEqual(tree.parent.parent, None)  # rotated, top of the tree
        self.assertEqual(tree.parent.key, 200)
        self.assertEqual(tree.left.key, 300)

        tree = _create_tree()
        self.assertRaises(redblack.NullNodeError,
                          redblack._right_rotation,
                          tree.right.left)  # not possible

    def test_find_node_by_key(self):
        tree = _create_tree()
        self.assertEqual(redblack._find_node_by_key(tree, 700).key,
                         700)  # findable
        self.assertRaises(KeyError,
                          redblack._find_node_by_key,
                          tree,
                          750)  # not findable
        self.assertRaises(KeyError,
                          redblack._find_node_by_key,
                          None,
                          700)  # no tree provided

    def test_red_uncle_recolor(self):
        tree = _create_tree()
        tree.right.right.color = redblack.RED
        redblack._red_uncle_recolor(tree.right)
        self.assertEqual(tree.color, redblack.BLACK)
        self.assertEqual(tree.left.color, redblack.BLACK)
        self.assertEqual(tree.right.color, redblack.BLACK)

    def test_describe(self):
        tree = _insert_tree()
        result = tree._describe()
        self.assertEqual(result['right']['left']['key'], 300)

    def test_insert_and_get(self):
        tree = _insert_tree()
        self.assertEqual(tree.get_content(800), 'g')
        self.assertRaises(KeyError,
                          tree.get_content,
                          600)

    def test_insert_and_validate(self):
        tree = _insert_tree()
        self.assertTrue(tree._validate())

    def test_copy_node(self):
        tree = _create_tree()
        redblack._copy_node(tree.right.right, tree.right)
        self.assertEqual(tree.right.right.key, tree.right.key)
        self.assertEqual(tree.right.right.content, tree.right.content)
        self.assertNotEqual(tree.right.right.parent, tree.right.parent)


if __name__ == '__main__':
    unittest.main()

<filename>algo/redblack_test.py<gh_stars>1-10
import unittest
import redblack


def _create_tree():
    root = redblack.RedBlackNode(500, 'e', redblack.BLACK)

    redblack._insert_at_node(root, 200, 'b', redblack.RED)
    redblack._insert_at_node(root.left, 100, 'a', redblack.BLACK)
    redblack._insert_at_node(root.left, 300, 'c', redblack.BLACK)

    redblack._insert_at_node(root, 800, 'g', redblack.RED)
    redblack._insert_at_node(root.right, 700, 'f', redblack.BLACK)
    redblack._insert_at_node(root.right, 900, 'h', redblack.BLACK)

    return root


def _insert_tree():
    tree = redblack.RedBlackTree()
    tree.insert(100, 'a')
    tree.insert(200, 'b')
    tree.insert(300, 'c')
    tree.insert(500, 'e')
    tree.insert(700, 'f')
    tree.insert(800, 'g')
    tree.insert(900, 'h')

    return tree


class TestRedBlack(unittest.TestCase):
    def test_create_tree_and(self):
        tree = _create_tree()
        self.assertEqual(tree.key, 500)
        self.assertEqual(tree.left.left.key, 100)
        self.assertEqual(tree.right.right.key, 900)

    def test_validate_redblack_tree(self):
        tree = _create_tree()
        self.assertTrue(redblack._validate_redblack_tree(tree))

    def test_find_closest_ancestor_by_key(self):
        tree = _create_tree()
        found = redblack._find_closest_ancestor_by_key(tree, 750)
        self.assertEqual(found.key, 700)

    def test_find_sibling(self):
        tree = _create_tree()
        self.assertEqual(redblack._find_sibling(tree.left.right).key, 100)
        self.assertEqual(redblack._find_sibling(tree), None)

    def test_get_node_color(self):
        tree = _create_tree()
        self.assertEqual(redblack._get_node_color(tree.left.right),
                         redblack.BLACK)

    def test_flip_color(self):
        node = redblack.RedBlackNode(1)
        redblack._flip_color(node)
        self.assertEqual(node.color, redblack.BLACK)

    def test_left_rotation(self):
        tree = _create_tree()
        redblack._left_rotation(tree.left)
        self.assertEqual(tree.left.left.left.key, 100)  # rotated

        tree = _create_tree()
        redblack._left_rotation(tree)
        self.assertEqual(tree.parent.parent, None)  # rotated, top of the tree
        self.assertEqual(tree.parent.key, 800)
        self.assertEqual(tree.left.key, 200)

        tree = _create_tree()
        self.assertRaises(redblack.NullNodeError,
                          redblack._left_rotation,
                          tree.left.right)  # not possible

    def test_right_rotation(self):
        tree = _create_tree()
        redblack._right_rotation(tree.left)
        self.assertEqual(tree.left.right.right.key, 300)  # rotated

        tree = _create_tree()
        redblack._right_rotation(tree)
        self.assertEqual(tree.parent.parent, None)  # rotated, top of the tree
        self.assertEqual(tree.parent.key, 200)
        self.assertEqual(tree.left.key, 300)

        tree = _create_tree()
        self.assertRaises(redblack.NullNodeError,
                          redblack._right_rotation,
                          tree.right.left)  # not possible

    def test_find_node_by_key(self):
        tree = _create_tree()
        self.assertEqual(redblack._find_node_by_key(tree, 700).key,
                         700)  # findable
        self.assertRaises(KeyError,
                          redblack._find_node_by_key,
                          tree,
                          750)  # not findable
        self.assertRaises(KeyError,
                          redblack._find_node_by_key,
                          None,
                          700)  # no tree provided

    def test_red_uncle_recolor(self):
        tree = _create_tree()
        tree.right.right.color = redblack.RED
        redblack._red_uncle_recolor(tree.right)
        self.assertEqual(tree.color, redblack.BLACK)
        self.assertEqual(tree.left.color, redblack.BLACK)
        self.assertEqual(tree.right.color, redblack.BLACK)

    def test_describe(self):
        tree = _insert_tree()
        result = tree._describe()
        self.assertEqual(result['right']['left']['key'], 300)

    def test_insert_and_get(self):
        tree = _insert_tree()
        self.assertEqual(tree.get_content(800), 'g')
        self.assertRaises(KeyError,
                          tree.get_content,
                          600)

    def test_insert_and_validate(self):
        tree = _insert_tree()
        self.assertTrue(tree._validate())

    def test_copy_node(self):
        tree = _create_tree()
        redblack._copy_node(tree.right.right, tree.right)
        self.assertEqual(tree.right.right.key, tree.right.key)
        self.assertEqual(tree.right.right.content, tree.right.content)
        self.assertNotEqual(tree.right.right.parent, tree.right.parent)


if __name__ == '__main__':
    unittest.main()

# rotated # rotated, top of the tree # not possible # rotated # rotated, top of the tree # not possible # findable # not findable # no tree provided