LXR qemu/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
  23from UserDict import DictMixin
  24
  25
  26class 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
 129