Mercurial > repos > shellac > sam_consensus_v3
diff env/lib/python3.9/site-packages/boltons/iterutils.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
| author | shellac |
|---|---|
| date | Mon, 22 Mar 2021 18:12:50 +0000 |
| parents | |
| children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/env/lib/python3.9/site-packages/boltons/iterutils.py Mon Mar 22 18:12:50 2021 +0000 @@ -0,0 +1,1466 @@ +# -*- coding: utf-8 -*- +""":mod:`itertools` is full of great examples of Python generator +usage. However, there are still some critical gaps. ``iterutils`` +fills many of those gaps with featureful, tested, and Pythonic +solutions. + +Many of the functions below have two versions, one which +returns an iterator (denoted by the ``*_iter`` naming pattern), and a +shorter-named convenience form that returns a list. Some of the +following are based on examples in itertools docs. +""" + +import os +import math +import time +import codecs +import random +import itertools + +try: + from collections.abc import Mapping, Sequence, Set, ItemsView, Iterable +except ImportError: + from collections import Mapping, Sequence, Set, ItemsView, Iterable + + +try: + from typeutils import make_sentinel + _UNSET = make_sentinel('_UNSET') + _REMAP_EXIT = make_sentinel('_REMAP_EXIT') +except ImportError: + _REMAP_EXIT = object() + _UNSET = object() + +try: + from future_builtins import filter + from itertools import izip + _IS_PY3 = False +except ImportError: + # Python 3 compat + _IS_PY3 = True + basestring = (str, bytes) + unicode = str + izip, xrange = zip, range + + +def is_iterable(obj): + """Similar in nature to :func:`callable`, ``is_iterable`` returns + ``True`` if an object is `iterable`_, ``False`` if not. + + >>> is_iterable([]) + True + >>> is_iterable(object()) + False + + .. _iterable: https://docs.python.org/2/glossary.html#term-iterable + """ + try: + iter(obj) + except TypeError: + return False + return True + + +def is_scalar(obj): + """A near-mirror of :func:`is_iterable`. Returns ``False`` if an + object is an iterable container type. Strings are considered + scalar as well, because strings are more often treated as whole + values as opposed to iterables of 1-character substrings. + + >>> is_scalar(object()) + True + >>> is_scalar(range(10)) + False + >>> is_scalar('hello') + True + """ + return not is_iterable(obj) or isinstance(obj, basestring) + + +def is_collection(obj): + """The opposite of :func:`is_scalar`. Returns ``True`` if an object + is an iterable other than a string. + + >>> is_collection(object()) + False + >>> is_collection(range(10)) + True + >>> is_collection('hello') + False + """ + return is_iterable(obj) and not isinstance(obj, basestring) + + +def split(src, sep=None, maxsplit=None): + """Splits an iterable based on a separator. Like :meth:`str.split`, + but for all iterables. Returns a list of lists. + + >>> split(['hi', 'hello', None, None, 'sup', None, 'soap', None]) + [['hi', 'hello'], ['sup'], ['soap']] + + See :func:`split_iter` docs for more info. + """ + return list(split_iter(src, sep, maxsplit)) + + +def split_iter(src, sep=None, maxsplit=None): + """Splits an iterable based on a separator, *sep*, a max of + *maxsplit* times (no max by default). *sep* can be: + + * a single value + * an iterable of separators + * a single-argument callable that returns True when a separator is + encountered + + ``split_iter()`` yields lists of non-separator values. A separator will + never appear in the output. + + >>> list(split_iter(['hi', 'hello', None, None, 'sup', None, 'soap', None])) + [['hi', 'hello'], ['sup'], ['soap']] + + Note that ``split_iter`` is based on :func:`str.split`, so if + *sep* is ``None``, ``split()`` **groups** separators. If empty lists + are desired between two contiguous ``None`` values, simply use + ``sep=[None]``: + + >>> list(split_iter(['hi', 'hello', None, None, 'sup', None])) + [['hi', 'hello'], ['sup']] + >>> list(split_iter(['hi', 'hello', None, None, 'sup', None], sep=[None])) + [['hi', 'hello'], [], ['sup'], []] + + Using a callable separator: + + >>> falsy_sep = lambda x: not x + >>> list(split_iter(['hi', 'hello', None, '', 'sup', False], falsy_sep)) + [['hi', 'hello'], [], ['sup'], []] + + See :func:`split` for a list-returning version. + + """ + if not is_iterable(src): + raise TypeError('expected an iterable') + + if maxsplit is not None: + maxsplit = int(maxsplit) + if maxsplit == 0: + yield [src] + return + + if callable(sep): + sep_func = sep + elif not is_scalar(sep): + sep = frozenset(sep) + sep_func = lambda x: x in sep + else: + sep_func = lambda x: x == sep + + cur_group = [] + split_count = 0 + for s in src: + if maxsplit is not None and split_count >= maxsplit: + sep_func = lambda x: False + if sep_func(s): + if sep is None and not cur_group: + # If sep is none, str.split() "groups" separators + # check the str.split() docs for more info + continue + split_count += 1 + yield cur_group + cur_group = [] + else: + cur_group.append(s) + + if cur_group or sep is not None: + yield cur_group + return + + +def lstrip(iterable, strip_value=None): + """Strips values from the beginning of an iterable. Stripped items will + match the value of the argument strip_value. Functionality is analigous + to that of the method str.lstrip. Returns a list. + + >>> lstrip(['Foo', 'Bar', 'Bam'], 'Foo') + ['Bar', 'Bam'] + + """ + return list(lstrip_iter(iterable, strip_value)) + + +def lstrip_iter(iterable, strip_value=None): + """Strips values from the beginning of an iterable. Stripped items will + match the value of the argument strip_value. Functionality is analigous + to that of the method str.lstrip. Returns a generator. + + >>> list(lstrip_iter(['Foo', 'Bar', 'Bam'], 'Foo')) + ['Bar', 'Bam'] + + """ + iterator = iter(iterable) + for i in iterator: + if i != strip_value: + yield i + break + for i in iterator: + yield i + + +def rstrip(iterable, strip_value=None): + """Strips values from the end of an iterable. Stripped items will + match the value of the argument strip_value. Functionality is analigous + to that of the method str.rstrip. Returns a list. + + >>> rstrip(['Foo', 'Bar', 'Bam'], 'Bam') + ['Foo', 'Bar'] + + """ + return list(rstrip_iter(iterable,strip_value)) + + +def rstrip_iter(iterable, strip_value=None): + """Strips values from the end of an iterable. Stripped items will + match the value of the argument strip_value. Functionality is analigous + to that of the method str.rstrip. Returns a generator. + + >>> list(rstrip_iter(['Foo', 'Bar', 'Bam'], 'Bam')) + ['Foo', 'Bar'] + + """ + iterator = iter(iterable) + for i in iterator: + if i == strip_value: + cache = list() + cache.append(i) + broken = False + for i in iterator: + if i == strip_value: + cache.append(i) + else: + broken = True + break + if not broken: # Return to caller here because the end of the + return # iterator has been reached + for t in cache: + yield t + yield i + + +def strip(iterable, strip_value=None): + """Strips values from the beginning and end of an iterable. Stripped items + will match the value of the argument strip_value. Functionality is + analigous to that of the method str.strip. Returns a list. + + >>> strip(['Fu', 'Foo', 'Bar', 'Bam', 'Fu'], 'Fu') + ['Foo', 'Bar', 'Bam'] + + """ + return list(strip_iter(iterable,strip_value)) + + +def strip_iter(iterable,strip_value=None): + """Strips values from the beginning and end of an iterable. Stripped items + will match the value of the argument strip_value. Functionality is + analigous to that of the method str.strip. Returns a generator. + + >>> list(strip_iter(['Fu', 'Foo', 'Bar', 'Bam', 'Fu'], 'Fu')) + ['Foo', 'Bar', 'Bam'] + + """ + return rstrip_iter(lstrip_iter(iterable,strip_value),strip_value) + + +def chunked(src, size, count=None, **kw): + """Returns a list of *count* chunks, each with *size* elements, + generated from iterable *src*. If *src* is not evenly divisible by + *size*, the final chunk will have fewer than *size* elements. + Provide the *fill* keyword argument to provide a pad value and + enable padding, otherwise no padding will take place. + + >>> chunked(range(10), 3) + [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]] + >>> chunked(range(10), 3, fill=None) + [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, None, None]] + >>> chunked(range(10), 3, count=2) + [[0, 1, 2], [3, 4, 5]] + + See :func:`chunked_iter` for more info. + """ + chunk_iter = chunked_iter(src, size, **kw) + if count is None: + return list(chunk_iter) + else: + return list(itertools.islice(chunk_iter, count)) + + +def chunked_iter(src, size, **kw): + """Generates *size*-sized chunks from *src* iterable. Unless the + optional *fill* keyword argument is provided, iterables not evenly + divisible by *size* will have a final chunk that is smaller than + *size*. + + >>> list(chunked_iter(range(10), 3)) + [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]] + >>> list(chunked_iter(range(10), 3, fill=None)) + [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, None, None]] + + Note that ``fill=None`` in fact uses ``None`` as the fill value. + """ + # TODO: add count kwarg? + if not is_iterable(src): + raise TypeError('expected an iterable') + size = int(size) + if size <= 0: + raise ValueError('expected a positive integer chunk size') + do_fill = True + try: + fill_val = kw.pop('fill') + except KeyError: + do_fill = False + fill_val = None + if kw: + raise ValueError('got unexpected keyword arguments: %r' % kw.keys()) + if not src: + return + postprocess = lambda chk: chk + if isinstance(src, basestring): + postprocess = lambda chk, _sep=type(src)(): _sep.join(chk) + if _IS_PY3 and isinstance(src, bytes): + postprocess = lambda chk: bytes(chk) + src_iter = iter(src) + while True: + cur_chunk = list(itertools.islice(src_iter, size)) + if not cur_chunk: + break + lc = len(cur_chunk) + if lc < size and do_fill: + cur_chunk[lc:] = [fill_val] * (size - lc) + yield postprocess(cur_chunk) + return + + +def pairwise(src): + """Convenience function for calling :func:`windowed` on *src*, with + *size* set to 2. + + >>> pairwise(range(5)) + [(0, 1), (1, 2), (2, 3), (3, 4)] + >>> pairwise([]) + [] + + The number of pairs is always one less than the number of elements + in the iterable passed in, except on empty inputs, which returns + an empty list. + """ + return windowed(src, 2) + + +def pairwise_iter(src): + """Convenience function for calling :func:`windowed_iter` on *src*, + with *size* set to 2. + + >>> list(pairwise_iter(range(5))) + [(0, 1), (1, 2), (2, 3), (3, 4)] + >>> list(pairwise_iter([])) + [] + + The number of pairs is always one less than the number of elements + in the iterable passed in, or zero, when *src* is empty. + + """ + return windowed_iter(src, 2) + + +def windowed(src, size): + """Returns tuples with exactly length *size*. If the iterable is + too short to make a window of length *size*, no tuples are + returned. See :func:`windowed_iter` for more. + """ + return list(windowed_iter(src, size)) + + +def windowed_iter(src, size): + """Returns tuples with length *size* which represent a sliding + window over iterable *src*. + + >>> list(windowed_iter(range(7), 3)) + [(0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 6)] + + If the iterable is too short to make a window of length *size*, + then no window tuples are returned. + + >>> list(windowed_iter(range(3), 5)) + [] + """ + # TODO: lists? (for consistency) + tees = itertools.tee(src, size) + try: + for i, t in enumerate(tees): + for _ in xrange(i): + next(t) + except StopIteration: + return izip([]) + return izip(*tees) + + +def xfrange(stop, start=None, step=1.0): + """Same as :func:`frange`, but generator-based instead of returning a + list. + + >>> tuple(xfrange(1, 3, step=0.75)) + (1.0, 1.75, 2.5) + + See :func:`frange` for more details. + """ + if not step: + raise ValueError('step must be non-zero') + if start is None: + start, stop = 0.0, stop * 1.0 + else: + # swap when all args are used + stop, start = start * 1.0, stop * 1.0 + cur = start + while cur < stop: + yield cur + cur += step + + +def frange(stop, start=None, step=1.0): + """A :func:`range` clone for float-based ranges. + + >>> frange(5) + [0.0, 1.0, 2.0, 3.0, 4.0] + >>> frange(6, step=1.25) + [0.0, 1.25, 2.5, 3.75, 5.0] + >>> frange(100.5, 101.5, 0.25) + [100.5, 100.75, 101.0, 101.25] + >>> frange(5, 0) + [] + >>> frange(5, 0, step=-1.25) + [5.0, 3.75, 2.5, 1.25] + """ + if not step: + raise ValueError('step must be non-zero') + if start is None: + start, stop = 0.0, stop * 1.0 + else: + # swap when all args are used + stop, start = start * 1.0, stop * 1.0 + count = int(math.ceil((stop - start) / step)) + ret = [None] * count + if not ret: + return ret + ret[0] = start + for i in xrange(1, count): + ret[i] = ret[i - 1] + step + return ret + + +def backoff(start, stop, count=None, factor=2.0, jitter=False): + """Returns a list of geometrically-increasing floating-point numbers, + suitable for usage with `exponential backoff`_. Exactly like + :func:`backoff_iter`, but without the ``'repeat'`` option for + *count*. See :func:`backoff_iter` for more details. + + .. _exponential backoff: https://en.wikipedia.org/wiki/Exponential_backoff + + >>> backoff(1, 10) + [1.0, 2.0, 4.0, 8.0, 10.0] + """ + if count == 'repeat': + raise ValueError("'repeat' supported in backoff_iter, not backoff") + return list(backoff_iter(start, stop, count=count, + factor=factor, jitter=jitter)) + + +def backoff_iter(start, stop, count=None, factor=2.0, jitter=False): + """Generates a sequence of geometrically-increasing floats, suitable + for usage with `exponential backoff`_. Starts with *start*, + increasing by *factor* until *stop* is reached, optionally + stopping iteration once *count* numbers are yielded. *factor* + defaults to 2. In general retrying with properly-configured + backoff creates a better-behaved component for a larger service + ecosystem. + + .. _exponential backoff: https://en.wikipedia.org/wiki/Exponential_backoff + + >>> list(backoff_iter(1.0, 10.0, count=5)) + [1.0, 2.0, 4.0, 8.0, 10.0] + >>> list(backoff_iter(1.0, 10.0, count=8)) + [1.0, 2.0, 4.0, 8.0, 10.0, 10.0, 10.0, 10.0] + >>> list(backoff_iter(0.25, 100.0, factor=10)) + [0.25, 2.5, 25.0, 100.0] + + A simplified usage example: + + .. code-block:: python + + for timeout in backoff_iter(0.25, 5.0): + try: + res = network_call() + break + except Exception as e: + log(e) + time.sleep(timeout) + + An enhancement for large-scale systems would be to add variation, + or *jitter*, to timeout values. This is done to avoid a thundering + herd on the receiving end of the network call. + + Finally, for *count*, the special value ``'repeat'`` can be passed to + continue yielding indefinitely. + + Args: + + start (float): Positive number for baseline. + stop (float): Positive number for maximum. + count (int): Number of steps before stopping + iteration. Defaults to the number of steps between *start* and + *stop*. Pass the string, `'repeat'`, to continue iteration + indefinitely. + factor (float): Rate of exponential increase. Defaults to `2.0`, + e.g., `[1, 2, 4, 8, 16]`. + jitter (float): A factor between `-1.0` and `1.0`, used to + uniformly randomize and thus spread out timeouts in a distributed + system, avoiding rhythm effects. Positive values use the base + backoff curve as a maximum, negative values use the curve as a + minimum. Set to 1.0 or `True` for a jitter approximating + Ethernet's time-tested backoff solution. Defaults to `False`. + + """ + start = float(start) + stop = float(stop) + factor = float(factor) + if start < 0.0: + raise ValueError('expected start >= 0, not %r' % start) + if factor < 1.0: + raise ValueError('expected factor >= 1.0, not %r' % factor) + if stop == 0.0: + raise ValueError('expected stop >= 0') + if stop < start: + raise ValueError('expected stop >= start, not %r' % stop) + if count is None: + denom = start if start else 1 + count = 1 + math.ceil(math.log(stop/denom, factor)) + count = count if start else count + 1 + if count != 'repeat' and count < 0: + raise ValueError('count must be positive or "repeat", not %r' % count) + if jitter: + jitter = float(jitter) + if not (-1.0 <= jitter <= 1.0): + raise ValueError('expected jitter -1 <= j <= 1, not: %r' % jitter) + + cur, i = start, 0 + while count == 'repeat' or i < count: + if not jitter: + cur_ret = cur + elif jitter: + cur_ret = cur - (cur * jitter * random.random()) + yield cur_ret + i += 1 + if cur == 0: + cur = 1 + elif cur < stop: + cur *= factor + if cur > stop: + cur = stop + return + + +def bucketize(src, key=bool, value_transform=None, key_filter=None): + """Group values in the *src* iterable by the value returned by *key*. + + >>> bucketize(range(5)) + {False: [0], True: [1, 2, 3, 4]} + >>> is_odd = lambda x: x % 2 == 1 + >>> bucketize(range(5), is_odd) + {False: [0, 2, 4], True: [1, 3]} + + *key* is :class:`bool` by default, but can either be a callable or a string + name of the attribute on which to bucketize objects. + + >>> bucketize([1+1j, 2+2j, 1, 2], key='real') + {1.0: [(1+1j), 1], 2.0: [(2+2j), 2]} + + Value lists are not deduplicated: + + >>> bucketize([None, None, None, 'hello']) + {False: [None, None, None], True: ['hello']} + + Bucketize into more than 3 groups + + >>> bucketize(range(10), lambda x: x % 3) + {0: [0, 3, 6, 9], 1: [1, 4, 7], 2: [2, 5, 8]} + + ``bucketize`` has a couple of advanced options useful in certain + cases. *value_transform* can be used to modify values as they are + added to buckets, and *key_filter* will allow excluding certain + buckets from being collected. + + >>> bucketize(range(5), value_transform=lambda x: x*x) + {False: [0], True: [1, 4, 9, 16]} + + >>> bucketize(range(10), key=lambda x: x % 3, key_filter=lambda k: k % 3 != 1) + {0: [0, 3, 6, 9], 2: [2, 5, 8]} + + Note in some of these examples there were at most two keys, ``True`` and + ``False``, and each key present has a list with at least one + item. See :func:`partition` for a version specialized for binary + use cases. + + """ + if not is_iterable(src): + raise TypeError('expected an iterable') + + if isinstance(key, basestring): + key_func = lambda x: getattr(x, key, x) + elif callable(key): + key_func = key + else: + raise TypeError('expected key to be callable or a string') + + if value_transform is None: + value_transform = lambda x: x + if not callable(value_transform): + raise TypeError('expected callable value transform function') + + ret = {} + for val in src: + key_of_val = key_func(val) + if key_filter is None or key_filter(key_of_val): + ret.setdefault(key_of_val, []).append(value_transform(val)) + return ret + + +def partition(src, key=bool): + """No relation to :meth:`str.partition`, ``partition`` is like + :func:`bucketize`, but for added convenience returns a tuple of + ``(truthy_values, falsy_values)``. + + >>> nonempty, empty = partition(['', '', 'hi', '', 'bye']) + >>> nonempty + ['hi', 'bye'] + + *key* defaults to :class:`bool`, but can be carefully overridden to + use either a function that returns either ``True`` or ``False`` or + a string name of the attribute on which to partition objects. + + >>> import string + >>> is_digit = lambda x: x in string.digits + >>> decimal_digits, hexletters = partition(string.hexdigits, is_digit) + >>> ''.join(decimal_digits), ''.join(hexletters) + ('0123456789', 'abcdefABCDEF') + """ + bucketized = bucketize(src, key) + return bucketized.get(True, []), bucketized.get(False, []) + + +def unique(src, key=None): + """``unique()`` returns a list of unique values, as determined by + *key*, in the order they first appeared in the input iterable, + *src*. + + >>> ones_n_zeros = '11010110001010010101010' + >>> ''.join(unique(ones_n_zeros)) + '10' + + See :func:`unique_iter` docs for more details. + """ + return list(unique_iter(src, key)) + + +def unique_iter(src, key=None): + """Yield unique elements from the iterable, *src*, based on *key*, + in the order in which they first appeared in *src*. + + >>> repetitious = [1, 2, 3] * 10 + >>> list(unique_iter(repetitious)) + [1, 2, 3] + + By default, *key* is the object itself, but *key* can either be a + callable or, for convenience, a string name of the attribute on + which to uniqueify objects, falling back on identity when the + attribute is not present. + + >>> pleasantries = ['hi', 'hello', 'ok', 'bye', 'yes'] + >>> list(unique_iter(pleasantries, key=lambda x: len(x))) + ['hi', 'hello', 'bye'] + """ + if not is_iterable(src): + raise TypeError('expected an iterable, not %r' % type(src)) + if key is None: + key_func = lambda x: x + elif callable(key): + key_func = key + elif isinstance(key, basestring): + key_func = lambda x: getattr(x, key, x) + else: + raise TypeError('"key" expected a string or callable, not %r' % key) + seen = set() + for i in src: + k = key_func(i) + if k not in seen: + seen.add(k) + yield i + return + + +def redundant(src, key=None, groups=False): + """The complement of :func:`unique()`. + + By default returns non-unique/duplicate values as a list of the + *first* redundant value in *src*. Pass ``groups=True`` to get + groups of all values with redundancies, ordered by position of the + first redundant value. This is useful in conjunction with some + normalizing *key* function. + + >>> redundant([1, 2, 3, 4]) + [] + >>> redundant([1, 2, 3, 2, 3, 3, 4]) + [2, 3] + >>> redundant([1, 2, 3, 2, 3, 3, 4], groups=True) + [[2, 2], [3, 3, 3]] + + An example using a *key* function to do case-insensitive + redundancy detection. + + >>> redundant(['hi', 'Hi', 'HI', 'hello'], key=str.lower) + ['Hi'] + >>> redundant(['hi', 'Hi', 'HI', 'hello'], groups=True, key=str.lower) + [['hi', 'Hi', 'HI']] + + *key* should also be used when the values in *src* are not hashable. + + .. note:: + + This output of this function is designed for reporting + duplicates in contexts when a unique input is desired. Due to + the grouped return type, there is no streaming equivalent of + this function for the time being. + + """ + if key is None: + pass + elif callable(key): + key_func = key + elif isinstance(key, basestring): + key_func = lambda x: getattr(x, key, x) + else: + raise TypeError('"key" expected a string or callable, not %r' % key) + seen = {} # key to first seen item + redundant_order = [] + redundant_groups = {} + for i in src: + k = key_func(i) if key else i + if k not in seen: + seen[k] = i + else: + if k in redundant_groups: + if groups: + redundant_groups[k].append(i) + else: + redundant_order.append(k) + redundant_groups[k] = [seen[k], i] + if not groups: + ret = [redundant_groups[k][1] for k in redundant_order] + else: + ret = [redundant_groups[k] for k in redundant_order] + return ret + + +def one(src, default=None, key=None): + """Along the same lines as builtins, :func:`all` and :func:`any`, and + similar to :func:`first`, ``one()`` returns the single object in + the given iterable *src* that evaluates to ``True``, as determined + by callable *key*. If unset, *key* defaults to :class:`bool`. If + no such objects are found, *default* is returned. If *default* is + not passed, ``None`` is returned. + + If *src* has more than one object that evaluates to ``True``, or + if there is no object that fulfills such condition, return + *default*. It's like an `XOR`_ over an iterable. + + >>> one((True, False, False)) + True + >>> one((True, False, True)) + >>> one((0, 0, 'a')) + 'a' + >>> one((0, False, None)) + >>> one((True, True), default=False) + False + >>> bool(one(('', 1))) + True + >>> one((10, 20, 30, 42), key=lambda i: i > 40) + 42 + + See `MartÃn Gaitán's original repo`_ for further use cases. + + .. _MartÃn Gaitán's original repo: https://github.com/mgaitan/one + .. _XOR: https://en.wikipedia.org/wiki/Exclusive_or + + """ + ones = list(itertools.islice(filter(key, src), 2)) + return ones[0] if len(ones) == 1 else default + + +def first(iterable, default=None, key=None): + """Return first element of *iterable* that evaluates to ``True``, else + return ``None`` or optional *default*. Similar to :func:`one`. + + >>> first([0, False, None, [], (), 42]) + 42 + >>> first([0, False, None, [], ()]) is None + True + >>> first([0, False, None, [], ()], default='ohai') + 'ohai' + >>> import re + >>> m = first(re.match(regex, 'abc') for regex in ['b.*', 'a(.*)']) + >>> m.group(1) + 'bc' + + The optional *key* argument specifies a one-argument predicate function + like that used for *filter()*. The *key* argument, if supplied, should be + in keyword form. For example, finding the first even number in an iterable: + + >>> first([1, 1, 3, 4, 5], key=lambda x: x % 2 == 0) + 4 + + Contributed by Hynek Schlawack, author of `the original standalone module`_. + + .. _the original standalone module: https://github.com/hynek/first + """ + return next(filter(key, iterable), default) + + +def flatten_iter(iterable): + """``flatten_iter()`` yields all the elements from *iterable* while + collapsing any nested iterables. + + >>> nested = [[1, 2], [[3], [4, 5]]] + >>> list(flatten_iter(nested)) + [1, 2, 3, 4, 5] + """ + for item in iterable: + if isinstance(item, Iterable) and not isinstance(item, basestring): + for subitem in flatten_iter(item): + yield subitem + else: + yield item + +def flatten(iterable): + """``flatten()`` returns a collapsed list of all the elements from + *iterable* while collapsing any nested iterables. + + >>> nested = [[1, 2], [[3], [4, 5]]] + >>> flatten(nested) + [1, 2, 3, 4, 5] + """ + return list(flatten_iter(iterable)) + + +def same(iterable, ref=_UNSET): + """``same()`` returns ``True`` when all values in *iterable* are + equal to one another, or optionally a reference value, + *ref*. Similar to :func:`all` and :func:`any` in that it evaluates + an iterable and returns a :class:`bool`. ``same()`` returns + ``True`` for empty iterables. + + >>> same([]) + True + >>> same([1]) + True + >>> same(['a', 'a', 'a']) + True + >>> same(range(20)) + False + >>> same([[], []]) + True + >>> same([[], []], ref='test') + False + + """ + iterator = iter(iterable) + if ref is _UNSET: + ref = next(iterator, ref) + return all(val == ref for val in iterator) + + +def default_visit(path, key, value): + # print('visit(%r, %r, %r)' % (path, key, value)) + return key, value + +# enable the extreme: monkeypatching iterutils with a different default_visit +_orig_default_visit = default_visit + + +def default_enter(path, key, value): + # print('enter(%r, %r)' % (key, value)) + if isinstance(value, basestring): + return value, False + elif isinstance(value, Mapping): + return value.__class__(), ItemsView(value) + elif isinstance(value, Sequence): + return value.__class__(), enumerate(value) + elif isinstance(value, Set): + return value.__class__(), enumerate(value) + else: + # files, strings, other iterables, and scalars are not + # traversed + return value, False + + +def default_exit(path, key, old_parent, new_parent, new_items): + # print('exit(%r, %r, %r, %r, %r)' + # % (path, key, old_parent, new_parent, new_items)) + ret = new_parent + if isinstance(new_parent, Mapping): + new_parent.update(new_items) + elif isinstance(new_parent, Sequence): + vals = [v for i, v in new_items] + try: + new_parent.extend(vals) + except AttributeError: + ret = new_parent.__class__(vals) # tuples + elif isinstance(new_parent, Set): + vals = [v for i, v in new_items] + try: + new_parent.update(vals) + except AttributeError: + ret = new_parent.__class__(vals) # frozensets + else: + raise RuntimeError('unexpected iterable type: %r' % type(new_parent)) + return ret + + +def remap(root, visit=default_visit, enter=default_enter, exit=default_exit, + **kwargs): + """The remap ("recursive map") function is used to traverse and + transform nested structures. Lists, tuples, sets, and dictionaries + are just a few of the data structures nested into heterogenous + tree-like structures that are so common in programming. + Unfortunately, Python's built-in ways to manipulate collections + are almost all flat. List comprehensions may be fast and succinct, + but they do not recurse, making it tedious to apply quick changes + or complex transforms to real-world data. + + remap goes where list comprehensions cannot. + + Here's an example of removing all Nones from some data: + + >>> from pprint import pprint + >>> reviews = {'Star Trek': {'TNG': 10, 'DS9': 8.5, 'ENT': None}, + ... 'Babylon 5': 6, 'Dr. Who': None} + >>> pprint(remap(reviews, lambda p, k, v: v is not None)) + {'Babylon 5': 6, 'Star Trek': {'DS9': 8.5, 'TNG': 10}} + + Notice how both Nones have been removed despite the nesting in the + dictionary. Not bad for a one-liner, and that's just the beginning. + See `this remap cookbook`_ for more delicious recipes. + + .. _this remap cookbook: http://sedimental.org/remap.html + + remap takes four main arguments: the object to traverse and three + optional callables which determine how the remapped object will be + created. + + Args: + + root: The target object to traverse. By default, remap + supports iterables like :class:`list`, :class:`tuple`, + :class:`dict`, and :class:`set`, but any object traversable by + *enter* will work. + visit (callable): This function is called on every item in + *root*. It must accept three positional arguments, *path*, + *key*, and *value*. *path* is simply a tuple of parents' + keys. *visit* should return the new key-value pair. It may + also return ``True`` as shorthand to keep the old item + unmodified, or ``False`` to drop the item from the new + structure. *visit* is called after *enter*, on the new parent. + + The *visit* function is called for every item in root, + including duplicate items. For traversable values, it is + called on the new parent object, after all its children + have been visited. The default visit behavior simply + returns the key-value pair unmodified. + enter (callable): This function controls which items in *root* + are traversed. It accepts the same arguments as *visit*: the + path, the key, and the value of the current item. It returns a + pair of the blank new parent, and an iterator over the items + which should be visited. If ``False`` is returned instead of + an iterator, the value will not be traversed. + + The *enter* function is only called once per unique value. The + default enter behavior support mappings, sequences, and + sets. Strings and all other iterables will not be traversed. + exit (callable): This function determines how to handle items + once they have been visited. It gets the same three + arguments as the other functions -- *path*, *key*, *value* + -- plus two more: the blank new parent object returned + from *enter*, and a list of the new items, as remapped by + *visit*. + + Like *enter*, the *exit* function is only called once per + unique value. The default exit behavior is to simply add + all new items to the new parent, e.g., using + :meth:`list.extend` and :meth:`dict.update` to add to the + new parent. Immutable objects, such as a :class:`tuple` or + :class:`namedtuple`, must be recreated from scratch, but + use the same type as the new parent passed back from the + *enter* function. + reraise_visit (bool): A pragmatic convenience for the *visit* + callable. When set to ``False``, remap ignores any errors + raised by the *visit* callback. Items causing exceptions + are kept. See examples for more details. + + remap is designed to cover the majority of cases with just the + *visit* callable. While passing in multiple callables is very + empowering, remap is designed so very few cases should require + passing more than one function. + + When passing *enter* and *exit*, it's common and easiest to build + on the default behavior. Simply add ``from boltons.iterutils import + default_enter`` (or ``default_exit``), and have your enter/exit + function call the default behavior before or after your custom + logic. See `this example`_. + + Duplicate and self-referential objects (aka reference loops) are + automatically handled internally, `as shown here`_. + + .. _this example: http://sedimental.org/remap.html#sort_all_lists + .. _as shown here: http://sedimental.org/remap.html#corner_cases + + """ + # TODO: improve argument formatting in sphinx doc + # TODO: enter() return (False, items) to continue traverse but cancel copy? + if not callable(visit): + raise TypeError('visit expected callable, not: %r' % visit) + if not callable(enter): + raise TypeError('enter expected callable, not: %r' % enter) + if not callable(exit): + raise TypeError('exit expected callable, not: %r' % exit) + reraise_visit = kwargs.pop('reraise_visit', True) + if kwargs: + raise TypeError('unexpected keyword arguments: %r' % kwargs.keys()) + + path, registry, stack = (), {}, [(None, root)] + new_items_stack = [] + while stack: + key, value = stack.pop() + id_value = id(value) + if key is _REMAP_EXIT: + key, new_parent, old_parent = value + id_value = id(old_parent) + path, new_items = new_items_stack.pop() + value = exit(path, key, old_parent, new_parent, new_items) + registry[id_value] = value + if not new_items_stack: + continue + elif id_value in registry: + value = registry[id_value] + else: + res = enter(path, key, value) + try: + new_parent, new_items = res + except TypeError: + # TODO: handle False? + raise TypeError('enter should return a tuple of (new_parent,' + ' items_iterator), not: %r' % res) + if new_items is not False: + # traverse unless False is explicitly passed + registry[id_value] = new_parent + new_items_stack.append((path, [])) + if value is not root: + path += (key,) + stack.append((_REMAP_EXIT, (key, new_parent, value))) + if new_items: + stack.extend(reversed(list(new_items))) + continue + if visit is _orig_default_visit: + # avoid function call overhead by inlining identity operation + visited_item = (key, value) + else: + try: + visited_item = visit(path, key, value) + except Exception: + if reraise_visit: + raise + visited_item = True + if visited_item is False: + continue # drop + elif visited_item is True: + visited_item = (key, value) + # TODO: typecheck? + # raise TypeError('expected (key, value) from visit(),' + # ' not: %r' % visited_item) + try: + new_items_stack[-1][1].append(visited_item) + except IndexError: + raise TypeError('expected remappable root, not: %r' % root) + return value + + +class PathAccessError(KeyError, IndexError, TypeError): + """An amalgamation of KeyError, IndexError, and TypeError, + representing what can occur when looking up a path in a nested + object. + """ + def __init__(self, exc, seg, path): + self.exc = exc + self.seg = seg + self.path = path + + def __repr__(self): + cn = self.__class__.__name__ + return '%s(%r, %r, %r)' % (cn, self.exc, self.seg, self.path) + + def __str__(self): + return ('could not access %r from path %r, got error: %r' + % (self.seg, self.path, self.exc)) + + +def get_path(root, path, default=_UNSET): + """Retrieve a value from a nested object via a tuple representing the + lookup path. + + >>> root = {'a': {'b': {'c': [[1], [2], [3]]}}} + >>> get_path(root, ('a', 'b', 'c', 2, 0)) + 3 + + The path format is intentionally consistent with that of + :func:`remap`. + + One of get_path's chief aims is improved error messaging. EAFP is + great, but the error messages are not. + + For instance, ``root['a']['b']['c'][2][1]`` gives back + ``IndexError: list index out of range`` + + What went out of range where? get_path currently raises + ``PathAccessError: could not access 2 from path ('a', 'b', 'c', 2, + 1), got error: IndexError('list index out of range',)``, a + subclass of IndexError and KeyError. + + You can also pass a default that covers the entire operation, + should the lookup fail at any level. + + Args: + root: The target nesting of dictionaries, lists, or other + objects supporting ``__getitem__``. + path (tuple): A list of strings and integers to be successively + looked up within *root*. + default: The value to be returned should any + ``PathAccessError`` exceptions be raised. + """ + if isinstance(path, basestring): + path = path.split('.') + cur = root + try: + for seg in path: + try: + cur = cur[seg] + except (KeyError, IndexError) as exc: + raise PathAccessError(exc, seg, path) + except TypeError as exc: + # either string index in a list, or a parent that + # doesn't support indexing + try: + seg = int(seg) + cur = cur[seg] + except (ValueError, KeyError, IndexError, TypeError): + if not is_iterable(cur): + exc = TypeError('%r object is not indexable' + % type(cur).__name__) + raise PathAccessError(exc, seg, path) + except PathAccessError: + if default is _UNSET: + raise + return default + return cur + + +def research(root, query=lambda p, k, v: True, reraise=False): + """The :func:`research` function uses :func:`remap` to recurse over + any data nested in *root*, and find values which match a given + criterion, specified by the *query* callable. + + Results are returned as a list of ``(path, value)`` pairs. The + paths are tuples in the same format accepted by + :func:`get_path`. This can be useful for comparing values nested + in two or more different structures. + + Here's a simple example that finds all integers: + + >>> root = {'a': {'b': 1, 'c': (2, 'd', 3)}, 'e': None} + >>> res = research(root, query=lambda p, k, v: isinstance(v, int)) + >>> print(sorted(res)) + [(('a', 'b'), 1), (('a', 'c', 0), 2), (('a', 'c', 2), 3)] + + Note how *query* follows the same, familiar ``path, key, value`` + signature as the ``visit`` and ``enter`` functions on + :func:`remap`, and returns a :class:`bool`. + + Args: + root: The target object to search. Supports the same types of + objects as :func:`remap`, including :class:`list`, + :class:`tuple`, :class:`dict`, and :class:`set`. + query (callable): The function called on every object to + determine whether to include it in the search results. The + callable must accept three arguments, *path*, *key*, and + *value*, commonly abbreviated *p*, *k*, and *v*, same as + *enter* and *visit* from :func:`remap`. + reraise (bool): Whether to reraise exceptions raised by *query* + or to simply drop the result that caused the error. + + + With :func:`research` it's easy to inspect the details of a data + structure, like finding values that are at a certain depth (using + ``len(p)``) and much more. If more advanced functionality is + needed, check out the code and make your own :func:`remap` + wrapper, and consider `submitting a patch`_! + + .. _submitting a patch: https://github.com/mahmoud/boltons/pulls + """ + ret = [] + + if not callable(query): + raise TypeError('query expected callable, not: %r' % query) + + def enter(path, key, value): + try: + if query(path, key, value): + ret.append((path + (key,), value)) + except Exception: + if reraise: + raise + return default_enter(path, key, value) + + remap(root, enter=enter) + return ret + + +# TODO: recollect() +# TODO: refilter() +# TODO: reiter() + + +# GUID iterators: 10x faster and somewhat more compact than uuid. + +class GUIDerator(object): + """The GUIDerator is an iterator that yields a globally-unique + identifier (GUID) on every iteration. The GUIDs produced are + hexadecimal strings. + + Testing shows it to be around 12x faster than the uuid module. By + default it is also more compact, partly due to its default 96-bit + (24-hexdigit) length. 96 bits of randomness means that there is a + 1 in 2 ^ 32 chance of collision after 2 ^ 64 iterations. If more + or less uniqueness is desired, the *size* argument can be adjusted + accordingly. + + Args: + size (int): character length of the GUID, defaults to 24. Lengths + between 20 and 36 are considered valid. + + The GUIDerator has built-in fork protection that causes it to + detect a fork on next iteration and reseed accordingly. + + """ + def __init__(self, size=24): + self.size = size + if size < 20 or size > 36: + raise ValueError('expected 20 < size <= 36') + import hashlib + self._sha1 = hashlib.sha1 + self.count = itertools.count() + self.reseed() + + def reseed(self): + import socket + self.pid = os.getpid() + self.salt = '-'.join([str(self.pid), + socket.gethostname() or b'<nohostname>', + str(time.time()), + codecs.encode(os.urandom(6), + 'hex_codec').decode('ascii')]) + # that codecs trick is the best/only way to get a bytes to + # hexbytes in py2/3 + return + + def __iter__(self): + return self + + if _IS_PY3: + def __next__(self): + if os.getpid() != self.pid: + self.reseed() + target_bytes = (self.salt + str(next(self.count))).encode('utf8') + hash_text = self._sha1(target_bytes).hexdigest()[:self.size] + return hash_text + else: + def __next__(self): + if os.getpid() != self.pid: + self.reseed() + return self._sha1(self.salt + + str(next(self.count))).hexdigest()[:self.size] + + next = __next__ + + +class SequentialGUIDerator(GUIDerator): + """Much like the standard GUIDerator, the SequentialGUIDerator is an + iterator that yields a globally-unique identifier (GUID) on every + iteration. The GUIDs produced are hexadecimal strings. + + The SequentialGUIDerator differs in that it picks a starting GUID + value and increments every iteration. This yields GUIDs which are + of course unique, but also ordered and lexicographically sortable. + + The SequentialGUIDerator is around 50% faster than the normal + GUIDerator, making it almost 20x as fast as the built-in uuid + module. By default it is also more compact, partly due to its + 96-bit (24-hexdigit) default length. 96 bits of randomness means that + there is a 1 in 2 ^ 32 chance of collision after 2 ^ 64 + iterations. If more or less uniqueness is desired, the *size* + argument can be adjusted accordingly. + + Args: + size (int): character length of the GUID, defaults to 24. + + Note that with SequentialGUIDerator there is a chance of GUIDs + growing larger than the size configured. The SequentialGUIDerator + has built-in fork protection that causes it to detect a fork on + next iteration and reseed accordingly. + + """ + + if _IS_PY3: + def reseed(self): + super(SequentialGUIDerator, self).reseed() + start_str = self._sha1(self.salt.encode('utf8')).hexdigest() + self.start = int(start_str[:self.size], 16) + self.start |= (1 << ((self.size * 4) - 2)) + else: + def reseed(self): + super(SequentialGUIDerator, self).reseed() + start_str = self._sha1(self.salt).hexdigest() + self.start = int(start_str[:self.size], 16) + self.start |= (1 << ((self.size * 4) - 2)) + + def __next__(self): + if os.getpid() != self.pid: + self.reseed() + return '%x' % (next(self.count) + self.start) + + next = __next__ + + +guid_iter = GUIDerator() +seq_guid_iter = SequentialGUIDerator() + + +def soft_sorted(iterable, first=None, last=None, key=None, reverse=False): + """For when you care about the order of some elements, but not about + others. + + Use this to float to the top and/or sink to the bottom a specific + ordering, while sorting the rest of the elements according to + normal :func:`sorted` rules. + + >>> soft_sorted(['two', 'b', 'one', 'a'], first=['one', 'two']) + ['one', 'two', 'a', 'b'] + >>> soft_sorted(range(7), first=[6, 15], last=[2, 4], reverse=True) + [6, 5, 3, 1, 0, 2, 4] + >>> import string + >>> ''.join(soft_sorted(string.hexdigits, first='za1', last='b', key=str.lower)) + 'aA1023456789cCdDeEfFbB' + + Args: + iterable (list): A list or other iterable to sort. + first (list): A sequence to enforce for elements which should + appear at the beginning of the returned list. + last (list): A sequence to enforce for elements which should + appear at the end of the returned list. + key (callable): Callable used to generate a comparable key for + each item to be sorted, same as the key in + :func:`sorted`. Note that entries in *first* and *last* + should be the keys for the items. Defaults to + passthrough/the identity function. + reverse (bool): Whether or not elements not explicitly ordered + by *first* and *last* should be in reverse order or not. + + Returns a new list in sorted order. + """ + first = first or [] + last = last or [] + key = key or (lambda x: x) + seq = list(iterable) + other = [x for x in seq if not ((first and key(x) in first) or (last and key(x) in last))] + other.sort(key=key, reverse=reverse) + + if first: + first = sorted([x for x in seq if key(x) in first], key=lambda x: first.index(key(x))) + if last: + last = sorted([x for x in seq if key(x) in last], key=lambda x: last.index(key(x))) + return first + other + last + + +def untyped_sorted(iterable, key=None, reverse=False): + """A version of :func:`sorted` which will happily sort an iterable of + heterogenous types and return a new list, similar to legacy Python's + behavior. + + >>> untyped_sorted(['abc', 2.0, 1, 2, 'def']) + [1, 2.0, 2, 'abc', 'def'] + + Note how mutually orderable types are sorted as expected, as in + the case of the integers and floats above. + + .. note:: + + Results may vary across Python versions and builds, but the + function will produce a sorted list, except in the case of + explicitly unorderable objects. + + """ + class _Wrapper(object): + slots = ('obj',) + + def __init__(self, obj): + self.obj = obj + + def __lt__(self, other): + obj = key(self.obj) if key is not None else self.obj + other = key(other.obj) if key is not None else other.obj + try: + ret = obj < other + except TypeError: + ret = ((type(obj).__name__, id(type(obj)), obj) + < (type(other).__name__, id(type(other)), other)) + return ret + + if key is not None and not callable(key): + raise TypeError('expected function or callable object for key, not: %r' + % key) + + return sorted(iterable, key=_Wrapper, reverse=reverse) + +""" +May actually be faster to do an isinstance check for a str path + +$ python -m timeit -s "x = [1]" "x[0]" +10000000 loops, best of 3: 0.0207 usec per loop +$ python -m timeit -s "x = [1]" "try: x[0] \nexcept: pass" +10000000 loops, best of 3: 0.029 usec per loop +$ python -m timeit -s "x = [1]" "try: x[1] \nexcept: pass" +1000000 loops, best of 3: 0.315 usec per loop +# setting up try/except is fast, only around 0.01us +# actually triggering the exception takes almost 10x as long + +$ python -m timeit -s "x = [1]" "isinstance(x, basestring)" +10000000 loops, best of 3: 0.141 usec per loop +$ python -m timeit -s "x = [1]" "isinstance(x, str)" +10000000 loops, best of 3: 0.131 usec per loop +$ python -m timeit -s "x = [1]" "try: x.split('.')\n except: pass" +1000000 loops, best of 3: 0.443 usec per loop +$ python -m timeit -s "x = [1]" "try: x.split('.') \nexcept AttributeError: pass" +1000000 loops, best of 3: 0.544 usec per loop +"""