Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/boltons/iterutils.py: 22%
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 count = int(math.ceil((stop - start) / step))
530 cur = start
531 for _ in range(count):
532 yield cur
533 cur += step
536def frange(stop, start=None, step=1.0):
537 """A :func:`range` clone for float-based ranges.
539 >>> frange(5)
540 [0.0, 1.0, 2.0, 3.0, 4.0]
541 >>> frange(6, step=1.25)
542 [0.0, 1.25, 2.5, 3.75, 5.0]
543 >>> frange(100.5, 101.5, 0.25)
544 [100.5, 100.75, 101.0, 101.25]
545 >>> frange(5, 0)
546 []
547 >>> frange(5, 0, step=-1.25)
548 [5.0, 3.75, 2.5, 1.25]
549 """
550 if not step:
551 raise ValueError('step must be non-zero')
552 if start is None:
553 start, stop = 0.0, stop * 1.0
554 else:
555 # swap when all args are used
556 stop, start = start * 1.0, stop * 1.0
557 count = int(math.ceil((stop - start) / step))
558 ret = [None] * count
559 if not ret:
560 return ret
561 ret[0] = start
562 for i in range(1, count):
563 ret[i] = ret[i - 1] + step
564 return ret
567def backoff(start, stop, count=None, factor=2.0, jitter=False):
568 """Returns a list of geometrically-increasing floating-point numbers,
569 suitable for usage with `exponential backoff`_. Exactly like
570 :func:`backoff_iter`, but without the ``'repeat'`` option for
571 *count*. See :func:`backoff_iter` for more details.
573 .. _exponential backoff: https://en.wikipedia.org/wiki/Exponential_backoff
575 >>> backoff(1, 10)
576 [1.0, 2.0, 4.0, 8.0, 10.0]
577 """
578 if count == 'repeat':
579 raise ValueError("'repeat' supported in backoff_iter, not backoff")
580 return list(backoff_iter(start, stop, count=count,
581 factor=factor, jitter=jitter))
584def backoff_iter(start, stop, count=None, factor=2.0, jitter=False):
585 """Generates a sequence of geometrically-increasing floats, suitable
586 for usage with `exponential backoff`_. Starts with *start*,
587 increasing by *factor* until *stop* is reached, optionally
588 stopping iteration once *count* numbers are yielded. *factor*
589 defaults to 2. In general retrying with properly-configured
590 backoff creates a better-behaved component for a larger service
591 ecosystem.
593 .. _exponential backoff: https://en.wikipedia.org/wiki/Exponential_backoff
595 >>> list(backoff_iter(1.0, 10.0, count=5))
596 [1.0, 2.0, 4.0, 8.0, 10.0]
597 >>> list(backoff_iter(1.0, 10.0, count=8))
598 [1.0, 2.0, 4.0, 8.0, 10.0, 10.0, 10.0, 10.0]
599 >>> list(backoff_iter(0.25, 100.0, factor=10))
600 [0.25, 2.5, 25.0, 100.0]
602 A simplified usage example:
604 .. code-block:: python
606 for timeout in backoff_iter(0.25, 5.0):
607 try:
608 res = network_call()
609 break
610 except Exception as e:
611 log(e)
612 time.sleep(timeout)
614 An enhancement for large-scale systems would be to add variation,
615 or *jitter*, to timeout values. This is done to avoid a thundering
616 herd on the receiving end of the network call.
618 Finally, for *count*, the special value ``'repeat'`` can be passed to
619 continue yielding indefinitely.
621 Args:
623 start (float): Positive number for baseline.
624 stop (float): Positive number for maximum.
625 count (int): Number of steps before stopping
626 iteration. Defaults to the number of steps between *start* and
627 *stop*. Pass the string, `'repeat'`, to continue iteration
628 indefinitely.
629 factor (float): Rate of exponential increase. Defaults to `2.0`,
630 e.g., `[1, 2, 4, 8, 16]`.
631 jitter (float): A factor between `-1.0` and `1.0`, used to
632 uniformly randomize and thus spread out timeouts in a distributed
633 system, avoiding rhythm effects. Positive values use the base
634 backoff curve as a maximum, negative values use the curve as a
635 minimum. Set to 1.0 or `True` for a jitter approximating
636 Ethernet's time-tested backoff solution. Defaults to `False`.
638 """
639 start = float(start)
640 stop = float(stop)
641 factor = float(factor)
642 if start < 0.0:
643 raise ValueError('expected start >= 0, not %r' % start)
644 if factor < 1.0:
645 raise ValueError('expected factor >= 1.0, not %r' % factor)
646 if stop == 0.0:
647 raise ValueError('expected stop >= 0')
648 if stop < start:
649 raise ValueError('expected stop >= start, not %r' % stop)
650 if count is None:
651 denom = start if start else 1
652 if factor == 1.0:
653 if start != stop:
654 raise ValueError('expected factor > 1.0 when count is None'
655 ' and start != stop, not %r' % factor)
656 count = 1
657 else:
658 count = 1 + math.ceil(math.log(stop/denom, factor))
659 count = count if start else count + 1
660 if count != 'repeat' and count < 0:
661 raise ValueError('count must be positive or "repeat", not %r' % count)
662 if jitter:
663 jitter = float(jitter)
664 if not (-1.0 <= jitter <= 1.0):
665 raise ValueError('expected jitter -1 <= j <= 1, not: %r' % jitter)
667 cur, i = start, 0
668 while count == 'repeat' or i < count:
669 if not jitter:
670 cur_ret = cur
671 elif jitter:
672 cur_ret = cur - (cur * jitter * random.random())
673 yield cur_ret
674 i += 1
675 if cur == 0:
676 cur = 1
677 elif cur < stop:
678 cur *= factor
679 if cur > stop:
680 cur = stop
681 return
684def bucketize(src, key=bool, value_transform=None, key_filter=None):
685 """Group values in the *src* iterable by the value returned by *key*.
687 >>> bucketize(range(5))
688 {False: [0], True: [1, 2, 3, 4]}
689 >>> is_odd = lambda x: x % 2 == 1
690 >>> bucketize(range(5), is_odd)
691 {False: [0, 2, 4], True: [1, 3]}
693 *key* is :class:`bool` by default, but can either be a callable or a string or a list
694 if it is a string, it is the name of the attribute on which to bucketize objects.
696 >>> bucketize([1+1j, 2+2j, 1, 2], key='real')
697 {1.0: [(1+1j), 1], 2.0: [(2+2j), 2]}
699 if *key* is a list, it contains the buckets where to put each object
701 >>> bucketize([1,2,365,4,98],key=[0,1,2,0,2])
702 {0: [1, 4], 1: [2], 2: [365, 98]}
705 Value lists are not deduplicated:
707 >>> bucketize([None, None, None, 'hello'])
708 {False: [None, None, None], True: ['hello']}
710 Bucketize into more than 3 groups
712 >>> bucketize(range(10), lambda x: x % 3)
713 {0: [0, 3, 6, 9], 1: [1, 4, 7], 2: [2, 5, 8]}
715 ``bucketize`` has a couple of advanced options useful in certain
716 cases. *value_transform* can be used to modify values as they are
717 added to buckets, and *key_filter* will allow excluding certain
718 buckets from being collected.
720 >>> bucketize(range(5), value_transform=lambda x: x*x)
721 {False: [0], True: [1, 4, 9, 16]}
723 >>> bucketize(range(10), key=lambda x: x % 3, key_filter=lambda k: k % 3 != 1)
724 {0: [0, 3, 6, 9], 2: [2, 5, 8]}
726 Note in some of these examples there were at most two keys, ``True`` and
727 ``False``, and each key present has a list with at least one
728 item. See :func:`partition` for a version specialized for binary
729 use cases.
731 """
732 if not is_iterable(src):
733 raise TypeError('expected an iterable')
734 elif isinstance(key, list):
735 if len(key) != len(src):
736 raise ValueError("key and src have to be the same length")
737 src = zip(key, src)
739 if isinstance(key, str):
740 def key_func(x): return getattr(x, key, x)
741 elif callable(key):
742 key_func = key
743 elif isinstance(key, list):
744 def key_func(x): return x[0]
745 else:
746 raise TypeError('expected key to be callable or a string or a list')
748 if value_transform is None:
749 def value_transform(x): return x
750 if not callable(value_transform):
751 raise TypeError('expected callable value transform function')
752 if isinstance(key, list):
753 f = value_transform
754 def value_transform(x): return f(x[1])
756 ret = {}
757 for val in src:
758 key_of_val = key_func(val)
759 if key_filter is None or key_filter(key_of_val):
760 ret.setdefault(key_of_val, []).append(value_transform(val))
761 return ret
764def partition(src, key=bool, *keys):
765 """No relation to :meth:`str.partition`, ``partition`` is like
766 :func:`bucketize`, but for added convenience returns a collection for
767 each predicate passed.
769 ``partition`` now accepts multiple *key* functions and will return
770 ``N + 1`` lists for ``N`` predicates. Each value from *src* is placed
771 into the first list whose predicate evaluates to ``True`` with values
772 that match none of the predicates placed in the last list.
774 >>> nonempty, empty = partition(['', '', 'hi', '', 'bye'])
775 >>> nonempty
776 ['hi', 'bye']
778 *key* defaults to :class:`bool`, but can be carefully overridden to
779 use either a function that returns either ``True`` or ``False`` or
780 a string name of the attribute on which to partition objects.
782 >>> import string
783 >>> is_digit = lambda x: x in string.digits
784 >>> decimal_digits, hexletters = partition(string.hexdigits, is_digit)
785 >>> ''.join(decimal_digits), ''.join(hexletters)
786 ('0123456789', 'abcdefABCDEF')
788 Multiple predicates may be supplied to divide into more buckets:
790 >>> positive, negative, zero = partition(range(-1, 2),
791 ... lambda i: i > 0,
792 ... lambda i: i < 0)
793 >>> positive, negative, zero
794 ([1], [-1], [0])
795 """
796 if not is_iterable(src):
797 raise TypeError('expected an iterable')
799 def _make_key_func(k):
800 if isinstance(k, str):
801 return lambda x, k=k: getattr(x, k, False)
802 if callable(k):
803 return k
804 raise TypeError('expected key to be callable or a string')
806 key_funcs = [_make_key_func(key)] + [_make_key_func(k) for k in keys]
807 parts = [[] for _ in range(len(key_funcs) + 1)]
809 for val in src:
810 for idx, func in enumerate(key_funcs):
811 if func(val):
812 parts[idx].append(val)
813 break
814 else:
815 parts[-1].append(val)
817 return tuple(parts)
820def unique(src, key=None):
821 """``unique()`` returns a list of unique values, as determined by
822 *key*, in the order they first appeared in the input iterable,
823 *src*.
825 >>> ones_n_zeros = '11010110001010010101010'
826 >>> ''.join(unique(ones_n_zeros))
827 '10'
829 See :func:`unique_iter` docs for more details.
830 """
831 return list(unique_iter(src, key))
834def unique_iter(src, key=None):
835 """Yield unique elements from the iterable, *src*, based on *key*,
836 in the order in which they first appeared in *src*.
838 >>> repetitious = [1, 2, 3] * 10
839 >>> list(unique_iter(repetitious))
840 [1, 2, 3]
842 By default, *key* is the object itself, but *key* can either be a
843 callable or, for convenience, a string name of the attribute on
844 which to uniqueify objects, falling back on identity when the
845 attribute is not present.
847 >>> pleasantries = ['hi', 'hello', 'ok', 'bye', 'yes']
848 >>> list(unique_iter(pleasantries, key=lambda x: len(x)))
849 ['hi', 'hello', 'bye']
850 """
851 if not is_iterable(src):
852 raise TypeError('expected an iterable, not %r' % type(src))
853 if key is None:
854 def key_func(x): return x
855 elif callable(key):
856 key_func = key
857 elif isinstance(key, str):
858 def key_func(x): return getattr(x, key, x)
859 else:
860 raise TypeError('"key" expected a string or callable, not %r' % key)
861 seen = set()
862 for i in src:
863 k = key_func(i)
864 if k not in seen:
865 seen.add(k)
866 yield i
867 return
870def redundant(src, key=None, groups=False):
871 """The complement of :func:`unique()`.
873 By default returns non-unique/duplicate values as a list of the
874 *first* redundant value in *src*. Pass ``groups=True`` to get
875 groups of all values with redundancies, ordered by position of the
876 first redundant value. This is useful in conjunction with some
877 normalizing *key* function.
879 >>> redundant([1, 2, 3, 4])
880 []
881 >>> redundant([1, 2, 3, 2, 3, 3, 4])
882 [2, 3]
883 >>> redundant([1, 2, 3, 2, 3, 3, 4], groups=True)
884 [[2, 2], [3, 3, 3]]
886 An example using a *key* function to do case-insensitive
887 redundancy detection.
889 >>> redundant(['hi', 'Hi', 'HI', 'hello'], key=str.lower)
890 ['Hi']
891 >>> redundant(['hi', 'Hi', 'HI', 'hello'], groups=True, key=str.lower)
892 [['hi', 'Hi', 'HI']]
894 *key* should also be used when the values in *src* are not hashable.
896 .. note::
898 This output of this function is designed for reporting
899 duplicates in contexts when a unique input is desired. Due to
900 the grouped return type, there is no streaming equivalent of
901 this function for the time being.
903 """
904 if key is None:
905 pass
906 elif callable(key):
907 key_func = key
908 elif isinstance(key, (str, bytes)):
909 def key_func(x): return getattr(x, key, x)
910 else:
911 raise TypeError('"key" expected a string or callable, not %r' % key)
912 seen = {} # key to first seen item
913 redundant_order = []
914 redundant_groups = {}
915 for i in src:
916 k = key_func(i) if key else i
917 if k not in seen:
918 seen[k] = i
919 else:
920 if k in redundant_groups:
921 if groups:
922 redundant_groups[k].append(i)
923 else:
924 redundant_order.append(k)
925 redundant_groups[k] = [seen[k], i]
926 if not groups:
927 ret = [redundant_groups[k][1] for k in redundant_order]
928 else:
929 ret = [redundant_groups[k] for k in redundant_order]
930 return ret
933def one(src, default=None, key=None):
934 """Along the same lines as builtins, :func:`all` and :func:`any`, and
935 similar to :func:`first`, ``one()`` returns the single object in
936 the given iterable *src* that evaluates to ``True``, as determined
937 by callable *key*. If unset, *key* defaults to :class:`bool`. If
938 no such objects are found, *default* is returned. If *default* is
939 not passed, ``None`` is returned.
941 If *src* has more than one object that evaluates to ``True``, or
942 if there is no object that fulfills such condition, return
943 *default*. It's like an `XOR`_ over an iterable.
945 >>> one((True, False, False))
946 True
947 >>> one((True, False, True))
948 >>> one((0, 0, 'a'))
949 'a'
950 >>> one((0, False, None))
951 >>> one((True, True), default=False)
952 False
953 >>> bool(one(('', 1)))
954 True
955 >>> one((10, 20, 30, 42), key=lambda i: i > 40)
956 42
958 See `Martín Gaitán's original repo`_ for further use cases.
960 .. _Martín Gaitán's original repo: https://github.com/mgaitan/one
961 .. _XOR: https://en.wikipedia.org/wiki/Exclusive_or
963 """
964 ones = list(itertools.islice(filter(key, src), 2))
965 return ones[0] if len(ones) == 1 else default
968def first(iterable, default=None, key=None):
969 """Return first element of *iterable* that evaluates to ``True``, else
970 return ``None`` or optional *default*. Similar to :func:`one`.
972 >>> first([0, False, None, [], (), 42])
973 42
974 >>> first([0, False, None, [], ()]) is None
975 True
976 >>> first([0, False, None, [], ()], default='ohai')
977 'ohai'
978 >>> import re
979 >>> m = first(re.match(regex, 'abc') for regex in ['b.*', 'a(.*)'])
980 >>> m.group(1)
981 'bc'
983 The optional *key* argument specifies a one-argument predicate function
984 like that used for *filter()*. The *key* argument, if supplied, should be
985 in keyword form. For example, finding the first even number in an iterable:
987 >>> first([1, 1, 3, 4, 5], key=lambda x: x % 2 == 0)
988 4
990 Contributed by Hynek Schlawack, author of `the original standalone module`_.
992 .. _the original standalone module: https://github.com/hynek/first
993 """
994 return next(filter(key, iterable), default)
997def flatten_iter(iterable):
998 """``flatten_iter()`` yields all the elements from *iterable* while
999 collapsing any nested iterables.
1001 >>> nested = [[1, 2], [[3], [4, 5]]]
1002 >>> list(flatten_iter(nested))
1003 [1, 2, 3, 4, 5]
1004 """
1005 for item in iterable:
1006 if isinstance(item, Iterable) and not isinstance(item, (str, bytes)):
1007 yield from flatten_iter(item)
1008 else:
1009 yield item
1012def flatten(iterable):
1013 """``flatten()`` returns a collapsed list of all the elements from
1014 *iterable* while collapsing any nested iterables.
1016 >>> nested = [[1, 2], [[3], [4, 5]]]
1017 >>> flatten(nested)
1018 [1, 2, 3, 4, 5]
1019 """
1020 return list(flatten_iter(iterable))
1023def same(iterable, ref=_UNSET):
1024 """``same()`` returns ``True`` when all values in *iterable* are
1025 equal to one another, or optionally a reference value,
1026 *ref*. Similar to :func:`all` and :func:`any` in that it evaluates
1027 an iterable and returns a :class:`bool`. ``same()`` returns
1028 ``True`` for empty iterables.
1030 >>> same([])
1031 True
1032 >>> same([1])
1033 True
1034 >>> same(['a', 'a', 'a'])
1035 True
1036 >>> same(range(20))
1037 False
1038 >>> same([[], []])
1039 True
1040 >>> same([[], []], ref='test')
1041 False
1043 """
1044 iterator = iter(iterable)
1045 if ref is _UNSET:
1046 ref = next(iterator, ref)
1047 return all(val == ref for val in iterator)
1050def default_visit(path, key, value):
1051 # print('visit(%r, %r, %r)' % (path, key, value))
1052 return key, value
1055# enable the extreme: monkeypatching iterutils with a different default_visit
1056_orig_default_visit = default_visit
1059def default_enter(path, key, value):
1060 # print('enter(%r, %r)' % (key, value))
1061 if isinstance(value, (str, bytes)):
1062 return value, False
1063 elif isinstance(value, Mapping):
1064 return value.__class__(), ItemsView(value)
1065 elif isinstance(value, Sequence):
1066 return value.__class__(), enumerate(value)
1067 elif isinstance(value, Set):
1068 return value.__class__(), enumerate(value)
1069 else:
1070 # files, strings, other iterables, and scalars are not
1071 # traversed
1072 return value, False
1075def default_exit(path, key, old_parent, new_parent, new_items):
1076 # print('exit(%r, %r, %r, %r, %r)'
1077 # % (path, key, old_parent, new_parent, new_items))
1078 ret = new_parent
1079 if isinstance(new_parent, Mapping):
1080 new_parent.update(new_items)
1081 elif isinstance(new_parent, Sequence):
1082 vals = [v for i, v in new_items]
1083 try:
1084 new_parent.extend(vals)
1085 except AttributeError:
1086 ret = new_parent.__class__(vals) # tuples
1087 elif isinstance(new_parent, Set):
1088 vals = [v for i, v in new_items]
1089 try:
1090 new_parent.update(vals)
1091 except AttributeError:
1092 ret = new_parent.__class__(vals) # frozensets
1093 else:
1094 raise RuntimeError('unexpected iterable type: %r' % type(new_parent))
1095 return ret
1098def remap(
1099 root,
1100 visit=default_visit,
1101 enter=default_enter,
1102 exit=default_exit,
1103 cache: bool = True,
1104 **kwargs,
1105):
1106 """The remap ("recursive map") function is used to traverse and
1107 transform nested structures. Lists, tuples, sets, and dictionaries
1108 are just a few of the data structures nested into heterogeneous
1109 tree-like structures that are so common in programming.
1110 Unfortunately, Python's built-in ways to manipulate collections
1111 are almost all flat. List comprehensions may be fast and succinct,
1112 but they do not recurse, making it tedious to apply quick changes
1113 or complex transforms to real-world data.
1115 remap goes where list comprehensions cannot.
1117 Here's an example of removing all Nones from some data:
1119 >>> from pprint import pprint
1120 >>> reviews = {'Star Trek': {'TNG': 10, 'DS9': 8.5, 'ENT': None},
1121 ... 'Babylon 5': 6, 'Dr. Who': None}
1122 >>> pprint(remap(reviews, lambda p, k, v: v is not None))
1123 {'Babylon 5': 6, 'Star Trek': {'DS9': 8.5, 'TNG': 10}}
1125 Notice how both Nones have been removed despite the nesting in the
1126 dictionary. Not bad for a one-liner, and that's just the beginning.
1127 See `this remap cookbook`_ for more delicious recipes.
1129 .. _this remap cookbook: http://sedimental.org/remap.html
1131 remap takes four main arguments: the object to traverse and three
1132 optional callables which determine how the remapped object will be
1133 created.
1135 Args:
1137 root: The target object to traverse. By default, remap
1138 supports iterables like :class:`list`, :class:`tuple`,
1139 :class:`dict`, and :class:`set`, but any object traversable by
1140 *enter* will work.
1141 visit (callable): This function is called on every item in
1142 *root*. It must accept three positional arguments, *path*,
1143 *key*, and *value*. *path* is simply a tuple of parents'
1144 keys. *visit* should return the new key-value pair. It may
1145 also return ``True`` as shorthand to keep the old item
1146 unmodified, or ``False`` to drop the item from the new
1147 structure. *visit* is called after *enter*, on the new parent.
1149 The *visit* function is called for every item in root,
1150 including duplicate items. For traversable values, it is
1151 called on the new parent object, after all its children
1152 have been visited. The default visit behavior simply
1153 returns the key-value pair unmodified.
1154 enter (callable): This function controls which items in *root*
1155 are traversed. It accepts the same arguments as *visit*: the
1156 path, the key, and the value of the current item. It returns a
1157 pair of the blank new parent, and an iterator over the items
1158 which should be visited. If ``False`` is returned instead of
1159 an iterator, the value will not be traversed.
1161 The *enter* function is only called once per unique value. The
1162 default enter behavior support mappings, sequences, and
1163 sets. Strings and all other iterables will not be traversed.
1164 exit (callable): This function determines how to handle items
1165 once they have been visited. It gets the same three
1166 arguments as the other functions -- *path*, *key*, *value*
1167 -- plus two more: the blank new parent object returned
1168 from *enter*, and a list of the new items, as remapped by
1169 *visit*.
1171 Like *enter*, the *exit* function is only called once per
1172 unique value. The default exit behavior is to simply add
1173 all new items to the new parent, e.g., using
1174 :meth:`list.extend` and :meth:`dict.update` to add to the
1175 new parent. Immutable objects, such as a :class:`tuple` or
1176 :class:`namedtuple`, must be recreated from scratch, but
1177 use the same type as the new parent passed back from the
1178 *enter* function.
1179 cache (bool): Controls whether to cache transformed
1180 objects. Uses object identity for the cache. For example
1181 this is turned off for applications like `research` which
1182 need to traverse all trees.
1183 reraise_visit (bool): A pragmatic convenience for the *visit*
1184 callable. When set to ``False``, remap ignores any errors
1185 raised by the *visit* callback. Items causing exceptions
1186 are kept. See examples for more details.
1187 trace (bool): Pass ``trace=True`` to print out the entire
1188 traversal. Or pass a tuple of ``'visit'``, ``'enter'``,
1189 or ``'exit'`` to print only the selected events.
1191 remap is designed to cover the majority of cases with just the
1192 *visit* callable. While passing in multiple callables is very
1193 empowering, remap is designed so very few cases should require
1194 passing more than one function.
1196 When passing *enter* and *exit*, it's common and easiest to build
1197 on the default behavior. Simply add ``from boltons.iterutils import
1198 default_enter`` (or ``default_exit``), and have your enter/exit
1199 function call the default behavior before or after your custom
1200 logic. See `this example`_.
1202 Duplicate and self-referential objects (aka reference loops) are
1203 automatically handled internally, `as shown here`_.
1205 .. _this example: http://sedimental.org/remap.html#sort_all_lists
1206 .. _as shown here: http://sedimental.org/remap.html#corner_cases
1208 """
1209 # TODO: improve argument formatting in sphinx doc
1210 # TODO: enter() return (False, items) to continue traverse but cancel copy?
1211 if not callable(visit):
1212 raise TypeError('visit expected callable, not: %r' % visit)
1213 if not callable(enter):
1214 raise TypeError('enter expected callable, not: %r' % enter)
1215 if not callable(exit):
1216 raise TypeError('exit expected callable, not: %r' % exit)
1217 reraise_visit = kwargs.pop('reraise_visit', True)
1218 trace = kwargs.pop('trace', ())
1219 if trace is True:
1220 trace = ('visit', 'enter', 'exit')
1221 elif isinstance(trace, str):
1222 trace = (trace,)
1223 if not isinstance(trace, (tuple, list, set)):
1224 raise TypeError('trace expected tuple of event names, not: %r' % trace)
1225 trace_enter, trace_exit, trace_visit = 'enter' in trace, 'exit' in trace, 'visit' in trace
1227 if kwargs:
1228 raise TypeError('unexpected keyword arguments: %r' % kwargs.keys())
1230 path, registry, stack = (), {}, [(None, root)]
1231 new_items_stack = []
1232 while stack:
1233 key, value = stack.pop()
1234 id_value = id(value)
1235 if key is _REMAP_EXIT:
1236 key, new_parent, old_parent = value
1237 id_value = id(old_parent)
1238 path, new_items = new_items_stack.pop()
1239 if trace_exit:
1240 print(' .. remap exit:', path, '-', key, '-',
1241 old_parent, '-', new_parent, '-', new_items)
1242 value = exit(path, key, old_parent, new_parent, new_items)
1243 if trace_exit:
1244 print(' .. remap exit result:', value)
1245 registry[id_value] = value
1246 if not new_items_stack:
1247 continue
1248 elif cache and id_value in registry:
1249 value = registry[id_value]
1250 else:
1251 if trace_enter:
1252 print(' .. remap enter:', path, '-', key, '-', value)
1253 res = enter(path, key, value)
1254 if trace_enter:
1255 print(' .. remap enter result:', res)
1256 try:
1257 new_parent, new_items = res
1258 except TypeError:
1259 # TODO: handle False?
1260 raise TypeError('enter should return a tuple of (new_parent,'
1261 ' items_iterator), not: %r' % res)
1262 if new_items is not False:
1263 # traverse unless False is explicitly passed
1264 registry[id_value] = new_parent
1265 new_items_stack.append((path, []))
1266 if value is not root:
1267 path += (key,)
1268 stack.append((_REMAP_EXIT, (key, new_parent, value)))
1269 if new_items:
1270 stack.extend(reversed(list(new_items)))
1271 if trace_enter:
1272 print(' .. remap stack size now:', len(stack))
1273 continue
1274 if visit is _orig_default_visit:
1275 # avoid function call overhead by inlining identity operation
1276 visited_item = (key, value)
1277 else:
1278 try:
1279 if trace_visit:
1280 print(' .. remap visit:', path, '-', key, '-', value)
1281 visited_item = visit(path, key, value)
1282 except Exception:
1283 if reraise_visit:
1284 raise
1285 visited_item = True
1286 if visited_item is False:
1287 if trace_visit:
1288 print(' .. remap visit result: <drop>')
1289 continue # drop
1290 elif visited_item is True:
1291 visited_item = (key, value)
1292 if trace_visit:
1293 print(' .. remap visit result:', visited_item)
1294 # TODO: typecheck?
1295 # raise TypeError('expected (key, value) from visit(),'
1296 # ' not: %r' % visited_item)
1297 try:
1298 new_items_stack[-1][1].append(visited_item)
1299 except IndexError:
1300 raise TypeError('expected remappable root, not: %r' % root)
1301 return value
1304class PathAccessError(KeyError, IndexError, TypeError):
1305 """An amalgamation of KeyError, IndexError, and TypeError,
1306 representing what can occur when looking up a path in a nested
1307 object.
1308 """
1310 def __init__(self, exc, seg, path):
1311 self.exc = exc
1312 self.seg = seg
1313 self.path = path
1315 def __repr__(self):
1316 cn = self.__class__.__name__
1317 return f'{cn}({self.exc!r}, {self.seg!r}, {self.path!r})'
1319 def __str__(self):
1320 return ('could not access %r from path %r, got error: %r'
1321 % (self.seg, self.path, self.exc))
1324def get_path(root, path, default=_UNSET):
1325 """Retrieve a value from a nested object via a tuple representing the
1326 lookup path.
1328 >>> root = {'a': {'b': {'c': [[1], [2], [3]]}}}
1329 >>> get_path(root, ('a', 'b', 'c', 2, 0))
1330 3
1332 The path tuple format is intentionally consistent with that of
1333 :func:`remap`, but a single dotted string can also be passed.
1335 One of get_path's chief aims is improved error messaging. EAFP is
1336 great, but the error messages are not.
1338 For instance, ``root['a']['b']['c'][2][1]`` gives back
1339 ``IndexError: list index out of range``
1341 What went out of range where? get_path currently raises
1342 ``PathAccessError: could not access 2 from path ('a', 'b', 'c', 2,
1343 1), got error: IndexError('list index out of range',)``, a
1344 subclass of IndexError and KeyError.
1346 You can also pass a default that covers the entire operation,
1347 should the lookup fail at any level.
1349 Args:
1350 root: The target nesting of dictionaries, lists, or other
1351 objects supporting ``__getitem__``.
1352 path (tuple): A sequence of strings and integers to be successively
1353 looked up within *root*. A dot-separated (``a.b``) string may
1354 also be passed.
1355 default: The value to be returned should any
1356 ``PathAccessError`` exceptions be raised.
1357 """
1358 if isinstance(path, str):
1359 path = path.split('.')
1360 cur = root
1361 try:
1362 for seg in path:
1363 try:
1364 cur = cur[seg]
1365 except (KeyError, IndexError) as exc:
1366 raise PathAccessError(exc, seg, path)
1367 except TypeError as exc:
1368 # either string index in a list, or a parent that
1369 # doesn't support indexing
1370 try:
1371 seg = int(seg)
1372 cur = cur[seg]
1373 except (ValueError, KeyError, IndexError, TypeError):
1374 if not is_iterable(cur):
1375 exc = TypeError('%r object is not indexable'
1376 % type(cur).__name__)
1377 raise PathAccessError(exc, seg, path)
1378 except PathAccessError:
1379 if default is _UNSET:
1380 raise
1381 return default
1382 return cur
1385def research(root, query=lambda p, k, v: True, reraise=False, enter=default_enter):
1386 """The :func:`research` function uses :func:`remap` to recurse over
1387 any data nested in *root*, and find values which match a given
1388 criterion, specified by the *query* callable.
1390 Results are returned as a list of ``(path, value)`` pairs. The
1391 paths are tuples in the same format accepted by
1392 :func:`get_path`. This can be useful for comparing values nested
1393 in two or more different structures.
1395 Here's a simple example that finds all integers:
1397 >>> root = {'a': {'b': 1, 'c': (2, 'd', 3)}, 'e': None}
1398 >>> res = research(root, query=lambda p, k, v: isinstance(v, int))
1399 >>> print(sorted(res))
1400 [(('a', 'b'), 1), (('a', 'c', 0), 2), (('a', 'c', 2), 3)]
1402 Note how *query* follows the same, familiar ``path, key, value``
1403 signature as the ``visit`` and ``enter`` functions on
1404 :func:`remap`, and returns a :class:`bool`.
1406 Args:
1407 root: The target object to search. Supports the same types of
1408 objects as :func:`remap`, including :class:`list`,
1409 :class:`tuple`, :class:`dict`, and :class:`set`.
1410 query (callable): The function called on every object to
1411 determine whether to include it in the search results. The
1412 callable must accept three arguments, *path*, *key*, and
1413 *value*, commonly abbreviated *p*, *k*, and *v*, same as
1414 *enter* and *visit* from :func:`remap`.
1415 reraise (bool): Whether to reraise exceptions raised by *query*
1416 or to simply drop the result that caused the error.
1419 With :func:`research` it's easy to inspect the details of a data
1420 structure, like finding values that are at a certain depth (using
1421 ``len(p)``) and much more. If more advanced functionality is
1422 needed, check out the code and make your own :func:`remap`
1423 wrapper, and consider `submitting a patch`_!
1425 .. _submitting a patch: https://github.com/mahmoud/boltons/pulls
1426 """
1427 ret = []
1429 if not callable(query):
1430 raise TypeError('query expected callable, not: %r' % query)
1432 def _enter(path, key, value):
1433 try:
1434 if query(path, key, value):
1435 ret.append((path + (key,), value))
1436 except Exception:
1437 if reraise:
1438 raise
1439 return enter(path, key, value)
1441 remap(root, enter=_enter, cache=False)
1442 return ret
1445# TODO: recollect()
1446# TODO: refilter()
1447# TODO: reiter()
1450# GUID iterators: 10x faster and somewhat more compact than uuid.
1452class GUIDerator:
1453 """The GUIDerator is an iterator that yields a globally-unique
1454 identifier (GUID) on every iteration. The GUIDs produced are
1455 hexadecimal strings.
1457 Testing shows it to be around 12x faster than the uuid module. By
1458 default it is also more compact, partly due to its default 96-bit
1459 (24-hexdigit) length. 96 bits of randomness means that there is a
1460 1 in 2 ^ 32 chance of collision after 2 ^ 64 iterations. If more
1461 or less uniqueness is desired, the *size* argument can be adjusted
1462 accordingly.
1464 Args:
1465 size (int): character length of the GUID, defaults to 24. Lengths
1466 between 20 and 36 are considered valid.
1468 The GUIDerator has built-in fork protection that causes it to
1469 detect a fork on next iteration and reseed accordingly.
1471 """
1473 def __init__(self, size=24):
1474 self.size = size
1475 if size < 20 or size > 36:
1476 raise ValueError('expected 20 <= size <= 36')
1477 import hashlib
1478 self._sha1 = hashlib.sha1
1479 self.count = itertools.count()
1480 self.reseed()
1482 def reseed(self):
1483 import socket
1484 self.pid = os.getpid()
1485 self.salt = '-'.join([str(self.pid),
1486 socket.gethostname() or '<nohostname>',
1487 str(time.time()),
1488 os.urandom(6).hex()])
1489 return
1491 def __iter__(self):
1492 return self
1494 def __next__(self):
1495 if os.getpid() != self.pid:
1496 self.reseed()
1497 target_bytes = (self.salt + str(next(self.count))).encode('utf8')
1498 hash_text = self._sha1(target_bytes).hexdigest()[:self.size]
1499 return hash_text
1501 next = __next__
1504class SequentialGUIDerator(GUIDerator):
1505 """Much like the standard GUIDerator, the SequentialGUIDerator is an
1506 iterator that yields a globally-unique identifier (GUID) on every
1507 iteration. The GUIDs produced are hexadecimal strings.
1509 The SequentialGUIDerator differs in that it picks a starting GUID
1510 value and increments every iteration. This yields GUIDs which are
1511 of course unique, but also ordered and lexicographically sortable.
1513 The SequentialGUIDerator is around 50% faster than the normal
1514 GUIDerator, making it almost 20x as fast as the built-in uuid
1515 module. By default it is also more compact, partly due to its
1516 96-bit (24-hexdigit) default length. 96 bits of randomness means that
1517 there is a 1 in 2 ^ 32 chance of collision after 2 ^ 64
1518 iterations. If more or less uniqueness is desired, the *size*
1519 argument can be adjusted accordingly.
1521 Args:
1522 size (int): character length of the GUID, defaults to 24.
1524 Note that with SequentialGUIDerator there is a chance of GUIDs
1525 growing larger than the size configured. The SequentialGUIDerator
1526 has built-in fork protection that causes it to detect a fork on
1527 next iteration and reseed accordingly.
1529 """
1531 def reseed(self):
1532 super().reseed()
1533 start_str = self._sha1(self.salt.encode('utf8')).hexdigest()
1534 self.start = int(start_str[:self.size], 16)
1535 self.start |= (1 << ((self.size * 4) - 2))
1537 def __next__(self):
1538 if os.getpid() != self.pid:
1539 self.reseed()
1540 return '%x' % (next(self.count) + self.start)
1542 next = __next__
1545guid_iter = GUIDerator()
1546seq_guid_iter = SequentialGUIDerator()
1549def soft_sorted(iterable, first=None, last=None, key=None, reverse=False):
1550 """For when you care about the order of some elements, but not about
1551 others.
1553 Use this to float to the top and/or sink to the bottom a specific
1554 ordering, while sorting the rest of the elements according to
1555 normal :func:`sorted` rules.
1557 >>> soft_sorted(['two', 'b', 'one', 'a'], first=['one', 'two'])
1558 ['one', 'two', 'a', 'b']
1559 >>> soft_sorted(range(7), first=[6, 15], last=[2, 4], reverse=True)
1560 [6, 5, 3, 1, 0, 2, 4]
1561 >>> import string
1562 >>> ''.join(soft_sorted(string.hexdigits, first='za1', last='b', key=str.lower))
1563 'aA1023456789cCdDeEfFbB'
1565 Args:
1566 iterable (list): A list or other iterable to sort.
1567 first (list): A sequence to enforce for elements which should
1568 appear at the beginning of the returned list.
1569 last (list): A sequence to enforce for elements which should
1570 appear at the end of the returned list.
1571 key (callable): Callable used to generate a comparable key for
1572 each item to be sorted, same as the key in
1573 :func:`sorted`. Note that entries in *first* and *last*
1574 should be the keys for the items. Defaults to
1575 passthrough/the identity function.
1576 reverse (bool): Whether or not elements not explicitly ordered
1577 by *first* and *last* should be in reverse order or not.
1579 Returns a new list in sorted order.
1580 """
1581 first = first or []
1582 last = last or []
1583 key = key or (lambda x: x)
1584 seq = list(iterable)
1585 other = [x for x in seq if not (
1586 (first and key(x) in first) or (last and key(x) in last))]
1587 other.sort(key=key, reverse=reverse)
1589 if first:
1590 first = sorted([x for x in seq if key(x) in first],
1591 key=lambda x: first.index(key(x)))
1592 if last:
1593 last = sorted([x for x in seq if key(x) in last],
1594 key=lambda x: last.index(key(x)))
1595 return first + other + last
1598def untyped_sorted(iterable, key=None, reverse=False):
1599 """A version of :func:`sorted` which will happily sort an iterable of
1600 heterogeneous types and return a new list, similar to legacy Python's
1601 behavior.
1603 >>> untyped_sorted(['abc', 2.0, 1, 2, 'def'])
1604 [1, 2.0, 2, 'abc', 'def']
1606 Note how mutually orderable types are sorted as expected, as in
1607 the case of the integers and floats above.
1609 .. note::
1611 Results may vary across Python versions and builds, but the
1612 function will produce a sorted list, except in the case of
1613 explicitly unorderable objects.
1615 """
1616 class _Wrapper:
1617 slots = ('obj',)
1619 def __init__(self, obj):
1620 self.obj = obj
1622 def __lt__(self, other):
1623 obj = key(self.obj) if key is not None else self.obj
1624 other = key(other.obj) if key is not None else other.obj
1625 try:
1626 ret = obj < other
1627 except TypeError:
1628 ret = ((type(obj).__name__, id(type(obj)), obj)
1629 < (type(other).__name__, id(type(other)), other))
1630 return ret
1632 if key is not None and not callable(key):
1633 raise TypeError('expected function or callable object for key, not: %r'
1634 % key)
1636 return sorted(iterable, key=_Wrapper, reverse=reverse)
1639"""
1640May actually be faster to do an isinstance check for a str path
1642$ python -m timeit -s "x = [1]" "x[0]"
164310000000 loops, best of 3: 0.0207 usec per loop
1644$ python -m timeit -s "x = [1]" "try: x[0] \nexcept: pass"
164510000000 loops, best of 3: 0.029 usec per loop
1646$ python -m timeit -s "x = [1]" "try: x[1] \nexcept: pass"
16471000000 loops, best of 3: 0.315 usec per loop
1648# setting up try/except is fast, only around 0.01us
1649# actually triggering the exception takes almost 10x as long
1651$ python -m timeit -s "x = [1]" "isinstance(x, basestring)"
165210000000 loops, best of 3: 0.141 usec per loop
1653$ python -m timeit -s "x = [1]" "isinstance(x, str)"
165410000000 loops, best of 3: 0.131 usec per loop
1655$ python -m timeit -s "x = [1]" "try: x.split('.')\n except: pass"
16561000000 loops, best of 3: 0.443 usec per loop
1657$ python -m timeit -s "x = [1]" "try: x.split('.') \nexcept AttributeError: pass"
16581000000 loops, best of 3: 0.544 usec per loop
1659"""