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