OrderedSet

ordered_set.py

from collections import OrderedDict


class OrderedSet(OrderedDict):
    def pop(self):
        """ Returns and removes last element of the set """
        if not self:
            raise KeyError('dictionary is empty')

        key = next(reversed(self))
        del self[key]
        return key

    def peek(self):
        """ Returns last element of the set without removing it """
        if not self:
            raise KeyError('dictionary is empty')

        key = next(reversed(self))
        return key

    def at(self, i):
        """ Returns element at the index """
        if not self:
            raise KeyError('dictionary is empty')
        return list(self)[i]

    def extend(self, iterable):
        """ Extends OrderedList by appending elements from the iterable """
        for element in iterable:
            if element not in self:
                self[element] = True

    def append(self, element):
        """ Appends an element to the end of the ordered set """
        if element not in self:
            self[element] = True

test_ordered_set.py

def test_ordered_set_a():
    o_s = OrderedSet()
    SIZE = 100
    for i in range(SIZE):
        o_s.append(i)

    for i in range(SIZE * 2):
        assert o_s.peek() == SIZE - 1

    for i in range(SIZE):
        assert o_s.pop() == SIZE - 1 - i
    assert len(o_s) == 0

    just_a_list = [i for i in range(SIZE)]
    o_s.extend(just_a_list)

    for i in range(SIZE):
        assert o_s.at(i) == i

    o_s.extend(just_a_list)
    assert len(o_s) == SIZE
    for i in range(SIZE):
        assert o_s.at(i) == i

    just_a_list = [i for i in range(SIZE / 2, SIZE * 2)]
    o_s.extend(just_a_list)
    assert len(o_s) == SIZE * 2
    for i in range(SIZE * 2):
        assert o_s.at(i) == i