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