Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Miscellaneous function (re)definitions from the Py3.4+ standard library
3for Python 2.6/2.7.
5- math.ceil (for Python 2.7)
6- collections.OrderedDict (for Python 2.6)
7- collections.Counter (for Python 2.6)
8- collections.ChainMap (for all versions prior to Python 3.3)
9- itertools.count (for Python 2.6, with step parameter)
10- subprocess.check_output (for Python 2.6)
11- reprlib.recursive_repr (for Python 2.6+)
12- functools.cmp_to_key (for Python 2.6)
13"""
15from __future__ import absolute_import
17import subprocess
18from math import ceil as oldceil
20from operator import itemgetter as _itemgetter, eq as _eq
21import sys
22import heapq as _heapq
23from _weakref import proxy as _proxy
24from itertools import repeat as _repeat, chain as _chain, starmap as _starmap
25from socket import getaddrinfo, SOCK_STREAM, error, socket
27from future.utils import iteritems, itervalues, PY2, PY26, PY3
29if PY2:
30 from collections import Mapping, MutableMapping
31else:
32 from collections.abc import Mapping, MutableMapping
35def ceil(x):
36 """
37 Return the ceiling of x as an int.
38 This is the smallest integral value >= x.
39 """
40 return int(oldceil(x))
43########################################################################
44### reprlib.recursive_repr decorator from Py3.4
45########################################################################
47from itertools import islice
49if PY26:
50 # itertools.count in Py 2.6 doesn't accept a step parameter
51 def count(start=0, step=1):
52 while True:
53 yield start
54 start += step
55else:
56 from itertools import count
59if PY3:
60 try:
61 from _thread import get_ident
62 except ImportError:
63 from _dummy_thread import get_ident
64else:
65 try:
66 from thread import get_ident
67 except ImportError:
68 from dummy_thread import get_ident
71def recursive_repr(fillvalue='...'):
72 'Decorator to make a repr function return fillvalue for a recursive call'
74 def decorating_function(user_function):
75 repr_running = set()
77 def wrapper(self):
78 key = id(self), get_ident()
79 if key in repr_running:
80 return fillvalue
81 repr_running.add(key)
82 try:
83 result = user_function(self)
84 finally:
85 repr_running.discard(key)
86 return result
88 # Can't use functools.wraps() here because of bootstrap issues
89 wrapper.__module__ = getattr(user_function, '__module__')
90 wrapper.__doc__ = getattr(user_function, '__doc__')
91 wrapper.__name__ = getattr(user_function, '__name__')
92 wrapper.__annotations__ = getattr(user_function, '__annotations__', {})
93 return wrapper
95 return decorating_function
98# OrderedDict Shim from Raymond Hettinger, python core dev
99# http://code.activestate.com/recipes/576693-ordered-dictionary-for-py24/
100# here to support version 2.6.
102################################################################################
103### OrderedDict
104################################################################################
106class _Link(object):
107 __slots__ = 'prev', 'next', 'key', '__weakref__'
109class OrderedDict(dict):
110 'Dictionary that remembers insertion order'
111 # An inherited dict maps keys to values.
112 # The inherited dict provides __getitem__, __len__, __contains__, and get.
113 # The remaining methods are order-aware.
114 # Big-O running times for all methods are the same as regular dictionaries.
116 # The internal self.__map dict maps keys to links in a doubly linked list.
117 # The circular doubly linked list starts and ends with a sentinel element.
118 # The sentinel element never gets deleted (this simplifies the algorithm).
119 # The sentinel is in self.__hardroot with a weakref proxy in self.__root.
120 # The prev links are weakref proxies (to prevent circular references).
121 # Individual links are kept alive by the hard reference in self.__map.
122 # Those hard references disappear when a key is deleted from an OrderedDict.
124 def __init__(*args, **kwds):
125 '''Initialize an ordered dictionary. The signature is the same as
126 regular dictionaries, but keyword arguments are not recommended because
127 their insertion order is arbitrary.
129 '''
130 if not args:
131 raise TypeError("descriptor '__init__' of 'OrderedDict' object "
132 "needs an argument")
133 self = args[0]
134 args = args[1:]
135 if len(args) > 1:
136 raise TypeError('expected at most 1 arguments, got %d' % len(args))
137 try:
138 self.__root
139 except AttributeError:
140 self.__hardroot = _Link()
141 self.__root = root = _proxy(self.__hardroot)
142 root.prev = root.next = root
143 self.__map = {}
144 self.__update(*args, **kwds)
146 def __setitem__(self, key, value,
147 dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
148 'od.__setitem__(i, y) <==> od[i]=y'
149 # Setting a new item creates a new link at the end of the linked list,
150 # and the inherited dictionary is updated with the new key/value pair.
151 if key not in self:
152 self.__map[key] = link = Link()
153 root = self.__root
154 last = root.prev
155 link.prev, link.next, link.key = last, root, key
156 last.next = link
157 root.prev = proxy(link)
158 dict_setitem(self, key, value)
160 def __delitem__(self, key, dict_delitem=dict.__delitem__):
161 'od.__delitem__(y) <==> del od[y]'
162 # Deleting an existing item uses self.__map to find the link which gets
163 # removed by updating the links in the predecessor and successor nodes.
164 dict_delitem(self, key)
165 link = self.__map.pop(key)
166 link_prev = link.prev
167 link_next = link.next
168 link_prev.next = link_next
169 link_next.prev = link_prev
171 def __iter__(self):
172 'od.__iter__() <==> iter(od)'
173 # Traverse the linked list in order.
174 root = self.__root
175 curr = root.next
176 while curr is not root:
177 yield curr.key
178 curr = curr.next
180 def __reversed__(self):
181 'od.__reversed__() <==> reversed(od)'
182 # Traverse the linked list in reverse order.
183 root = self.__root
184 curr = root.prev
185 while curr is not root:
186 yield curr.key
187 curr = curr.prev
189 def clear(self):
190 'od.clear() -> None. Remove all items from od.'
191 root = self.__root
192 root.prev = root.next = root
193 self.__map.clear()
194 dict.clear(self)
196 def popitem(self, last=True):
197 '''od.popitem() -> (k, v), return and remove a (key, value) pair.
198 Pairs are returned in LIFO order if last is true or FIFO order if false.
200 '''
201 if not self:
202 raise KeyError('dictionary is empty')
203 root = self.__root
204 if last:
205 link = root.prev
206 link_prev = link.prev
207 link_prev.next = root
208 root.prev = link_prev
209 else:
210 link = root.next
211 link_next = link.next
212 root.next = link_next
213 link_next.prev = root
214 key = link.key
215 del self.__map[key]
216 value = dict.pop(self, key)
217 return key, value
219 def move_to_end(self, key, last=True):
220 '''Move an existing element to the end (or beginning if last==False).
222 Raises KeyError if the element does not exist.
223 When last=True, acts like a fast version of self[key]=self.pop(key).
225 '''
226 link = self.__map[key]
227 link_prev = link.prev
228 link_next = link.next
229 link_prev.next = link_next
230 link_next.prev = link_prev
231 root = self.__root
232 if last:
233 last = root.prev
234 link.prev = last
235 link.next = root
236 last.next = root.prev = link
237 else:
238 first = root.next
239 link.prev = root
240 link.next = first
241 root.next = first.prev = link
243 def __sizeof__(self):
244 sizeof = sys.getsizeof
245 n = len(self) + 1 # number of links including root
246 size = sizeof(self.__dict__) # instance dictionary
247 size += sizeof(self.__map) * 2 # internal dict and inherited dict
248 size += sizeof(self.__hardroot) * n # link objects
249 size += sizeof(self.__root) * n # proxy objects
250 return size
252 update = __update = MutableMapping.update
253 keys = MutableMapping.keys
254 values = MutableMapping.values
255 items = MutableMapping.items
256 __ne__ = MutableMapping.__ne__
258 __marker = object()
260 def pop(self, key, default=__marker):
261 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding
262 value. If key is not found, d is returned if given, otherwise KeyError
263 is raised.
265 '''
266 if key in self:
267 result = self[key]
268 del self[key]
269 return result
270 if default is self.__marker:
271 raise KeyError(key)
272 return default
274 def setdefault(self, key, default=None):
275 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
276 if key in self:
277 return self[key]
278 self[key] = default
279 return default
281 @recursive_repr()
282 def __repr__(self):
283 'od.__repr__() <==> repr(od)'
284 if not self:
285 return '%s()' % (self.__class__.__name__,)
286 return '%s(%r)' % (self.__class__.__name__, list(self.items()))
288 def __reduce__(self):
289 'Return state information for pickling'
290 inst_dict = vars(self).copy()
291 for k in vars(OrderedDict()):
292 inst_dict.pop(k, None)
293 return self.__class__, (), inst_dict or None, None, iter(self.items())
295 def copy(self):
296 'od.copy() -> a shallow copy of od'
297 return self.__class__(self)
299 @classmethod
300 def fromkeys(cls, iterable, value=None):
301 '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.
302 If not specified, the value defaults to None.
304 '''
305 self = cls()
306 for key in iterable:
307 self[key] = value
308 return self
310 def __eq__(self, other):
311 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
312 while comparison to a regular mapping is order-insensitive.
314 '''
315 if isinstance(other, OrderedDict):
316 return dict.__eq__(self, other) and all(map(_eq, self, other))
317 return dict.__eq__(self, other)
320# {{{ http://code.activestate.com/recipes/576611/ (r11)
322try:
323 from operator import itemgetter
324 from heapq import nlargest
325except ImportError:
326 pass
328########################################################################
329### Counter
330########################################################################
332def _count_elements(mapping, iterable):
333 'Tally elements from the iterable.'
334 mapping_get = mapping.get
335 for elem in iterable:
336 mapping[elem] = mapping_get(elem, 0) + 1
338class Counter(dict):
339 '''Dict subclass for counting hashable items. Sometimes called a bag
340 or multiset. Elements are stored as dictionary keys and their counts
341 are stored as dictionary values.
343 >>> c = Counter('abcdeabcdabcaba') # count elements from a string
345 >>> c.most_common(3) # three most common elements
346 [('a', 5), ('b', 4), ('c', 3)]
347 >>> sorted(c) # list all unique elements
348 ['a', 'b', 'c', 'd', 'e']
349 >>> ''.join(sorted(c.elements())) # list elements with repetitions
350 'aaaaabbbbcccdde'
351 >>> sum(c.values()) # total of all counts
352 15
354 >>> c['a'] # count of letter 'a'
355 5
356 >>> for elem in 'shazam': # update counts from an iterable
357 ... c[elem] += 1 # by adding 1 to each element's count
358 >>> c['a'] # now there are seven 'a'
359 7
360 >>> del c['b'] # remove all 'b'
361 >>> c['b'] # now there are zero 'b'
362 0
364 >>> d = Counter('simsalabim') # make another counter
365 >>> c.update(d) # add in the second counter
366 >>> c['a'] # now there are nine 'a'
367 9
369 >>> c.clear() # empty the counter
370 >>> c
371 Counter()
373 Note: If a count is set to zero or reduced to zero, it will remain
374 in the counter until the entry is deleted or the counter is cleared:
376 >>> c = Counter('aaabbc')
377 >>> c['b'] -= 2 # reduce the count of 'b' by two
378 >>> c.most_common() # 'b' is still in, but its count is zero
379 [('a', 3), ('c', 1), ('b', 0)]
381 '''
382 # References:
383 # http://en.wikipedia.org/wiki/Multiset
384 # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html
385 # http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm
386 # http://code.activestate.com/recipes/259174/
387 # Knuth, TAOCP Vol. II section 4.6.3
389 def __init__(*args, **kwds):
390 '''Create a new, empty Counter object. And if given, count elements
391 from an input iterable. Or, initialize the count from another mapping
392 of elements to their counts.
394 >>> c = Counter() # a new, empty counter
395 >>> c = Counter('gallahad') # a new counter from an iterable
396 >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping
397 >>> c = Counter(a=4, b=2) # a new counter from keyword args
399 '''
400 if not args:
401 raise TypeError("descriptor '__init__' of 'Counter' object "
402 "needs an argument")
403 self = args[0]
404 args = args[1:]
405 if len(args) > 1:
406 raise TypeError('expected at most 1 arguments, got %d' % len(args))
407 super(Counter, self).__init__()
408 self.update(*args, **kwds)
410 def __missing__(self, key):
411 'The count of elements not in the Counter is zero.'
412 # Needed so that self[missing_item] does not raise KeyError
413 return 0
415 def most_common(self, n=None):
416 '''List the n most common elements and their counts from the most
417 common to the least. If n is None, then list all element counts.
419 >>> Counter('abcdeabcdabcaba').most_common(3)
420 [('a', 5), ('b', 4), ('c', 3)]
422 '''
423 # Emulate Bag.sortedByCount from Smalltalk
424 if n is None:
425 return sorted(self.items(), key=_itemgetter(1), reverse=True)
426 return _heapq.nlargest(n, self.items(), key=_itemgetter(1))
428 def elements(self):
429 '''Iterator over elements repeating each as many times as its count.
431 >>> c = Counter('ABCABC')
432 >>> sorted(c.elements())
433 ['A', 'A', 'B', 'B', 'C', 'C']
435 # Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1
436 >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})
437 >>> product = 1
438 >>> for factor in prime_factors.elements(): # loop over factors
439 ... product *= factor # and multiply them
440 >>> product
441 1836
443 Note, if an element's count has been set to zero or is a negative
444 number, elements() will ignore it.
446 '''
447 # Emulate Bag.do from Smalltalk and Multiset.begin from C++.
448 return _chain.from_iterable(_starmap(_repeat, self.items()))
450 # Override dict methods where necessary
452 @classmethod
453 def fromkeys(cls, iterable, v=None):
454 # There is no equivalent method for counters because setting v=1
455 # means that no element can have a count greater than one.
456 raise NotImplementedError(
457 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.')
459 def update(*args, **kwds):
460 '''Like dict.update() but add counts instead of replacing them.
462 Source can be an iterable, a dictionary, or another Counter instance.
464 >>> c = Counter('which')
465 >>> c.update('witch') # add elements from another iterable
466 >>> d = Counter('watch')
467 >>> c.update(d) # add elements from another counter
468 >>> c['h'] # four 'h' in which, witch, and watch
469 4
471 '''
472 # The regular dict.update() operation makes no sense here because the
473 # replace behavior results in the some of original untouched counts
474 # being mixed-in with all of the other counts for a mismash that
475 # doesn't have a straight-forward interpretation in most counting
476 # contexts. Instead, we implement straight-addition. Both the inputs
477 # and outputs are allowed to contain zero and negative counts.
479 if not args:
480 raise TypeError("descriptor 'update' of 'Counter' object "
481 "needs an argument")
482 self = args[0]
483 args = args[1:]
484 if len(args) > 1:
485 raise TypeError('expected at most 1 arguments, got %d' % len(args))
486 iterable = args[0] if args else None
487 if iterable is not None:
488 if isinstance(iterable, Mapping):
489 if self:
490 self_get = self.get
491 for elem, count in iterable.items():
492 self[elem] = count + self_get(elem, 0)
493 else:
494 super(Counter, self).update(iterable) # fast path when counter is empty
495 else:
496 _count_elements(self, iterable)
497 if kwds:
498 self.update(kwds)
500 def subtract(*args, **kwds):
501 '''Like dict.update() but subtracts counts instead of replacing them.
502 Counts can be reduced below zero. Both the inputs and outputs are
503 allowed to contain zero and negative counts.
505 Source can be an iterable, a dictionary, or another Counter instance.
507 >>> c = Counter('which')
508 >>> c.subtract('witch') # subtract elements from another iterable
509 >>> c.subtract(Counter('watch')) # subtract elements from another counter
510 >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch
511 0
512 >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch
513 -1
515 '''
516 if not args:
517 raise TypeError("descriptor 'subtract' of 'Counter' object "
518 "needs an argument")
519 self = args[0]
520 args = args[1:]
521 if len(args) > 1:
522 raise TypeError('expected at most 1 arguments, got %d' % len(args))
523 iterable = args[0] if args else None
524 if iterable is not None:
525 self_get = self.get
526 if isinstance(iterable, Mapping):
527 for elem, count in iterable.items():
528 self[elem] = self_get(elem, 0) - count
529 else:
530 for elem in iterable:
531 self[elem] = self_get(elem, 0) - 1
532 if kwds:
533 self.subtract(kwds)
535 def copy(self):
536 'Return a shallow copy.'
537 return self.__class__(self)
539 def __reduce__(self):
540 return self.__class__, (dict(self),)
542 def __delitem__(self, elem):
543 'Like dict.__delitem__() but does not raise KeyError for missing values.'
544 if elem in self:
545 super(Counter, self).__delitem__(elem)
547 def __repr__(self):
548 if not self:
549 return '%s()' % self.__class__.__name__
550 try:
551 items = ', '.join(map('%r: %r'.__mod__, self.most_common()))
552 return '%s({%s})' % (self.__class__.__name__, items)
553 except TypeError:
554 # handle case where values are not orderable
555 return '{0}({1!r})'.format(self.__class__.__name__, dict(self))
557 # Multiset-style mathematical operations discussed in:
558 # Knuth TAOCP Volume II section 4.6.3 exercise 19
559 # and at http://en.wikipedia.org/wiki/Multiset
560 #
561 # Outputs guaranteed to only include positive counts.
562 #
563 # To strip negative and zero counts, add-in an empty counter:
564 # c += Counter()
566 def __add__(self, other):
567 '''Add counts from two counters.
569 >>> Counter('abbb') + Counter('bcc')
570 Counter({'b': 4, 'c': 2, 'a': 1})
572 '''
573 if not isinstance(other, Counter):
574 return NotImplemented
575 result = Counter()
576 for elem, count in self.items():
577 newcount = count + other[elem]
578 if newcount > 0:
579 result[elem] = newcount
580 for elem, count in other.items():
581 if elem not in self and count > 0:
582 result[elem] = count
583 return result
585 def __sub__(self, other):
586 ''' Subtract count, but keep only results with positive counts.
588 >>> Counter('abbbc') - Counter('bccd')
589 Counter({'b': 2, 'a': 1})
591 '''
592 if not isinstance(other, Counter):
593 return NotImplemented
594 result = Counter()
595 for elem, count in self.items():
596 newcount = count - other[elem]
597 if newcount > 0:
598 result[elem] = newcount
599 for elem, count in other.items():
600 if elem not in self and count < 0:
601 result[elem] = 0 - count
602 return result
604 def __or__(self, other):
605 '''Union is the maximum of value in either of the input counters.
607 >>> Counter('abbb') | Counter('bcc')
608 Counter({'b': 3, 'c': 2, 'a': 1})
610 '''
611 if not isinstance(other, Counter):
612 return NotImplemented
613 result = Counter()
614 for elem, count in self.items():
615 other_count = other[elem]
616 newcount = other_count if count < other_count else count
617 if newcount > 0:
618 result[elem] = newcount
619 for elem, count in other.items():
620 if elem not in self and count > 0:
621 result[elem] = count
622 return result
624 def __and__(self, other):
625 ''' Intersection is the minimum of corresponding counts.
627 >>> Counter('abbb') & Counter('bcc')
628 Counter({'b': 1})
630 '''
631 if not isinstance(other, Counter):
632 return NotImplemented
633 result = Counter()
634 for elem, count in self.items():
635 other_count = other[elem]
636 newcount = count if count < other_count else other_count
637 if newcount > 0:
638 result[elem] = newcount
639 return result
641 def __pos__(self):
642 'Adds an empty counter, effectively stripping negative and zero counts'
643 return self + Counter()
645 def __neg__(self):
646 '''Subtracts from an empty counter. Strips positive and zero counts,
647 and flips the sign on negative counts.
649 '''
650 return Counter() - self
652 def _keep_positive(self):
653 '''Internal method to strip elements with a negative or zero count'''
654 nonpositive = [elem for elem, count in self.items() if not count > 0]
655 for elem in nonpositive:
656 del self[elem]
657 return self
659 def __iadd__(self, other):
660 '''Inplace add from another counter, keeping only positive counts.
662 >>> c = Counter('abbb')
663 >>> c += Counter('bcc')
664 >>> c
665 Counter({'b': 4, 'c': 2, 'a': 1})
667 '''
668 for elem, count in other.items():
669 self[elem] += count
670 return self._keep_positive()
672 def __isub__(self, other):
673 '''Inplace subtract counter, but keep only results with positive counts.
675 >>> c = Counter('abbbc')
676 >>> c -= Counter('bccd')
677 >>> c
678 Counter({'b': 2, 'a': 1})
680 '''
681 for elem, count in other.items():
682 self[elem] -= count
683 return self._keep_positive()
685 def __ior__(self, other):
686 '''Inplace union is the maximum of value from either counter.
688 >>> c = Counter('abbb')
689 >>> c |= Counter('bcc')
690 >>> c
691 Counter({'b': 3, 'c': 2, 'a': 1})
693 '''
694 for elem, other_count in other.items():
695 count = self[elem]
696 if other_count > count:
697 self[elem] = other_count
698 return self._keep_positive()
700 def __iand__(self, other):
701 '''Inplace intersection is the minimum of corresponding counts.
703 >>> c = Counter('abbb')
704 >>> c &= Counter('bcc')
705 >>> c
706 Counter({'b': 1})
708 '''
709 for elem, count in self.items():
710 other_count = other[elem]
711 if other_count < count:
712 self[elem] = other_count
713 return self._keep_positive()
716def check_output(*popenargs, **kwargs):
717 """
718 For Python 2.6 compatibility: see
719 http://stackoverflow.com/questions/4814970/
720 """
722 if 'stdout' in kwargs:
723 raise ValueError('stdout argument not allowed, it will be overridden.')
724 process = subprocess.Popen(stdout=subprocess.PIPE, *popenargs, **kwargs)
725 output, unused_err = process.communicate()
726 retcode = process.poll()
727 if retcode:
728 cmd = kwargs.get("args")
729 if cmd is None:
730 cmd = popenargs[0]
731 raise subprocess.CalledProcessError(retcode, cmd)
732 return output
735def count(start=0, step=1):
736 """
737 ``itertools.count`` in Py 2.6 doesn't accept a step
738 parameter. This is an enhanced version of ``itertools.count``
739 for Py2.6 equivalent to ``itertools.count`` in Python 2.7+.
740 """
741 while True:
742 yield start
743 start += step
746########################################################################
747### ChainMap (helper for configparser and string.Template)
748### From the Py3.4 source code. See also:
749### https://github.com/kkxue/Py2ChainMap/blob/master/py2chainmap.py
750########################################################################
752class ChainMap(MutableMapping):
753 ''' A ChainMap groups multiple dicts (or other mappings) together
754 to create a single, updateable view.
756 The underlying mappings are stored in a list. That list is public and can
757 accessed or updated using the *maps* attribute. There is no other state.
759 Lookups search the underlying mappings successively until a key is found.
760 In contrast, writes, updates, and deletions only operate on the first
761 mapping.
763 '''
765 def __init__(self, *maps):
766 '''Initialize a ChainMap by setting *maps* to the given mappings.
767 If no mappings are provided, a single empty dictionary is used.
769 '''
770 self.maps = list(maps) or [{}] # always at least one map
772 def __missing__(self, key):
773 raise KeyError(key)
775 def __getitem__(self, key):
776 for mapping in self.maps:
777 try:
778 return mapping[key] # can't use 'key in mapping' with defaultdict
779 except KeyError:
780 pass
781 return self.__missing__(key) # support subclasses that define __missing__
783 def get(self, key, default=None):
784 return self[key] if key in self else default
786 def __len__(self):
787 return len(set().union(*self.maps)) # reuses stored hash values if possible
789 def __iter__(self):
790 return iter(set().union(*self.maps))
792 def __contains__(self, key):
793 return any(key in m for m in self.maps)
795 def __bool__(self):
796 return any(self.maps)
798 # Py2 compatibility:
799 __nonzero__ = __bool__
801 @recursive_repr()
802 def __repr__(self):
803 return '{0.__class__.__name__}({1})'.format(
804 self, ', '.join(map(repr, self.maps)))
806 @classmethod
807 def fromkeys(cls, iterable, *args):
808 'Create a ChainMap with a single dict created from the iterable.'
809 return cls(dict.fromkeys(iterable, *args))
811 def copy(self):
812 'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]'
813 return self.__class__(self.maps[0].copy(), *self.maps[1:])
815 __copy__ = copy
817 def new_child(self, m=None): # like Django's Context.push()
818 '''
819 New ChainMap with a new map followed by all previous maps. If no
820 map is provided, an empty dict is used.
821 '''
822 if m is None:
823 m = {}
824 return self.__class__(m, *self.maps)
826 @property
827 def parents(self): # like Django's Context.pop()
828 'New ChainMap from maps[1:].'
829 return self.__class__(*self.maps[1:])
831 def __setitem__(self, key, value):
832 self.maps[0][key] = value
834 def __delitem__(self, key):
835 try:
836 del self.maps[0][key]
837 except KeyError:
838 raise KeyError('Key not found in the first mapping: {0!r}'.format(key))
840 def popitem(self):
841 'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.'
842 try:
843 return self.maps[0].popitem()
844 except KeyError:
845 raise KeyError('No keys found in the first mapping.')
847 def pop(self, key, *args):
848 'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].'
849 try:
850 return self.maps[0].pop(key, *args)
851 except KeyError:
852 raise KeyError('Key not found in the first mapping: {0!r}'.format(key))
854 def clear(self):
855 'Clear maps[0], leaving maps[1:] intact.'
856 self.maps[0].clear()
859# Re-use the same sentinel as in the Python stdlib socket module:
860from socket import _GLOBAL_DEFAULT_TIMEOUT
861# Was: _GLOBAL_DEFAULT_TIMEOUT = object()
864def create_connection(address, timeout=_GLOBAL_DEFAULT_TIMEOUT,
865 source_address=None):
866 """Backport of 3-argument create_connection() for Py2.6.
868 Connect to *address* and return the socket object.
870 Convenience function. Connect to *address* (a 2-tuple ``(host,
871 port)``) and return the socket object. Passing the optional
872 *timeout* parameter will set the timeout on the socket instance
873 before attempting to connect. If no *timeout* is supplied, the
874 global default timeout setting returned by :func:`getdefaulttimeout`
875 is used. If *source_address* is set it must be a tuple of (host, port)
876 for the socket to bind as a source address before making the connection.
877 An host of '' or port 0 tells the OS to use the default.
878 """
880 host, port = address
881 err = None
882 for res in getaddrinfo(host, port, 0, SOCK_STREAM):
883 af, socktype, proto, canonname, sa = res
884 sock = None
885 try:
886 sock = socket(af, socktype, proto)
887 if timeout is not _GLOBAL_DEFAULT_TIMEOUT:
888 sock.settimeout(timeout)
889 if source_address:
890 sock.bind(source_address)
891 sock.connect(sa)
892 return sock
894 except error as _:
895 err = _
896 if sock is not None:
897 sock.close()
899 if err is not None:
900 raise err
901 else:
902 raise error("getaddrinfo returns an empty list")
904# Backport from Py2.7 for Py2.6:
905def cmp_to_key(mycmp):
906 """Convert a cmp= function into a key= function"""
907 class K(object):
908 __slots__ = ['obj']
909 def __init__(self, obj, *args):
910 self.obj = obj
911 def __lt__(self, other):
912 return mycmp(self.obj, other.obj) < 0
913 def __gt__(self, other):
914 return mycmp(self.obj, other.obj) > 0
915 def __eq__(self, other):
916 return mycmp(self.obj, other.obj) == 0
917 def __le__(self, other):
918 return mycmp(self.obj, other.obj) <= 0
919 def __ge__(self, other):
920 return mycmp(self.obj, other.obj) >= 0
921 def __ne__(self, other):
922 return mycmp(self.obj, other.obj) != 0
923 def __hash__(self):
924 raise TypeError('hash not implemented')
925 return K
927# Back up our definitions above in case they're useful
928_OrderedDict = OrderedDict
929_Counter = Counter
930_check_output = check_output
931_count = count
932_ceil = ceil
933__count_elements = _count_elements
934_recursive_repr = recursive_repr
935_ChainMap = ChainMap
936_create_connection = create_connection
937_cmp_to_key = cmp_to_key
939# Overwrite the definitions above with the usual ones
940# from the standard library:
941if sys.version_info >= (2, 7):
942 from collections import OrderedDict, Counter
943 from itertools import count
944 from functools import cmp_to_key
945 try:
946 from subprocess import check_output
947 except ImportError:
948 # Not available. This happens with Google App Engine: see issue #231
949 pass
950 from socket import create_connection
952if sys.version_info >= (3, 0):
953 from math import ceil
954 from collections import _count_elements
956if sys.version_info >= (3, 3):
957 from reprlib import recursive_repr
958 from collections import ChainMap