ordereddict.py
Go to the documentation of this file.
00001 # Copyright (c) 2009 Raymond Hettinger
00002 #
00003 # Permission is hereby granted, free of charge, to any person
00004 # obtaining a copy of this software and associated documentation files
00005 # (the "Software"), to deal in the Software without restriction,
00006 # including without limitation the rights to use, copy, modify, merge,
00007 # publish, distribute, sublicense, and/or sell copies of the Software,
00008 # and to permit persons to whom the Software is furnished to do so,
00009 # subject to the following conditions:
00010 #
00011 #     The above copyright notice and this permission notice shall be
00012 #     included in all copies or substantial portions of the Software.
00013 #
00014 #     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00015 #     EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
00016 #     OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00017 #     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
00018 #     HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
00019 #     WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
00020 #     FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
00021 #     OTHER DEALINGS IN THE SOFTWARE.
00022 
00023 from UserDict import DictMixin
00024 
00025 class OrderedDict(dict, DictMixin):
00026 
00027     def __init__(self, *args, **kwds):
00028         if len(args) > 1:
00029             raise TypeError('expected at most 1 arguments, got %d' % len(args))
00030         try:
00031             self.__end
00032         except AttributeError:
00033             self.clear()
00034         self.update(*args, **kwds)
00035 
00036     def clear(self):
00037         self.__end = end = []
00038         end += [None, end, end]         # sentinel node for doubly linked list
00039         self.__map = {}                 # key --> [key, prev, next]
00040         dict.clear(self)
00041 
00042     def __setitem__(self, key, value):
00043         if key not in self:
00044             end = self.__end
00045             curr = end[1]
00046             curr[2] = end[1] = self.__map[key] = [key, curr, end]
00047         dict.__setitem__(self, key, value)
00048 
00049     def __delitem__(self, key):
00050         dict.__delitem__(self, key)
00051         key, prev, next = self.__map.pop(key)
00052         prev[2] = next
00053         next[1] = prev
00054 
00055     def __iter__(self):
00056         end = self.__end
00057         curr = end[2]
00058         while curr is not end:
00059             yield curr[0]
00060             curr = curr[2]
00061 
00062     def __reversed__(self):
00063         end = self.__end
00064         curr = end[1]
00065         while curr is not end:
00066             yield curr[0]
00067             curr = curr[1]
00068 
00069     def popitem(self, last=True):
00070         if not self:
00071             raise KeyError('dictionary is empty')
00072         if last:
00073             key = reversed(self).next()
00074         else:
00075             key = iter(self).next()
00076         value = self.pop(key)
00077         return key, value
00078 
00079     def __reduce__(self):
00080         items = [[k, self[k]] for k in self]
00081         tmp = self.__map, self.__end
00082         del self.__map, self.__end
00083         inst_dict = vars(self).copy()
00084         self.__map, self.__end = tmp
00085         if inst_dict:
00086             return (self.__class__, (items,), inst_dict)
00087         return self.__class__, (items,)
00088 
00089     def keys(self):
00090         return list(self)
00091 
00092     setdefault = DictMixin.setdefault
00093     update = DictMixin.update
00094     pop = DictMixin.pop
00095     values = DictMixin.values
00096     items = DictMixin.items
00097     iterkeys = DictMixin.iterkeys
00098     itervalues = DictMixin.itervalues
00099     iteritems = DictMixin.iteritems
00100 
00101     def __repr__(self):
00102         if not self:
00103             return '%s()' % (self.__class__.__name__,)
00104         return '%s(%r)' % (self.__class__.__name__, self.items())
00105 
00106     def copy(self):
00107         return self.__class__(self)
00108 
00109     @classmethod
00110     def fromkeys(cls, iterable, value=None):
00111         d = cls()
00112         for key in iterable:
00113             d[key] = value
00114         return d
00115 
00116     def __eq__(self, other):
00117         if isinstance(other, OrderedDict):
00118             if len(self) != len(other):
00119                 return False
00120             for p, q in  zip(self.items(), other.items()):
00121                 if p != q:
00122                     return False
00123             return True
00124         return dict.__eq__(self, other)
00125 
00126     def __ne__(self, other):
00127         return not self == other
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends


bride
Author(s): Alexander Bubeck
autogenerated on Wed Aug 14 2013 10:05:57