Lib/test/test_collections.py

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