Lib/test/test_collections.py

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