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