"""Cells for majority.py (Q85): the generalized Boyer-Moore vote.

No collected test imported the module, so its `__main__` corpus was the only
thing that ever ran it.  Every cell here compares against a Counter, which
shares no code with the module, so the vote's bookkeeping is graded rather
than echoed.
"""
import random
import unittest
from collections import Counter

import majority as M


def brute_gt_k(data, k):
    n = len(data)
    return sorted(x for x, c in Counter(data).items() if c > n // k)


def brute_majority(data):
    if not data:
        return None
    hits = [x for x, c in Counter(data).items() if c > len(data) // 2]
    return hits[0] if hits else None


class TestMajority(unittest.TestCase):
    def test_empty_and_small(self):
        self.assertIsNone(M.majority_element([]))
        self.assertEqual(M.majority_element([1]), 1)
        self.assertIsNone(M.majority_element([1, 2]))
        self.assertEqual(M.majority_element([1, 1, 2]), 1)
        self.assertIsNone(M.majority_element([1, 2, 3]))

    def test_odd_and_even_near_misses(self):
        # Exactly half is not a majority; one more than half is.
        self.assertIsNone(M.majority_element([1, 1, 2, 2]))
        self.assertEqual(M.majority_element([1, 1, 1, 2]), 1)
        self.assertIsNone(M.majority_element([1, 1, 2, 3]))

    def test_aliases_agree(self):
        data = [4, 4, 4, 1, 2]
        self.assertEqual(M.majority(data), M.majority_element_v2(data))
        self.assertEqual(M.majority(data), 4)

    def test_counter_resistant_pattern(self):
        # The order that defeats a naive "cancel adjacent" reading: no prefix
        # has more candidates than cancellations until the very end.
        data = [2, 1, 2, 1, 2]
        self.assertEqual(M.majority_element(data), 2)
        data = [1, 2, 1, 2, 1, 2, 2]
        self.assertEqual(M.majority_element(data), 2)

    def test_random_majority_against_counter(self):
        rng = random.Random(42)
        for _ in range(1500):
            n = rng.randint(0, 40)
            if n and rng.random() < 0.5:
                maj = rng.randint(0, 5)
                data = [maj] * (n // 2 + 1) + [rng.randint(0, 5) for _ in range(n - n // 2 - 1)]
                rng.shuffle(data)
            else:
                data = [rng.randint(0, 5) for _ in range(n)]
            self.assertEqual(M.majority_element(data), brute_majority(data), data)

    def test_gt_k_is_sound_and_complete(self):
        # Returned values are exactly the ones above n//k -- no false positive
        # (the docstring's reason for the verification pass) and no omission.
        rng = random.Random(1234)
        for _ in range(800):
            n = rng.randint(0, 30)
            data = [rng.randint(0, 6) for _ in range(n)]
            for k in (2, 3, 4, 5):
                got = M.majority_gt_k(data, k)
                self.assertEqual(sorted(got), brute_gt_k(data, k), (data, k))
                self.assertEqual(len(got), len(set(got)), "duplicate in the result")
                self.assertLessEqual(len(got), k - 1)

    def test_gt_k_structure_cases(self):
        self.assertEqual(M.majority_gt_k([], 3), [])
        self.assertEqual(M.majority_gt_k([1, 1, 2, 2, 3, 3], 3), [])
        self.assertEqual(sorted(M.majority_gt_k([1, 1, 1, 2, 2, 3], 3)), [1])
        # "More than n//k" is strict: at k=2, exactly half of four is not a
        # majority, so nothing is returned.  (Written the other way first and
        # the cell failed -- the module was right, the expectation was not.)
        self.assertEqual(M.majority_gt_k([1, 1, 2, 2], 2), [])
        self.assertEqual(sorted(M.majority_gt_k([1, 1, 1, 2], 2)), [1])

    def test_third_is_k_three(self):
        self.assertEqual(M.majority_third([1, 1, 2]), [1])
        self.assertEqual(M.majority_third([1, 1, 2, 2, 3, 3]), [])
        self.assertEqual(M.majority_third([1, 1, 1, 2, 3]), [1])

    def test_k_below_two_is_refused(self):
        for k in (1, 0, -3):
            with self.assertRaises(ValueError, msg="k=%r" % k):
                M.majority_gt_k([1, 2], k)

    def test_one_shot_input_is_materialised(self):
        # `data = list(nums)` is what makes a generator safe; without it the
        # second pass over `nums` would see nothing.
        gen = (x for x in [1, 1, 2])
        self.assertEqual(M.majority_element(gen), 1)
        gen = (x for x in [1, 1, 2, 2, 3, 3])
        self.assertEqual(M.majority_gt_k(gen, 3), [])


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