Lib/test/test_collections.py

   1 """Unit tests for collections.py."""
   2
   3 import unittest, doctest
   4 import inspect
   5 from test import support
   6 from collections import namedtuple, Counter, OrderedDict
   7 from test import mapping_tests
   8 import pickle, copy
   9 from random import randrange, shuffle
  10 import operator
  11 import keyword
  12 import re
  13 from collections import Hashable, Iterable, Iterator
  14 from collections import Sized, Container, Callable
  15 from collections import Set, MutableSet
  16 from collections import Mapping, MutableMapping
  17 from collections import Sequence, MutableSequence
  18 from collections import ByteString
  19
  20 TestNT = namedtuple('TestNT', 'x y z')    # type used for pickle tests
  21
  22 class TestNamedTuple(unittest.TestCase):
  23
  24     def test_factory(self):
  25         Point = namedtuple('Point', 'x y')
  26         self.assertEqual(Point.__name__, 'Point')
  27         self.assertEqual(Point.__doc__, 'Point(x, y)')
  28         self.assertEqual(Point.__slots__, ())
  29         self.assertEqual(Point.__module__, __name__)
  30         self.assertEqual(Point.__getitem__, tuple.__getitem__)
  31         self.assertEqual(Point._fields, ('x', 'y'))
  32
  33         self.assertRaises(ValueError, namedtuple, 'abc%', 'efg ghi')       # type has non-alpha char
  34         self.assertRaises(ValueError, namedtuple, 'class', 'efg ghi')      # type has keyword
  35         self.assertRaises(ValueError, namedtuple, '9abc', 'efg ghi')       # type starts with digit
  36
  37         self.assertRaises(ValueError, namedtuple, 'abc', 'efg g%hi')       # field with non-alpha char
  38         self.assertRaises(ValueError, namedtuple, 'abc', 'abc class')      # field has keyword
  39         self.assertRaises(ValueError, namedtuple, 'abc', '8efg 9ghi')      # field starts with digit
  40         self.assertRaises(ValueError, namedtuple, 'abc', '_efg ghi')       # field with leading underscore
  41         self.assertRaises(ValueError, namedtuple, 'abc', 'efg efg ghi')    # duplicate field
  42
  43         namedtuple('Point0', 'x1 y2')   # Verify that numbers are allowed in names
  44         namedtuple('_', 'a b c')        # Test leading underscores in a typename
  45
  46         nt = namedtuple('nt', 'the quick brown fox')                       # check unicode input
  47         self.assert_("u'" not in repr(nt._fields))
  48         nt = namedtuple('nt', ('the', 'quick'))                           # check unicode input
  49         self.assert_("u'" not in repr(nt._fields))
  50
  51         self.assertRaises(TypeError, Point._make, [11])                     # catch too few args
  52         self.assertRaises(TypeError, Point._make, [11, 22, 33])             # catch too many args
  53
  54     def test_name_fixer(self):
  55         for spec, renamed in [
  56             [('efg', 'g%hi'),  ('efg', '_1')],                              # field with non-alpha char
  57             [('abc', 'class'), ('abc', '_1')],                              # field has keyword
  58             [('8efg', '9ghi'), ('_0', '_1')],                               # field starts with digit
  59             [('abc', '_efg'), ('abc', '_1')],                               # field with leading underscore
  60             [('abc', 'efg', 'efg', 'ghi'), ('abc', 'efg', '_2', 'ghi')],    # duplicate field
  61             [('abc', '', 'x'), ('abc', '_1', 'x')],                         # fieldname is a space
  62         ]:
  63             self.assertEqual(namedtuple('NT', spec, rename=True)._fields, renamed)
  64
  65     def test_instance(self):
  66         Point = namedtuple('Point', 'x y')
  67         p = Point(11, 22)
  68         self.assertEqual(p, Point(x=11, y=22))
  69         self.assertEqual(p, Point(11, y=22))
  70         self.assertEqual(p, Point(y=22, x=11))
  71         self.assertEqual(p, Point(*(11, 22)))
  72         self.assertEqual(p, Point(**dict(x=11, y=22)))
  73         self.assertRaises(TypeError, Point, 1)                              # too few args
  74         self.assertRaises(TypeError, Point, 1, 2, 3)                        # too many args
  75         self.assertRaises(TypeError, eval, 'Point(XXX=1, y=2)', locals())   # wrong keyword argument
  76         self.assertRaises(TypeError, eval, 'Point(x=1)', locals())          # missing keyword argument
  77         self.assertEqual(repr(p), 'Point(x=11, y=22)')
  78         self.assert_('__dict__' not in dir(p))                              # verify instance has no dict
  79         self.assert_('__weakref__' not in dir(p))
  80         self.assertEqual(p, Point._make([11, 22]))                          # test _make classmethod
  81         self.assertEqual(p._fields, ('x', 'y'))                             # test _fields attribute
  82         self.assertEqual(p._replace(x=1), (1, 22))                          # test _replace method
  83         self.assertEqual(p._asdict(), dict(x=11, y=22))                     # test _asdict method
  84
  85         try:
  86             p._replace(x=1, error=2)
  87         except ValueError:
  88             pass
  89         else:
  90             self._fail('Did not detect an incorrect fieldname')
  91
  92         # verify that field string can have commas
  93         Point = namedtuple('Point', 'x, y')
  94         p = Point(x=11, y=22)
  95         self.assertEqual(repr(p), 'Point(x=11, y=22)')
  96
  97         # verify that fieldspec can be a non-string sequence
  98         Point = namedtuple('Point', ('x', 'y'))
  99         p = Point(x=11, y=22)
 100         self.assertEqual(repr(p), 'Point(x=11, y=22)')
 101
 102     def test_tupleness(self):
 103         Point = namedtuple('Point', 'x y')
 104         p = Point(11, 22)
 105
 106         self.assert_(isinstance(p, tuple))
 107         self.assertEqual(p, (11, 22))                                       # matches a real tuple
 108         self.assertEqual(tuple(p), (11, 22))                                # coercable to a real tuple
 109         self.assertEqual(list(p), [11, 22])                                 # coercable to a list
 110         self.assertEqual(max(p), 22)                                        # iterable
 111         self.assertEqual(max(*p), 22)                                       # star-able
 112         x, y = p
 113         self.assertEqual(p, (x, y))                                         # unpacks like a tuple
 114         self.assertEqual((p[0], p[1]), (11, 22))                            # indexable like a tuple
 115         self.assertRaises(IndexError, p.__getitem__, 3)
 116
 117         self.assertEqual(p.x, x)
 118         self.assertEqual(p.y, y)
 119         self.assertRaises(AttributeError, eval, 'p.z', locals())
 120
 121     def test_odd_sizes(self):
 122         Zero = namedtuple('Zero', '')
 123         self.assertEqual(Zero(), ())
 124         self.assertEqual(Zero._make([]), ())
 125         self.assertEqual(repr(Zero()), 'Zero()')
 126         self.assertEqual(Zero()._asdict(), {})
 127         self.assertEqual(Zero()._fields, ())
 128
 129         Dot = namedtuple('Dot', 'd')
 130         self.assertEqual(Dot(1), (1,))
 131         self.assertEqual(Dot._make([1]), (1,))
 132         self.assertEqual(Dot(1).d, 1)
 133         self.assertEqual(repr(Dot(1)), 'Dot(d=1)')
 134         self.assertEqual(Dot(1)._asdict(), {'d':1})
 135         self.assertEqual(Dot(1)._replace(d=999), (999,))
 136         self.assertEqual(Dot(1)._fields, ('d',))
 137
 138         # n = 5000
 139         n = 254 # SyntaxError: more than 255 arguments:
 140         import string, random
 141         names = list(set(''.join([random.choice(string.ascii_letters)
 142                                   for j in range(10)]) for i in range(n)))
 143         n = len(names)
 144         Big = namedtuple('Big', names)
 145         b = Big(*range(n))
 146         self.assertEqual(b, tuple(range(n)))
 147         self.assertEqual(Big._make(range(n)), tuple(range(n)))
 148         for pos, name in enumerate(names):
 149             self.assertEqual(getattr(b, name), pos)
 150         repr(b)                                 # make sure repr() doesn't blow-up
 151         d = b._asdict()
 152         d_expected = dict(zip(names, range(n)))
 153         self.assertEqual(d, d_expected)
 154         b2 = b._replace(**dict([(names[1], 999),(names[-5], 42)]))
 155         b2_expected = list(range(n))
 156         b2_expected[1] = 999
 157         b2_expected[-5] = 42
 158         self.assertEqual(b2, tuple(b2_expected))
 159         self.assertEqual(b._fields, tuple(names))
 160
 161     def test_pickle(self):
 162         p = TestNT(x=10, y=20, z=30)
 163         for module in (pickle,):
 164             loads = getattr(module, 'loads')
 165             dumps = getattr(module, 'dumps')
 166             for protocol in -1, 0, 1, 2:
 167                 q = loads(dumps(p, protocol))
 168                 self.assertEqual(p, q)
 169                 self.assertEqual(p._fields, q._fields)
 170
 171     def test_copy(self):
 172         p = TestNT(x=10, y=20, z=30)
 173         for copier in copy.copy, copy.deepcopy:
 174             q = copier(p)
 175             self.assertEqual(p, q)
 176             self.assertEqual(p._fields, q._fields)
 177
 178     def test_name_conflicts(self):
 179         # Some names like "self", "cls", "tuple", "itemgetter", and "property"
 180         # failed when used as field names.  Test to make sure these now work.
 181         T = namedtuple('T', 'itemgetter property self cls tuple')
 182         t = T(1, 2, 3, 4, 5)
 183         self.assertEqual(t, (1,2,3,4,5))
 184         newt = t._replace(itemgetter=10, property=20, self=30, cls=40, tuple=50)
 185         self.assertEqual(newt, (10,20,30,40,50))
 186
 187         # Broader test of all interesting names in a template
 188         with support.captured_stdout() as template:
 189             T = namedtuple('T', 'x', verbose=True)
 190         words = set(re.findall('[A-Za-z]+', template.getvalue()))
 191         words -= set(keyword.kwlist)
 192         T = namedtuple('T', words)
 193         # test __new__
 194         values = tuple(range(len(words)))
 195         t = T(*values)
 196         self.assertEqual(t, values)
 197         t = T(**dict(zip(T._fields, values)))
 198         self.assertEqual(t, values)
 199         # test _make
 200         t = T._make(values)
 201         self.assertEqual(t, values)
 202         # exercise __repr__
 203         repr(t)
 204         # test _asdict
 205         self.assertEqual(t._asdict(), dict(zip(T._fields, values)))
 206         # test _replace
 207         t = T._make(values)
 208         newvalues = tuple(v*10 for v in values)
 209         newt = t._replace(**dict(zip(T._fields, newvalues)))
 210         self.assertEqual(newt, newvalues)
 211         # test _fields
 212         self.assertEqual(T._fields, tuple(words))
 213         # test __getnewargs__
 214         self.assertEqual(t.__getnewargs__(), values)
 215
 216 class ABCTestCase(unittest.TestCase):
 217
 218     def validate_abstract_methods(self, abc, *names):
 219         methodstubs = dict.fromkeys(names, lambda s, *args: 0)
 220
 221         # everything should work will all required methods are present
 222         C = type('C', (abc,), methodstubs)
 223         C()
 224
 225         # instantiation should fail if a required method is missing
 226         for name in names:
 227             stubs = methodstubs.copy()
 228             del stubs[name]
 229             C = type('C', (abc,), stubs)
 230             self.assertRaises(TypeError, C, name)
 231
 232
 233 class TestOneTrickPonyABCs(ABCTestCase):
 234
 235     def test_Hashable(self):
 236         # Check some non-hashables
 237         non_samples = [bytearray(), list(), set(), dict()]
 238         for x in non_samples:
 239             self.failIf(isinstance(x, Hashable), repr(x))
 240             self.failIf(issubclass(type(x), Hashable), repr(type(x)))
 241         # Check some hashables
 242         samples = [None,
 243                    int(), float(), complex(),
 244                    str(),
 245                    tuple(), frozenset(),
 246                    int, list, object, type, bytes()
 247                    ]
 248         for x in samples:
 249             self.failUnless(isinstance(x, Hashable), repr(x))
 250             self.failUnless(issubclass(type(x), Hashable), repr(type(x)))
 251         self.assertRaises(TypeError, Hashable)
 252         # Check direct subclassing
 253         class H(Hashable):
 254             def __hash__(self):
 255                 return super().__hash__()
 256         self.assertEqual(hash(H()), 0)
 257         self.failIf(issubclass(int, H))
 258         self.validate_abstract_methods(Hashable, '__hash__')
 259
 260     def test_Iterable(self):
 261         # Check some non-iterables
 262         non_samples = [None, 42, 3.14, 1j]
 263         for x in non_samples:
 264             self.failIf(isinstance(x, Iterable), repr(x))
 265             self.failIf(issubclass(type(x), Iterable), repr(type(x)))
 266         # Check some iterables
 267         samples = [bytes(), str(),
 268                    tuple(), list(), set(), frozenset(), dict(),
 269                    dict().keys(), dict().items(), dict().values(),
 270                    (lambda: (yield))(),
 271                    (x for x in []),
 272                    ]
 273         for x in samples:
 274             self.failUnless(isinstance(x, Iterable), repr(x))
 275             self.failUnless(issubclass(type(x), Iterable), repr(type(x)))
 276         # Check direct subclassing
 277         class I(Iterable):
 278             def __iter__(self):
 279                 return super().__iter__()
 280         self.assertEqual(list(I()), [])
 281         self.failIf(issubclass(str, I))
 282         self.validate_abstract_methods(Iterable, '__iter__')
 283
 284     def test_Iterator(self):
 285         non_samples = [None, 42, 3.14, 1j, b"", "", (), [], {}, set()]
 286         for x in non_samples:
 287             self.failIf(isinstance(x, Iterator), repr(x))
 288             self.failIf(issubclass(type(x), Iterator), repr(type(x)))
 289         samples = [iter(bytes()), iter(str()),
 290                    iter(tuple()), iter(list()), iter(dict()),
 291                    iter(set()), iter(frozenset()),
 292                    iter(dict().keys()), iter(dict().items()),
 293                    iter(dict().values()),
 294                    (lambda: (yield))(),
 295                    (x for x in []),
 296                    ]
 297         for x in samples:
 298             self.failUnless(isinstance(x, Iterator), repr(x))
 299             self.failUnless(issubclass(type(x), Iterator), repr(type(x)))
 300         self.validate_abstract_methods(Iterator, '__next__')
 301
 302     def test_Sized(self):
 303         non_samples = [None, 42, 3.14, 1j,
 304                        (lambda: (yield))(),
 305                        (x for x in []),
 306                        ]
 307         for x in non_samples:
 308             self.failIf(isinstance(x, Sized), repr(x))
 309             self.failIf(issubclass(type(x), Sized), repr(type(x)))
 310         samples = [bytes(), str(),
 311                    tuple(), list(), set(), frozenset(), dict(),
 312                    dict().keys(), dict().items(), dict().values(),
 313                    ]
 314         for x in samples:
 315             self.failUnless(isinstance(x, Sized), repr(x))
 316             self.failUnless(issubclass(type(x), Sized), repr(type(x)))
 317         self.validate_abstract_methods(Sized, '__len__')
 318
 319     def test_Container(self):
 320         non_samples = [None, 42, 3.14, 1j,
 321                        (lambda: (yield))(),
 322                        (x for x in []),
 323                        ]
 324         for x in non_samples:
 325             self.failIf(isinstance(x, Container), repr(x))
 326             self.failIf(issubclass(type(x), Container), repr(type(x)))
 327         samples = [bytes(), str(),
 328                    tuple(), list(), set(), frozenset(), dict(),
 329                    dict().keys(), dict().items(),
 330                    ]
 331         for x in samples:
 332             self.failUnless(isinstance(x, Container), repr(x))
 333             self.failUnless(issubclass(type(x), Container), repr(type(x)))
 334         self.validate_abstract_methods(Container, '__contains__')
 335
 336     def test_Callable(self):
 337         non_samples = [None, 42, 3.14, 1j,
 338                        "", b"", (), [], {}, set(),
 339                        (lambda: (yield))(),
 340                        (x for x in []),
 341                        ]
 342         for x in non_samples:
 343             self.failIf(isinstance(x, Callable), repr(x))
 344             self.failIf(issubclass(type(x), Callable), repr(type(x)))
 345         samples = [lambda: None,
 346                    type, int, object,
 347                    len,
 348                    list.append, [].append,
 349                    ]
 350         for x in samples:
 351             self.failUnless(isinstance(x, Callable), repr(x))
 352             self.failUnless(issubclass(type(x), Callable), repr(type(x)))
 353         self.validate_abstract_methods(Callable, '__call__')
 354
 355     def test_direct_subclassing(self):
 356         for B in Hashable, Iterable, Iterator, Sized, Container, Callable:
 357             class C(B):
 358                 pass
 359             self.failUnless(issubclass(C, B))
 360             self.failIf(issubclass(int, C))
 361
 362     def test_registration(self):
 363         for B in Hashable, Iterable, Iterator, Sized, Container, Callable:
 364             class C:
 365                 __hash__ = None  # Make sure it isn't hashable by default
 366             self.failIf(issubclass(C, B), B.__name__)
 367             B.register(C)
 368             self.failUnless(issubclass(C, B))
 369
 370 class WithSet(MutableSet):
 371
 372     def __init__(self, it=()):
 373         self.data = set(it)
 374
 375     def __len__(self):
 376         return len(self.data)
 377
 378     def __iter__(self):
 379         return iter(self.data)
 380
 381     def __contains__(self, item):
 382         return item in self.data
 383
 384     def add(self, item):
 385         self.data.add(item)
 386
 387     def discard(self, item):
 388         self.data.discard(item)
 389
 390 class TestCollectionABCs(ABCTestCase):
 391
 392     # XXX For now, we only test some virtual inheritance properties.
 393     # We should also test the proper behavior of the collection ABCs
 394     # as real base classes or mix-in classes.
 395
 396     def test_Set(self):
 397         for sample in [set, frozenset]:
 398             self.failUnless(isinstance(sample(), Set))
 399             self.failUnless(issubclass(sample, Set))
 400         self.validate_abstract_methods(Set, '__contains__', '__iter__', '__len__')
 401
 402     def test_hash_Set(self):
 403         class OneTwoThreeSet(Set):
 404             def __init__(self):
 405                 self.contents = [1, 2, 3]
 406             def __contains__(self, x):
 407                 return x in self.contents
 408             def __len__(self):
 409                 return len(self.contents)
 410             def __iter__(self):
 411                 return iter(self.contents)
 412             def __hash__(self):
 413                 return self._hash()
 414         a, b = OneTwoThreeSet(), OneTwoThreeSet()
 415         self.failUnless(hash(a) == hash(b))
 416
 417     def test_MutableSet(self):
 418         self.failUnless(isinstance(set(), MutableSet))
 419         self.failUnless(issubclass(set, MutableSet))
 420         self.failIf(isinstance(frozenset(), MutableSet))
 421         self.failIf(issubclass(frozenset, MutableSet))
 422         self.validate_abstract_methods(MutableSet, '__contains__', '__iter__', '__len__',
 423             'add', 'discard')
 424
 425     def test_issue_5647(self):
 426         # MutableSet.__iand__ mutated the set during iteration
 427         s = WithSet('abcd')
 428         s &= WithSet('cdef')            # This used to fail
 429         self.assertEqual(set(s), set('cd'))
 430
 431     def test_issue_4920(self):
 432         # MutableSet.pop() method did not work
 433         class MySet(collections.MutableSet):
 434             __slots__=['__s']
 435             def __init__(self,items=None):
 436                 if items is None:
 437                     items=[]
 438                 self.__s=set(items)
 439             def __contains__(self,v):
 440                 return v in self.__s
 441             def __iter__(self):
 442                 return iter(self.__s)
 443             def __len__(self):
 444                 return len(self.__s)
 445             def add(self,v):
 446                 result=v not in self.__s
 447                 self.__s.add(v)
 448                 return result
 449             def discard(self,v):
 450                 result=v in self.__s
 451                 self.__s.discard(v)
 452                 return result
 453             def __repr__(self):
 454                 return "MySet(%s)" % repr(list(self))
 455         s = MySet([5,43,2,1])
 456         self.assertEqual(s.pop(), 1)
 457
 458     def test_Mapping(self):
 459         for sample in [dict]:
 460             self.failUnless(isinstance(sample(), Mapping))
 461             self.failUnless(issubclass(sample, Mapping))
 462         self.validate_abstract_methods(Mapping, '__contains__', '__iter__', '__len__',
 463             '__getitem__')
 464
 465     def test_MutableMapping(self):
 466         for sample in [dict]:
 467             self.failUnless(isinstance(sample(), MutableMapping))
 468             self.failUnless(issubclass(sample, MutableMapping))
 469         self.validate_abstract_methods(MutableMapping, '__contains__', '__iter__', '__len__',
 470             '__getitem__', '__setitem__', '__delitem__')
 471
 472     def test_Sequence(self):
 473         for sample in [tuple, list, bytes, str]:
 474             self.failUnless(isinstance(sample(), Sequence))
 475             self.failUnless(issubclass(sample, Sequence))
 476         self.failUnless(isinstance(range(10), Sequence))
 477         self.failUnless(issubclass(range, Sequence))
 478         self.failUnless(issubclass(str, Sequence))
 479         self.validate_abstract_methods(Sequence, '__contains__', '__iter__', '__len__',
 480             '__getitem__')
 481
 482     def test_ByteString(self):
 483         for sample in [bytes, bytearray]:
 484             self.failUnless(isinstance(sample(), ByteString))
 485             self.failUnless(issubclass(sample, ByteString))
 486         for sample in [str, list, tuple]:
 487             self.failIf(isinstance(sample(), ByteString))
 488             self.failIf(issubclass(sample, ByteString))
 489         self.failIf(isinstance(memoryview(b""), ByteString))
 490         self.failIf(issubclass(memoryview, ByteString))
 491
 492     def test_MutableSequence(self):
 493         for sample in [tuple, str, bytes]:
 494             self.failIf(isinstance(sample(), MutableSequence))
 495             self.failIf(issubclass(sample, MutableSequence))
 496         for sample in [list, bytearray]:
 497             self.failUnless(isinstance(sample(), MutableSequence))
 498             self.failUnless(issubclass(sample, MutableSequence))
 499         self.failIf(issubclass(str, MutableSequence))
 500         self.validate_abstract_methods(MutableSequence, '__contains__', '__iter__',
 501             '__len__', '__getitem__', '__setitem__', '__delitem__', 'insert')
 502
 503 class TestCounter(unittest.TestCase):
 504
 505     def test_basics(self):
 506         c = Counter('abcaba')
 507         self.assertEqual(c, Counter({'a':3 , 'b': 2, 'c': 1}))
 508         self.assertEqual(c, Counter(a=3, b=2, c=1))
 509         self.assert_(isinstance(c, dict))
 510         self.assert_(isinstance(c, Mapping))
 511         self.assert_(issubclass(Counter, dict))
 512         self.assert_(issubclass(Counter, Mapping))
 513         self.assertEqual(len(c), 3)
 514         self.assertEqual(sum(c.values()), 6)
 515         self.assertEqual(sorted(c.values()), [1, 2, 3])
 516         self.assertEqual(sorted(c.keys()), ['a', 'b', 'c'])
 517         self.assertEqual(sorted(c), ['a', 'b', 'c'])
 518         self.assertEqual(sorted(c.items()),
 519                          [('a', 3), ('b', 2), ('c', 1)])
 520         self.assertEqual(c['b'], 2)
 521         self.assertEqual(c['z'], 0)
 522         self.assertEqual(c.__contains__('c'), True)
 523         self.assertEqual(c.__contains__('z'), False)
 524         self.assertEqual(c.get('b', 10), 2)
 525         self.assertEqual(c.get('z', 10), 10)
 526         self.assertEqual(c, dict(a=3, b=2, c=1))
 527         self.assertEqual(repr(c), "Counter({'a': 3, 'b': 2, 'c': 1})")
 528         self.assertEqual(c.most_common(), [('a', 3), ('b', 2), ('c', 1)])
 529         for i in range(5):
 530             self.assertEqual(c.most_common(i),
 531                              [('a', 3), ('b', 2), ('c', 1)][:i])
 532         self.assertEqual(''.join(sorted(c.elements())), 'aaabbc')
 533         c['a'] += 1         # increment an existing value
 534         c['b'] -= 2         # sub existing value to zero
 535         del c['c']          # remove an entry
 536         del c['c']          # make sure that del doesn't raise KeyError
 537         c['d'] -= 2         # sub from a missing value
 538         c['e'] = -5         # directly assign a missing value
 539         c['f'] += 4         # add to a missing value
 540         self.assertEqual(c, dict(a=4, b=0, d=-2, e=-5, f=4))
 541         self.assertEqual(''.join(sorted(c.elements())), 'aaaaffff')
 542         self.assertEqual(c.pop('f'), 4)
 543         self.assertEqual('f' in c, False)
 544         for i in range(3):
 545             elem, cnt = c.popitem()
 546             self.assertEqual(elem in c, False)
 547         c.clear()
 548         self.assertEqual(c, {})
 549         self.assertEqual(repr(c), 'Counter()')
 550         self.assertRaises(NotImplementedError, Counter.fromkeys, 'abc')
 551         self.assertRaises(TypeError, hash, c)
 552         c.update(dict(a=5, b=3))
 553         c.update(c=1)
 554         c.update(Counter('a' * 50 + 'b' * 30))
 555         c.update()          # test case with no args
 556         c.__init__('a' * 500 + 'b' * 300)
 557         c.__init__('cdc')
 558         c.__init__()
 559         self.assertEqual(c, dict(a=555, b=333, c=3, d=1))
 560         self.assertEqual(c.setdefault('d', 5), 1)
 561         self.assertEqual(c['d'], 1)
 562         self.assertEqual(c.setdefault('e', 5), 5)
 563         self.assertEqual(c['e'], 5)
 564
 565     def test_copying(self):
 566         # Check that counters are copyable, deepcopyable, picklable, and
 567         #have a repr/eval round-trip
 568         words = Counter('which witch had which witches wrist watch'.split())
 569         update_test = Counter()
 570         update_test.update(words)
 571         for i, dup in enumerate([
 572                     words.copy(),
 573                     copy.copy(words),
 574                     copy.deepcopy(words),
 575                     pickle.loads(pickle.dumps(words, 0)),
 576                     pickle.loads(pickle.dumps(words, 1)),
 577                     pickle.loads(pickle.dumps(words, 2)),
 578                     pickle.loads(pickle.dumps(words, -1)),
 579                     eval(repr(words)),
 580                     update_test,
 581                     Counter(words),
 582                     ]):
 583             msg = (i, dup, words)
 584             self.assert_(dup is not words)
 585             self.assertEquals(dup, words)
 586             self.assertEquals(len(dup), len(words))
 587             self.assertEquals(type(dup), type(words))
 588
 589     def test_conversions(self):
 590         # Convert to: set, list, dict
 591         s = 'she sells sea shells by the sea shore'
 592         self.assertEqual(sorted(Counter(s).elements()), sorted(s))
 593         self.assertEqual(sorted(Counter(s)), sorted(set(s)))
 594         self.assertEqual(dict(Counter(s)), dict(Counter(s).items()))
 595         self.assertEqual(set(Counter(s)), set(s))
 596
 597     def test_invariant_for_the_in_operator(self):
 598         c = Counter(a=10, b=-2, c=0)
 599         for elem in c:
 600             self.assert_(elem in c)
 601
 602     def test_multiset_operations(self):
 603         # Verify that adding a zero counter will strip zeros and negatives
 604         c = Counter(a=10, b=-2, c=0) + Counter()
 605         self.assertEqual(dict(c), dict(a=10))
 606
 607         elements = 'abcd'
 608         for i in range(1000):
 609             # test random pairs of multisets
 610             p = Counter(dict((elem, randrange(-2,4)) for elem in elements))
 611             p.update(e=1, f=-1, g=0)
 612             q = Counter(dict((elem, randrange(-2,4)) for elem in elements))
 613             q.update(h=1, i=-1, j=0)
 614             for counterop, numberop in [
 615                 (Counter.__add__, lambda x, y: max(0, x+y)),
 616                 (Counter.__sub__, lambda x, y: max(0, x-y)),
 617                 (Counter.__or__, lambda x, y: max(0,x,y)),
 618                 (Counter.__and__, lambda x, y: max(0, min(x,y))),
 619             ]:
 620                 result = counterop(p, q)
 621                 for x in elements:
 622                     self.assertEqual(numberop(p[x], q[x]), result[x],
 623                                      (counterop, x, p, q))
 624                 # verify that results exclude non-positive counts
 625                 self.assert_(x>0 for x in result.values())
 626
 627         elements = 'abcdef'
 628         for i in range(100):
 629             # verify that random multisets with no repeats are exactly like sets
 630             p = Counter(dict((elem, randrange(0, 2)) for elem in elements))
 631             q = Counter(dict((elem, randrange(0, 2)) for elem in elements))
 632             for counterop, setop in [
 633                 (Counter.__sub__, set.__sub__),
 634                 (Counter.__or__, set.__or__),
 635                 (Counter.__and__, set.__and__),
 636             ]:
 637                 counter_result = counterop(p, q)
 638                 set_result = setop(set(p.elements()), set(q.elements()))
 639                 self.assertEqual(counter_result, dict.fromkeys(set_result, 1))
 640
 641
 642 class TestOrderedDict(unittest.TestCase):
 643
 644     def test_init(self):
 645         with self.assertRaises(TypeError):
 646             OrderedDict([('a', 1), ('b', 2)], None)                                 # too many args
 647         pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
 648         self.assertEqual(sorted(OrderedDict(dict(pairs)).items()), pairs)           # dict input
 649         self.assertEqual(sorted(OrderedDict(**dict(pairs)).items()), pairs)         # kwds input
 650         self.assertEqual(list(OrderedDict(pairs).items()), pairs)                   # pairs input
 651         self.assertEqual(list(OrderedDict([('a', 1), ('b', 2), ('c', 9), ('d', 4)],
 652                                           c=3, e=5).items()), pairs)                # mixed input
 653
 654         # make sure no positional args conflict with possible kwdargs
 655         self.assertEqual(inspect.getargspec(OrderedDict.__dict__['__init__']).args,
 656                          ['self'])
 657
 658         # Make sure that direct calls to __init__ do not clear previous contents
 659         d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)])
 660         d.__init__([('e', 5), ('f', 6)], g=7, d=4)
 661         self.assertEqual(list(d.items()),
 662             [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)])
 663
 664     def test_update(self):
 665         with self.assertRaises(TypeError):
 666             OrderedDict().update([('a', 1), ('b', 2)], None)                        # too many args
 667         pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
 668         od = OrderedDict()
 669         od.update(dict(pairs))
 670         self.assertEqual(sorted(od.items()), pairs)                                 # dict input
 671         od = OrderedDict()
 672         od.update(**dict(pairs))
 673         self.assertEqual(sorted(od.items()), pairs)                                 # kwds input
 674         od = OrderedDict()
 675         od.update(pairs)
 676         self.assertEqual(list(od.items()), pairs)                                   # pairs input
 677         od = OrderedDict()
 678         od.update([('a', 1), ('b', 2), ('c', 9), ('d', 4)], c=3, e=5)
 679         self.assertEqual(list(od.items()), pairs)                                   # mixed input
 680
 681         # Make sure that direct calls to update do not clear previous contents
 682         # add that updates items are not moved to the end
 683         d = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 44), ('e', 55)])
 684         d.update([('e', 5), ('f', 6)], g=7, d=4)
 685         self.assertEqual(list(d.items()),
 686             [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)])
 687
 688     def test_clear(self):
 689         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 690         shuffle(pairs)
 691         od = OrderedDict(pairs)
 692         self.assertEqual(len(od), len(pairs))
 693         od.clear()
 694         self.assertEqual(len(od), 0)
 695
 696     def test_delitem(self):
 697         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 698         od = OrderedDict(pairs)
 699         del od['a']
 700         self.assert_('a' not in od)
 701         with self.assertRaises(KeyError):
 702             del od['a']
 703         self.assertEqual(list(od.items()), pairs[:2] + pairs[3:])
 704
 705     def test_setitem(self):
 706         od = OrderedDict([('d', 1), ('b', 2), ('c', 3), ('a', 4), ('e', 5)])
 707         od['c'] = 10           # existing element
 708         od['f'] = 20           # new element
 709         self.assertEqual(list(od.items()),
 710                          [('d', 1), ('b', 2), ('c', 10), ('a', 4), ('e', 5), ('f', 20)])
 711
 712     def test_iterators(self):
 713         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 714         shuffle(pairs)
 715         od = OrderedDict(pairs)
 716         self.assertEqual(list(od), [t[0] for t in pairs])
 717         self.assertEqual(list(od.keys()), [t[0] for t in pairs])
 718         self.assertEqual(list(od.values()), [t[1] for t in pairs])
 719         self.assertEqual(list(od.items()), pairs)
 720         self.assertEqual(list(reversed(od)),
 721                          [t[0] for t in reversed(pairs)])
 722
 723     def test_popitem(self):
 724         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 725         shuffle(pairs)
 726         od = OrderedDict(pairs)
 727         while pairs:
 728             self.assertEqual(od.popitem(), pairs.pop())
 729         with self.assertRaises(KeyError):
 730             od.popitem()
 731         self.assertEqual(len(od), 0)
 732
 733     def test_pop(self):
 734         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 735         shuffle(pairs)
 736         od = OrderedDict(pairs)
 737         shuffle(pairs)
 738         while pairs:
 739             k, v = pairs.pop()
 740             self.assertEqual(od.pop(k), v)
 741         with self.assertRaises(KeyError):
 742             od.pop('xyz')
 743         self.assertEqual(len(od), 0)
 744         self.assertEqual(od.pop(k, 12345), 12345)
 745
 746     def test_equality(self):
 747         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 748         shuffle(pairs)
 749         od1 = OrderedDict(pairs)
 750         od2 = OrderedDict(pairs)
 751         self.assertEqual(od1, od2)          # same order implies equality
 752         pairs = pairs[2:] + pairs[:2]
 753         od2 = OrderedDict(pairs)
 754         self.assertNotEqual(od1, od2)       # different order implies inequality
 755         # comparison to regular dict is not order sensitive
 756         self.assertEqual(od1, dict(od2))
 757         self.assertEqual(dict(od2), od1)
 758         # different length implied inequality
 759         self.assertNotEqual(od1, OrderedDict(pairs[:-1]))
 760
 761     def test_copying(self):
 762         # Check that ordered dicts are copyable, deepcopyable, picklable,
 763         # and have a repr/eval round-trip
 764         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 765         od = OrderedDict(pairs)
 766         update_test = OrderedDict()
 767         update_test.update(od)
 768         for i, dup in enumerate([
 769                     od.copy(),
 770                     copy.copy(od),
 771                     copy.deepcopy(od),
 772                     pickle.loads(pickle.dumps(od, 0)),
 773                     pickle.loads(pickle.dumps(od, 1)),
 774                     pickle.loads(pickle.dumps(od, 2)),
 775                     pickle.loads(pickle.dumps(od, 3)),
 776                     pickle.loads(pickle.dumps(od, -1)),
 777                     eval(repr(od)),
 778                     update_test,
 779                     OrderedDict(od),
 780                     ]):
 781             self.assert_(dup is not od)
 782             self.assertEquals(dup, od)
 783             self.assertEquals(list(dup.items()), list(od.items()))
 784             self.assertEquals(len(dup), len(od))
 785             self.assertEquals(type(dup), type(od))
 786
 787     def test_yaml_linkage(self):
 788         # Verify that __reduce__ is setup in a way that supports PyYAML's dump() feature.
 789         # In yaml, lists are native but tuples are not.
 790         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 791         od = OrderedDict(pairs)
 792         # yaml.dump(od) -->
 793         # '!!python/object/apply:__main__.OrderedDict\n- - [a, 1]\n  - [b, 2]\n'
 794         self.assert_(all(type(pair)==list for pair in od.__reduce__()[1]))
 795
 796     def test_reduce_not_too_fat(self):
 797         # do not save instance dictionary if not needed
 798         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 799         od = OrderedDict(pairs)
 800         self.assertEqual(len(od.__reduce__()), 2)
 801         od.x = 10
 802         self.assertEqual(len(od.__reduce__()), 3)
 803
 804     def test_repr(self):
 805         od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])
 806         self.assertEqual(repr(od),
 807             "OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])")
 808         self.assertEqual(eval(repr(od)), od)
 809         self.assertEqual(repr(OrderedDict()), "OrderedDict()")
 810
 811     def test_setdefault(self):
 812         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
 813         shuffle(pairs)
 814         od = OrderedDict(pairs)
 815         pair_order = list(od.items())
 816         self.assertEqual(od.setdefault('a', 10), 3)
 817         # make sure order didn't change
 818         self.assertEqual(list(od.items()), pair_order)
 819         self.assertEqual(od.setdefault('x', 10), 10)
 820         # make sure 'x' is added to the end
 821         self.assertEqual(list(od.items())[-1], ('x', 10))
 822
 823     def test_reinsert(self):
 824         # Given insert a, insert b, delete a, re-insert a,
 825         # verify that a is now later than b.
 826         od = OrderedDict()
 827         od['a'] = 1
 828         od['b'] = 2
 829         del od['a']
 830         od['a'] = 1
 831         self.assertEqual(list(od.items()), [('b', 2), ('a', 1)])
 832
 833
 834
 835 class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
 836     type2test = OrderedDict
 837
 838     def test_popitem(self):
 839         d = self._empty_mapping()
 840         self.assertRaises(KeyError, d.popitem)
 841
 842 class MyOrderedDict(OrderedDict):
 843     pass
 844
 845 class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
 846     type2test = MyOrderedDict
 847
 848     def test_popitem(self):
 849         d = self._empty_mapping()
 850         self.assertRaises(KeyError, d.popitem)
 851
 852
 853 import doctest, collections
 854
 855 def test_main(verbose=None):
 856     NamedTupleDocs = doctest.DocTestSuite(module=collections)
 857     test_classes = [TestNamedTuple, NamedTupleDocs, TestOneTrickPonyABCs,
 858                     TestCollectionABCs, TestCounter,
 859                     TestOrderedDict, GeneralMappingTests, SubclassMappingTests]
 860     support.run_unittest(*test_classes)
 861     support.run_doctest(collections, verbose)
 862
 863
 864 if __name__ == "__main__":
 865     test_main(verbose=True)