import random
import unittest
from example import Fenwick, sliding_maximum


class RangeTests(unittest.TestCase):
    def test_updates_against_list(self):
        rng = random.Random(17)
        values = [rng.randint(-8, 8) for _ in range(20)]
        tree = Fenwick(values)
        for _ in range(300):
            if rng.random() < 0.5:
                index, delta = rng.randrange(len(values)), rng.randint(-5, 5)
                values[index] += delta
                tree.add(index, delta)
            else:
                left = rng.randrange(len(values) + 1)
                right = rng.randrange(left, len(values) + 1)
                self.assertEqual(tree.range_sum(left, right), sum(values[left:right]))
        self.assertEqual(Fenwick([]).range_sum(0, 0), 0)
        with self.assertRaises(IndexError):
            tree.add(-1, 1)

    def test_windows_against_slices(self):
        rng = random.Random(18)
        for n in range(1, 30):
            values = [rng.randint(-10, 10) for _ in range(n)]
            for k in range(1, n + 1):
                self.assertEqual(sliding_maximum(values, k),
                                 [max(values[i:i + k]) for i in range(n - k + 1)])
        with self.assertRaises(ValueError):
            sliding_maximum([], 0)


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