1#!/usr/bin/env python 2from __future__ import absolute_import, division, print_function 3"""A dictionary in which the order of adding items is preserved. 4 5Replacing an existing item replaces it at its current location. 6 7Deprecated: use collections.OrderedDict instead 8 9History: 102002-02-01 ROwen First release. 112002-02-04 ROwen Added code for iterkeys, itervalues and iteritems 12 (as I feared I would have to do, but my limited tests suggested otherwise). 13 Thanks to Jason Orendorff for insisting and for supplying the nice code 14 for itervalues and iteritems. Also added __str__ and copy methods, 15 allowed the constructor to make copies and improved the self tests. 162002-02-05 ROwen Keys now returns a copy of the keys instead of the internal list. 17 Added the remaining missing methods: popitem, setdefault and update. 18 Made all iterators explicitly depend on self.iterkeys(), reducing dependency 19 on internals and so making it easier to subclass OrderedDict. 202003-08-05 ROwen Modified to accept a sequence as an initializer (like normal dict). 212004-03-25 ROwen Added sort method to OrderedDict. 222005-04-13 ROwen Added ReverseOrderedDict. 23 Corrected some odd indentation. 242005-06-09 ROwen Bug fix: pop needed to be implemented. 252005-06-15 ROwen Added index and insert methods. 262005-06-27 ROwen Fixed a nonfunctional assert statement in the test code. 27 Added a #! line. 282005-08-12 ROwen Applied changes kindly suggested by "bearophile": 29 - Redefined copy to make subclassing easier and safer. 30 - Renamed checkIntegrity to _checkIntegrity. 31 - Eliminated use of the obsolete string module. 32 Bug fix: ReverseOrderedDict.copy returned an OrderedDict 33 instead of a ReverseOrderedDict. 34 Modified __repr__ to return a string that can recreate the dict. 35 Added __str__ to output the traditional dict representation. 362015-09-24 ROwen Replace "== None" with "is None" to modernize the code. 37""" 38__all__ = ["OrderedDict", "ReverseOrderedDict"] 39 40class OrderedDict(dict): 41 """A dictionary in which the order of adding items is preserved. 42 Replacing an existing item replaces it at its current location. 43 44 Inputs: 45 - seqOrDict: a sequence of (key, value) tuples or a dictionary 46 """ 47 def __init__(self, seqOrDict=None): 48 dict.__init__(self) 49 self.__keyList = [] 50 if seqOrDict is None: 51 return 52 elif hasattr(seqOrDict, "iteritems"): 53 for key, val in seqOrDict.iteritems(): 54 self[key] = val 55 else: 56 for key, val in seqOrDict: 57 self[key] = val 58 59 def clear(self): 60 self.__keyList = [] 61 dict.clear(self) 62 63 def copy(self): 64 return self.__class__(self) 65 66 def iterkeys(self): 67 return iter(self.__keyList) 68 69 def itervalues(self): 70 for key in self.iterkeys(): 71 yield self[key] 72 73 def iteritems(self): 74 for key in self: 75 yield (key, self[key]) 76 77 def index(self, key): 78 """Return the index of key. 79 Raise KeyError if not found. 80 """ 81 try: 82 return self.__keyList.index(key) 83 except ValueError: 84 raise KeyError("key=%r not in %s" % (key, self.__class__.__name__)) 85 86 def insert(self, ind, key, value): 87 """Insert a key, value pair before the specified index. 88 If the key already exists, it is NOT moved but its value is updated. 89 ind >= len appends to the end (like list.index). 90 """ 91 if key not in self: 92 self.__keyList.insert(ind, key) 93 dict.__setitem__(self, key, value) 94 95 def keys(self): 96 return self.__keyList[:] 97 98 def pop(self, key): 99 val = self[key] 100 self.__delitem__(key) 101 return val 102 103 def popitem(self, i=-1): 104 """Remove the ith item from the dictionary (the last item if i is omitted) 105 and returns (key, value). This emulates list.pop() instead of dict.popitem(), 106 since ordered dictionaries have a defined order. 107 """ 108 key = self.__keyList[i] 109 item = (key, self[key]) 110 self.__delitem__(key) 111 return item 112 113 def setdefault(self, key, value): 114 if key not in self: 115 self[key] = value 116 return self[key] 117 118 def sort(self, cmpFunc=None): 119 """Sort the keys. 120 """ 121 self.__keyList.sort(cmpFunc) 122 123 def update(self, aDict): 124 """Add all items from dictionary aDict to self (in order if aDict is an ordered dictionary). 125 """ 126 for key, value in aDict.iteritems(): 127 self[key] = value 128 129 def values(self): 130 return [self[key] for key in self.iterkeys()] 131 132 def _checkIntegrity(self): 133 """Perform an internal consistency check and raise an AssertionError if anything is wrong. 134 135 In principal a bug could lead to the system getting out of synch, hence this method. 136 """ 137 assert len(self) == len(self.__keyList), \ 138 "length of dict %r != length of key list %r" % (len(self), len(self.__keyList)) 139 for key in self.iterkeys(): 140 assert key in self, \ 141 "key %r in key list missing from dictionary" % (key,) 142 143 def __delitem__(self, key): 144 dict.__delitem__(self, key) 145 self.__keyList.remove(key) 146 147 def __iter__(self): 148 return self.iterkeys() 149 150 def __repr__(self): 151 return "%s([%s])" % (self.__class__.__name__, ', '.join(["(%r, %r)" % item for item in self.iteritems()])) 152 153 def __str__(self): 154 return "{%s}" % (', '.join(["(%r, %r)" % item for item in self.iteritems()]),) 155 156 def __setitem__(self, key, value): 157 if not self.has_key(key): 158 self.__keyList.append(key) 159 dict.__setitem__(self, key, value) 160 161 162class ReverseOrderedDict(OrderedDict): 163 """An ordered dictionary in which each new item is stored at the front. 164 Replacing an existing item replaces it at its current location. 165 166 Inputs: 167 - seqOrDict: a sequence of (key, value) tuples or a dictionary 168 169 Note: the data from seqOrDict will be reversed in the dict 170 because seqOrDict is read in normal left-to-right order 171 and each new entry goes at the beginning of the dict. Thus 172 ReverseOrderedDict([(1, "a"), (2, "b")]) stores keys in order 2, 1. 173 174 This has one nasty side effect: repr() shows the items 175 in the reverse order in which they are stored internally. 176 This is because it shows the call needed to recreate the dict. 177 str() has no such issues. Thus str() and repr() show the data 178 in opposite order. str() is generally what you want to see. 179 """ 180 def __setitem__(self, key, value): 181 if key not in self: 182 self._OrderedDict__keyList.insert(0, key) 183 dict.__setitem__(self, key, value) 184 185 def copy(self): 186 revCopy = self.__class__(self) 187 revCopy._OrderedDict__keyList.reverse() 188 return revCopy 189 190 def __repr__(self): 191 descrList = ["(%r, %r)" % item for item in self.iteritems()] 192 descrList.reverse() 193 return "%s([%s])" % (self.__class__.__name__, ', '.join(descrList)) 194 195if __name__ == "__main__": 196 print("testing OrderedDict") 197 import copy 198 import random 199 200 # basic setup 201 showOutput = 0 # display results or just complain if failure? 202 nItems = 10 # length of dictionary to test 203 nToDelete = 2 # number of items to delete 204 nToReplace = 5 # number of items to replace 205 206 assert nToDelete > 0 207 assert nToReplace > 0 208 assert nItems >= nToDelete + nToReplace 209 210 def testDict(desKeys, desValues, theDict): 211 """Test an ordered dictionary, given the expected keys and values (in order)""" 212 actKeys = theDict.keys() 213 assert desKeys == actKeys, "keys() failed; keys %r != %r" % (desKeys, actKeys) 214 215 actValues = theDict.values() 216 assert desValues == actValues, "values() failed; values %r != %r" % (desValues, actValues) 217 218 assert len(theDict) == len(desKeys), "len() failed: %r != %r" % (len(desKeys), len(theDict)) 219 220 # verify that iteration works: 221 actKeys = [key for key in theDict] 222 assert desKeys == actKeys, "__iter__() failed; keys %r != %r" % (desKeys, actKeys) 223 224 actValues = [v for v in theDict.itervalues()] 225 assert desValues == actValues, "itervalues() failed; values %r != %r" % (desValues, actValues) 226 227 desKeyValues = map(lambda key, v: (key, v), desKeys, desValues) 228 actKeyValues = [kv for kv in theDict.iteritems()] 229 assert desKeyValues == actKeyValues, "iteritems() failed; values %r != %r" % (desKeyValues, actKeyValues) 230 231 theDict._checkIntegrity() 232 233 234 def keyToValue(key): 235 return "val[%r]" % (key,) 236 237 def altKeyToValue(key): 238 return "alt[%r]" % (key,) 239 240 oDict = OrderedDict() 241 242 # start with a simple dictionary with no repeating keys 243 inKeys = [x for x in range(0, nItems)] 244 random.shuffle(inKeys) 245 inValues = [keyToValue(key) for key in inKeys] 246 for key in inKeys: 247 oDict[key] = keyToValue(key) 248 if showOutput: 249 print(("initial dictionary: %r" % (oDict))) 250 testDict(inKeys, inValues, oDict) 251 252 # now delete some items 253 for ii in range(nToDelete): 254 delKey = random.choice(inKeys) 255 inKeys.remove(delKey) 256 del(oDict[delKey]) 257 inValues = [keyToValue(key) for key in inKeys] 258 if showOutput: 259 print(("after %r items removed: %r" % (nToDelete, oDict))) 260 testDict(inKeys, inValues, oDict) 261 262 # now replace some items; use new values so you can tell the difference 263 replaceKeys = copy.deepcopy(inKeys) 264 random.shuffle(replaceKeys) 265 replaceKeys = replaceKeys[0:nToReplace] 266 for key in replaceKeys: 267 ind = inKeys.index(key) 268 inValues[ind] = altKeyToValue(key) 269 oDict[key] = altKeyToValue(key) 270 testDict(inKeys, inValues, oDict) 271 if showOutput: 272 print(("after replacing %r items: %r" % (nToReplace, oDict))) 273 274 # test copying 275 dictCopy = oDict.copy() 276 assert dictCopy.keys() == oDict.keys(), "copy failed; keys %r != %r" % (dictCopy.keys(), testDict.keys()) 277 278 testKey = dictCopy.keys()[0] 279 dictCopy[testKey] = "changed value" 280 assert dictCopy.values() != oDict.values(), "copy failed; changing a value in one affected the other" 281 282 # add a new item to dictCopy and make sure the integrity of both are preserved 283 # (verifies that the __keyList lists in each dictionary are separate entities) 284 dictCopy[()] = "value for ()" 285 dictCopy._checkIntegrity() 286 oDict._checkIntegrity() 287