import itertools
import random
import unittest

from graphs_lab import delivery_plan, task_order


class DeliveryTests(unittest.TestCase):
    def test_worked_example(self):
        roads = [(0, 1, 2), (0, 2, 5), (1, 2, 1), (2, 3, 2), (1, 3, 8)]
        self.assertEqual(delivery_plan(4, roads, [3, 1, 2], [(1, 3), (2, 3)]),
            {"order": [1, 2, 3], "legs": [
                {"from": 0, "to": 1, "path": [0, 1], "cost": 2},
                {"from": 1, "to": 2, "path": [1, 2], "cost": 1},
                {"from": 2, "to": 3, "path": [2, 3], "cost": 2}], "total_cost": 5})

    def test_empty_deliveries_and_start_delivery(self):
        self.assertEqual(delivery_plan(1, [], [], []), {"order": [], "legs": [], "total_cost": 0})
        self.assertEqual(delivery_plan(1, [], [0], [])["legs"][0]["path"], [0])

    def test_duplicate_dependencies_are_one_constraint(self):
        self.assertEqual(task_order([2, 0, 1], [(0, 2), (0, 2)]), [0, 1, 2])

    def test_cycle_and_self_cycle(self):
        for edges in [[(0, 1), (1, 0)], [(0, 0)]]:
            with self.subTest(edges=edges), self.assertRaises(ValueError):
                delivery_plan(2, [], [0, 1], edges)

    def test_unreachable_respects_road_direction(self):
        with self.assertRaises(ValueError):
            delivery_plan(2, [(1, 0, 1)], [1], [])

    def test_stale_entries_zero_weight_and_parallel_roads(self):
        roads = [(0, 1, 10), (0, 2, 1), (2, 1, 0), (1, 3, 2), (0, 2, 7)]
        result = delivery_plan(4, roads, [3], [])
        self.assertEqual(result["legs"][0], {"from": 0, "to": 3, "path": [0, 2, 1, 3], "cost": 3})

    def test_invalid_input(self):
        for n, roads, deliveries, dependencies in [
                (0, [], [], []), (2, [(0, 1, -1)], [1], []),
                (2, [(0, 2, 1)], [1], []), (2, [], [1, 1], []),
                (2, [], [3], []), (2, [], [1], [(0, 1)])]:
            with self.subTest(n=n, roads=roads), self.assertRaises(ValueError):
                delivery_plan(n, roads, deliveries, dependencies)

    def test_lexicographic_topology_against_permutations(self):
        tasks, dependencies = [3, 1, 0, 2], [(0, 2), (1, 2)]
        valid = [order for order in itertools.permutations(tasks)
                 if all(order.index(a) < order.index(b) for a, b in dependencies)]
        self.assertEqual(task_order(tasks, dependencies), list(min(valid)))

    def test_random_costs_against_floyd_warshall(self):
        rng = random.Random(93)
        for _ in range(50):
            n = rng.randint(2, 6)
            roads = [(a, b, rng.randrange(10)) for a in range(n) for b in range(n) if a != b]
            distances = [[0 if a == b else float("inf") for b in range(n)] for a in range(n)]
            for a, b, cost in roads:
                distances[a][b] = min(distances[a][b], cost)
            for via in range(n):
                for a in range(n):
                    for b in range(n):
                        distances[a][b] = min(distances[a][b], distances[a][via] + distances[via][b])
            deliveries = list(range(1, n))
            result = delivery_plan(n, roads, deliveries, [])
            current, total = 0, 0
            weights = {(a, b): cost for a, b, cost in roads}
            for leg in result["legs"]:
                self.assertEqual(leg["cost"], distances[current][leg["to"]])
                self.assertEqual(sum(weights[a, b] for a, b in zip(leg["path"], leg["path"][1:])), leg["cost"])
                total += distances[current][leg["to"]]
                current = leg["to"]
            self.assertEqual(result["total_cost"], total)


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