1import copy
2import pickle
3from random import shuffle
4import unittest
5from collections import OrderedDict
6from collections import MutableMapping
7from test import mapping_tests, test_support
8
9
10class TestOrderedDict(unittest.TestCase):
11
12    def test_init(self):
13        with self.assertRaises(TypeError):
14            OrderedDict([('a', 1), ('b', 2)], None)                                 # too many args
15        pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
16        self.assertEqual(sorted(OrderedDict(dict(pairs)).items()), pairs)           # dict input
17        self.assertEqual(sorted(OrderedDict(**dict(pairs)).items()), pairs)         # kwds input
18        self.assertEqual(list(OrderedDict(pairs).items()), pairs)                   # pairs input
19        self.assertEqual(list(OrderedDict([('a', 1), ('b', 2), ('c', 9), ('d', 4)],
20                                          c=3, e=5).items()), pairs)                # mixed input
21
22        # make sure no positional args conflict with possible kwdargs
23        self.assertEqual(list(OrderedDict(self=42).items()), [('self', 42)])
24        self.assertEqual(list(OrderedDict(other=42).items()), [('other', 42)])
25        self.assertRaises(TypeError, OrderedDict, 42)
26        self.assertRaises(TypeError, OrderedDict, (), ())
27        self.assertRaises(TypeError, OrderedDict.__init__)
28
29        # Make sure that direct calls to __init__ do not clear previous contents
30        d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)])
31        d.__init__([('e', 5), ('f', 6)], g=7, d=4)
32        self.assertEqual(list(d.items()),
33            [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)])
34
35    def test_update(self):
36        with self.assertRaises(TypeError):
37            OrderedDict().update([('a', 1), ('b', 2)], None)                        # too many args
38        pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
39        od = OrderedDict()
40        od.update(dict(pairs))
41        self.assertEqual(sorted(od.items()), pairs)                                 # dict input
42        od = OrderedDict()
43        od.update(**dict(pairs))
44        self.assertEqual(sorted(od.items()), pairs)                                 # kwds input
45        od = OrderedDict()
46        od.update(pairs)
47        self.assertEqual(list(od.items()), pairs)                                   # pairs input
48        od = OrderedDict()
49        od.update([('a', 1), ('b', 2), ('c', 9), ('d', 4)], c=3, e=5)
50        self.assertEqual(list(od.items()), pairs)                                   # mixed input
51
52        # Issue 9137: Named argument called 'other' or 'self'
53        # shouldn't be treated specially.
54        od = OrderedDict()
55        od.update(self=23)
56        self.assertEqual(list(od.items()), [('self', 23)])
57        od = OrderedDict()
58        od.update(other={})
59        self.assertEqual(list(od.items()), [('other', {})])
60        od = OrderedDict()
61        od.update(red=5, blue=6, other=7, self=8)
62        self.assertEqual(sorted(list(od.items())),
63                         [('blue', 6), ('other', 7), ('red', 5), ('self', 8)])
64
65        # Make sure that direct calls to update do not clear previous contents
66        # add that updates items are not moved to the end
67        d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)])
68        d.update([('e', 5), ('f', 6)], g=7, d=4)
69        self.assertEqual(list(d.items()),
70            [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)])
71
72        self.assertRaises(TypeError, OrderedDict().update, 42)
73        self.assertRaises(TypeError, OrderedDict().update, (), ())
74        self.assertRaises(TypeError, OrderedDict.update)
75
76    def test_abc(self):
77        self.assertIsInstance(OrderedDict(), MutableMapping)
78        self.assertTrue(issubclass(OrderedDict, MutableMapping))
79
80    def test_clear(self):
81        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
82        shuffle(pairs)
83        od = OrderedDict(pairs)
84        self.assertEqual(len(od), len(pairs))
85        od.clear()
86        self.assertEqual(len(od), 0)
87
88    def test_delitem(self):
89        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
90        od = OrderedDict(pairs)
91        del od['a']
92        self.assertNotIn('a', od)
93        with self.assertRaises(KeyError):
94            del od['a']
95        self.assertEqual(list(od.items()), pairs[:2] + pairs[3:])
96
97    def test_setitem(self):
98        od = OrderedDict([('d', 1), ('b', 2), ('c', 3), ('a', 4), ('e', 5)])
99        od['c'] = 10           # existing element
100        od['f'] = 20           # new element
101        self.assertEqual(list(od.items()),
102                         [('d', 1), ('b', 2), ('c', 10), ('a', 4), ('e', 5), ('f', 20)])
103
104    def test_iterators(self):
105        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
106        shuffle(pairs)
107        od = OrderedDict(pairs)
108        self.assertEqual(list(od), [t[0] for t in pairs])
109        self.assertEqual(od.keys()[:], [t[0] for t in pairs])
110        self.assertEqual(od.values()[:], [t[1] for t in pairs])
111        self.assertEqual(od.items()[:], pairs)
112        self.assertEqual(list(od.iterkeys()), [t[0] for t in pairs])
113        self.assertEqual(list(od.itervalues()), [t[1] for t in pairs])
114        self.assertEqual(list(od.iteritems()), pairs)
115        self.assertEqual(list(reversed(od)),
116                         [t[0] for t in reversed(pairs)])
117
118    def test_popitem(self):
119        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
120        shuffle(pairs)
121        od = OrderedDict(pairs)
122        while pairs:
123            self.assertEqual(od.popitem(), pairs.pop())
124        with self.assertRaises(KeyError):
125            od.popitem()
126        self.assertEqual(len(od), 0)
127
128    def test_pop(self):
129        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
130        shuffle(pairs)
131        od = OrderedDict(pairs)
132        shuffle(pairs)
133        while pairs:
134            k, v = pairs.pop()
135            self.assertEqual(od.pop(k), v)
136        with self.assertRaises(KeyError):
137            od.pop('xyz')
138        self.assertEqual(len(od), 0)
139        self.assertEqual(od.pop(k, 12345), 12345)
140
141        # make sure pop still works when __missing__ is defined
142        class Missing(OrderedDict):
143            def __missing__(self, key):
144                return 0
145        m = Missing(a=1)
146        self.assertEqual(m.pop('b', 5), 5)
147        self.assertEqual(m.pop('a', 6), 1)
148        self.assertEqual(m.pop('a', 6), 6)
149        with self.assertRaises(KeyError):
150            m.pop('a')
151
152    def test_equality(self):
153        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
154        shuffle(pairs)
155        od1 = OrderedDict(pairs)
156        od2 = OrderedDict(pairs)
157        self.assertEqual(od1, od2)          # same order implies equality
158        pairs = pairs[2:] + pairs[:2]
159        od2 = OrderedDict(pairs)
160        self.assertNotEqual(od1, od2)       # different order implies inequality
161        # comparison to regular dict is not order sensitive
162        self.assertEqual(od1, dict(od2))
163        self.assertEqual(dict(od2), od1)
164        # different length implied inequality
165        self.assertNotEqual(od1, OrderedDict(pairs[:-1]))
166
167    def test_copying(self):
168        # Check that ordered dicts are copyable, deepcopyable, picklable,
169        # and have a repr/eval round-trip
170        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
171        od = OrderedDict(pairs)
172        update_test = OrderedDict()
173        update_test.update(od)
174        for i, dup in enumerate([
175                    od.copy(),
176                    copy.copy(od),
177                    copy.deepcopy(od),
178                    pickle.loads(pickle.dumps(od, 0)),
179                    pickle.loads(pickle.dumps(od, 1)),
180                    pickle.loads(pickle.dumps(od, 2)),
181                    pickle.loads(pickle.dumps(od, -1)),
182                    eval(repr(od)),
183                    update_test,
184                    OrderedDict(od),
185                    ]):
186            self.assertTrue(dup is not od)
187            self.assertEqual(dup, od)
188            self.assertEqual(list(dup.items()), list(od.items()))
189            self.assertEqual(len(dup), len(od))
190            self.assertEqual(type(dup), type(od))
191
192    def test_yaml_linkage(self):
193        # Verify that __reduce__ is setup in a way that supports PyYAML's dump() feature.
194        # In yaml, lists are native but tuples are not.
195        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
196        od = OrderedDict(pairs)
197        # yaml.dump(od) -->
198        # '!!python/object/apply:__main__.OrderedDict\n- - [a, 1]\n  - [b, 2]\n'
199        self.assertTrue(all(type(pair)==list for pair in od.__reduce__()[1]))
200
201    def test_reduce_not_too_fat(self):
202        # do not save instance dictionary if not needed
203        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
204        od = OrderedDict(pairs)
205        self.assertEqual(len(od.__reduce__()), 2)
206        od.x = 10
207        self.assertEqual(len(od.__reduce__()), 3)
208
209    def test_repr(self):
210        od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])
211        self.assertEqual(repr(od),
212            "OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])")
213        self.assertEqual(eval(repr(od)), od)
214        self.assertEqual(repr(OrderedDict()), "OrderedDict()")
215
216    def test_repr_recursive(self):
217        # See issue #9826
218        od = OrderedDict.fromkeys('abc')
219        od['x'] = od
220        self.assertEqual(repr(od),
221            "OrderedDict([('a', None), ('b', None), ('c', None), ('x', ...)])")
222
223    def test_repr_recursive_values(self):
224        od = OrderedDict()
225        od[42] = od.viewvalues()
226        r = repr(od)
227        # Cannot perform a stronger test, as the contents of the repr
228        # are implementation-dependent.  All we can say is that we
229        # want a str result, not an exception of any sort.
230        self.assertIsInstance(r, str)
231        od[42] = od.viewitems()
232        r = repr(od)
233        # Again.
234        self.assertIsInstance(r, str)
235
236    def test_setdefault(self):
237        pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
238        shuffle(pairs)
239        od = OrderedDict(pairs)
240        pair_order = list(od.items())
241        self.assertEqual(od.setdefault('a', 10), 3)
242        # make sure order didn't change
243        self.assertEqual(list(od.items()), pair_order)
244        self.assertEqual(od.setdefault('x', 10), 10)
245        # make sure 'x' is added to the end
246        self.assertEqual(list(od.items())[-1], ('x', 10))
247
248        # make sure setdefault still works when __missing__ is defined
249        class Missing(OrderedDict):
250            def __missing__(self, key):
251                return 0
252        self.assertEqual(Missing().setdefault(5, 9), 9)
253
254    def test_reinsert(self):
255        # Given insert a, insert b, delete a, re-insert a,
256        # verify that a is now later than b.
257        od = OrderedDict()
258        od['a'] = 1
259        od['b'] = 2
260        del od['a']
261        od['a'] = 1
262        self.assertEqual(list(od.items()), [('b', 2), ('a', 1)])
263
264    def test_views(self):
265        s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split()
266        od = OrderedDict.fromkeys(s)
267        self.assertEqual(list(od.viewkeys()),  s)
268        self.assertEqual(list(od.viewvalues()),  [None for k in s])
269        self.assertEqual(list(od.viewitems()),  [(k, None) for k in s])
270
271        # See http://bugs.python.org/issue24286
272        self.assertEqual(od.viewkeys(), dict(od).viewkeys())
273        self.assertEqual(od.viewitems(), dict(od).viewitems())
274
275    def test_override_update(self):
276        # Verify that subclasses can override update() without breaking __init__()
277        class MyOD(OrderedDict):
278            def update(self, *args, **kwds):
279                raise Exception()
280        items = [('a', 1), ('c', 3), ('b', 2)]
281        self.assertEqual(list(MyOD(items).items()), items)
282
283    def test_free_after_iterating(self):
284        test_support.check_free_after_iterating(self, iter, OrderedDict)
285        test_support.check_free_after_iterating(self, lambda d: d.iterkeys(), OrderedDict)
286        test_support.check_free_after_iterating(self, lambda d: d.itervalues(), OrderedDict)
287        test_support.check_free_after_iterating(self, lambda d: d.iteritems(), OrderedDict)
288        test_support.check_free_after_iterating(self, lambda d: iter(d.viewkeys()), OrderedDict)
289        test_support.check_free_after_iterating(self, lambda d: iter(d.viewvalues()), OrderedDict)
290        test_support.check_free_after_iterating(self, lambda d: iter(d.viewitems()), OrderedDict)
291
292class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
293    type2test = OrderedDict
294
295    def test_popitem(self):
296        d = self._empty_mapping()
297        self.assertRaises(KeyError, d.popitem)
298
299class MyOrderedDict(OrderedDict):
300    pass
301
302class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
303    type2test = MyOrderedDict
304
305    def test_popitem(self):
306        d = self._empty_mapping()
307        self.assertRaises(KeyError, d.popitem)
308
309
310def test_main(verbose=None):
311    test_classes = [TestOrderedDict, GeneralMappingTests, SubclassMappingTests]
312    test_support.run_unittest(*test_classes)
313
314if __name__ == "__main__":
315    test_main(verbose=True)
316