import random
import statistics
import unittest

from heap_lab import MedianTracker, schedule_report


def slow_schedule(jobs):
    pending, records, now = list(jobs), [], 0
    while pending:
        available = [job for job in pending if job[1] <= now]
        if not available:
            now = min(job[1] for job in pending)
            available = [job for job in pending if job[1] <= now]
        identity, arrival, duration = min(available, key=lambda job: (job[2], job[0]))
        records.append({"id": identity, "start": now,
                        "finish": now + duration, "wait": now - arrival})
        pending.remove((identity, arrival, duration))
        now += duration
    return records


class WorkshopTests(unittest.TestCase):
    def test_worked_example(self):
        result = schedule_report([("A", 0, 5), ("B", 1, 2), ("C", 1, 1), ("D", 9, 2)])
        self.assertEqual([row["id"] for row in result["schedule"]], ["A", "C", "B", "D"])
        self.assertEqual([row["wait"] for row in result["schedule"]], [0, 4, 5, 0])
        self.assertEqual(result["median_trace"], [0, 2, 4, 2])
        self.assertEqual((result["total_wait"], result["finish"]), (9, 11))

    def test_empty(self):
        self.assertEqual(schedule_report([]), {"schedule": [], "total_wait": 0,
            "median_trace": [], "median_wait": None, "finish": 0})

    def test_equal_durations_break_ties_by_id(self):
        result = schedule_report([("z", 0, 2), ("a", 0, 2), ("b", 0, 2)])
        self.assertEqual([row["id"] for row in result["schedule"]], ["a", "b", "z"])

    def test_no_preemption(self):
        result = schedule_report([("long", 0, 20), ("short", 1, 1)])
        self.assertEqual(result["schedule"][1]["start"], 20)

    def test_idle_clock_jump_and_boundary_arrival(self):
        result = schedule_report([("A", 10, 2), ("B", 12, 1), ("C", 30, 4)])
        self.assertEqual([row["start"] for row in result["schedule"]], [10, 12, 30])
        self.assertEqual(result["total_wait"], 0)

    def test_invalid_jobs(self):
        for jobs in [[("A", -1, 2)], [("A", 0, 0)], [("A", 0, -1)],
                     [("A", 0, 1), ("A", 2, 3)]]:
            with self.subTest(jobs=jobs), self.assertRaises(ValueError):
                schedule_report(jobs)

    def test_median_heap_invariants(self):
        tracker, observed = MedianTracker(), []
        for value in [9, 0, 2, 2, 100, 1, 11, 4]:
            observed.append(value)
            self.assertEqual(tracker.add(value), statistics.median(observed))
            self.assertIn(len(tracker.lower) - len(tracker.upper), (0, 1))
            if tracker.upper:
                self.assertLessEqual(-tracker.lower[0], tracker.upper[0])

    def test_random_schedules_against_scan_oracle(self):
        rng = random.Random(82)
        for _ in range(100):
            jobs = [(str(i), rng.randrange(15), rng.randint(1, 8))
                    for i in range(rng.randrange(15))]
            rng.shuffle(jobs)
            result = schedule_report(jobs)
            self.assertEqual(result["schedule"], slow_schedule(jobs))
            waits = [row["wait"] for row in result["schedule"]]
            self.assertEqual(result["median_trace"],
                             [statistics.median(waits[:i]) for i in range(1, len(waits) + 1)])


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