import random
import unittest

from practice.sorting_lab import bubble_sort, merge_sort, quick_sort, lower_bound, upper_bound, catalog_report


class SortingLabTests(unittest.TestCase):
    def test_worked_report(self):
        report = catalog_report([("A", 40), ("B", 20), ("C", 40), ("D", 10)], [40, 25], 20)
        self.assertEqual(report["ordered"], [("D", 10), ("B", 20), ("A", 40), ("C", 40)])
        self.assertEqual(report["matches"], [{"price": 40, "ids": ["A", "C"]}, {"price": 25, "ids": []}])
        self.assertEqual(report["affordable"], ["D", "B"])

    def test_empty_and_single(self):
        self.assertEqual(catalog_report([], [0], 0)["matches"], [{"price": 0, "ids": []}])
        self.assertEqual(catalog_report([("free", 0)], [0], 0)["affordable"], ["free"])

    def test_stability_and_input_unchanged(self):
        data = [("z", 1), ("a", 0), ("b", 1), ("x", 0)]
        for algorithm in (bubble_sort, merge_sort, quick_sort):
            with self.subTest(algorithm=algorithm.__name__):
                self.assertEqual(algorithm(data, key=lambda x: x[1]), [("a", 0), ("x", 0), ("z", 1), ("b", 1)])
        self.assertEqual(data, [("z", 1), ("a", 0), ("b", 1), ("x", 0)])

    def test_bounds_with_duplicates_and_absent_targets(self):
        data = [1, 2, 2, 2, 5]
        for target, pair in [(0, (0, 0)), (2, (1, 4)), (3, (4, 4)), (6, (5, 5))]:
            self.assertEqual((lower_bound(data, target), upper_bound(data, target)), pair)
        self.assertEqual((lower_bound([], 1), upper_bound([], 1)), (0, 0))

    def test_seeded_oracle(self):
        rng = random.Random(20261023)
        for _ in range(100):
            data = [rng.randint(-5, 5) for _ in range(rng.randrange(30))]
            expected = sorted(data)
            for algorithm in (bubble_sort, merge_sort, quick_sort):
                self.assertEqual(algorithm(data), expected)
            for target in range(-6, 7):
                self.assertEqual(lower_bound(expected, target), sum(x < target for x in data))
                self.assertEqual(upper_bound(expected, target), sum(x <= target for x in data))

    def test_bubble_early_exit_comparisons(self):
        stats = {"comparisons": 0}
        bubble_sort(range(20), stats=stats)
        self.assertEqual(stats["comparisons"], 19)

    def test_repeated_queries_are_not_lost(self):
        result = catalog_report([("A", 2)], [2, 2], 1)
        self.assertEqual(len(result["matches"]), 2)
        self.assertEqual(result["affordable"], [])

    def test_invalid_inputs(self):
        cases = [([("A", 1), ("A", 2)], [], 0), ([("A", -1)], [], 0),
                 ([("A", True)], [], 0), ([("", 1)], [], 0), (["bad"], [], 0),
                 ([], [-1], 0), ([], [], -1), ([(str(i), i) for i in range(201)], [], 0)]
        for products, queries, budget in cases:
            with self.subTest(products=products[:2], queries=queries, budget=budget), self.assertRaises(ValueError):
                catalog_report(products, queries, budget)


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