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