import random
import unittest

from practice.linked_list_lab import Node, build_manifest, from_values, to_values


class ManifestTests(unittest.TestCase):
    def test_worked_example(self):
        result = build_manifest(from_values([1, 4, 7]), from_values([2, 3, 6, 8]), {3, 7}, 2)
        self.assertEqual(to_values(result), [2, 1, 6, 4, 8])

    def test_empty(self):
        self.assertIsNone(build_manifest(None, None))

    def test_all_cancelled(self):
        self.assertIsNone(build_manifest(from_values([1, 1]), from_values([2]), {1, 2}))

    def test_partial_group_unchanged(self):
        self.assertEqual(to_values(build_manifest(from_values([1, 2]), None, (), 3)), [1, 2])

    def test_size_one_and_duplicates(self):
        self.assertEqual(to_values(build_manifest(from_values([1, 2]), from_values([1, 2]), (), 1)), [1, 1, 2, 2])

    def test_reuses_nodes(self):
        left, right = from_values([1, 3]), from_values([2, 4])
        original = {id(left), id(left.next), id(right), id(right.next)}
        head = build_manifest(left, right)
        actual = set()
        while head:
            actual.add(id(head)); head = head.next
        self.assertEqual(actual, original)

    def test_cycle_rejected(self):
        head = Node(1); head.next = head
        with self.assertRaises(ValueError):
            build_manifest(head, None)

    def test_shared_tail_rejected(self):
        common = Node(5)
        with self.assertRaises(ValueError):
            build_manifest(Node(1, common), Node(2, common))

    def test_invalid_size_or_order(self):
        with self.assertRaises(ValueError):
            build_manifest(None, None, (), 0)
        with self.assertRaises(ValueError):
            build_manifest(from_values([3, 1]), None)

    def test_random_against_array_model(self):
        rng = random.Random(17)
        for _ in range(150):
            a = sorted(rng.randrange(8) for _ in range(rng.randrange(8)))
            b = sorted(rng.randrange(8) for _ in range(rng.randrange(8)))
            cancelled = {rng.randrange(8), rng.randrange(8)}
            size = rng.randrange(1, 6)
            values = [v for v in sorted(a + b) if v not in cancelled]
            expected = []
            for start in range(0, len(values), size):
                group = values[start:start + size]
                expected.extend(group[::-1] if len(group) == size else group)
            self.assertEqual(to_values(build_manifest(from_values(a), from_values(b), cancelled, size)), expected)


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