Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/boltons/iterutils.py: 15%
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# Copyright (c) 2013, Mahmoud Hashemi
2#
3# Redistribution and use in source and binary forms, with or without
4# modification, are permitted provided that the following conditions are
5# met:
6#
7# * Redistributions of source code must retain the above copyright
8# notice, this list of conditions and the following disclaimer.
9#
10# * Redistributions in binary form must reproduce the above
11# copyright notice, this list of conditions and the following
12# disclaimer in the documentation and/or other materials provided
13# with the distribution.
14#
15# * The names of the contributors may not be used to endorse or
16# promote products derived from this software without specific
17# prior written permission.
18#
19# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31""":mod:`itertools` is full of great examples of Python generator
32usage. However, there are still some critical gaps. ``iterutils``
33fills many of those gaps with featureful, tested, and Pythonic
34solutions.
36Many of the functions below have two versions, one which
37returns an iterator (denoted by the ``*_iter`` naming pattern), and a
38shorter-named convenience form that returns a list. Some of the
39following are based on examples in itertools docs.
40"""
42import os
43import math
44import time
45import codecs
46import random
47import itertools
48from itertools import zip_longest
49from collections.abc import Mapping, Sequence, Set, ItemsView, Iterable
52try:
53 from .typeutils import make_sentinel
54 _UNSET = make_sentinel('_UNSET')
55 _REMAP_EXIT = make_sentinel('_REMAP_EXIT')
56except ImportError:
57 _REMAP_EXIT = object()
58 _UNSET = object()
61def is_iterable(obj):
62 """Similar in nature to :func:`callable`, ``is_iterable`` returns
63 ``True`` if an object is `iterable`_, ``False`` if not.
65 >>> is_iterable([])
66 True
67 >>> is_iterable(object())
68 False
70 .. _iterable: https://docs.python.org/2/glossary.html#term-iterable
71 """
72 try:
73 iter(obj)
74 except TypeError:
75 return False
76 return True
79def is_scalar(obj):
80 """A near-mirror of :func:`is_iterable`. Returns ``False`` if an
81 object is an iterable container type. Strings are considered
82 scalar as well, because strings are more often treated as whole
83 values as opposed to iterables of 1-character substrings.
85 >>> is_scalar(object())
86 True
87 >>> is_scalar(range(10))
88 False
89 >>> is_scalar('hello')
90 True
91 """
92 return not is_iterable(obj) or isinstance(obj, (str, bytes))
95def is_collection(obj):
96 """The opposite of :func:`is_scalar`. Returns ``True`` if an object
97 is an iterable other than a string.
99 >>> is_collection(object())
100 False
101 >>> is_collection(range(10))
102 True
103 >>> is_collection('hello')
104 False
105 """
106 return is_iterable(obj) and not isinstance(obj, (str, bytes))
109def split(src, sep=None, maxsplit=None):
110 """Splits an iterable based on a separator. Like :meth:`str.split`,
111 but for all iterables. Returns a list of lists.
113 >>> split(['hi', 'hello', None, None, 'sup', None, 'soap', None])
114 [['hi', 'hello'], ['sup'], ['soap']]
116 See :func:`split_iter` docs for more info.
117 """
118 return list(split_iter(src, sep, maxsplit))
121def split_iter(src, sep=None, maxsplit=None):
122 """Splits an iterable based on a separator, *sep*, a max of
123 *maxsplit* times (no max by default). *sep* can be:
125 * a single value
126 * an iterable of separators
127 * a single-argument callable that returns True when a separator is
128 encountered
130 ``split_iter()`` yields lists of non-separator values. A separator will
131 never appear in the output.
133 >>> list(split_iter(['hi', 'hello', None, None, 'sup', None, 'soap', None]))
134 [['hi', 'hello'], ['sup'], ['soap']]
136 Note that ``split_iter`` is based on :func:`str.split`, so if
137 *sep* is ``None``, ``split()`` **groups** separators. If empty lists
138 are desired between two contiguous ``None`` values, simply use
139 ``sep=[None]``:
141 >>> list(split_iter(['hi', 'hello', None, None, 'sup', None]))
142 [['hi', 'hello'], ['sup']]
143 >>> list(split_iter(['hi', 'hello', None, None, 'sup', None], sep=[None]))
144 [['hi', 'hello'], [], ['sup'], []]
146 Using a callable separator:
148 >>> falsy_sep = lambda x: not x
149 >>> list(split_iter(['hi', 'hello', None, '', 'sup', False], falsy_sep))
150 [['hi', 'hello'], [], ['sup'], []]
152 See :func:`split` for a list-returning version.
154 """
155 if not is_iterable(src):
156 raise TypeError('expected an iterable')
158 if maxsplit is not None:
159 maxsplit = int(maxsplit)
160 if maxsplit == 0:
161 yield list(src)
162 return
164 if callable(sep):
165 sep_func = sep
166 elif not is_scalar(sep):
167 sep = frozenset(sep)
168 def sep_func(x): return x in sep
169 else:
170 def sep_func(x): return x == sep
172 cur_group = []
173 split_count = 0
174 for s in src:
175 if maxsplit is not None and split_count >= maxsplit:
176 def sep_func(x): return False
177 if sep_func(s):
178 if sep is None and not cur_group:
179 # If sep is none, str.split() "groups" separators
180 # check the str.split() docs for more info
181 continue
182 split_count += 1
183 yield cur_group
184 cur_group = []
185 else:
186 cur_group.append(s)
188 if cur_group or sep is not None:
189 yield cur_group
190 return
193def lstrip(iterable, strip_value=None):
194 """Strips values from the beginning of an iterable. Stripped items will
195 match the value of the argument strip_value. Functionality is analogous
196 to that of the method str.lstrip. Returns a list.
198 >>> lstrip(['Foo', 'Bar', 'Bam'], 'Foo')
199 ['Bar', 'Bam']
201 """
202 return list(lstrip_iter(iterable, strip_value))
205def lstrip_iter(iterable, strip_value=None):
206 """Strips values from the beginning of an iterable. Stripped items will
207 match the value of the argument strip_value. Functionality is analogous
208 to that of the method str.lstrip. Returns a generator.
210 >>> list(lstrip_iter(['Foo', 'Bar', 'Bam'], 'Foo'))
211 ['Bar', 'Bam']
213 """
214 iterator = iter(iterable)
215 for i in iterator:
216 if i != strip_value:
217 yield i
218 break
219 for i in iterator:
220 yield i
223def rstrip(iterable, strip_value=None):
224 """Strips values from the end of an iterable. Stripped items will
225 match the value of the argument strip_value. Functionality is analogous
226 to that of the method str.rstrip. Returns a list.
228 >>> rstrip(['Foo', 'Bar', 'Bam'], 'Bam')
229 ['Foo', 'Bar']
231 """
232 return list(rstrip_iter(iterable, strip_value))
235def rstrip_iter(iterable, strip_value=None):
236 """Strips values from the end of an iterable. Stripped items will
237 match the value of the argument strip_value. Functionality is analogous
238 to that of the method str.rstrip. Returns a generator.
240 >>> list(rstrip_iter(['Foo', 'Bar', 'Bam'], 'Bam'))
241 ['Foo', 'Bar']
243 """
244 iterator = iter(iterable)
245 for i in iterator:
246 if i == strip_value:
247 cache = list()
248 cache.append(i)
249 broken = False
250 for i in iterator:
251 if i == strip_value:
252 cache.append(i)
253 else:
254 broken = True
255 break
256 if not broken: # Return to caller here because the end of the
257 return # iterator has been reached
258 yield from cache
259 yield i
262def strip(iterable, strip_value=None):
263 """Strips values from the beginning and end of an iterable. Stripped items
264 will match the value of the argument strip_value. Functionality is
265 analogous to that of the method str.strip. Returns a list.
267 >>> strip(['Fu', 'Foo', 'Bar', 'Bam', 'Fu'], 'Fu')
268 ['Foo', 'Bar', 'Bam']
270 """
271 return list(strip_iter(iterable, strip_value))
274def strip_iter(iterable, strip_value=None):
275 """Strips values from the beginning and end of an iterable. Stripped items
276 will match the value of the argument strip_value. Functionality is
277 analogous to that of the method str.strip. Returns a generator.
279 >>> list(strip_iter(['Fu', 'Foo', 'Bar', 'Bam', 'Fu'], 'Fu'))
280 ['Foo', 'Bar', 'Bam']
282 """
283 return rstrip_iter(lstrip_iter(iterable, strip_value), strip_value)
286def chunked(src, size, count=None, **kw):
287 """Returns a list of *count* chunks, each with *size* elements,
288 generated from iterable *src*. If *src* is not evenly divisible by
289 *size*, the final chunk will have fewer than *size* elements.
290 Provide the *fill* keyword argument to provide a pad value and
291 enable padding, otherwise no padding will take place.
293 >>> chunked(range(10), 3)
294 [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]]
295 >>> chunked(range(10), 3, fill=None)
296 [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, None, None]]
297 >>> chunked(range(10), 3, count=2)
298 [[0, 1, 2], [3, 4, 5]]
300 See :func:`chunked_iter` for more info.
301 """
302 chunk_iter = chunked_iter(src, size, **kw)
303 if count is None:
304 return list(chunk_iter)
305 else:
306 return list(itertools.islice(chunk_iter, count))
309def _validate_positive_int(value, name, strictly_positive=True):
310 value = int(value)
311 if value < 0 or (strictly_positive and value == 0):
312 raise ValueError('expected a positive integer ' + name)
313 return value
316def chunked_iter(src, size, **kw):
317 """Generates *size*-sized chunks from *src* iterable. Unless the
318 optional *fill* keyword argument is provided, iterables not evenly
319 divisible by *size* will have a final chunk that is smaller than
320 *size*.
322 >>> list(chunked_iter(range(10), 3))
323 [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]]
324 >>> list(chunked_iter(range(10), 3, fill=None))
325 [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, None, None]]
327 Note that ``fill=None`` in fact uses ``None`` as the fill value.
328 """
329 # TODO: add count kwarg?
330 if not is_iterable(src):
331 raise TypeError('expected an iterable')
332 size = _validate_positive_int(size, 'chunk size')
333 do_fill = True
334 try:
335 fill_val = kw.pop('fill')
336 except KeyError:
337 do_fill = False
338 fill_val = None
339 if kw:
340 raise ValueError('got unexpected keyword arguments: %r' % kw.keys())
341 if not src:
342 return
344 def postprocess(chk): return chk
345 if isinstance(src, (str, bytes)):
346 def postprocess(chk, _sep=type(src)()): return _sep.join(chk)
347 if isinstance(src, bytes):
348 def postprocess(chk): return bytes(chk)
349 src_iter = iter(src)
350 while True:
351 cur_chunk = list(itertools.islice(src_iter, size))
352 if not cur_chunk:
353 break
354 lc = len(cur_chunk)
355 if lc < size and do_fill:
356 cur_chunk[lc:] = [fill_val] * (size - lc)
357 yield postprocess(cur_chunk)
358 return
361def chunk_ranges(input_size, chunk_size, input_offset=0, overlap_size=0, align=False):
362 """Generates *chunk_size*-sized chunk ranges for an input with length *input_size*.
363 Optionally, a start of the input can be set via *input_offset*, and
364 and overlap between the chunks may be specified via *overlap_size*.
365 Also, if *align* is set to *True*, any items with *i % (chunk_size-overlap_size) == 0*
366 are always at the beginning of the chunk.
368 Returns an iterator of (start, end) tuples, one tuple per chunk.
370 >>> list(chunk_ranges(input_offset=10, input_size=10, chunk_size=5))
371 [(10, 15), (15, 20)]
372 >>> list(chunk_ranges(input_offset=10, input_size=10, chunk_size=5, overlap_size=1))
373 [(10, 15), (14, 19), (18, 20)]
374 >>> list(chunk_ranges(input_offset=10, input_size=10, chunk_size=5, overlap_size=2))
375 [(10, 15), (13, 18), (16, 20)]
377 >>> list(chunk_ranges(input_offset=4, input_size=15, chunk_size=5, align=False))
378 [(4, 9), (9, 14), (14, 19)]
379 >>> list(chunk_ranges(input_offset=4, input_size=15, chunk_size=5, align=True))
380 [(4, 5), (5, 10), (10, 15), (15, 19)]
382 >>> list(chunk_ranges(input_offset=2, input_size=15, chunk_size=5, overlap_size=1, align=False))
383 [(2, 7), (6, 11), (10, 15), (14, 17)]
384 >>> list(chunk_ranges(input_offset=2, input_size=15, chunk_size=5, overlap_size=1, align=True))
385 [(2, 5), (4, 9), (8, 13), (12, 17)]
386 >>> list(chunk_ranges(input_offset=3, input_size=15, chunk_size=5, overlap_size=1, align=True))
387 [(3, 5), (4, 9), (8, 13), (12, 17), (16, 18)]
388 """
389 input_size = _validate_positive_int(
390 input_size, 'input_size', strictly_positive=False)
391 chunk_size = _validate_positive_int(chunk_size, 'chunk_size')
392 input_offset = _validate_positive_int(
393 input_offset, 'input_offset', strictly_positive=False)
394 overlap_size = _validate_positive_int(
395 overlap_size, 'overlap_size', strictly_positive=False)
397 input_stop = input_offset + input_size
399 if align:
400 initial_chunk_len = chunk_size - \
401 input_offset % (chunk_size - overlap_size)
402 if initial_chunk_len != overlap_size:
403 yield (input_offset, min(input_offset + initial_chunk_len, input_stop))
404 if input_offset + initial_chunk_len >= input_stop:
405 return
406 input_offset = input_offset + initial_chunk_len - overlap_size
408 for i in range(input_offset, input_stop, chunk_size - overlap_size):
409 yield (i, min(i + chunk_size, input_stop))
411 if i + chunk_size >= input_stop:
412 return
415def pairwise(src, end=_UNSET):
416 """Convenience function for calling :func:`windowed` on *src*, with
417 *size* set to 2.
419 >>> pairwise(range(5))
420 [(0, 1), (1, 2), (2, 3), (3, 4)]
421 >>> pairwise([])
422 []
424 Unless *end* is set, the number of pairs is always one less than
425 the number of elements in the iterable passed in, except on an empty input,
426 which will return an empty list.
428 With *end* set, a number of pairs equal to the length of *src* is returned,
429 with the last item of the last pair being equal to *end*.
431 >>> list(pairwise(range(3), end=None))
432 [(0, 1), (1, 2), (2, None)]
434 This way, *end* values can be useful as sentinels to signal the end of the iterable.
435 """
436 return windowed(src, 2, fill=end)
439def pairwise_iter(src, end=_UNSET):
440 """Convenience function for calling :func:`windowed_iter` on *src*,
441 with *size* set to 2.
443 >>> list(pairwise_iter(range(5)))
444 [(0, 1), (1, 2), (2, 3), (3, 4)]
445 >>> list(pairwise_iter([]))
446 []
448 Unless *end* is set, the number of pairs is always one less
449 than the number of elements in the iterable passed in,
450 or zero, when *src* is empty.
452 With *end* set, a number of pairs equal to the length of *src* is returned,
453 with the last item of the last pair being equal to *end*.
455 >>> list(pairwise_iter(range(3), end=None))
456 [(0, 1), (1, 2), (2, None)]
458 This way, *end* values can be useful as sentinels to signal the end
459 of the iterable. For infinite iterators, setting *end* has no effect.
460 """
461 return windowed_iter(src, 2, fill=end)
464def windowed(src, size, fill=_UNSET):
465 """Returns tuples with exactly length *size*. If *fill* is unset
466 and the iterable is too short to make a window of length *size*,
467 no tuples are returned. See :func:`windowed_iter` for more.
468 """
469 return list(windowed_iter(src, size, fill=fill))
472def windowed_iter(src, size, fill=_UNSET):
473 """Returns tuples with length *size* which represent a sliding
474 window over iterable *src*.
476 >>> list(windowed_iter(range(7), 3))
477 [(0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 6)]
479 If *fill* is unset, and the iterable is too short to make a window
480 of length *size*, then no window tuples are returned.
482 >>> list(windowed_iter(range(3), 5))
483 []
485 With *fill* set, the iterator always yields a number of windows
486 equal to the length of the *src* iterable.
488 >>> windowed(range(4), 3, fill=None)
489 [(0, 1, 2), (1, 2, 3), (2, 3, None), (3, None, None)]
491 This way, *fill* values can be useful to signal the end of the iterable.
492 For infinite iterators, setting *fill* has no effect.
493 """
494 tees = itertools.tee(src, size)
495 if fill is _UNSET:
496 try:
497 for i, t in enumerate(tees):
498 for _ in range(i):
499 next(t)
500 except StopIteration:
501 return zip([])
502 return zip(*tees)
504 for i, t in enumerate(tees):
505 for _ in range(i):
506 try:
507 next(t)
508 except StopIteration:
509 continue
510 return zip_longest(*tees, fillvalue=fill)
513def xfrange(stop, start=None, step=1.0):
514 """Same as :func:`frange`, but generator-based instead of returning a
515 list.
517 >>> tuple(xfrange(1, 3, step=0.75))
518 (1.0, 1.75, 2.5)
520 See :func:`frange` for more details.
521 """
522 if not step:
523 raise ValueError('step must be non-zero')
524 if start is None:
525 start, stop = 0.0, stop * 1.0
526 else:
527 # swap when all args are used
528 stop, start = start * 1.0, stop * 1.0
529 cur = start
530 while cur < stop:
531 yield cur
532 cur += step
535def frange(stop, start=None, step=1.0):
536 """A :func:`range` clone for float-based ranges.
538 >>> frange(5)
539 [0.0, 1.0, 2.0, 3.0, 4.0]
540 >>> frange(6, step=1.25)
541 [0.0, 1.25, 2.5, 3.75, 5.0]
542 >>> frange(100.5, 101.5, 0.25)
543 [100.5, 100.75, 101.0, 101.25]
544 >>> frange(5, 0)
545 []
546 >>> frange(5, 0, step=-1.25)
547 [5.0, 3.75, 2.5, 1.25]
548 """
549 if not step:
550 raise ValueError('step must be non-zero')
551 if start is None:
552 start, stop = 0.0, stop * 1.0
553 else:
554 # swap when all args are used
555 stop, start = start * 1.0, stop * 1.0
556 count = int(math.ceil((stop - start) / step))
557 ret = [None] * count
558 if not ret:
559 return ret
560 ret[0] = start
561 for i in range(1, count):
562 ret[i] = ret[i - 1] + step
563 return ret
566def backoff(start, stop, count=None, factor=2.0, jitter=False):
567 """Returns a list of geometrically-increasing floating-point numbers,
568 suitable for usage with `exponential backoff`_. Exactly like
569 :func:`backoff_iter`, but without the ``'repeat'`` option for
570 *count*. See :func:`backoff_iter` for more details.
572 .. _exponential backoff: https://en.wikipedia.org/wiki/Exponential_backoff
574 >>> backoff(1, 10)
575 [1.0, 2.0, 4.0, 8.0, 10.0]
576 """
577 if count == 'repeat':
578 raise ValueError("'repeat' supported in backoff_iter, not backoff")
579 return list(backoff_iter(start, stop, count=count,
580 factor=factor, jitter=jitter))
583def backoff_iter(start, stop, count=None, factor=2.0, jitter=False):
584 """Generates a sequence of geometrically-increasing floats, suitable
585 for usage with `exponential backoff`_. Starts with *start*,
586 increasing by *factor* until *stop* is reached, optionally
587 stopping iteration once *count* numbers are yielded. *factor*
588 defaults to 2. In general retrying with properly-configured
589 backoff creates a better-behaved component for a larger service
590 ecosystem.
592 .. _exponential backoff: https://en.wikipedia.org/wiki/Exponential_backoff
594 >>> list(backoff_iter(1.0, 10.0, count=5))
595 [1.0, 2.0, 4.0, 8.0, 10.0]
596 >>> list(backoff_iter(1.0, 10.0, count=8))
597 [1.0, 2.0, 4.0, 8.0, 10.0, 10.0, 10.0, 10.0]
598 >>> list(backoff_iter(0.25, 100.0, factor=10))
599 [0.25, 2.5, 25.0, 100.0]
601 A simplified usage example:
603 .. code-block:: python
605 for timeout in backoff_iter(0.25, 5.0):
606 try:
607 res = network_call()
608 break
609 except Exception as e:
610 log(e)
611 time.sleep(timeout)
613 An enhancement for large-scale systems would be to add variation,
614 or *jitter*, to timeout values. This is done to avoid a thundering
615 herd on the receiving end of the network call.
617 Finally, for *count*, the special value ``'repeat'`` can be passed to
618 continue yielding indefinitely.
620 Args:
622 start (float): Positive number for baseline.
623 stop (float): Positive number for maximum.
624 count (int): Number of steps before stopping
625 iteration. Defaults to the number of steps between *start* and
626 *stop*. Pass the string, `'repeat'`, to continue iteration
627 indefinitely.
628 factor (float): Rate of exponential increase. Defaults to `2.0`,
629 e.g., `[1, 2, 4, 8, 16]`.
630 jitter (float): A factor between `-1.0` and `1.0`, used to
631 uniformly randomize and thus spread out timeouts in a distributed
632 system, avoiding rhythm effects. Positive values use the base
633 backoff curve as a maximum, negative values use the curve as a
634 minimum. Set to 1.0 or `True` for a jitter approximating
635 Ethernet's time-tested backoff solution. Defaults to `False`.
637 """
638 start = float(start)
639 stop = float(stop)
640 factor = float(factor)
641 if start < 0.0:
642 raise ValueError('expected start >= 0, not %r' % start)
643 if factor < 1.0:
644 raise ValueError('expected factor >= 1.0, not %r' % factor)
645 if stop == 0.0:
646 raise ValueError('expected stop >= 0')
647 if stop < start:
648 raise ValueError('expected stop >= start, not %r' % stop)
649 if count is None:
650 denom = start if start else 1
651 count = 1 + math.ceil(math.log(stop/denom, factor))
652 count = count if start else count + 1
653 if count != 'repeat' and count < 0:
654 raise ValueError('count must be positive or "repeat", not %r' % count)
655 if jitter:
656 jitter = float(jitter)
657 if not (-1.0 <= jitter <= 1.0):
658 raise ValueError('expected jitter -1 <= j <= 1, not: %r' % jitter)
660 cur, i = start, 0
661 while count == 'repeat' or i < count:
662 if not jitter:
663 cur_ret = cur
664 elif jitter:
665 cur_ret = cur - (cur * jitter * random.random())
666 yield cur_ret
667 i += 1
668 if cur == 0:
669 cur = 1
670 elif cur < stop:
671 cur *= factor
672 if cur > stop:
673 cur = stop
674 return
677def bucketize(src, key=bool, value_transform=None, key_filter=None):
678 """Group values in the *src* iterable by the value returned by *key*.
680 >>> bucketize(range(5))
681 {False: [0], True: [1, 2, 3, 4]}
682 >>> is_odd = lambda x: x % 2 == 1
683 >>> bucketize(range(5), is_odd)
684 {False: [0, 2, 4], True: [1, 3]}
686 *key* is :class:`bool` by default, but can either be a callable or a string or a list
687 if it is a string, it is the name of the attribute on which to bucketize objects.
689 >>> bucketize([1+1j, 2+2j, 1, 2], key='real')
690 {1.0: [(1+1j), 1], 2.0: [(2+2j), 2]}
692 if *key* is a list, it contains the buckets where to put each object
694 >>> bucketize([1,2,365,4,98],key=[0,1,2,0,2])
695 {0: [1, 4], 1: [2], 2: [365, 98]}
698 Value lists are not deduplicated:
700 >>> bucketize([None, None, None, 'hello'])
701 {False: [None, None, None], True: ['hello']}
703 Bucketize into more than 3 groups
705 >>> bucketize(range(10), lambda x: x % 3)
706 {0: [0, 3, 6, 9], 1: [1, 4, 7], 2: [2, 5, 8]}
708 ``bucketize`` has a couple of advanced options useful in certain
709 cases. *value_transform* can be used to modify values as they are
710 added to buckets, and *key_filter* will allow excluding certain
711 buckets from being collected.
713 >>> bucketize(range(5), value_transform=lambda x: x*x)
714 {False: [0], True: [1, 4, 9, 16]}
716 >>> bucketize(range(10), key=lambda x: x % 3, key_filter=lambda k: k % 3 != 1)
717 {0: [0, 3, 6, 9], 2: [2, 5, 8]}
719 Note in some of these examples there were at most two keys, ``True`` and
720 ``False``, and each key present has a list with at least one
721 item. See :func:`partition` for a version specialized for binary
722 use cases.
724 """
725 if not is_iterable(src):
726 raise TypeError('expected an iterable')
727 elif isinstance(key, list):
728 if len(key) != len(src):
729 raise ValueError("key and src have to be the same length")
730 src = zip(key, src)
732 if isinstance(key, str):
733 def key_func(x): return getattr(x, key, x)
734 elif callable(key):
735 key_func = key
736 elif isinstance(key, list):
737 def key_func(x): return x[0]
738 else:
739 raise TypeError('expected key to be callable or a string or a list')
741 if value_transform is None:
742 def value_transform(x): return x
743 if not callable(value_transform):
744 raise TypeError('expected callable value transform function')
745 if isinstance(key, list):
746 f = value_transform
747 def value_transform(x): return f(x[1])
749 ret = {}
750 for val in src:
751 key_of_val = key_func(val)
752 if key_filter is None or key_filter(key_of_val):
753 ret.setdefault(key_of_val, []).append(value_transform(val))
754 return ret
757def partition(src, key=bool, *keys):
758 """No relation to :meth:`str.partition`, ``partition`` is like
759 :func:`bucketize`, but for added convenience returns a collection for
760 each predicate passed.
762 ``partition`` now accepts multiple *key* functions and will return
763 ``N + 1`` lists for ``N`` predicates. Each value from *src* is placed
764 into the first list whose predicate evaluates to ``True`` with values
765 that match none of the predicates placed in the last list.
767 >>> nonempty, empty = partition(['', '', 'hi', '', 'bye'])
768 >>> nonempty
769 ['hi', 'bye']
771 *key* defaults to :class:`bool`, but can be carefully overridden to
772 use either a function that returns either ``True`` or ``False`` or
773 a string name of the attribute on which to partition objects.
775 >>> import string
776 >>> is_digit = lambda x: x in string.digits
777 >>> decimal_digits, hexletters = partition(string.hexdigits, is_digit)
778 >>> ''.join(decimal_digits), ''.join(hexletters)
779 ('0123456789', 'abcdefABCDEF')
781 Multiple predicates may be supplied to divide into more buckets:
783 >>> positive, negative, zero = partition(range(-1, 2),
784 ... lambda i: i > 0,
785 ... lambda i: i < 0)
786 >>> positive, negative, zero
787 ([1], [-1], [0])
788 """
789 if not is_iterable(src):
790 raise TypeError('expected an iterable')
792 def _make_key_func(k):
793 if isinstance(k, str):
794 return lambda x, k=k: getattr(x, k, False)
795 if callable(k):
796 return k
797 raise TypeError('expected key to be callable or a string')
799 key_funcs = [_make_key_func(key)] + [_make_key_func(k) for k in keys]
800 parts = [[] for _ in range(len(key_funcs) + 1)]
802 for val in src:
803 for idx, func in enumerate(key_funcs):
804 if func(val):
805 parts[idx].append(val)
806 break
807 else:
808 parts[-1].append(val)
810 return tuple(parts)
813def unique(src, key=None):
814 """``unique()`` returns a list of unique values, as determined by
815 *key*, in the order they first appeared in the input iterable,
816 *src*.
818 >>> ones_n_zeros = '11010110001010010101010'
819 >>> ''.join(unique(ones_n_zeros))
820 '10'
822 See :func:`unique_iter` docs for more details.
823 """
824 return list(unique_iter(src, key))
827def unique_iter(src, key=None):
828 """Yield unique elements from the iterable, *src*, based on *key*,
829 in the order in which they first appeared in *src*.
831 >>> repetitious = [1, 2, 3] * 10
832 >>> list(unique_iter(repetitious))
833 [1, 2, 3]
835 By default, *key* is the object itself, but *key* can either be a
836 callable or, for convenience, a string name of the attribute on
837 which to uniqueify objects, falling back on identity when the
838 attribute is not present.
840 >>> pleasantries = ['hi', 'hello', 'ok', 'bye', 'yes']
841 >>> list(unique_iter(pleasantries, key=lambda x: len(x)))
842 ['hi', 'hello', 'bye']
843 """
844 if not is_iterable(src):
845 raise TypeError('expected an iterable, not %r' % type(src))
846 if key is None:
847 def key_func(x): return x
848 elif callable(key):
849 key_func = key
850 elif isinstance(key, str):
851 def key_func(x): return getattr(x, key, x)
852 else:
853 raise TypeError('"key" expected a string or callable, not %r' % key)
854 seen = set()
855 for i in src:
856 k = key_func(i)
857 if k not in seen:
858 seen.add(k)
859 yield i
860 return
863def redundant(src, key=None, groups=False):
864 """The complement of :func:`unique()`.
866 By default returns non-unique/duplicate values as a list of the
867 *first* redundant value in *src*. Pass ``groups=True`` to get
868 groups of all values with redundancies, ordered by position of the
869 first redundant value. This is useful in conjunction with some
870 normalizing *key* function.
872 >>> redundant([1, 2, 3, 4])
873 []
874 >>> redundant([1, 2, 3, 2, 3, 3, 4])
875 [2, 3]
876 >>> redundant([1, 2, 3, 2, 3, 3, 4], groups=True)
877 [[2, 2], [3, 3, 3]]
879 An example using a *key* function to do case-insensitive
880 redundancy detection.
882 >>> redundant(['hi', 'Hi', 'HI', 'hello'], key=str.lower)
883 ['Hi']
884 >>> redundant(['hi', 'Hi', 'HI', 'hello'], groups=True, key=str.lower)
885 [['hi', 'Hi', 'HI']]
887 *key* should also be used when the values in *src* are not hashable.
889 .. note::
891 This output of this function is designed for reporting
892 duplicates in contexts when a unique input is desired. Due to
893 the grouped return type, there is no streaming equivalent of
894 this function for the time being.
896 """
897 if key is None:
898 pass
899 elif callable(key):
900 key_func = key
901 elif isinstance(key, (str, bytes)):
902 def key_func(x): return getattr(x, key, x)
903 else:
904 raise TypeError('"key" expected a string or callable, not %r' % key)
905 seen = {} # key to first seen item
906 redundant_order = []
907 redundant_groups = {}
908 for i in src:
909 k = key_func(i) if key else i
910 if k not in seen:
911 seen[k] = i
912 else:
913 if k in redundant_groups:
914 if groups:
915 redundant_groups[k].append(i)
916 else:
917 redundant_order.append(k)
918 redundant_groups[k] = [seen[k], i]
919 if not groups:
920 ret = [redundant_groups[k][1] for k in redundant_order]
921 else:
922 ret = [redundant_groups[k] for k in redundant_order]
923 return ret
926def one(src, default=None, key=None):
927 """Along the same lines as builtins, :func:`all` and :func:`any`, and
928 similar to :func:`first`, ``one()`` returns the single object in
929 the given iterable *src* that evaluates to ``True``, as determined
930 by callable *key*. If unset, *key* defaults to :class:`bool`. If
931 no such objects are found, *default* is returned. If *default* is
932 not passed, ``None`` is returned.
934 If *src* has more than one object that evaluates to ``True``, or
935 if there is no object that fulfills such condition, return
936 *default*. It's like an `XOR`_ over an iterable.
938 >>> one((True, False, False))
939 True
940 >>> one((True, False, True))
941 >>> one((0, 0, 'a'))
942 'a'
943 >>> one((0, False, None))
944 >>> one((True, True), default=False)
945 False
946 >>> bool(one(('', 1)))
947 True
948 >>> one((10, 20, 30, 42), key=lambda i: i > 40)
949 42
951 See `Martín Gaitán's original repo`_ for further use cases.
953 .. _Martín Gaitán's original repo: https://github.com/mgaitan/one
954 .. _XOR: https://en.wikipedia.org/wiki/Exclusive_or
956 """
957 ones = list(itertools.islice(filter(key, src), 2))
958 return ones[0] if len(ones) == 1 else default
961def first(iterable, default=None, key=None):
962 """Return first element of *iterable* that evaluates to ``True``, else
963 return ``None`` or optional *default*. Similar to :func:`one`.
965 >>> first([0, False, None, [], (), 42])
966 42
967 >>> first([0, False, None, [], ()]) is None
968 True
969 >>> first([0, False, None, [], ()], default='ohai')
970 'ohai'
971 >>> import re
972 >>> m = first(re.match(regex, 'abc') for regex in ['b.*', 'a(.*)'])
973 >>> m.group(1)
974 'bc'
976 The optional *key* argument specifies a one-argument predicate function
977 like that used for *filter()*. The *key* argument, if supplied, should be
978 in keyword form. For example, finding the first even number in an iterable:
980 >>> first([1, 1, 3, 4, 5], key=lambda x: x % 2 == 0)
981 4
983 Contributed by Hynek Schlawack, author of `the original standalone module`_.
985 .. _the original standalone module: https://github.com/hynek/first
986 """
987 return next(filter(key, iterable), default)
990def flatten_iter(iterable):
991 """``flatten_iter()`` yields all the elements from *iterable* while
992 collapsing any nested iterables.
994 >>> nested = [[1, 2], [[3], [4, 5]]]
995 >>> list(flatten_iter(nested))
996 [1, 2, 3, 4, 5]
997 """
998 for item in iterable:
999 if isinstance(item, Iterable) and not isinstance(item, (str, bytes)):
1000 yield from flatten_iter(item)
1001 else:
1002 yield item
1005def flatten(iterable):
1006 """``flatten()`` returns a collapsed list of all the elements from
1007 *iterable* while collapsing any nested iterables.
1009 >>> nested = [[1, 2], [[3], [4, 5]]]
1010 >>> flatten(nested)
1011 [1, 2, 3, 4, 5]
1012 """
1013 return list(flatten_iter(iterable))
1016def same(iterable, ref=_UNSET):
1017 """``same()`` returns ``True`` when all values in *iterable* are
1018 equal to one another, or optionally a reference value,
1019 *ref*. Similar to :func:`all` and :func:`any` in that it evaluates
1020 an iterable and returns a :class:`bool`. ``same()`` returns
1021 ``True`` for empty iterables.
1023 >>> same([])
1024 True
1025 >>> same([1])
1026 True
1027 >>> same(['a', 'a', 'a'])
1028 True
1029 >>> same(range(20))
1030 False
1031 >>> same([[], []])
1032 True
1033 >>> same([[], []], ref='test')
1034 False
1036 """
1037 iterator = iter(iterable)
1038 if ref is _UNSET:
1039 ref = next(iterator, ref)
1040 return all(val == ref for val in iterator)
1043def default_visit(path, key, value):
1044 # print('visit(%r, %r, %r)' % (path, key, value))
1045 return key, value
1048# enable the extreme: monkeypatching iterutils with a different default_visit
1049_orig_default_visit = default_visit
1052def default_enter(path, key, value):
1053 # print('enter(%r, %r)' % (key, value))
1054 if isinstance(value, (str, bytes)):
1055 return value, False
1056 elif isinstance(value, Mapping):
1057 return value.__class__(), ItemsView(value)
1058 elif isinstance(value, Sequence):
1059 return value.__class__(), enumerate(value)
1060 elif isinstance(value, Set):
1061 return value.__class__(), enumerate(value)
1062 else:
1063 # files, strings, other iterables, and scalars are not
1064 # traversed
1065 return value, False
1068def default_exit(path, key, old_parent, new_parent, new_items):
1069 # print('exit(%r, %r, %r, %r, %r)'
1070 # % (path, key, old_parent, new_parent, new_items))
1071 ret = new_parent
1072 if isinstance(new_parent, Mapping):
1073 new_parent.update(new_items)
1074 elif isinstance(new_parent, Sequence):
1075 vals = [v for i, v in new_items]
1076 try:
1077 new_parent.extend(vals)
1078 except AttributeError:
1079 ret = new_parent.__class__(vals) # tuples
1080 elif isinstance(new_parent, Set):
1081 vals = [v for i, v in new_items]
1082 try:
1083 new_parent.update(vals)
1084 except AttributeError:
1085 ret = new_parent.__class__(vals) # frozensets
1086 else:
1087 raise RuntimeError('unexpected iterable type: %r' % type(new_parent))
1088 return ret
1091def remap(
1092 root,
1093 visit=default_visit,
1094 enter=default_enter,
1095 exit=default_exit,
1096 cache: bool = True,
1097 **kwargs,
1098):
1099 """The remap ("recursive map") function is used to traverse and
1100 transform nested structures. Lists, tuples, sets, and dictionaries
1101 are just a few of the data structures nested into heterogeneous
1102 tree-like structures that are so common in programming.
1103 Unfortunately, Python's built-in ways to manipulate collections
1104 are almost all flat. List comprehensions may be fast and succinct,
1105 but they do not recurse, making it tedious to apply quick changes
1106 or complex transforms to real-world data.
1108 remap goes where list comprehensions cannot.
1110 Here's an example of removing all Nones from some data:
1112 >>> from pprint import pprint
1113 >>> reviews = {'Star Trek': {'TNG': 10, 'DS9': 8.5, 'ENT': None},
1114 ... 'Babylon 5': 6, 'Dr. Who': None}
1115 >>> pprint(remap(reviews, lambda p, k, v: v is not None))
1116 {'Babylon 5': 6, 'Star Trek': {'DS9': 8.5, 'TNG': 10}}
1118 Notice how both Nones have been removed despite the nesting in the
1119 dictionary. Not bad for a one-liner, and that's just the beginning.
1120 See `this remap cookbook`_ for more delicious recipes.
1122 .. _this remap cookbook: http://sedimental.org/remap.html
1124 remap takes four main arguments: the object to traverse and three
1125 optional callables which determine how the remapped object will be
1126 created.
1128 Args:
1130 root: The target object to traverse. By default, remap
1131 supports iterables like :class:`list`, :class:`tuple`,
1132 :class:`dict`, and :class:`set`, but any object traversable by
1133 *enter* will work.
1134 visit (callable): This function is called on every item in
1135 *root*. It must accept three positional arguments, *path*,
1136 *key*, and *value*. *path* is simply a tuple of parents'
1137 keys. *visit* should return the new key-value pair. It may
1138 also return ``True`` as shorthand to keep the old item
1139 unmodified, or ``False`` to drop the item from the new
1140 structure. *visit* is called after *enter*, on the new parent.
1142 The *visit* function is called for every item in root,
1143 including duplicate items. For traversable values, it is
1144 called on the new parent object, after all its children
1145 have been visited. The default visit behavior simply
1146 returns the key-value pair unmodified.
1147 enter (callable): This function controls which items in *root*
1148 are traversed. It accepts the same arguments as *visit*: the
1149 path, the key, and the value of the current item. It returns a
1150 pair of the blank new parent, and an iterator over the items
1151 which should be visited. If ``False`` is returned instead of
1152 an iterator, the value will not be traversed.
1154 The *enter* function is only called once per unique value. The
1155 default enter behavior support mappings, sequences, and
1156 sets. Strings and all other iterables will not be traversed.
1157 exit (callable): This function determines how to handle items
1158 once they have been visited. It gets the same three
1159 arguments as the other functions -- *path*, *key*, *value*
1160 -- plus two more: the blank new parent object returned
1161 from *enter*, and a list of the new items, as remapped by
1162 *visit*.
1164 Like *enter*, the *exit* function is only called once per
1165 unique value. The default exit behavior is to simply add
1166 all new items to the new parent, e.g., using
1167 :meth:`list.extend` and :meth:`dict.update` to add to the
1168 new parent. Immutable objects, such as a :class:`tuple` or
1169 :class:`namedtuple`, must be recreated from scratch, but
1170 use the same type as the new parent passed back from the
1171 *enter* function.
1172 cache (bool): Controls whether to cache transformed
1173 objects. Uses object identity for the cache. For example
1174 this is turned off for applications like `research` which
1175 need to traverse all trees.
1176 reraise_visit (bool): A pragmatic convenience for the *visit*
1177 callable. When set to ``False``, remap ignores any errors
1178 raised by the *visit* callback. Items causing exceptions
1179 are kept. See examples for more details.
1180 trace (bool): Pass ``trace=True`` to print out the entire
1181 traversal. Or pass a tuple of ``'visit'``, ``'enter'``,
1182 or ``'exit'`` to print only the selected events.
1184 remap is designed to cover the majority of cases with just the
1185 *visit* callable. While passing in multiple callables is very
1186 empowering, remap is designed so very few cases should require
1187 passing more than one function.
1189 When passing *enter* and *exit*, it's common and easiest to build
1190 on the default behavior. Simply add ``from boltons.iterutils import
1191 default_enter`` (or ``default_exit``), and have your enter/exit
1192 function call the default behavior before or after your custom
1193 logic. See `this example`_.
1195 Duplicate and self-referential objects (aka reference loops) are
1196 automatically handled internally, `as shown here`_.
1198 .. _this example: http://sedimental.org/remap.html#sort_all_lists
1199 .. _as shown here: http://sedimental.org/remap.html#corner_cases
1201 """
1202 # TODO: improve argument formatting in sphinx doc
1203 # TODO: enter() return (False, items) to continue traverse but cancel copy?
1204 if not callable(visit):
1205 raise TypeError('visit expected callable, not: %r' % visit)
1206 if not callable(enter):
1207 raise TypeError('enter expected callable, not: %r' % enter)
1208 if not callable(exit):
1209 raise TypeError('exit expected callable, not: %r' % exit)
1210 reraise_visit = kwargs.pop('reraise_visit', True)
1211 trace = kwargs.pop('trace', ())
1212 if trace is True:
1213 trace = ('visit', 'enter', 'exit')
1214 elif isinstance(trace, str):
1215 trace = (trace,)
1216 if not isinstance(trace, (tuple, list, set)):
1217 raise TypeError('trace expected tuple of event names, not: %r' % trace)
1218 trace_enter, trace_exit, trace_visit = 'enter' in trace, 'exit' in trace, 'visit' in trace
1220 if kwargs:
1221 raise TypeError('unexpected keyword arguments: %r' % kwargs.keys())
1223 path, registry, stack = (), {}, [(None, root)]
1224 new_items_stack = []
1225 while stack:
1226 key, value = stack.pop()
1227 id_value = id(value)
1228 if key is _REMAP_EXIT:
1229 key, new_parent, old_parent = value
1230 id_value = id(old_parent)
1231 path, new_items = new_items_stack.pop()
1232 if trace_exit:
1233 print(' .. remap exit:', path, '-', key, '-',
1234 old_parent, '-', new_parent, '-', new_items)
1235 value = exit(path, key, old_parent, new_parent, new_items)
1236 if trace_exit:
1237 print(' .. remap exit result:', value)
1238 registry[id_value] = value
1239 if not new_items_stack:
1240 continue
1241 elif cache and id_value in registry:
1242 value = registry[id_value]
1243 else:
1244 if trace_enter:
1245 print(' .. remap enter:', path, '-', key, '-', value)
1246 res = enter(path, key, value)
1247 if trace_enter:
1248 print(' .. remap enter result:', res)
1249 try:
1250 new_parent, new_items = res
1251 except TypeError:
1252 # TODO: handle False?
1253 raise TypeError('enter should return a tuple of (new_parent,'
1254 ' items_iterator), not: %r' % res)
1255 if new_items is not False:
1256 # traverse unless False is explicitly passed
1257 registry[id_value] = new_parent
1258 new_items_stack.append((path, []))
1259 if value is not root:
1260 path += (key,)
1261 stack.append((_REMAP_EXIT, (key, new_parent, value)))
1262 if new_items:
1263 stack.extend(reversed(list(new_items)))
1264 if trace_enter:
1265 print(' .. remap stack size now:', len(stack))
1266 continue
1267 if visit is _orig_default_visit:
1268 # avoid function call overhead by inlining identity operation
1269 visited_item = (key, value)
1270 else:
1271 try:
1272 if trace_visit:
1273 print(' .. remap visit:', path, '-', key, '-', value)
1274 visited_item = visit(path, key, value)
1275 except Exception:
1276 if reraise_visit:
1277 raise
1278 visited_item = True
1279 if visited_item is False:
1280 if trace_visit:
1281 print(' .. remap visit result: <drop>')
1282 continue # drop
1283 elif visited_item is True:
1284 visited_item = (key, value)
1285 if trace_visit:
1286 print(' .. remap visit result:', visited_item)
1287 # TODO: typecheck?
1288 # raise TypeError('expected (key, value) from visit(),'
1289 # ' not: %r' % visited_item)
1290 try:
1291 new_items_stack[-1][1].append(visited_item)
1292 except IndexError:
1293 raise TypeError('expected remappable root, not: %r' % root)
1294 return value
1297class PathAccessError(KeyError, IndexError, TypeError):
1298 """An amalgamation of KeyError, IndexError, and TypeError,
1299 representing what can occur when looking up a path in a nested
1300 object.
1301 """
1303 def __init__(self, exc, seg, path):
1304 self.exc = exc
1305 self.seg = seg
1306 self.path = path
1308 def __repr__(self):
1309 cn = self.__class__.__name__
1310 return f'{cn}({self.exc!r}, {self.seg!r}, {self.path!r})'
1312 def __str__(self):
1313 return ('could not access %r from path %r, got error: %r'
1314 % (self.seg, self.path, self.exc))
1317def get_path(root, path, default=_UNSET):
1318 """Retrieve a value from a nested object via a tuple representing the
1319 lookup path.
1321 >>> root = {'a': {'b': {'c': [[1], [2], [3]]}}}
1322 >>> get_path(root, ('a', 'b', 'c', 2, 0))
1323 3
1325 The path tuple format is intentionally consistent with that of
1326 :func:`remap`, but a single dotted string can also be passed.
1328 One of get_path's chief aims is improved error messaging. EAFP is
1329 great, but the error messages are not.
1331 For instance, ``root['a']['b']['c'][2][1]`` gives back
1332 ``IndexError: list index out of range``
1334 What went out of range where? get_path currently raises
1335 ``PathAccessError: could not access 2 from path ('a', 'b', 'c', 2,
1336 1), got error: IndexError('list index out of range',)``, a
1337 subclass of IndexError and KeyError.
1339 You can also pass a default that covers the entire operation,
1340 should the lookup fail at any level.
1342 Args:
1343 root: The target nesting of dictionaries, lists, or other
1344 objects supporting ``__getitem__``.
1345 path (tuple): A sequence of strings and integers to be successively
1346 looked up within *root*. A dot-separated (``a.b``) string may
1347 also be passed.
1348 default: The value to be returned should any
1349 ``PathAccessError`` exceptions be raised.
1350 """
1351 if isinstance(path, str):
1352 path = path.split('.')
1353 cur = root
1354 try:
1355 for seg in path:
1356 try:
1357 cur = cur[seg]
1358 except (KeyError, IndexError) as exc:
1359 raise PathAccessError(exc, seg, path)
1360 except TypeError as exc:
1361 # either string index in a list, or a parent that
1362 # doesn't support indexing
1363 try:
1364 seg = int(seg)
1365 cur = cur[seg]
1366 except (ValueError, KeyError, IndexError, TypeError):
1367 if not is_iterable(cur):
1368 exc = TypeError('%r object is not indexable'
1369 % type(cur).__name__)
1370 raise PathAccessError(exc, seg, path)
1371 except PathAccessError:
1372 if default is _UNSET:
1373 raise
1374 return default
1375 return cur
1378def research(root, query=lambda p, k, v: True, reraise=False, enter=default_enter):
1379 """The :func:`research` function uses :func:`remap` to recurse over
1380 any data nested in *root*, and find values which match a given
1381 criterion, specified by the *query* callable.
1383 Results are returned as a list of ``(path, value)`` pairs. The
1384 paths are tuples in the same format accepted by
1385 :func:`get_path`. This can be useful for comparing values nested
1386 in two or more different structures.
1388 Here's a simple example that finds all integers:
1390 >>> root = {'a': {'b': 1, 'c': (2, 'd', 3)}, 'e': None}
1391 >>> res = research(root, query=lambda p, k, v: isinstance(v, int))
1392 >>> print(sorted(res))
1393 [(('a', 'b'), 1), (('a', 'c', 0), 2), (('a', 'c', 2), 3)]
1395 Note how *query* follows the same, familiar ``path, key, value``
1396 signature as the ``visit`` and ``enter`` functions on
1397 :func:`remap`, and returns a :class:`bool`.
1399 Args:
1400 root: The target object to search. Supports the same types of
1401 objects as :func:`remap`, including :class:`list`,
1402 :class:`tuple`, :class:`dict`, and :class:`set`.
1403 query (callable): The function called on every object to
1404 determine whether to include it in the search results. The
1405 callable must accept three arguments, *path*, *key*, and
1406 *value*, commonly abbreviated *p*, *k*, and *v*, same as
1407 *enter* and *visit* from :func:`remap`.
1408 reraise (bool): Whether to reraise exceptions raised by *query*
1409 or to simply drop the result that caused the error.
1412 With :func:`research` it's easy to inspect the details of a data
1413 structure, like finding values that are at a certain depth (using
1414 ``len(p)``) and much more. If more advanced functionality is
1415 needed, check out the code and make your own :func:`remap`
1416 wrapper, and consider `submitting a patch`_!
1418 .. _submitting a patch: https://github.com/mahmoud/boltons/pulls
1419 """
1420 ret = []
1422 if not callable(query):
1423 raise TypeError('query expected callable, not: %r' % query)
1425 def _enter(path, key, value):
1426 try:
1427 if query(path, key, value):
1428 ret.append((path + (key,), value))
1429 except Exception:
1430 if reraise:
1431 raise
1432 return enter(path, key, value)
1434 remap(root, enter=_enter, cache=False)
1435 return ret
1438# TODO: recollect()
1439# TODO: refilter()
1440# TODO: reiter()
1443# GUID iterators: 10x faster and somewhat more compact than uuid.
1445class GUIDerator:
1446 """The GUIDerator is an iterator that yields a globally-unique
1447 identifier (GUID) on every iteration. The GUIDs produced are
1448 hexadecimal strings.
1450 Testing shows it to be around 12x faster than the uuid module. By
1451 default it is also more compact, partly due to its default 96-bit
1452 (24-hexdigit) length. 96 bits of randomness means that there is a
1453 1 in 2 ^ 32 chance of collision after 2 ^ 64 iterations. If more
1454 or less uniqueness is desired, the *size* argument can be adjusted
1455 accordingly.
1457 Args:
1458 size (int): character length of the GUID, defaults to 24. Lengths
1459 between 20 and 36 are considered valid.
1461 The GUIDerator has built-in fork protection that causes it to
1462 detect a fork on next iteration and reseed accordingly.
1464 """
1466 def __init__(self, size=24):
1467 self.size = size
1468 if size < 20 or size > 36:
1469 raise ValueError('expected 20 < size <= 36')
1470 import hashlib
1471 self._sha1 = hashlib.sha1
1472 self.count = itertools.count()
1473 self.reseed()
1475 def reseed(self):
1476 import socket
1477 self.pid = os.getpid()
1478 self.salt = '-'.join([str(self.pid),
1479 socket.gethostname() or '<nohostname>',
1480 str(time.time()),
1481 os.urandom(6).hex()])
1482 return
1484 def __iter__(self):
1485 return self
1487 def __next__(self):
1488 if os.getpid() != self.pid:
1489 self.reseed()
1490 target_bytes = (self.salt + str(next(self.count))).encode('utf8')
1491 hash_text = self._sha1(target_bytes).hexdigest()[:self.size]
1492 return hash_text
1494 next = __next__
1497class SequentialGUIDerator(GUIDerator):
1498 """Much like the standard GUIDerator, the SequentialGUIDerator is an
1499 iterator that yields a globally-unique identifier (GUID) on every
1500 iteration. The GUIDs produced are hexadecimal strings.
1502 The SequentialGUIDerator differs in that it picks a starting GUID
1503 value and increments every iteration. This yields GUIDs which are
1504 of course unique, but also ordered and lexicographically sortable.
1506 The SequentialGUIDerator is around 50% faster than the normal
1507 GUIDerator, making it almost 20x as fast as the built-in uuid
1508 module. By default it is also more compact, partly due to its
1509 96-bit (24-hexdigit) default length. 96 bits of randomness means that
1510 there is a 1 in 2 ^ 32 chance of collision after 2 ^ 64
1511 iterations. If more or less uniqueness is desired, the *size*
1512 argument can be adjusted accordingly.
1514 Args:
1515 size (int): character length of the GUID, defaults to 24.
1517 Note that with SequentialGUIDerator there is a chance of GUIDs
1518 growing larger than the size configured. The SequentialGUIDerator
1519 has built-in fork protection that causes it to detect a fork on
1520 next iteration and reseed accordingly.
1522 """
1524 def reseed(self):
1525 super().reseed()
1526 start_str = self._sha1(self.salt.encode('utf8')).hexdigest()
1527 self.start = int(start_str[:self.size], 16)
1528 self.start |= (1 << ((self.size * 4) - 2))
1530 def __next__(self):
1531 if os.getpid() != self.pid:
1532 self.reseed()
1533 return '%x' % (next(self.count) + self.start)
1535 next = __next__
1538guid_iter = GUIDerator()
1539seq_guid_iter = SequentialGUIDerator()
1542def soft_sorted(iterable, first=None, last=None, key=None, reverse=False):
1543 """For when you care about the order of some elements, but not about
1544 others.
1546 Use this to float to the top and/or sink to the bottom a specific
1547 ordering, while sorting the rest of the elements according to
1548 normal :func:`sorted` rules.
1550 >>> soft_sorted(['two', 'b', 'one', 'a'], first=['one', 'two'])
1551 ['one', 'two', 'a', 'b']
1552 >>> soft_sorted(range(7), first=[6, 15], last=[2, 4], reverse=True)
1553 [6, 5, 3, 1, 0, 2, 4]
1554 >>> import string
1555 >>> ''.join(soft_sorted(string.hexdigits, first='za1', last='b', key=str.lower))
1556 'aA1023456789cCdDeEfFbB'
1558 Args:
1559 iterable (list): A list or other iterable to sort.
1560 first (list): A sequence to enforce for elements which should
1561 appear at the beginning of the returned list.
1562 last (list): A sequence to enforce for elements which should
1563 appear at the end of the returned list.
1564 key (callable): Callable used to generate a comparable key for
1565 each item to be sorted, same as the key in
1566 :func:`sorted`. Note that entries in *first* and *last*
1567 should be the keys for the items. Defaults to
1568 passthrough/the identity function.
1569 reverse (bool): Whether or not elements not explicitly ordered
1570 by *first* and *last* should be in reverse order or not.
1572 Returns a new list in sorted order.
1573 """
1574 first = first or []
1575 last = last or []
1576 key = key or (lambda x: x)
1577 seq = list(iterable)
1578 other = [x for x in seq if not (
1579 (first and key(x) in first) or (last and key(x) in last))]
1580 other.sort(key=key, reverse=reverse)
1582 if first:
1583 first = sorted([x for x in seq if key(x) in first],
1584 key=lambda x: first.index(key(x)))
1585 if last:
1586 last = sorted([x for x in seq if key(x) in last],
1587 key=lambda x: last.index(key(x)))
1588 return first + other + last
1591def untyped_sorted(iterable, key=None, reverse=False):
1592 """A version of :func:`sorted` which will happily sort an iterable of
1593 heterogeneous types and return a new list, similar to legacy Python's
1594 behavior.
1596 >>> untyped_sorted(['abc', 2.0, 1, 2, 'def'])
1597 [1, 2.0, 2, 'abc', 'def']
1599 Note how mutually orderable types are sorted as expected, as in
1600 the case of the integers and floats above.
1602 .. note::
1604 Results may vary across Python versions and builds, but the
1605 function will produce a sorted list, except in the case of
1606 explicitly unorderable objects.
1608 """
1609 class _Wrapper:
1610 slots = ('obj',)
1612 def __init__(self, obj):
1613 self.obj = obj
1615 def __lt__(self, other):
1616 obj = key(self.obj) if key is not None else self.obj
1617 other = key(other.obj) if key is not None else other.obj
1618 try:
1619 ret = obj < other
1620 except TypeError:
1621 ret = ((type(obj).__name__, id(type(obj)), obj)
1622 < (type(other).__name__, id(type(other)), other))
1623 return ret
1625 if key is not None and not callable(key):
1626 raise TypeError('expected function or callable object for key, not: %r'
1627 % key)
1629 return sorted(iterable, key=_Wrapper, reverse=reverse)
1632"""
1633May actually be faster to do an isinstance check for a str path
1635$ python -m timeit -s "x = [1]" "x[0]"
163610000000 loops, best of 3: 0.0207 usec per loop
1637$ python -m timeit -s "x = [1]" "try: x[0] \nexcept: pass"
163810000000 loops, best of 3: 0.029 usec per loop
1639$ python -m timeit -s "x = [1]" "try: x[1] \nexcept: pass"
16401000000 loops, best of 3: 0.315 usec per loop
1641# setting up try/except is fast, only around 0.01us
1642# actually triggering the exception takes almost 10x as long
1644$ python -m timeit -s "x = [1]" "isinstance(x, basestring)"
164510000000 loops, best of 3: 0.141 usec per loop
1646$ python -m timeit -s "x = [1]" "isinstance(x, str)"
164710000000 loops, best of 3: 0.131 usec per loop
1648$ python -m timeit -s "x = [1]" "try: x.split('.')\n except: pass"
16491000000 loops, best of 3: 0.443 usec per loop
1650$ python -m timeit -s "x = [1]" "try: x.split('.') \nexcept AttributeError: pass"
16511000000 loops, best of 3: 0.544 usec per loop
1652"""