scripts/ordereddict.py

   1 # Copyright (c) 2009 Raymond Hettinger
   2 #
   3 # Permission is hereby granted, free of charge, to any person
   4 # obtaining a copy of this software and associated documentation files
   5 # (the "Software"), to deal in the Software without restriction,
   6 # including without limitation the rights to use, copy, modify, merge,
   7 # publish, distribute, sublicense, and/or sell copies of the Software,
   8 # and to permit persons to whom the Software is furnished to do so,
   9 # subject to the following conditions:
  10 #
  11 #     The above copyright notice and this permission notice shall be
  12 #     included in all copies or substantial portions of the Software.
  13 #
  14 #     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  15 #     EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  16 #     OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  17 #     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  18 #     HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  19 #     WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20 #     FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  21 #     OTHER DEALINGS IN THE SOFTWARE.
  22
  23 from UserDict import DictMixin
  24
  25 class OrderedDict(dict, DictMixin):
  26
  27     def __init__(self, *args, **kwds):
  28         if len(args) > 1:
  29             raise TypeError('expected at most 1 arguments, got %d' % len(args))
  30         try:
  31             self.__end
  32         except AttributeError:
  33             self.clear()
  34         self.update(*args, **kwds)
  35
  36     def clear(self):
  37         self.__end = end = []
  38         end += [None, end, end]         # sentinel node for doubly linked list
  39         self.__map = {}                 # key --> [key, prev, next]
  40         dict.clear(self)
  41
  42     def __setitem__(self, key, value):
  43         if key not in self:
  44             end = self.__end
  45             curr = end[1]
  46             curr[2] = end[1] = self.__map[key] = [key, curr, end]
  47         dict.__setitem__(self, key, value)
  48
  49     def __delitem__(self, key):
  50         dict.__delitem__(self, key)
  51         key, prev, next = self.__map.pop(key)
  52         prev[2] = next
  53         next[1] = prev
  54
  55     def __iter__(self):
  56         end = self.__end
  57         curr = end[2]
  58         while curr is not end:
  59             yield curr[0]
  60             curr = curr[2]
  61
  62     def __reversed__(self):
  63         end = self.__end
  64         curr = end[1]
  65         while curr is not end:
  66             yield curr[0]
  67             curr = curr[1]
  68
  69     def popitem(self, last=True):
  70         if not self:
  71             raise KeyError('dictionary is empty')
  72         if last:
  73             key = reversed(self).next()
  74         else:
  75             key = iter(self).next()
  76         value = self.pop(key)
  77         return key, value
  78
  79     def __reduce__(self):
  80         items = [[k, self[k]] for k in self]
  81         tmp = self.__map, self.__end
  82         del self.__map, self.__end
  83         inst_dict = vars(self).copy()
  84         self.__map, self.__end = tmp
  85         if inst_dict:
  86             return (self.__class__, (items,), inst_dict)
  87         return self.__class__, (items,)
  88
  89     def keys(self):
  90         return list(self)
  91
  92     setdefault = DictMixin.setdefault
  93     update = DictMixin.update
  94     pop = DictMixin.pop
  95     values = DictMixin.values
  96     items = DictMixin.items
  97     iterkeys = DictMixin.iterkeys
  98     itervalues = DictMixin.itervalues
  99     iteritems = DictMixin.iteritems
 100
 101     def __repr__(self):
 102         if not self:
 103             return '%s()' % (self.__class__.__name__,)
 104         return '%s(%r)' % (self.__class__.__name__, self.items())
 105
 106     def copy(self):
 107         return self.__class__(self)
 108
 109     @classmethod
 110     def fromkeys(cls, iterable, value=None):
 111         d = cls()
 112         for key in iterable:
 113             d[key] = value
 114         return d
 115
 116     def __eq__(self, other):
 117         if isinstance(other, OrderedDict):
 118             if len(self) != len(other):
 119                 return False
 120             for p, q in  zip(self.items(), other.items()):
 121                 if p != q:
 122                     return False
 123             return True
 124         return dict.__eq__(self, other)
 125
 126     def __ne__(self, other):
 127         return not self == other