simplejson/ordered_dict.py

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