Dictionary that remembers insertion order
| 76 | __slots__ = 'prev', 'next', 'key', '__weakref__' |
| 77 | |
| 78 | class OrderedDict(dict): |
| 79 | 'Dictionary that remembers insertion order' |
| 80 | # An inherited dict maps keys to values. |
| 81 | # The inherited dict provides __getitem__, __len__, __contains__, and get. |
| 82 | # The remaining methods are order-aware. |
| 83 | # Big-O running times for all methods are the same as regular dictionaries. |
| 84 | |
| 85 | # The internal self.__map dict maps keys to links in a doubly linked list. |
| 86 | # The circular doubly linked list starts and ends with a sentinel element. |
| 87 | # The sentinel element never gets deleted (this simplifies the algorithm). |
| 88 | # The sentinel is in self.__hardroot with a weakref proxy in self.__root. |
| 89 | # The prev links are weakref proxies (to prevent circular references). |
| 90 | # Individual links are kept alive by the hard reference in self.__map. |
| 91 | # Those hard references disappear when a key is deleted from an OrderedDict. |
| 92 | |
| 93 | def __new__(cls, /, *args, **kwds): |
| 94 | "Create the ordered dict object and set up the underlying structures." |
| 95 | self = dict.__new__(cls) |
| 96 | self.__hardroot = _Link() |
| 97 | self.__root = root = _proxy(self.__hardroot) |
| 98 | root.prev = root.next = root |
| 99 | self.__map = {} |
| 100 | return self |
| 101 | |
| 102 | def __init__(self, other=(), /, **kwds): |
| 103 | '''Initialize an ordered dictionary. The signature is the same as |
| 104 | regular dictionaries. Keyword argument order is preserved. |
| 105 | ''' |
| 106 | self.__update(other, **kwds) |
| 107 | |
| 108 | def __setitem__(self, key, value, |
| 109 | dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link): |
| 110 | 'od.__setitem__(i, y) <==> od[i]=y' |
| 111 | # Setting a new item creates a new link at the end of the linked list, |
| 112 | # and the inherited dictionary is updated with the new key/value pair. |
| 113 | if key not in self: |
| 114 | self.__map[key] = link = Link() |
| 115 | root = self.__root |
| 116 | last = root.prev |
| 117 | link.prev, link.next, link.key = last, root, key |
| 118 | last.next = link |
| 119 | root.prev = proxy(link) |
| 120 | dict_setitem(self, key, value) |
| 121 | |
| 122 | def __delitem__(self, key, dict_delitem=dict.__delitem__): |
| 123 | 'od.__delitem__(y) <==> del od[y]' |
| 124 | # Deleting an existing item uses self.__map to find the link which gets |
| 125 | # removed by updating the links in the predecessor and successor nodes. |
| 126 | dict_delitem(self, key) |
| 127 | link = self.__map.pop(key) |
| 128 | link_prev = link.prev |
| 129 | link_next = link.next |
| 130 | link_prev.next = link_next |
| 131 | link_next.prev = link_prev |
| 132 | link.prev = None |
| 133 | link.next = None |
| 134 | |
| 135 | def __iter__(self): |
no outgoing calls