Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/toolz/itertoolz.py: 70%
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
1import itertools
2import heapq
3import collections
4import operator
5from functools import partial
6from itertools import filterfalse, zip_longest
7from collections.abc import Sequence
8from toolz.utils import no_default
11__all__ = ('remove', 'accumulate', 'groupby', 'merge_sorted', 'interleave',
12 'unique', 'isiterable', 'isdistinct', 'take', 'drop', 'take_nth',
13 'first', 'second', 'nth', 'last', 'get', 'concat', 'concatv',
14 'mapcat', 'cons', 'interpose', 'frequencies', 'reduceby', 'iterate',
15 'sliding_window', 'partition', 'partition_all', 'count', 'pluck',
16 'join', 'tail', 'diff', 'topk', 'peek', 'peekn', 'random_sample')
19def remove(predicate, seq):
20 """ Return those items of sequence for which predicate(item) is False
22 >>> def iseven(x):
23 ... return x % 2 == 0
24 >>> list(remove(iseven, [1, 2, 3, 4]))
25 [1, 3]
26 """
27 return filterfalse(predicate, seq)
30def accumulate(binop, seq, initial=no_default):
31 """ Repeatedly apply binary function to a sequence, accumulating results
33 >>> from operator import add, mul
34 >>> list(accumulate(add, [1, 2, 3, 4, 5]))
35 [1, 3, 6, 10, 15]
36 >>> list(accumulate(mul, [1, 2, 3, 4, 5]))
37 [1, 2, 6, 24, 120]
39 Accumulate is similar to ``reduce`` and is good for making functions like
40 cumulative sum:
42 >>> from functools import partial, reduce
43 >>> sum = partial(reduce, add)
44 >>> cumsum = partial(accumulate, add)
46 Accumulate also takes an optional argument that will be used as the first
47 value. This is similar to reduce.
49 >>> list(accumulate(add, [1, 2, 3], -1))
50 [-1, 0, 2, 5]
51 >>> list(accumulate(add, [], 1))
52 [1]
54 See Also:
55 itertools.accumulate : In standard itertools for Python 3.2+
56 """
57 seq = iter(seq)
58 if initial == no_default:
59 try:
60 result = next(seq)
61 except StopIteration:
62 return
63 else:
64 result = initial
65 yield result
66 for elem in seq:
67 result = binop(result, elem)
68 yield result
71def groupby(key, seq):
72 """ Group a collection by a key function
74 >>> names = ['Alice', 'Bob', 'Charlie', 'Dan', 'Edith', 'Frank']
75 >>> groupby(len, names) # doctest: +SKIP
76 {3: ['Bob', 'Dan'], 5: ['Alice', 'Edith', 'Frank'], 7: ['Charlie']}
78 >>> iseven = lambda x: x % 2 == 0
79 >>> groupby(iseven, [1, 2, 3, 4, 5, 6, 7, 8]) # doctest: +SKIP
80 {False: [1, 3, 5, 7], True: [2, 4, 6, 8]}
82 Non-callable keys imply grouping on a member.
84 >>> groupby('gender', [{'name': 'Alice', 'gender': 'F'},
85 ... {'name': 'Bob', 'gender': 'M'},
86 ... {'name': 'Charlie', 'gender': 'M'}]) # doctest:+SKIP
87 {'F': [{'gender': 'F', 'name': 'Alice'}],
88 'M': [{'gender': 'M', 'name': 'Bob'},
89 {'gender': 'M', 'name': 'Charlie'}]}
91 Not to be confused with ``itertools.groupby``
93 See Also:
94 countby
95 """
96 if not callable(key):
97 key = getter(key)
98 d = collections.defaultdict(lambda: [].append)
99 for item in seq:
100 d[key(item)](item)
101 rv = {}
102 for k, v in d.items():
103 rv[k] = v.__self__
104 return rv
107def merge_sorted(*seqs, **kwargs):
108 """ Merge and sort a collection of sorted collections
110 This works lazily and only keeps one value from each iterable in memory.
112 >>> list(merge_sorted([1, 3, 5], [2, 4, 6]))
113 [1, 2, 3, 4, 5, 6]
115 >>> ''.join(merge_sorted('abc', 'abc', 'abc'))
116 'aaabbbccc'
118 The "key" function used to sort the input may be passed as a keyword.
120 >>> list(merge_sorted([2, 3], [1, 3], key=lambda x: x // 3))
121 [2, 1, 3, 3]
122 """
123 if len(seqs) == 0:
124 return iter([])
125 elif len(seqs) == 1:
126 return iter(seqs[0])
128 key = kwargs.get('key', None)
129 if key is None:
130 return _merge_sorted_binary(seqs)
131 else:
132 return _merge_sorted_binary_key(seqs, key)
135def _merge_sorted_binary(seqs):
136 mid = len(seqs) // 2
137 L1 = seqs[:mid]
138 if len(L1) == 1:
139 seq1 = iter(L1[0])
140 else:
141 seq1 = _merge_sorted_binary(L1)
142 L2 = seqs[mid:]
143 if len(L2) == 1:
144 seq2 = iter(L2[0])
145 else:
146 seq2 = _merge_sorted_binary(L2)
148 try:
149 val2 = next(seq2)
150 except StopIteration:
151 yield from seq1
152 return
154 for val1 in seq1:
155 if val2 < val1:
156 yield val2
157 for val2 in seq2:
158 if val2 < val1:
159 yield val2
160 else:
161 yield val1
162 break
163 else:
164 break
165 else:
166 yield val1
167 else:
168 yield val2
169 yield from seq2
170 return
171 yield val1
172 yield from seq1
175def _merge_sorted_binary_key(seqs, key):
176 mid = len(seqs) // 2
177 L1 = seqs[:mid]
178 if len(L1) == 1:
179 seq1 = iter(L1[0])
180 else:
181 seq1 = _merge_sorted_binary_key(L1, key)
182 L2 = seqs[mid:]
183 if len(L2) == 1:
184 seq2 = iter(L2[0])
185 else:
186 seq2 = _merge_sorted_binary_key(L2, key)
188 try:
189 val2 = next(seq2)
190 except StopIteration:
191 yield from seq1
192 return
193 key2 = key(val2)
195 for val1 in seq1:
196 key1 = key(val1)
197 if key2 < key1:
198 yield val2
199 for val2 in seq2:
200 key2 = key(val2)
201 if key2 < key1:
202 yield val2
203 else:
204 yield val1
205 break
206 else:
207 break
208 else:
209 yield val1
210 else:
211 yield val2
212 yield from seq2
213 return
214 yield val1
215 yield from seq1
218def interleave(seqs):
219 """ Interleave a sequence of sequences
221 >>> list(interleave([[1, 2], [3, 4]]))
222 [1, 3, 2, 4]
224 >>> ''.join(interleave(('ABC', 'XY')))
225 'AXBYC'
227 Both the individual sequences and the sequence of sequences may be infinite
229 Returns a lazy iterator
230 """
231 iters = itertools.cycle(map(iter, seqs))
232 while True:
233 try:
234 for itr in iters:
235 yield next(itr)
236 return
237 except StopIteration:
238 predicate = partial(operator.is_not, itr)
239 iters = itertools.cycle(itertools.takewhile(predicate, iters))
242def unique(seq, key=None):
243 """ Return only unique elements of a sequence
245 >>> tuple(unique((1, 2, 3)))
246 (1, 2, 3)
247 >>> tuple(unique((1, 2, 1, 3)))
248 (1, 2, 3)
250 Uniqueness can be defined by key keyword
252 >>> tuple(unique(['cat', 'mouse', 'dog', 'hen'], key=len))
253 ('cat', 'mouse')
254 """
255 seen = set()
256 seen_add = seen.add
257 if key is None:
258 for item in seq:
259 if item not in seen:
260 seen_add(item)
261 yield item
262 else: # calculate key
263 for item in seq:
264 val = key(item)
265 if val not in seen:
266 seen_add(val)
267 yield item
270def isiterable(x):
271 """ Is x iterable?
273 >>> isiterable([1, 2, 3])
274 True
275 >>> isiterable('abc')
276 True
277 >>> isiterable(5)
278 False
279 """
280 try:
281 iter(x)
282 return True
283 except TypeError:
284 return False
287def isdistinct(seq):
288 """ All values in sequence are distinct
290 >>> isdistinct([1, 2, 3])
291 True
292 >>> isdistinct([1, 2, 1])
293 False
295 >>> isdistinct("Hello")
296 False
297 >>> isdistinct("World")
298 True
299 """
300 if iter(seq) is seq:
301 seen = set()
302 seen_add = seen.add
303 for item in seq:
304 if item in seen:
305 return False
306 seen_add(item)
307 return True
308 else:
309 return len(seq) == len(set(seq))
312def take(n, seq):
313 """ The first n elements of a sequence
315 >>> list(take(2, [10, 20, 30, 40, 50]))
316 [10, 20]
318 See Also:
319 drop
320 tail
321 """
322 return itertools.islice(seq, n)
325def tail(n, seq):
326 """ The last n elements of a sequence
328 >>> tail(2, [10, 20, 30, 40, 50])
329 [40, 50]
331 See Also:
332 drop
333 take
334 """
335 try:
336 return seq[-n:]
337 except (TypeError, KeyError):
338 return tuple(collections.deque(seq, n))
341def drop(n, seq):
342 """ The sequence following the first n elements
344 >>> list(drop(2, [10, 20, 30, 40, 50]))
345 [30, 40, 50]
347 See Also:
348 take
349 tail
350 """
351 return itertools.islice(seq, n, None)
354def take_nth(n, seq):
355 """ Every nth item in seq
357 >>> list(take_nth(2, [10, 20, 30, 40, 50]))
358 [10, 30, 50]
359 """
360 return itertools.islice(seq, 0, None, n)
363def first(seq):
364 """ The first element in a sequence
366 >>> first('ABC')
367 'A'
368 """
369 return next(iter(seq))
372def second(seq):
373 """ The second element in a sequence
375 >>> second('ABC')
376 'B'
377 """
378 seq = iter(seq)
379 next(seq)
380 return next(seq)
383def nth(n, seq):
384 """ The nth element in a sequence
386 >>> nth(1, 'ABC')
387 'B'
388 """
389 if isinstance(seq, (tuple, list, Sequence)):
390 return seq[n]
391 else:
392 return next(itertools.islice(seq, n, None))
395def last(seq):
396 """ The last element in a sequence
398 >>> last('ABC')
399 'C'
400 """
401 return tail(1, seq)[0]
404rest = partial(drop, 1)
407def _get(ind, seq, default):
408 try:
409 return seq[ind]
410 except (KeyError, IndexError):
411 return default
414def get(ind, seq, default=no_default):
415 """ Get element in a sequence or dict
417 Provides standard indexing
419 >>> get(1, 'ABC') # Same as 'ABC'[1]
420 'B'
422 Pass a list to get multiple values
424 >>> get([1, 2], 'ABC') # ('ABC'[1], 'ABC'[2])
425 ('B', 'C')
427 Works on any value that supports indexing/getitem
428 For example here we see that it works with dictionaries
430 >>> phonebook = {'Alice': '555-1234',
431 ... 'Bob': '555-5678',
432 ... 'Charlie':'555-9999'}
433 >>> get('Alice', phonebook)
434 '555-1234'
436 >>> get(['Alice', 'Bob'], phonebook)
437 ('555-1234', '555-5678')
439 Provide a default for missing values
441 >>> get(['Alice', 'Dennis'], phonebook, None)
442 ('555-1234', None)
444 See Also:
445 pluck
446 """
447 try:
448 return seq[ind]
449 except TypeError: # `ind` may be a list
450 if isinstance(ind, list):
451 if default == no_default:
452 if len(ind) > 1:
453 return operator.itemgetter(*ind)(seq)
454 elif ind:
455 return seq[ind[0]],
456 else:
457 return ()
458 else:
459 return tuple(_get(i, seq, default) for i in ind)
460 elif default != no_default:
461 return default
462 else:
463 raise
464 except (KeyError, IndexError): # we know `ind` is not a list
465 if default == no_default:
466 raise
467 else:
468 return default
471def concat(seqs):
472 """ Concatenate zero or more iterables, any of which may be infinite.
474 An infinite sequence will prevent the rest of the arguments from
475 being included.
477 We use chain.from_iterable rather than ``chain(*seqs)`` so that seqs
478 can be a generator.
480 >>> list(concat([[], [1], [2, 3]]))
481 [1, 2, 3]
483 See also:
484 itertools.chain.from_iterable equivalent
485 """
486 return itertools.chain.from_iterable(seqs)
489def concatv(*seqs):
490 """ Variadic version of concat
492 >>> list(concatv([], ["a"], ["b", "c"]))
493 ['a', 'b', 'c']
495 See also:
496 itertools.chain
497 """
498 return concat(seqs)
501def mapcat(func, seqs):
502 """ Apply func to each sequence in seqs, concatenating results.
504 >>> list(mapcat(lambda s: [c.upper() for c in s],
505 ... [["a", "b"], ["c", "d", "e"]]))
506 ['A', 'B', 'C', 'D', 'E']
507 """
508 return concat(map(func, seqs))
511def cons(el, seq):
512 """ Add el to beginning of (possibly infinite) sequence seq.
514 >>> list(cons(1, [2, 3]))
515 [1, 2, 3]
516 """
517 return itertools.chain([el], seq)
520def interpose(el, seq):
521 """ Introduce element between each pair of elements in seq
523 >>> list(interpose("a", [1, 2, 3]))
524 [1, 'a', 2, 'a', 3]
525 >>> list(interpose("a", []))
526 []
527 """
528 inposed = concat(zip(itertools.repeat(el), seq))
529 try:
530 next(inposed)
531 except StopIteration:
532 return iter([])
533 return inposed
536def frequencies(seq):
537 """ Find number of occurrences of each value in seq
539 >>> frequencies(['cat', 'cat', 'ox', 'pig', 'pig', 'cat']) #doctest: +SKIP
540 {'cat': 3, 'ox': 1, 'pig': 2}
542 See Also:
543 countby
544 groupby
545 """
546 d = collections.defaultdict(int)
547 for item in seq:
548 d[item] += 1
549 return dict(d)
552def reduceby(key, binop, seq, init=no_default):
553 """ Perform a simultaneous groupby and reduction
555 The computation:
557 >>> result = reduceby(key, binop, seq, init) # doctest: +SKIP
559 is equivalent to the following:
561 >>> def reduction(group): # doctest: +SKIP
562 ... return reduce(binop, group, init) # doctest: +SKIP
564 >>> groups = groupby(key, seq) # doctest: +SKIP
565 >>> result = valmap(reduction, groups) # doctest: +SKIP
567 But the former does not build the intermediate groups, allowing it to
568 operate in much less space. This makes it suitable for larger datasets
569 that do not fit comfortably in memory
571 The ``init`` keyword argument is the default initialization of the
572 reduction. This can be either a constant value like ``0`` or a callable
573 like ``lambda : 0`` as might be used in ``defaultdict``.
575 Simple Examples
576 ---------------
578 >>> from operator import add, mul
579 >>> iseven = lambda x: x % 2 == 0
581 >>> data = [1, 2, 3, 4, 5]
583 >>> reduceby(iseven, add, data) # doctest: +SKIP
584 {False: 9, True: 6}
586 >>> reduceby(iseven, mul, data) # doctest: +SKIP
587 {False: 15, True: 8}
589 Complex Example
590 ---------------
592 >>> projects = [{'name': 'build roads', 'state': 'CA', 'cost': 1000000},
593 ... {'name': 'fight crime', 'state': 'IL', 'cost': 100000},
594 ... {'name': 'help farmers', 'state': 'IL', 'cost': 2000000},
595 ... {'name': 'help farmers', 'state': 'CA', 'cost': 200000}]
597 >>> reduceby('state', # doctest: +SKIP
598 ... lambda acc, x: acc + x['cost'],
599 ... projects, 0)
600 {'CA': 1200000, 'IL': 2100000}
602 Example Using ``init``
603 ----------------------
605 >>> def set_add(s, i):
606 ... s.add(i)
607 ... return s
609 >>> reduceby(iseven, set_add, [1, 2, 3, 4, 1, 2, 3], set) # doctest: +SKIP
610 {True: set([2, 4]),
611 False: set([1, 3])}
612 """
613 is_no_default = init == no_default
614 if not is_no_default and not callable(init):
615 _init = init
616 init = lambda: _init
617 if not callable(key):
618 key = getter(key)
619 d = {}
620 for item in seq:
621 k = key(item)
622 if k not in d:
623 if is_no_default:
624 d[k] = item
625 continue
626 else:
627 d[k] = init()
628 d[k] = binop(d[k], item)
629 return d
632def iterate(func, x):
633 """ Repeatedly apply a function func onto an original input
635 Yields x, then func(x), then func(func(x)), then func(func(func(x))), etc..
637 >>> def inc(x): return x + 1
638 >>> counter = iterate(inc, 0)
639 >>> next(counter)
640 0
641 >>> next(counter)
642 1
643 >>> next(counter)
644 2
646 >>> double = lambda x: x * 2
647 >>> powers_of_two = iterate(double, 1)
648 >>> next(powers_of_two)
649 1
650 >>> next(powers_of_two)
651 2
652 >>> next(powers_of_two)
653 4
654 >>> next(powers_of_two)
655 8
656 """
657 while True:
658 yield x
659 x = func(x)
662def sliding_window(n, seq):
663 """ A sequence of overlapping subsequences
665 >>> list(sliding_window(2, [1, 2, 3, 4]))
666 [(1, 2), (2, 3), (3, 4)]
668 This function creates a sliding window suitable for transformations like
669 sliding means / smoothing
671 >>> mean = lambda seq: float(sum(seq)) / len(seq)
672 >>> list(map(mean, sliding_window(2, [1, 2, 3, 4])))
673 [1.5, 2.5, 3.5]
674 """
675 return zip(*(collections.deque(itertools.islice(it, i), 0) or it
676 for i, it in enumerate(itertools.tee(seq, n))))
679no_pad = '__no__pad__'
682def partition(n, seq, pad=no_pad):
683 """ Partition sequence into tuples of length n
685 >>> list(partition(2, [1, 2, 3, 4]))
686 [(1, 2), (3, 4)]
688 If the length of ``seq`` is not evenly divisible by ``n``, the final tuple
689 is dropped if ``pad`` is not specified, or filled to length ``n`` by pad:
691 >>> list(partition(2, [1, 2, 3, 4, 5]))
692 [(1, 2), (3, 4)]
694 >>> list(partition(2, [1, 2, 3, 4, 5], pad=None))
695 [(1, 2), (3, 4), (5, None)]
697 See Also:
698 partition_all
699 """
700 args = [iter(seq)] * n
701 if pad is no_pad:
702 return zip(*args)
703 else:
704 return zip_longest(*args, fillvalue=pad)
707def partition_all(n, seq):
708 """ Partition all elements of sequence into tuples of length at most n
710 The final tuple may be shorter to accommodate extra elements.
712 >>> list(partition_all(2, [1, 2, 3, 4]))
713 [(1, 2), (3, 4)]
715 >>> list(partition_all(2, [1, 2, 3, 4, 5]))
716 [(1, 2), (3, 4), (5,)]
718 See Also:
719 partition
720 """
721 args = [iter(seq)] * n
722 it = zip_longest(*args, fillvalue=no_pad)
723 try:
724 prev = next(it)
725 except StopIteration:
726 return
727 for item in it:
728 yield prev
729 prev = item
730 if prev[-1] is no_pad:
731 try:
732 # If seq defines __len__, then
733 # we can quickly calculate where no_pad starts
734 end = len(seq) % n
735 if prev[end - 1] is no_pad or prev[end] is not no_pad:
736 raise LookupError(
737 'The sequence passed to `parition_all` has invalid length'
738 )
739 yield prev[:end]
740 except TypeError:
741 # Get first index of no_pad without using .index()
742 # https://github.com/pytoolz/toolz/issues/387
743 # Binary search from CPython's bisect module,
744 # modified for identity testing.
745 lo, hi = 0, n
746 while lo < hi:
747 mid = (lo + hi) // 2
748 if prev[mid] is no_pad:
749 hi = mid
750 else:
751 lo = mid + 1
752 yield prev[:lo]
753 else:
754 yield prev
757def count(seq):
758 """ Count the number of items in seq
760 Like the builtin ``len`` but works on lazy sequences.
762 Not to be confused with ``itertools.count``
764 See also:
765 len
766 """
767 if hasattr(seq, '__len__'):
768 return len(seq)
769 return sum(1 for i in seq)
772def pluck(ind, seqs, default=no_default):
773 """ plucks an element or several elements from each item in a sequence.
775 ``pluck`` maps ``itertoolz.get`` over a sequence and returns one or more
776 elements of each item in the sequence.
778 This is equivalent to running `map(curried.get(ind), seqs)`
780 ``ind`` can be either a single string/index or a list of strings/indices.
781 ``seqs`` should be sequence containing sequences or dicts.
783 e.g.
785 >>> data = [{'id': 1, 'name': 'Cheese'}, {'id': 2, 'name': 'Pies'}]
786 >>> list(pluck('name', data))
787 ['Cheese', 'Pies']
788 >>> list(pluck([0, 1], [[1, 2, 3], [4, 5, 7]]))
789 [(1, 2), (4, 5)]
791 See Also:
792 get
793 map
794 """
795 if default == no_default:
796 get = getter(ind)
797 return map(get, seqs)
798 elif isinstance(ind, list):
799 return (tuple(_get(item, seq, default) for item in ind)
800 for seq in seqs)
801 return (_get(ind, seq, default) for seq in seqs)
804def getter(index):
805 if isinstance(index, list):
806 if len(index) == 1:
807 index = index[0]
808 return lambda x: (x[index],)
809 elif index:
810 return operator.itemgetter(*index)
811 else:
812 return lambda x: ()
813 else:
814 return operator.itemgetter(index)
817def join(leftkey, leftseq, rightkey, rightseq,
818 left_default=no_default, right_default=no_default):
819 """ Join two sequences on common attributes
821 This is a semi-streaming operation. The LEFT sequence is fully evaluated
822 and placed into memory. The RIGHT sequence is evaluated lazily and so can
823 be arbitrarily large.
825 (Note: If right_default is defined, then unique keys of rightseq
826 will also be stored in memory.)
828 >>> friends = [('Alice', 'Edith'),
829 ... ('Alice', 'Zhao'),
830 ... ('Edith', 'Alice'),
831 ... ('Zhao', 'Alice'),
832 ... ('Zhao', 'Edith')]
834 >>> cities = [('Alice', 'NYC'),
835 ... ('Alice', 'Chicago'),
836 ... ('Dan', 'Sydney'),
837 ... ('Edith', 'Paris'),
838 ... ('Edith', 'Berlin'),
839 ... ('Zhao', 'Shanghai')]
841 >>> # Vacation opportunities
842 >>> # In what cities do people have friends?
843 >>> result = join(second, friends,
844 ... first, cities)
845 >>> for ((a, b), (c, d)) in sorted(unique(result)):
846 ... print((a, d))
847 ('Alice', 'Berlin')
848 ('Alice', 'Paris')
849 ('Alice', 'Shanghai')
850 ('Edith', 'Chicago')
851 ('Edith', 'NYC')
852 ('Zhao', 'Chicago')
853 ('Zhao', 'NYC')
854 ('Zhao', 'Berlin')
855 ('Zhao', 'Paris')
857 Specify outer joins with keyword arguments ``left_default`` and/or
858 ``right_default``. Here is a full outer join in which unmatched elements
859 are paired with None.
861 >>> identity = lambda x: x
862 >>> list(join(identity, [1, 2, 3],
863 ... identity, [2, 3, 4],
864 ... left_default=None, right_default=None))
865 [(2, 2), (3, 3), (None, 4), (1, None)]
867 Usually the key arguments are callables to be applied to the sequences. If
868 the keys are not obviously callable then it is assumed that indexing was
869 intended, e.g. the following is a legal change.
870 The join is implemented as a hash join and the keys of leftseq must be
871 hashable. Additionally, if right_default is defined, then keys of rightseq
872 must also be hashable.
874 >>> # result = join(second, friends, first, cities)
875 >>> result = join(1, friends, 0, cities) # doctest: +SKIP
876 """
877 if not callable(leftkey):
878 leftkey = getter(leftkey)
879 if not callable(rightkey):
880 rightkey = getter(rightkey)
882 d = groupby(leftkey, leftseq)
884 if left_default == no_default and right_default == no_default:
885 # Inner Join
886 for item in rightseq:
887 key = rightkey(item)
888 if key in d:
889 for left_match in d[key]:
890 yield (left_match, item)
891 elif left_default != no_default and right_default == no_default:
892 # Right Join
893 for item in rightseq:
894 key = rightkey(item)
895 if key in d:
896 for left_match in d[key]:
897 yield (left_match, item)
898 else:
899 yield (left_default, item)
900 elif right_default != no_default:
901 seen_keys = set()
902 seen = seen_keys.add
904 if left_default == no_default:
905 # Left Join
906 for item in rightseq:
907 key = rightkey(item)
908 seen(key)
909 if key in d:
910 for left_match in d[key]:
911 yield (left_match, item)
912 else:
913 # Full Join
914 for item in rightseq:
915 key = rightkey(item)
916 seen(key)
917 if key in d:
918 for left_match in d[key]:
919 yield (left_match, item)
920 else:
921 yield (left_default, item)
923 for key, matches in d.items():
924 if key not in seen_keys:
925 for match in matches:
926 yield (match, right_default)
929def diff(*seqs, **kwargs):
930 """ Return those items that differ between sequences
932 >>> list(diff([1, 2, 3], [1, 2, 10, 100]))
933 [(3, 10)]
935 Shorter sequences may be padded with a ``default`` value:
937 >>> list(diff([1, 2, 3], [1, 2, 10, 100], default=None))
938 [(3, 10), (None, 100)]
940 A ``key`` function may also be applied to each item to use during
941 comparisons:
943 >>> list(diff(['apples', 'bananas'], ['Apples', 'Oranges'], key=str.lower))
944 [('bananas', 'Oranges')]
945 """
946 N = len(seqs)
947 if N == 1 and isinstance(seqs[0], list):
948 seqs = seqs[0]
949 N = len(seqs)
950 if N < 2:
951 raise TypeError('Too few sequences given (min 2 required)')
952 default = kwargs.get('default', no_default)
953 if default == no_default:
954 iters = zip(*seqs)
955 else:
956 iters = zip_longest(*seqs, fillvalue=default)
957 key = kwargs.get('key', None)
958 if key is None:
959 for items in iters:
960 if items.count(items[0]) != N:
961 yield items
962 else:
963 for items in iters:
964 vals = tuple(map(key, items))
965 if vals.count(vals[0]) != N:
966 yield items
969def topk(k, seq, key=None):
970 """ Find the k largest elements of a sequence
972 Operates lazily in ``n*log(k)`` time
974 >>> topk(2, [1, 100, 10, 1000])
975 (1000, 100)
977 Use a key function to change sorted order
979 >>> topk(2, ['Alice', 'Bob', 'Charlie', 'Dan'], key=len)
980 ('Charlie', 'Alice')
982 See also:
983 heapq.nlargest
984 """
985 if key is not None and not callable(key):
986 key = getter(key)
987 return tuple(heapq.nlargest(k, seq, key=key))
990def peek(seq):
991 """ Retrieve the next element of a sequence
993 Returns the first element and an iterable equivalent to the original
994 sequence, still having the element retrieved.
996 >>> seq = [0, 1, 2, 3, 4]
997 >>> first, seq = peek(seq)
998 >>> first
999 0
1000 >>> list(seq)
1001 [0, 1, 2, 3, 4]
1002 """
1003 iterator = iter(seq)
1004 item = next(iterator)
1005 return item, itertools.chain((item,), iterator)
1008def peekn(n, seq):
1009 """ Retrieve the next n elements of a sequence
1011 Returns a tuple of the first n elements and an iterable equivalent
1012 to the original, still having the elements retrieved.
1014 >>> seq = [0, 1, 2, 3, 4]
1015 >>> first_two, seq = peekn(2, seq)
1016 >>> first_two
1017 (0, 1)
1018 >>> list(seq)
1019 [0, 1, 2, 3, 4]
1020 """
1021 iterator = iter(seq)
1022 peeked = tuple(take(n, iterator))
1023 return peeked, itertools.chain(iter(peeked), iterator)
1026def random_sample(prob, seq, random_state=None):
1027 """ Return elements from a sequence with probability of prob
1029 Returns a lazy iterator of random items from seq.
1031 ``random_sample`` considers each item independently and without
1032 replacement. See below how the first time it returned 13 items and the
1033 next time it returned 6 items.
1035 >>> seq = list(range(100))
1036 >>> list(random_sample(0.1, seq)) # doctest: +SKIP
1037 [6, 9, 19, 35, 45, 50, 58, 62, 68, 72, 78, 86, 95]
1038 >>> list(random_sample(0.1, seq)) # doctest: +SKIP
1039 [6, 44, 54, 61, 69, 94]
1041 Providing an integer seed for ``random_state`` will result in
1042 deterministic sampling. Given the same seed it will return the same sample
1043 every time.
1045 >>> list(random_sample(0.1, seq, random_state=2016))
1046 [7, 9, 19, 25, 30, 32, 34, 48, 59, 60, 81, 98]
1047 >>> list(random_sample(0.1, seq, random_state=2016))
1048 [7, 9, 19, 25, 30, 32, 34, 48, 59, 60, 81, 98]
1050 ``random_state`` can also be any object with a method ``random`` that
1051 returns floats between 0.0 and 1.0 (exclusive).
1053 >>> from random import Random
1054 >>> randobj = Random(2016)
1055 >>> list(random_sample(0.1, seq, random_state=randobj))
1056 [7, 9, 19, 25, 30, 32, 34, 48, 59, 60, 81, 98]
1057 """
1058 if not hasattr(random_state, 'random'):
1059 from random import Random
1061 random_state = Random(random_state)
1062 return filter(lambda _: random_state.random() < prob, seq)