Source Code for Module Bio._py3k._ordereddict

  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 
129