casa6

# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.

# Passes Python2.7's test suite and incorporates all the latest updates.

​

try:

    from thread import get_ident as _get_ident

except ImportError:

    from dummy_thread import get_ident as _get_ident

​

try:

    from _abcoll import KeysView, ValuesView, ItemsView

except ImportError:

    pass

​

​

class OrderedDict(dict):

    'Dictionary that remembers insertion order'

    # An inherited dict maps keys to values.

    # The inherited dict provides __getitem__, __len__, __contains__, and get.

    # The remaining methods are order-aware.

    # Big-O running times for all methods are the same as for regular dictionaries.

​

    # The internal self.__map dictionary maps keys to links in a doubly linked list.

    # The circular doubly linked list starts and ends with a sentinel element.

    # The sentinel element never gets deleted (this simplifies the algorithm).

    # Each link is stored as a list of length three:  [PREV, NEXT, KEY].

​

    def __init__(self, *args, **kwds):

        '''Initialize an ordered dictionary.  Signature is the same as for

        regular dictionaries, but keyword arguments are not recommended

        because their insertion order is arbitrary.

​

        '''

        if len(args) > 1:

            raise TypeError('expected at most 1 arguments, got %d' % len(args))

        try:

            self.__root

        except AttributeError:

            self.__root = root = []                     # sentinel node

            root[:] = [root, root, None]

            self.__map = {}

        self.__update(*args, **kwds)

​

    def __setitem__(self, key, value, dict_setitem=dict.__setitem__):

        'od.__setitem__(i, y) <==> od[i]=y'

        # Setting a new item creates a new link which goes at the end of the linked

        # list, and the inherited dictionary is updated with the new key/value pair.

        if key not in self:

            root = self.__root

            last = root[0]

            last[1] = root[0] = self.__map[key] = [last, root, key]

        dict_setitem(self, key, value)

​

    def __delitem__(self, key, dict_delitem=dict.__delitem__):

        'od.__delitem__(y) <==> del od[y]'

        # Deleting an existing item uses self.__map to find the link which is

        # then removed by updating the links in the predecessor and successor nodes.

        dict_delitem(self, key)

        link_prev, link_next, key = self.__map.pop(key)

        link_prev[1] = link_next

        link_next[0] = link_prev

​

    def __iter__(self):

        'od.__iter__() <==> iter(od)'