import math
import random
import unittest

from trees_lab import balanced_tree, catalogue_report, inorder, insert, levels


class CatalogueTests(unittest.TestCase):
    def test_worked_example(self):
        result = catalogue_report([10, 20, 30, 40, 50], 20, 45, 3, (10, 20))
        self.assertEqual(result, {"ordered": [10, 20, 30, 40, 50],
            "height_before": 5, "height_after": 3,
            "levels": [[30], [20, 50], [10, 40]],
            "in_range": [20, 30, 40], "kth": 30, "lca": 20})

    def test_single_book(self):
        result = catalogue_report([7], 7, 7, 1, (7, 7))
        self.assertEqual((result["lca"], result["in_range"], result["height_after"]),
                         (7, [7], 1))

    def test_range_outside_catalogue(self):
        result = catalogue_report([2, 1, 3], 8, 10, 3, (1, 3))
        self.assertEqual(result["in_range"], [])
        self.assertEqual(result["kth"], 3)

    def test_duplicate_id_rejected(self):
        with self.assertRaises(ValueError):
            catalogue_report([4, 4], 0, 10, 1, (4, 4))

    def test_invalid_queries(self):
        for ids, low, high, k, pair in [([], 0, 1, 1, (0, 0)),
                ([1], 2, 1, 1, (1, 1)), ([1], 0, 2, 0, (1, 1)),
                ([1], 0, 2, 2, (1, 1)), ([1], 0, 2, 1, (1, 9))]:
            with self.subTest(ids=ids, k=k, pair=pair), self.assertRaises(ValueError):
                catalogue_report(ids, low, high, k, pair)

    def test_rebuild_uses_balanced_linked_nodes(self):
        root = balanced_tree(list(range(60)))
        def inspect(node, lower, upper):
            if node is None:
                return 0
            self.assertTrue(lower < node.key < upper)
            left = inspect(node.left, lower, node.key)
            right = inspect(node.right, node.key, upper)
            self.assertLessEqual(abs(left - right), 1)
            return 1 + max(left, right)
        self.assertEqual(inspect(root, -1, 60), 6)
        self.assertEqual(inorder(root), list(range(60)))

    def test_long_skewed_input_does_not_overflow_recursion(self):
        result = catalogue_report(list(range(1200)), 1198, 1199, 1200, (0, 1199))
        self.assertEqual(result["height_before"], 1200)
        self.assertEqual(result["height_after"], 11)

    def test_random_queries_against_sorted_oracle(self):
        rng = random.Random(71)
        for _ in range(80):
            ids = rng.sample(range(-100, 101), rng.randint(1, 40))
            ordered = sorted(ids)
            low, high = sorted(rng.sample(range(-110, 111), 2))
            k = rng.randint(1, len(ids))
            result = catalogue_report(ids, low, high, k, (ids[0], ids[-1]))
            self.assertEqual(result["ordered"], ordered)
            self.assertEqual(result["in_range"], [x for x in ordered if low <= x <= high])
            self.assertEqual(result["kth"], ordered[k - 1])
            self.assertEqual(result["height_after"], math.ceil(math.log2(len(ids) + 1)))


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