import itertools
import random
import unittest
from example import select_intervals


class GreedyTests(unittest.TestCase):
    def test_boundaries(self):
        self.assertEqual(select_intervals([]), [])
        self.assertEqual(select_intervals([(0, 1), (1, 2)]), [(0, 1), (1, 2)])
        with self.assertRaises(ValueError):
            select_intervals([(1, 1)])

    def test_against_all_subsets(self):
        rng = random.Random(12)
        for _ in range(70):
            rows = []
            for _ in range(rng.randrange(8)):
                start = rng.randrange(-3, 6)
                rows.append((start, start + rng.randint(1, 5)))
            best = 0
            for mask in range(1 << len(rows)):
                picked = sorted(rows[i] for i in range(len(rows)) if mask & (1 << i))
                if all(a[1] <= b[0] for a, b in zip(picked, picked[1:])):
                    best = max(best, len(picked))
            self.assertEqual(len(select_intervals(rows)), best)


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