contrib/fuse/impl_b/pyfuse/OrderedDict.py

   1 from UserDict import DictMixin
   2
   3
   4 DELETED = object()
   5
   6
   7 class OrderedDict(DictMixin):
   8
   9     def __init__(self, *args, **kwds):
  10         self.clear()
  11         self.update(*args, **kwds)
  12
  13     def clear(self):
  14         self._keys = []
  15         self._content = {}    # {key: (index, value)}
  16         self._deleted = 0
  17
  18     def copy(self):
  19         return OrderedDict(self)
  20
  21     def __iter__(self):
  22         for key in self._keys:
  23             if key is not DELETED:
  24                 yield key
  25
  26     def keys(self):
  27         return [key for key in self._keys if key is not DELETED]
  28
  29     def popitem(self):
  30         while 1:
  31             try:
  32                 k = self._keys.pop()
  33             except IndexError:
  34                 raise KeyError, 'OrderedDict is empty'
  35             if k is not DELETED:
  36                 return k, self._content.pop(k)[1]
  37
  38     def __getitem__(self, key):
  39         index, value = self._content[key]
  40         return value
  41
  42     def __setitem__(self, key, value):
  43         try:
  44             index, oldvalue = self._content[key]
  45         except KeyError:
  46             index = len(self._keys)
  47             self._keys.append(key)
  48         self._content[key] = index, value
  49
  50     def __delitem__(self, key):
  51         index, oldvalue = self._content.pop(key)
  52         self._keys[index] = DELETED
  53         if self._deleted <= len(self._content):
  54             self._deleted += 1
  55         else:
  56             # compress
  57             newkeys = []
  58             for k in self._keys:
  59                 if k is not DELETED:
  60                     i, value = self._content[k]
  61                     self._content[k] = len(newkeys), value
  62                     newkeys.append(k)
  63             self._keys = newkeys
  64             self._deleted = 0
  65
  66     def __len__(self):
  67         return len(self._content)
  68
  69     def __repr__(self):
  70         res = ['%r: %r' % (key, self._content[key][1]) for key in self]
  71         return 'OrderedDict(%s)' % (', '.join(res),)
  72
  73     def __cmp__(self, other):
  74         if not isinstance(other, OrderedDict):
  75             return NotImplemented
  76         keys = self.keys()
  77         r = cmp(keys, other.keys())
  78         if r:
  79             return r
  80         for k in keys:
  81             r = cmp(self[k], other[k])
  82             if r:
  83                 return r
  84         return 0