| 29 | from collections import MutableMapping as DictMixin |
| 30 | |
| 31 | class OrderedDict(dict, DictMixin): |
| 32 | |
| 33 | def __init__(self, *args, **kwds): |
| 34 | if len(args) > 1: |
| 35 | raise TypeError('expected at most 1 arguments, got %d' % len(args)) |
| 36 | try: |
| 37 | self.__end |
| 38 | except AttributeError: |
| 39 | self.clear() |
| 40 | self.update(*args, **kwds) |
| 41 | |
| 42 | def clear(self): |
| 43 | self.__end = end = [] |
| 44 | end += [None, end, end] # sentinel node for doubly linked list |
| 45 | self.__map = {} # key --> [key, prev, next] |
| 46 | dict.clear(self) |
| 47 | |
| 48 | def __setitem__(self, key, value): |
| 49 | if key not in self: |
| 50 | end = self.__end |
| 51 | curr = end[1] |
| 52 | curr[2] = end[1] = self.__map[key] = [key, curr, end] |
| 53 | dict.__setitem__(self, key, value) |
| 54 | |
| 55 | def __delitem__(self, key): |
| 56 | dict.__delitem__(self, key) |
| 57 | key, prev, next = self.__map.pop(key) |
| 58 | prev[2] = next |
| 59 | next[1] = prev |
| 60 | |
| 61 | def __iter__(self): |
| 62 | end = self.__end |
| 63 | curr = end[2] |
| 64 | while curr is not end: |
| 65 | yield curr[0] |
| 66 | curr = curr[2] |
| 67 | |
| 68 | def __reversed__(self): |
| 69 | end = self.__end |
| 70 | curr = end[1] |
| 71 | while curr is not end: |
| 72 | yield curr[0] |
| 73 | curr = curr[1] |
| 74 | |
| 75 | def popitem(self, last=True): |
| 76 | if not self: |
| 77 | raise KeyError('dictionary is empty') |
| 78 | if last: |
| 79 | key = next(reversed(self)) |
| 80 | else: |
| 81 | key = next(iter(self)) |
| 82 | value = self.pop(key) |
| 83 | return key, value |
| 84 | |
| 85 | def __reduce__(self): |
| 86 | items = [[k, self[k]] for k in self] |
| 87 | tmp = self.__map, self.__end |
| 88 | del self.__map, self.__end |
no outgoing calls
no test coverage detected
searching dependent graphs…