AppPkg/Applications/Python/Python-2.7.10/Lib/collections.py

   1 __all__ = ['Counter', 'deque', 'defaultdict', 'namedtuple', 'OrderedDict']
   2 # For bootstrapping reasons, the collection ABCs are defined in _abcoll.py.
   3 # They should however be considered an integral part of collections.py.
   4 from _abcoll import *
   5 import _abcoll
   6 __all__ += _abcoll.__all__
   7
   8 from _collections import deque, defaultdict
   9 from operator import itemgetter as _itemgetter, eq as _eq
  10 from keyword import iskeyword as _iskeyword
  11 import sys as _sys
  12 import heapq as _heapq
  13 from itertools import repeat as _repeat, chain as _chain, starmap as _starmap
  14 from itertools import imap as _imap
  15
  16 try:
  17     from thread import get_ident as _get_ident
  18 except ImportError:
  19     from dummy_thread import get_ident as _get_ident
  20
  21
  22 ################################################################################
  23 ### OrderedDict
  24 ################################################################################
  25
  26 class OrderedDict(dict):
  27     'Dictionary that remembers insertion order'
  28     # An inherited dict maps keys to values.
  29     # The inherited dict provides __getitem__, __len__, __contains__, and get.
  30     # The remaining methods are order-aware.
  31     # Big-O running times for all methods are the same as regular dictionaries.
  32
  33     # The internal self.__map dict maps keys to links in a doubly linked list.
  34     # The circular doubly linked list starts and ends with a sentinel element.
  35     # The sentinel element never gets deleted (this simplifies the algorithm).
  36     # Each link is stored as a list of length three:  [PREV, NEXT, KEY].
  37
  38     def __init__(*args, **kwds):
  39         '''Initialize an ordered dictionary.  The signature is the same as
  40         regular dictionaries, but keyword arguments are not recommended because
  41         their insertion order is arbitrary.
  42
  43         '''
  44         if not args:
  45             raise TypeError("descriptor '__init__' of 'OrderedDict' object "
  46                             "needs an argument")
  47         self = args[0]
  48         args = args[1:]
  49         if len(args) > 1:
  50             raise TypeError('expected at most 1 arguments, got %d' % len(args))
  51         try:
  52             self.__root
  53         except AttributeError:
  54             self.__root = root = []                     # sentinel node
  55             root[:] = [root, root, None]
  56             self.__map = {}
  57         self.__update(*args, **kwds)
  58
  59     def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
  60         'od.__setitem__(i, y) <==> od[i]=y'
  61         # Setting a new item creates a new link at the end of the linked list,
  62         # and the inherited dictionary is updated with the new key/value pair.
  63         if key not in self:
  64             root = self.__root
  65             last = root[0]
  66             last[1] = root[0] = self.__map[key] = [last, root, key]
  67         return dict_setitem(self, key, value)
  68
  69     def __delitem__(self, key, dict_delitem=dict.__delitem__):
  70         'od.__delitem__(y) <==> del od[y]'
  71         # Deleting an existing item uses self.__map to find the link which gets
  72         # removed by updating the links in the predecessor and successor nodes.
  73         dict_delitem(self, key)
  74         link_prev, link_next, _ = self.__map.pop(key)
  75         link_prev[1] = link_next                        # update link_prev[NEXT]
  76         link_next[0] = link_prev                        # update link_next[PREV]
  77
  78     def __iter__(self):
  79         'od.__iter__() <==> iter(od)'
  80         # Traverse the linked list in order.
  81         root = self.__root
  82         curr = root[1]                                  # start at the first node
  83         while curr is not root:
  84             yield curr[2]                               # yield the curr[KEY]
  85             curr = curr[1]                              # move to next node
  86
  87     def __reversed__(self):
  88         'od.__reversed__() <==> reversed(od)'
  89         # Traverse the linked list in reverse order.
  90         root = self.__root
  91         curr = root[0]                                  # start at the last node
  92         while curr is not root:
  93             yield curr[2]                               # yield the curr[KEY]
  94             curr = curr[0]                              # move to previous node
  95
  96     def clear(self):
  97         'od.clear() -> None.  Remove all items from od.'
  98         root = self.__root
  99         root[:] = [root, root, None]
 100         self.__map.clear()
 101         dict.clear(self)
 102
 103     # -- the following methods do not depend on the internal structure --
 104
 105     def keys(self):
 106         'od.keys() -> list of keys in od'
 107         return list(self)
 108
 109     def values(self):
 110         'od.values() -> list of values in od'
 111         return [self[key] for key in self]
 112
 113     def items(self):
 114         'od.items() -> list of (key, value) pairs in od'
 115         return [(key, self[key]) for key in self]
 116
 117     def iterkeys(self):
 118         'od.iterkeys() -> an iterator over the keys in od'
 119         return iter(self)
 120
 121     def itervalues(self):
 122         'od.itervalues -> an iterator over the values in od'
 123         for k in self:
 124             yield self[k]
 125
 126     def iteritems(self):
 127         'od.iteritems -> an iterator over the (key, value) pairs in od'
 128         for k in self:
 129             yield (k, self[k])
 130
 131     update = MutableMapping.update
 132
 133     __update = update # let subclasses override update without breaking __init__
 134
 135     __marker = object()
 136
 137     def pop(self, key, default=__marker):
 138         '''od.pop(k[,d]) -> v, remove specified key and return the corresponding
 139         value.  If key is not found, d is returned if given, otherwise KeyError
 140         is raised.
 141
 142         '''
 143         if key in self:
 144             result = self[key]
 145             del self[key]
 146             return result
 147         if default is self.__marker:
 148             raise KeyError(key)
 149         return default
 150
 151     def setdefault(self, key, default=None):
 152         'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
 153         if key in self:
 154             return self[key]
 155         self[key] = default
 156         return default
 157
 158     def popitem(self, last=True):
 159         '''od.popitem() -> (k, v), return and remove a (key, value) pair.
 160         Pairs are returned in LIFO order if last is true or FIFO order if false.
 161
 162         '''
 163         if not self:
 164             raise KeyError('dictionary is empty')
 165         key = next(reversed(self) if last else iter(self))
 166         value = self.pop(key)
 167         return key, value
 168
 169     def __repr__(self, _repr_running={}):
 170         'od.__repr__() <==> repr(od)'
 171         call_key = id(self), _get_ident()
 172         if call_key in _repr_running:
 173             return '...'
 174         _repr_running[call_key] = 1
 175         try:
 176             if not self:
 177                 return '%s()' % (self.__class__.__name__,)
 178             return '%s(%r)' % (self.__class__.__name__, self.items())
 179         finally:
 180             del _repr_running[call_key]
 181
 182     def __reduce__(self):
 183         'Return state information for pickling'
 184         items = [[k, self[k]] for k in self]
 185         inst_dict = vars(self).copy()
 186         for k in vars(OrderedDict()):
 187             inst_dict.pop(k, None)
 188         if inst_dict:
 189             return (self.__class__, (items,), inst_dict)
 190         return self.__class__, (items,)
 191
 192     def copy(self):
 193         'od.copy() -> a shallow copy of od'
 194         return self.__class__(self)
 195
 196     @classmethod
 197     def fromkeys(cls, iterable, value=None):
 198         '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.
 199         If not specified, the value defaults to None.
 200
 201         '''
 202         self = cls()
 203         for key in iterable:
 204             self[key] = value
 205         return self
 206
 207     def __eq__(self, other):
 208         '''od.__eq__(y) <==> od==y.  Comparison to another OD is order-sensitive
 209         while comparison to a regular mapping is order-insensitive.
 210
 211         '''
 212         if isinstance(other, OrderedDict):
 213             return dict.__eq__(self, other) and all(_imap(_eq, self, other))
 214         return dict.__eq__(self, other)
 215
 216     def __ne__(self, other):
 217         'od.__ne__(y) <==> od!=y'
 218         return not self == other
 219
 220     # -- the following methods support python 3.x style dictionary views --
 221
 222     def viewkeys(self):
 223         "od.viewkeys() -> a set-like object providing a view on od's keys"
 224         return KeysView(self)
 225
 226     def viewvalues(self):
 227         "od.viewvalues() -> an object providing a view on od's values"
 228         return ValuesView(self)
 229
 230     def viewitems(self):
 231         "od.viewitems() -> a set-like object providing a view on od's items"
 232         return ItemsView(self)
 233
 234
 235 ################################################################################
 236 ### namedtuple
 237 ################################################################################
 238
 239 _class_template = '''\
 240 class {typename}(tuple):
 241     '{typename}({arg_list})'
 242
 243     __slots__ = ()
 244
 245     _fields = {field_names!r}
 246
 247     def __new__(_cls, {arg_list}):
 248         'Create new instance of {typename}({arg_list})'
 249         return _tuple.__new__(_cls, ({arg_list}))
 250
 251     @classmethod
 252     def _make(cls, iterable, new=tuple.__new__, len=len):
 253         'Make a new {typename} object from a sequence or iterable'
 254         result = new(cls, iterable)
 255         if len(result) != {num_fields:d}:
 256             raise TypeError('Expected {num_fields:d} arguments, got %d' % len(result))
 257         return result
 258
 259     def __repr__(self):
 260         'Return a nicely formatted representation string'
 261         return '{typename}({repr_fmt})' % self
 262
 263     def _asdict(self):
 264         'Return a new OrderedDict which maps field names to their values'
 265         return OrderedDict(zip(self._fields, self))
 266
 267     def _replace(_self, **kwds):
 268         'Return a new {typename} object replacing specified fields with new values'
 269         result = _self._make(map(kwds.pop, {field_names!r}, _self))
 270         if kwds:
 271             raise ValueError('Got unexpected field names: %r' % kwds.keys())
 272         return result
 273
 274     def __getnewargs__(self):
 275         'Return self as a plain tuple.  Used by copy and pickle.'
 276         return tuple(self)
 277
 278     __dict__ = _property(_asdict)
 279
 280     def __getstate__(self):
 281         'Exclude the OrderedDict from pickling'
 282         pass
 283
 284 {field_defs}
 285 '''
 286
 287 _repr_template = '{name}=%r'
 288
 289 _field_template = '''\
 290     {name} = _property(_itemgetter({index:d}), doc='Alias for field number {index:d}')
 291 '''
 292
 293 def namedtuple(typename, field_names, verbose=False, rename=False):
 294     """Returns a new subclass of tuple with named fields.
 295
 296     >>> Point = namedtuple('Point', ['x', 'y'])
 297     >>> Point.__doc__                   # docstring for the new class
 298     'Point(x, y)'
 299     >>> p = Point(11, y=22)             # instantiate with positional args or keywords
 300     >>> p[0] + p[1]                     # indexable like a plain tuple
 301     33
 302     >>> x, y = p                        # unpack like a regular tuple
 303     >>> x, y
 304     (11, 22)
 305     >>> p.x + p.y                       # fields also accessable by name
 306     33
 307     >>> d = p._asdict()                 # convert to a dictionary
 308     >>> d['x']
 309     11
 310     >>> Point(**d)                      # convert from a dictionary
 311     Point(x=11, y=22)
 312     >>> p._replace(x=100)               # _replace() is like str.replace() but targets named fields
 313     Point(x=100, y=22)
 314
 315     """
 316
 317     # Validate the field names.  At the user's option, either generate an error
 318     # message or automatically replace the field name with a valid name.
 319     if isinstance(field_names, basestring):
 320         field_names = field_names.replace(',', ' ').split()
 321     field_names = map(str, field_names)
 322     typename = str(typename)
 323     if rename:
 324         seen = set()
 325         for index, name in enumerate(field_names):
 326             if (not all(c.isalnum() or c=='_' for c in name)
 327                 or _iskeyword(name)
 328                 or not name
 329                 or name[0].isdigit()
 330                 or name.startswith('_')
 331                 or name in seen):
 332                 field_names[index] = '_%d' % index
 333             seen.add(name)
 334     for name in [typename] + field_names:
 335         if type(name) != str:
 336             raise TypeError('Type names and field names must be strings')
 337         if not all(c.isalnum() or c=='_' for c in name):
 338             raise ValueError('Type names and field names can only contain '
 339                              'alphanumeric characters and underscores: %r' % name)
 340         if _iskeyword(name):
 341             raise ValueError('Type names and field names cannot be a '
 342                              'keyword: %r' % name)
 343         if name[0].isdigit():
 344             raise ValueError('Type names and field names cannot start with '
 345                              'a number: %r' % name)
 346     seen = set()
 347     for name in field_names:
 348         if name.startswith('_') and not rename:
 349             raise ValueError('Field names cannot start with an underscore: '
 350                              '%r' % name)
 351         if name in seen:
 352             raise ValueError('Encountered duplicate field name: %r' % name)
 353         seen.add(name)
 354
 355     # Fill-in the class template
 356     class_definition = _class_template.format(
 357         typename = typename,
 358         field_names = tuple(field_names),
 359         num_fields = len(field_names),
 360         arg_list = repr(tuple(field_names)).replace("'", "")[1:-1],
 361         repr_fmt = ', '.join(_repr_template.format(name=name)
 362                              for name in field_names),
 363         field_defs = '\n'.join(_field_template.format(index=index, name=name)
 364                                for index, name in enumerate(field_names))
 365     )
 366     if verbose:
 367         print class_definition
 368
 369     # Execute the template string in a temporary namespace and support
 370     # tracing utilities by setting a value for frame.f_globals['__name__']
 371     namespace = dict(_itemgetter=_itemgetter, __name__='namedtuple_%s' % typename,
 372                      OrderedDict=OrderedDict, _property=property, _tuple=tuple)
 373     try:
 374         exec class_definition in namespace
 375     except SyntaxError as e:
 376         raise SyntaxError(e.message + ':\n' + class_definition)
 377     result = namespace[typename]
 378
 379     # For pickling to work, the __module__ variable needs to be set to the frame
 380     # where the named tuple is created.  Bypass this step in environments where
 381     # sys._getframe is not defined (Jython for example) or sys._getframe is not
 382     # defined for arguments greater than 0 (IronPython).
 383     try:
 384         result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__')
 385     except (AttributeError, ValueError):
 386         pass
 387
 388     return result
 389
 390
 391 ########################################################################
 392 ###  Counter
 393 ########################################################################
 394
 395 class Counter(dict):
 396     '''Dict subclass for counting hashable items.  Sometimes called a bag
 397     or multiset.  Elements are stored as dictionary keys and their counts
 398     are stored as dictionary values.
 399
 400     >>> c = Counter('abcdeabcdabcaba')  # count elements from a string
 401
 402     >>> c.most_common(3)                # three most common elements
 403     [('a', 5), ('b', 4), ('c', 3)]
 404     >>> sorted(c)                       # list all unique elements
 405     ['a', 'b', 'c', 'd', 'e']
 406     >>> ''.join(sorted(c.elements()))   # list elements with repetitions
 407     'aaaaabbbbcccdde'
 408     >>> sum(c.values())                 # total of all counts
 409     15
 410
 411     >>> c['a']                          # count of letter 'a'
 412     5
 413     >>> for elem in 'shazam':           # update counts from an iterable
 414     ...     c[elem] += 1                # by adding 1 to each element's count
 415     >>> c['a']                          # now there are seven 'a'
 416     7
 417     >>> del c['b']                      # remove all 'b'
 418     >>> c['b']                          # now there are zero 'b'
 419     0
 420
 421     >>> d = Counter('simsalabim')       # make another counter
 422     >>> c.update(d)                     # add in the second counter
 423     >>> c['a']                          # now there are nine 'a'
 424     9
 425
 426     >>> c.clear()                       # empty the counter
 427     >>> c
 428     Counter()
 429
 430     Note:  If a count is set to zero or reduced to zero, it will remain
 431     in the counter until the entry is deleted or the counter is cleared:
 432
 433     >>> c = Counter('aaabbc')
 434     >>> c['b'] -= 2                     # reduce the count of 'b' by two
 435     >>> c.most_common()                 # 'b' is still in, but its count is zero
 436     [('a', 3), ('c', 1), ('b', 0)]
 437
 438     '''
 439     # References:
 440     #   http://en.wikipedia.org/wiki/Multiset
 441     #   http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html
 442     #   http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm
 443     #   http://code.activestate.com/recipes/259174/
 444     #   Knuth, TAOCP Vol. II section 4.6.3
 445
 446     def __init__(*args, **kwds):
 447         '''Create a new, empty Counter object.  And if given, count elements
 448         from an input iterable.  Or, initialize the count from another mapping
 449         of elements to their counts.
 450
 451         >>> c = Counter()                           # a new, empty counter
 452         >>> c = Counter('gallahad')                 # a new counter from an iterable
 453         >>> c = Counter({'a': 4, 'b': 2})           # a new counter from a mapping
 454         >>> c = Counter(a=4, b=2)                   # a new counter from keyword args
 455
 456         '''
 457         if not args:
 458             raise TypeError("descriptor '__init__' of 'Counter' object "
 459                             "needs an argument")
 460         self = args[0]
 461         args = args[1:]
 462         if len(args) > 1:
 463             raise TypeError('expected at most 1 arguments, got %d' % len(args))
 464         super(Counter, self).__init__()
 465         self.update(*args, **kwds)
 466
 467     def __missing__(self, key):
 468         'The count of elements not in the Counter is zero.'
 469         # Needed so that self[missing_item] does not raise KeyError
 470         return 0
 471
 472     def most_common(self, n=None):
 473         '''List the n most common elements and their counts from the most
 474         common to the least.  If n is None, then list all element counts.
 475
 476         >>> Counter('abcdeabcdabcaba').most_common(3)
 477         [('a', 5), ('b', 4), ('c', 3)]
 478
 479         '''
 480         # Emulate Bag.sortedByCount from Smalltalk
 481         if n is None:
 482             return sorted(self.iteritems(), key=_itemgetter(1), reverse=True)
 483         return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1))
 484
 485     def elements(self):
 486         '''Iterator over elements repeating each as many times as its count.
 487
 488         >>> c = Counter('ABCABC')
 489         >>> sorted(c.elements())
 490         ['A', 'A', 'B', 'B', 'C', 'C']
 491
 492         # Knuth's example for prime factors of 1836:  2**2 * 3**3 * 17**1
 493         >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})
 494         >>> product = 1
 495         >>> for factor in prime_factors.elements():     # loop over factors
 496         ...     product *= factor                       # and multiply them
 497         >>> product
 498         1836
 499
 500         Note, if an element's count has been set to zero or is a negative
 501         number, elements() will ignore it.
 502
 503         '''
 504         # Emulate Bag.do from Smalltalk and Multiset.begin from C++.
 505         return _chain.from_iterable(_starmap(_repeat, self.iteritems()))
 506
 507     # Override dict methods where necessary
 508
 509     @classmethod
 510     def fromkeys(cls, iterable, v=None):
 511         # There is no equivalent method for counters because setting v=1
 512         # means that no element can have a count greater than one.
 513         raise NotImplementedError(
 514             'Counter.fromkeys() is undefined.  Use Counter(iterable) instead.')
 515
 516     def update(*args, **kwds):
 517         '''Like dict.update() but add counts instead of replacing them.
 518
 519         Source can be an iterable, a dictionary, or another Counter instance.
 520
 521         >>> c = Counter('which')
 522         >>> c.update('witch')           # add elements from another iterable
 523         >>> d = Counter('watch')
 524         >>> c.update(d)                 # add elements from another counter
 525         >>> c['h']                      # four 'h' in which, witch, and watch
 526         4
 527
 528         '''
 529         # The regular dict.update() operation makes no sense here because the
 530         # replace behavior results in the some of original untouched counts
 531         # being mixed-in with all of the other counts for a mismash that
 532         # doesn't have a straight-forward interpretation in most counting
 533         # contexts.  Instead, we implement straight-addition.  Both the inputs
 534         # and outputs are allowed to contain zero and negative counts.
 535
 536         if not args:
 537             raise TypeError("descriptor 'update' of 'Counter' object "
 538                             "needs an argument")
 539         self = args[0]
 540         args = args[1:]
 541         if len(args) > 1:
 542             raise TypeError('expected at most 1 arguments, got %d' % len(args))
 543         iterable = args[0] if args else None
 544         if iterable is not None:
 545             if isinstance(iterable, Mapping):
 546                 if self:
 547                     self_get = self.get
 548                     for elem, count in iterable.iteritems():
 549                         self[elem] = self_get(elem, 0) + count
 550                 else:
 551                     super(Counter, self).update(iterable) # fast path when counter is empty
 552             else:
 553                 self_get = self.get
 554                 for elem in iterable:
 555                     self[elem] = self_get(elem, 0) + 1
 556         if kwds:
 557             self.update(kwds)
 558
 559     def subtract(*args, **kwds):
 560         '''Like dict.update() but subtracts counts instead of replacing them.
 561         Counts can be reduced below zero.  Both the inputs and outputs are
 562         allowed to contain zero and negative counts.
 563
 564         Source can be an iterable, a dictionary, or another Counter instance.
 565
 566         >>> c = Counter('which')
 567         >>> c.subtract('witch')             # subtract elements from another iterable
 568         >>> c.subtract(Counter('watch'))    # subtract elements from another counter
 569         >>> c['h']                          # 2 in which, minus 1 in witch, minus 1 in watch
 570         0
 571         >>> c['w']                          # 1 in which, minus 1 in witch, minus 1 in watch
 572         -1
 573
 574         '''
 575         if not args:
 576             raise TypeError("descriptor 'subtract' of 'Counter' object "
 577                             "needs an argument")
 578         self = args[0]
 579         args = args[1:]
 580         if len(args) > 1:
 581             raise TypeError('expected at most 1 arguments, got %d' % len(args))
 582         iterable = args[0] if args else None
 583         if iterable is not None:
 584             self_get = self.get
 585             if isinstance(iterable, Mapping):
 586                 for elem, count in iterable.items():
 587                     self[elem] = self_get(elem, 0) - count
 588             else:
 589                 for elem in iterable:
 590                     self[elem] = self_get(elem, 0) - 1
 591         if kwds:
 592             self.subtract(kwds)
 593
 594     def copy(self):
 595         'Return a shallow copy.'
 596         return self.__class__(self)
 597
 598     def __reduce__(self):
 599         return self.__class__, (dict(self),)
 600
 601     def __delitem__(self, elem):
 602         'Like dict.__delitem__() but does not raise KeyError for missing values.'
 603         if elem in self:
 604             super(Counter, self).__delitem__(elem)
 605
 606     def __repr__(self):
 607         if not self:
 608             return '%s()' % self.__class__.__name__
 609         items = ', '.join(map('%r: %r'.__mod__, self.most_common()))
 610         return '%s({%s})' % (self.__class__.__name__, items)
 611
 612     # Multiset-style mathematical operations discussed in:
 613     #       Knuth TAOCP Volume II section 4.6.3 exercise 19
 614     #       and at http://en.wikipedia.org/wiki/Multiset
 615     #
 616     # Outputs guaranteed to only include positive counts.
 617     #
 618     # To strip negative and zero counts, add-in an empty counter:
 619     #       c += Counter()
 620
 621     def __add__(self, other):
 622         '''Add counts from two counters.
 623
 624         >>> Counter('abbb') + Counter('bcc')
 625         Counter({'b': 4, 'c': 2, 'a': 1})
 626
 627         '''
 628         if not isinstance(other, Counter):
 629             return NotImplemented
 630         result = Counter()
 631         for elem, count in self.items():
 632             newcount = count + other[elem]
 633             if newcount > 0:
 634                 result[elem] = newcount
 635         for elem, count in other.items():
 636             if elem not in self and count > 0:
 637                 result[elem] = count
 638         return result
 639
 640     def __sub__(self, other):
 641         ''' Subtract count, but keep only results with positive counts.
 642
 643         >>> Counter('abbbc') - Counter('bccd')
 644         Counter({'b': 2, 'a': 1})
 645
 646         '''
 647         if not isinstance(other, Counter):
 648             return NotImplemented
 649         result = Counter()
 650         for elem, count in self.items():
 651             newcount = count - other[elem]
 652             if newcount > 0:
 653                 result[elem] = newcount
 654         for elem, count in other.items():
 655             if elem not in self and count < 0:
 656                 result[elem] = 0 - count
 657         return result
 658
 659     def __or__(self, other):
 660         '''Union is the maximum of value in either of the input counters.
 661
 662         >>> Counter('abbb') | Counter('bcc')
 663         Counter({'b': 3, 'c': 2, 'a': 1})
 664
 665         '''
 666         if not isinstance(other, Counter):
 667             return NotImplemented
 668         result = Counter()
 669         for elem, count in self.items():
 670             other_count = other[elem]
 671             newcount = other_count if count < other_count else count
 672             if newcount > 0:
 673                 result[elem] = newcount
 674         for elem, count in other.items():
 675             if elem not in self and count > 0:
 676                 result[elem] = count
 677         return result
 678
 679     def __and__(self, other):
 680         ''' Intersection is the minimum of corresponding counts.
 681
 682         >>> Counter('abbb') & Counter('bcc')
 683         Counter({'b': 1})
 684
 685         '''
 686         if not isinstance(other, Counter):
 687             return NotImplemented
 688         result = Counter()
 689         for elem, count in self.items():
 690             other_count = other[elem]
 691             newcount = count if count < other_count else other_count
 692             if newcount > 0:
 693                 result[elem] = newcount
 694         return result
 695
 696
 697 if __name__ == '__main__':
 698     # verify that instances can be pickled
 699     from cPickle import loads, dumps
 700     Point = namedtuple('Point', 'x, y', True)
 701     p = Point(x=10, y=20)
 702     assert p == loads(dumps(p))
 703
 704     # test and demonstrate ability to override methods
 705     class Point(namedtuple('Point', 'x y')):
 706         __slots__ = ()
 707         @property
 708         def hypot(self):
 709             return (self.x ** 2 + self.y ** 2) ** 0.5
 710         def __str__(self):
 711             return 'Point: x=%6.3f  y=%6.3f  hypot=%6.3f' % (self.x, self.y, self.hypot)
 712
 713     for p in Point(3, 4), Point(14, 5/7.):
 714         print p
 715
 716     class Point(namedtuple('Point', 'x y')):
 717         'Point class with optimized _make() and _replace() without error-checking'
 718         __slots__ = ()
 719         _make = classmethod(tuple.__new__)
 720         def _replace(self, _map=map, **kwds):
 721             return self._make(_map(kwds.get, ('x', 'y'), self))
 722
 723     print Point(11, 22)._replace(x=100)
 724
 725     Point3D = namedtuple('Point3D', Point._fields + ('z',))
 726     print Point3D.__doc__
 727
 728     import doctest
 729     TestResults = namedtuple('TestResults', 'failed attempted')
 730     print TestResults(*doctest.testmod())