| # Copyright (c) 2009 Raymond Hettinger | |
| # | |
| # Permission is hereby granted, free of charge, to any person | |
| # obtaining a copy of this software and associated documentation files | |
| # (the "Software"), to deal in the Software without restriction, | |
| # including without limitation the rights to use, copy, modify, merge, | |
| # publish, distribute, sublicense, and/or sell copies of the Software, | |
| # and to permit persons to whom the Software is furnished to do so, | |
| # subject to the following conditions: | |
| # | |
| # The above copyright notice and this permission notice shall be | |
| # included in all copies or substantial portions of the Software. | |
| # | |
| # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | |
| # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES | |
| # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND | |
| # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT | |
| # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, | |
| # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING | |
| # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR | |
| # OTHER DEALINGS IN THE SOFTWARE. | |
| from UserDict import DictMixin | |
| class OrderedDict(dict, DictMixin): | |
| def __init__(self, *args, **kwds): | |
| if len(args) > 1: | |
| raise TypeError('expected at most 1 arguments, got %d' % len(args)) | |
| try: | |
| self.__end | |
| except AttributeError: | |
| self.clear() | |
| self.update(*args, **kwds) | |
| def clear(self): | |
| self.__end = end = [] | |
| end += [None, end, end] # sentinel node for doubly linked list | |
| self.__map = {} # key --> [key, prev, next] | |
| dict.clear(self) | |
| def __setitem__(self, key, value): | |
| if key not in self: | |
| end = self.__end | |
| curr = end[1] | |
| curr[2] = end[1] = self.__map[key] = [key, curr, end] | |
| dict.__setitem__(self, key, value) | |
| def __delitem__(self, key): | |
| dict.__delitem__(self, key) | |
| key, prev, next = self.__map.pop(key) | |
| prev[2] = next | |
| next[1] = prev | |
| def __iter__(self): | |
| end = self.__end | |
| curr = end[2] | |
| while curr is not end: | |
| yield curr[0] | |
| curr = curr[2] | |
| def __reversed__(self): | |
| end = self.__end | |
| curr = end[1] | |
| while curr is not end: | |
| yield curr[0] | |
| curr = curr[1] | |
| def popitem(self, last=True): | |
| if not self: | |
| raise KeyError('dictionary is empty') | |
| if last: | |
| key = reversed(self).next() | |
| else: | |
| key = iter(self).next() | |
| value = self.pop(key) | |
| return key, value | |
| def __reduce__(self): | |
| items = [[k, self[k]] for k in self] | |
| tmp = self.__map, self.__end | |
| del self.__map, self.__end | |
| inst_dict = vars(self).copy() | |
| self.__map, self.__end = tmp | |
| if inst_dict: | |
| return (self.__class__, (items,), inst_dict) | |
| return self.__class__, (items,) | |
| def keys(self): | |
| return list(self) | |
| setdefault = DictMixin.setdefault | |
| update = DictMixin.update | |
| pop = DictMixin.pop | |
| values = DictMixin.values | |
| items = DictMixin.items | |
| iterkeys = DictMixin.iterkeys | |
| itervalues = DictMixin.itervalues | |
| iteritems = DictMixin.iteritems | |
| def __repr__(self): | |
| if not self: | |
| return '%s()' % (self.__class__.__name__,) | |
| return '%s(%r)' % (self.__class__.__name__, self.items()) | |
| def copy(self): | |
| return self.__class__(self) | |
| @classmethod | |
| def fromkeys(cls, iterable, value=None): | |
| d = cls() | |
| for key in iterable: | |
| d[key] = value | |
| return d | |
| def __eq__(self, other): | |
| if isinstance(other, OrderedDict): | |
| if len(self) != len(other): | |
| return False | |
| for p, q in zip(self.items(), other.items()): | |
| if p != q: | |
| return False | |
| return True | |
| return dict.__eq__(self, other) | |
| def __ne__(self, other): | |
| return not self == other |