import bisect
from random import randint

N1 = 10000 # N1 > N2 > N3
N2 = N1 // 10
N3 = N1 // 100


class SortedDict(dict):
    """
    dict that keeps all its keys in sorted order
    """
    def __setitem__(self, key, value):
        """
        overload the setitem to add the item in sorted order

        We can assume that the existing keys are already in sorted order,
        so we can use bisect.

        NOTE: values may not be sortable, so we need to work with the keys.
        """
        # get the keys and values:
        # making copies so we won't lose them
        keys = list(self.keys())
        values = list(self.values())
        # find the insertion point
        idx = bisect.bisect(keys, key)
        # empty the dict
        self.clear()
        # refill the first half:
        for k, v in zip(keys[:idx], values[:idx]):
            super().__setitem__(k, v)
        # add the new item:
        super().__setitem__(key, value)
        # fill in the rest:
        for k, v in zip(keys[idx:], values[idx:]):
            super().__setitem__(k, v)

    def nth_smallest_key(self, n):
        """
        return the nth smallest key
        """
        return list(self.keys())[n]

    def nth_smallest_value(self, n):
        return self[list(self.keys())[n]]

    def nth_smallest_item(self, n):
        key = list(self.keys())[n]
        return (key, self[key])



dist = lambda: randint(0, 2147483647)


def test_sorted_dict_preserve_items():
    sd = SortedDict()

    sd[1] = "mary"
    sd[3] = "fred"
    sd[2] = "bob"

    # make sure it acts like a regular dict()
    assert sd[1] == "mary"
    assert sd[3] == "fred"
    assert sd[2] == "bob"


def test_sorted_dict_preserve_sort_order():
    sd = SortedDict()

    sd[1] = "mary"
    sd[3] = "fred"
    sd[2] = "bob"

    # make sure the keys are in order
    assert list(sd.keys()) ==  sorted(sd.keys())


def test_nth_smallest_key():
    sd = SortedDict()

    for i in range(20):
        sd[i] = i + 2

    assert sd.nth_smallest_key(2) == 2
    assert sd.nth_smallest_key(6) == 6


def test_nth_smallest_item():
    sd = SortedDict()

    for i in range(20):
        sd[i] = i + 2

    assert sd.nth_smallest_item(2) == (2, 4)
    assert sd.nth_smallest_item(6) == (6, 8)


def test_nth_smallest_value():
    sd = SortedDict()

    for i in range(20):
        sd[i] = i + 2

    assert sd.nth_smallest_value(2) == 4
    assert sd.nth_smallest_value(6) == 8


def nth_smallest_key(n, m):
    return sorted(m.keys())[n]


def main():
    my_map = SortedDict()

    # fills a map with N1 random mappings of type (int, int)
    for i in range(0, N1):
        my_map[dist()] = dist()

    # prints out the N3th smallest key and its value
    target_key = my_map.nth_smallest_key(N3)
    print("({}: {})".format(target_key, my_map[target_key]))

    # writes a new random mapping to the map
    # then prints out the N3th smallest key and its value if that key
    # has changed
    # 100000 times
    for i in range(N3):
        my_map[dist()] = dist()

        test_key = my_map.nth_smallest_key(N3)
        if target_key != test_key:
            target_key = test_key
            print(i, target_key, test_key)
            print("({}: {})".format(target_key, my_map[target_key]))

        # print an indicator every N3 iterations for comparison
        if i % N3 == 0:
            print("iteration: {}".format(i))


if __name__ == "__main__":
    main()