import random
import unittest

from range_queries_lab import Fenwick, MinimumTree, inventory_report


def naive_inventory(initial, events, threshold):
    stock, reports = list(initial), []
    for kind, left, right in events:
        if kind == "set":
            stock[left] = right
        else:
            minimum = min(stock[left:right])
            index = next(i for i in range(left, right) if stock[i] == minimum)
            needed = max(0, threshold - minimum)
            reports.append({"kind": kind, "range": (left, right), "total": sum(stock[left:right]),
                            "minimum": minimum, "index": index, "needed": needed})
            if kind == "refill":
                stock[index] += needed
    return {"reports": reports, "stock": stock}


class InventoryTests(unittest.TestCase):
    def test_worked_example(self):
        events = [("inspect", 0, 4), ("refill", 0, 4), ("set", 2, 0), ("inspect", 1, 4)]
        result = inventory_report([5, 1, 4, 1], events, 3)
        self.assertEqual(result["stock"], [5, 3, 0, 1])
        self.assertEqual(result["reports"][0], {"kind": "inspect", "range": (0, 4),
                         "total": 11, "minimum": 1, "index": 1, "needed": 2})
        self.assertEqual(result["reports"][-1], {"kind": "inspect", "range": (1, 4),
                         "total": 4, "minimum": 0, "index": 2, "needed": 3})

    def test_single_warehouse(self):
        result = inventory_report([0], [("refill", 0, 1), ("inspect", 0, 1)], 5)
        self.assertEqual(result["stock"], [5])
        self.assertEqual(result["reports"][-1]["total"], 5)

    def test_tie_uses_first_index_then_updates_both_trees(self):
        result = inventory_report([1, 1, 1], [("refill", 0, 3), ("refill", 0, 3)], 4)
        self.assertEqual([row["index"] for row in result["reports"]], [0, 1])
        self.assertEqual([row["total"] for row in result["reports"]], [3, 6])
        self.assertEqual(result["stock"], [4, 4, 1])

    def test_refill_above_threshold_does_not_remove_stock(self):
        result = inventory_report([8, 9], [("refill", 0, 2)], 3)
        self.assertEqual(result["stock"], [8, 9])
        self.assertEqual(result["reports"][0]["needed"], 0)

    def test_no_events_does_not_mutate_input(self):
        initial = [2, 3]
        self.assertEqual(inventory_report(initial, [], 0), {"reports": [], "stock": [2, 3]})
        inventory_report(initial, [("set", 0, 7)], 0)
        self.assertEqual(initial, [2, 3])

    def test_invalid_events_and_input(self):
        for initial, events, threshold in [([], [], 0), ([-1], [], 0), ([1], [], -1),
                ([1], [("set", 0, -1)], 0), ([1], [("set", 1, 0)], 0),
                ([1], [("inspect", 0, 0)], 0), ([1], [("inspect", 0, 2)], 0),
                ([1], [("unknown", 0, 1)], 0)]:
            with self.subTest(events=events), self.assertRaises(ValueError):
                inventory_report(initial, events, threshold)

    def test_non_power_of_two_tree_and_prefix_boundary(self):
        values = [3, 1, 9, 2, 4]
        totals, minima = Fenwick(values), MinimumTree(values)
        self.assertEqual(totals.prefix(0), 0)
        for left in range(len(values)):
            for right in range(left + 1, len(values) + 1):
                self.assertEqual(totals.range_sum(left, right), sum(values[left:right]))
                self.assertEqual(minima.minimum(left, right), min((values[i], i) for i in range(left, right)))

    def test_random_event_sequences_against_plain_array(self):
        rng = random.Random(115)
        for _ in range(80):
            n = rng.randint(1, 15)
            initial = [rng.randrange(20) for _ in range(n)]
            events = []
            for _ in range(40):
                kind = rng.choice(["set", "inspect", "refill"])
                left = rng.randrange(n)
                right = rng.randrange(20) if kind == "set" else rng.randint(left + 1, n)
                events.append((kind, left, right))
            threshold = rng.randrange(15)
            self.assertEqual(inventory_report(initial, events, threshold),
                             naive_inventory(initial, events, threshold))

    def test_direct_helpers_reject_out_of_bounds(self):
        totals, minima = Fenwick([3]), MinimumTree([3])
        for action in [lambda: totals.add(-1, 2), lambda: totals.add(1, 2),
                lambda: totals.prefix(-1), lambda: totals.prefix(2),
                lambda: totals.range_sum(1, 0), lambda: minima.set(-1, 2),
                lambda: minima.set(1, 2), lambda: minima.minimum(0, 0),
                lambda: minima.minimum(0, 2), lambda: MinimumTree([])]:
            with self.assertRaises(ValueError):
                action()
        self.assertEqual(Fenwick([]).prefix(0), 0)


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