diff options
| -rw-r--r-- | Doc/library/collections.rst | 29 | ||||
| -rw-r--r-- | Lib/collections.py | 78 | ||||
| -rw-r--r-- | Lib/test/test_collections.py | 197 | ||||
| -rw-r--r-- | Misc/NEWS | 2 |
4 files changed, 300 insertions, 6 deletions
diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst index c28704b..e4ad5f4 100644 --- a/Doc/library/collections.rst +++ b/Doc/library/collections.rst @@ -14,7 +14,7 @@ __name__ = '<doctest>' This module implements high-performance container datatypes. Currently, -there are three datatypes, :class:`Counter`, :class:`deque` and +there are four datatypes, :class:`Counter`, :class:`deque`, :class:`OrderedDict` and :class:`defaultdict`, and one datatype factory function, :func:`namedtuple`. The specialized containers provided in this module provide alternatives @@ -806,6 +806,33 @@ and more efficient to use a simple class declaration: adapted for Python 2.4. +:class:`OrderedDict` objects +---------------------------- + +Ordered dictionaries are just like regular dictionaries but they remember the +order that items were inserted. When iterating over an ordered dictionary, +the items are returned in the order their keys were first added. + +.. class:: OrderedDict([items]) + + Return an instance of a dict subclass, supporting the usual :class:`dict` + methods. An *OrderedDict* is a dict that remembers the order that keys + were first inserted. If a new entry overwrites an existing entry, the + original insertion position is left unchanged. Deleting an entry and + reinserting it will move it to the end. + + .. versionadded:: 2.7 + +The :meth:`popitem` method for ordered dictionaries returns and removes the +last added entry. The key/value pairs are returned in LIFO order. + +Equality tests between :class:`OrderedDict` objects are order-sensitive +and are implemented as ``list(od1.items())==list(od2.items())``. +Equality tests between :class:`OrderedDict` objects and other +:class:`Mapping` objects are order-insensitive like regular dictionaries. +This allows :class:`OrderedDict` objects to be substituted anywhere a +regular dictionary is used. + :class:`UserDict` objects ------------------------- diff --git a/Lib/collections.py b/Lib/collections.py index f8392b6..b65e12f 100644 --- a/Lib/collections.py +++ b/Lib/collections.py @@ -1,5 +1,5 @@ __all__ = ['deque', 'defaultdict', 'namedtuple', 'UserDict', 'UserList', - 'UserString', 'Counter'] + 'UserString', 'Counter', 'OrderedDict'] # For bootstrapping reasons, the collection ABCs are defined in _abcoll.py. # They should however be considered an integral part of collections.py. from _abcoll import * @@ -11,7 +11,81 @@ from operator import itemgetter as _itemgetter from keyword import iskeyword as _iskeyword import sys as _sys import heapq as _heapq -from itertools import repeat as _repeat, chain as _chain, starmap as _starmap +from itertools import repeat as _repeat, chain as _chain, starmap as _starmap, \ + zip_longest as _zip_longest + +################################################################################ +### OrderedDict +################################################################################ + +class OrderedDict(dict, MutableMapping): + + def __init__(self, *args, **kwds): + if len(args) > 1: + raise TypeError('expected at most 1 arguments, got %d' % len(args)) + if not hasattr(self, '_keys'): + self._keys = [] + self.update(*args, **kwds) + + def clear(self): + del self._keys[:] + dict.clear(self) + + def __setitem__(self, key, value): + if key not in self: + self._keys.append(key) + dict.__setitem__(self, key, value) + + def __delitem__(self, key): + dict.__delitem__(self, key) + self._keys.remove(key) + + def __iter__(self): + return iter(self._keys) + + def __reversed__(self): + return reversed(self._keys) + + def popitem(self): + if not self: + raise KeyError('dictionary is empty') + key = self._keys.pop() + value = dict.pop(self, key) + return key, value + + def __reduce__(self): + items = [[k, self[k]] for k in self] + inst_dict = vars(self).copy() + inst_dict.pop('_keys', None) + return (self.__class__, (items,), inst_dict) + + setdefault = MutableMapping.setdefault + update = MutableMapping.update + pop = MutableMapping.pop + keys = MutableMapping.keys + values = MutableMapping.values + items = MutableMapping.items + + def __repr__(self): + if not self: + return '%s()' % (self.__class__.__name__,) + return '%s(%r)' % (self.__class__.__name__, list(self.items())) + + def copy(self): + return self.__class__(self) + + @classmethod + def fromkeys(cls, iterable, value=None): + d = cls() + for key in iterable: + d[key] = value + return d + + def __eq__(self, other): + if isinstance(other, OrderedDict): + return all(p==q for p, q in _zip_longest(self.items(), other.items())) + return dict.__eq__(self, other) + ################################################################################ diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py index c73d89b..1e23d5b 100644 --- a/Lib/test/test_collections.py +++ b/Lib/test/test_collections.py @@ -1,10 +1,12 @@ """Unit tests for collections.py.""" import unittest, doctest +import inspect from test import support -from collections import namedtuple, Counter, Mapping +from collections import namedtuple, Counter, OrderedDict +from test import mapping_tests import pickle, copy -from random import randrange +from random import randrange, shuffle import operator from collections import Hashable, Iterable, Iterator from collections import Sized, Container, Callable @@ -571,12 +573,201 @@ class TestCounter(unittest.TestCase): set_result = setop(set(p.elements()), set(q.elements())) self.assertEqual(counter_result, dict.fromkeys(set_result, 1)) + +class TestOrderedDict(unittest.TestCase): + + def test_init(self): + with self.assertRaises(TypeError): + OrderedDict([('a', 1), ('b', 2)], None) # too many args + pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] + self.assertEqual(sorted(OrderedDict(dict(pairs)).items()), pairs) # dict input + self.assertEqual(sorted(OrderedDict(**dict(pairs)).items()), pairs) # kwds input + self.assertEqual(list(OrderedDict(pairs).items()), pairs) # pairs input + self.assertEqual(list(OrderedDict([('a', 1), ('b', 2), ('c', 9), ('d', 4)], + c=3, e=5).items()), pairs) # mixed input + + # make sure no positional args conflict with possible kwdargs + self.assertEqual(inspect.getargspec(OrderedDict.__dict__['__init__']).args, + ['self']) + + # Make sure that direct calls to __init__ do not clear previous contents + d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)]) + d.__init__([('e', 5), ('f', 6)], g=7, d=4) + self.assertEqual(list(d.items()), + [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)]) + + def test_update(self): + with self.assertRaises(TypeError): + OrderedDict().update([('a', 1), ('b', 2)], None) # too many args + pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] + od = OrderedDict() + od.update(dict(pairs)) + self.assertEqual(sorted(od.items()), pairs) # dict input + od = OrderedDict() + od.update(**dict(pairs)) + self.assertEqual(sorted(od.items()), pairs) # kwds input + od = OrderedDict() + od.update(pairs) + self.assertEqual(list(od.items()), pairs) # pairs input + od = OrderedDict() + od.update([('a', 1), ('b', 2), ('c', 9), ('d', 4)], c=3, e=5) + self.assertEqual(list(od.items()), pairs) # mixed input + + # Make sure that direct calls to update do not clear previous contents + # add that updates items are not moved to the end + d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)]) + d.update([('e', 5), ('f', 6)], g=7, d=4) + self.assertEqual(list(d.items()), + [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)]) + + def test_clear(self): + pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] + shuffle(pairs) + od = OrderedDict(pairs) + self.assertEqual(len(od), len(pairs)) + od.clear() + self.assertEqual(len(od), 0) + + def test_delitem(self): + pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] + od = OrderedDict(pairs) + del od['a'] + self.assert_('a' not in od) + with self.assertRaises(KeyError): + del od['a'] + self.assertEqual(list(od.items()), pairs[:2] + pairs[3:]) + + def test_setitem(self): + od = OrderedDict([('d', 1), ('b', 2), ('c', 3), ('a', 4), ('e', 5)]) + od['c'] = 10 # existing element + od['f'] = 20 # new element + self.assertEqual(list(od.items()), + [('d', 1), ('b', 2), ('c', 10), ('a', 4), ('e', 5), ('f', 20)]) + + def test_iterators(self): + pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] + shuffle(pairs) + od = OrderedDict(pairs) + self.assertEqual(list(od), [t[0] for t in pairs]) + self.assertEqual(list(od.keys()), [t[0] for t in pairs]) + self.assertEqual(list(od.values()), [t[1] for t in pairs]) + self.assertEqual(list(od.items()), pairs) + self.assertEqual(list(reversed(od)), + [t[0] for t in reversed(pairs)]) + + def test_popitem(self): + pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] + shuffle(pairs) + od = OrderedDict(pairs) + while pairs: + self.assertEqual(od.popitem(), pairs.pop()) + with self.assertRaises(KeyError): + od.popitem() + self.assertEqual(len(od), 0) + + def test_pop(self): + pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] + shuffle(pairs) + od = OrderedDict(pairs) + shuffle(pairs) + while pairs: + k, v = pairs.pop() + self.assertEqual(od.pop(k), v) + with self.assertRaises(KeyError): + od.pop('xyz') + self.assertEqual(len(od), 0) + self.assertEqual(od.pop(k, 12345), 12345) + + def test_equality(self): + pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] + shuffle(pairs) + od1 = OrderedDict(pairs) + od2 = OrderedDict(pairs) + self.assertEqual(od1, od2) # same order implies equality + pairs = pairs[2:] + pairs[:2] + od2 = OrderedDict(pairs) + self.assertNotEqual(od1, od2) # different order implies inequality + # comparison to regular dict is not order sensitive + self.assertEqual(od1, dict(od2)) + self.assertEqual(dict(od2), od1) + # different length implied inequality + self.assertNotEqual(od1, OrderedDict(pairs[:-1])) + + def test_copying(self): + # Check that ordered dicts are copyable, deepcopyable, picklable, + # and have a repr/eval round-trip + pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] + od = OrderedDict(pairs) + update_test = OrderedDict() + update_test.update(od) + for i, dup in enumerate([ + od.copy(), + copy.copy(od), + copy.deepcopy(od), + pickle.loads(pickle.dumps(od, 0)), + pickle.loads(pickle.dumps(od, 1)), + pickle.loads(pickle.dumps(od, 2)), + pickle.loads(pickle.dumps(od, 3)), + pickle.loads(pickle.dumps(od, -1)), + eval(repr(od)), + update_test, + OrderedDict(od), + ]): + self.assert_(dup is not od) + self.assertEquals(dup, od) + self.assertEquals(list(dup.items()), list(od.items())) + self.assertEquals(len(dup), len(od)) + self.assertEquals(type(dup), type(od)) + + def test_repr(self): + od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]) + self.assertEqual(repr(od), + "OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])") + self.assertEqual(eval(repr(od)), od) + self.assertEqual(repr(OrderedDict()), "OrderedDict()") + + def test_setdefault(self): + pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] + shuffle(pairs) + od = OrderedDict(pairs) + pair_order = list(od.items()) + self.assertEqual(od.setdefault('a', 10), 3) + # make sure order didn't change + self.assertEqual(list(od.items()), pair_order) + self.assertEqual(od.setdefault('x', 10), 10) + # make sure 'x' is added to the end + self.assertEqual(list(od.items())[-1], ('x', 10)) + + def test_reinsert(self): + # Given insert a, insert b, delete a, re-insert a, + # verify that a is now later than b. + od = OrderedDict() + od['a'] = 1 + od['b'] = 2 + del od['a'] + od['a'] = 1 + self.assertEqual(list(od.items()), [('b', 2), ('a', 1)]) + + + +class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol): + type2test = OrderedDict + +class MyOrderedDict(OrderedDict): + pass + +class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol): + type2test = MyOrderedDict + + + import doctest, collections def test_main(verbose=None): NamedTupleDocs = doctest.DocTestSuite(module=collections) test_classes = [TestNamedTuple, NamedTupleDocs, TestOneTrickPonyABCs, - TestCollectionABCs, TestCounter] + TestCollectionABCs, TestCounter, + TestOrderedDict, GeneralMappingTests, SubclassMappingTests] support.run_unittest(*test_classes) support.run_doctest(collections, verbose) @@ -175,6 +175,8 @@ Core and Builtins Library ------- +- PEP 372: Added collections.OrderedDict(). + - Issue #1733986: Fixed mmap crash in accessing elements of second map object with same tagname but larger size than first map. (Windows) |