ordered_dict.py 3.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119
  1. """Drop-in replacement for collections.OrderedDict by Raymond Hettinger
  2. http://code.activestate.com/recipes/576693/
  3. """
  4. from UserDict import DictMixin
  5. # Modified from original to support Python 2.4, see
  6. # http://code.google.com/p/simplejson/issues/detail?id=53
  7. try:
  8. all
  9. except NameError:
  10. def all(seq):
  11. for elem in seq:
  12. if not elem:
  13. return False
  14. return True
  15. class OrderedDict(dict, DictMixin):
  16. def __init__(self, *args, **kwds):
  17. if len(args) > 1:
  18. raise TypeError('expected at most 1 arguments, got %d' % len(args))
  19. try:
  20. self.__end
  21. except AttributeError:
  22. self.clear()
  23. self.update(*args, **kwds)
  24. def clear(self):
  25. self.__end = end = []
  26. end += [None, end, end] # sentinel node for doubly linked list
  27. self.__map = {} # key --> [key, prev, next]
  28. dict.clear(self)
  29. def __setitem__(self, key, value):
  30. if key not in self:
  31. end = self.__end
  32. curr = end[1]
  33. curr[2] = end[1] = self.__map[key] = [key, curr, end]
  34. dict.__setitem__(self, key, value)
  35. def __delitem__(self, key):
  36. dict.__delitem__(self, key)
  37. key, prev, next = self.__map.pop(key)
  38. prev[2] = next
  39. next[1] = prev
  40. def __iter__(self):
  41. end = self.__end
  42. curr = end[2]
  43. while curr is not end:
  44. yield curr[0]
  45. curr = curr[2]
  46. def __reversed__(self):
  47. end = self.__end
  48. curr = end[1]
  49. while curr is not end:
  50. yield curr[0]
  51. curr = curr[1]
  52. def popitem(self, last=True):
  53. if not self:
  54. raise KeyError('dictionary is empty')
  55. # Modified from original to support Python 2.4, see
  56. # http://code.google.com/p/simplejson/issues/detail?id=53
  57. if last:
  58. key = reversed(self).next()
  59. else:
  60. key = iter(self).next()
  61. value = self.pop(key)
  62. return key, value
  63. def __reduce__(self):
  64. items = [[k, self[k]] for k in self]
  65. tmp = self.__map, self.__end
  66. del self.__map, self.__end
  67. inst_dict = vars(self).copy()
  68. self.__map, self.__end = tmp
  69. if inst_dict:
  70. return (self.__class__, (items,), inst_dict)
  71. return self.__class__, (items,)
  72. def keys(self):
  73. return list(self)
  74. setdefault = DictMixin.setdefault
  75. update = DictMixin.update
  76. pop = DictMixin.pop
  77. values = DictMixin.values
  78. items = DictMixin.items
  79. iterkeys = DictMixin.iterkeys
  80. itervalues = DictMixin.itervalues
  81. iteritems = DictMixin.iteritems
  82. def __repr__(self):
  83. if not self:
  84. return '%s()' % (self.__class__.__name__,)
  85. return '%s(%r)' % (self.__class__.__name__, self.items())
  86. def copy(self):
  87. return self.__class__(self)
  88. @classmethod
  89. def fromkeys(cls, iterable, value=None):
  90. d = cls()
  91. for key in iterable:
  92. d[key] = value
  93. return d
  94. def __eq__(self, other):
  95. if isinstance(other, OrderedDict):
  96. return len(self)==len(other) and \
  97. all(p==q for p, q in zip(self.items(), other.items()))
  98. return dict.__eq__(self, other)
  99. def __ne__(self, other):
  100. return not self == other