Return to ordereddict.py CVS log

Up to [Qemu by Fabrice Bellard] / qemu / scripts

Annotation of qemu/scripts/ordereddict.py, revision 1.1.1.1

1.1       root        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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.