Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/more_itertools/more.py: 19%

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

1806 statements  

1__lazy_modules__ = frozenset({'queue', 'threading'}) 

2 

3import math 

4import types 

5 

6from collections import Counter, defaultdict, deque 

7from collections.abc import Sequence 

8from contextlib import suppress 

9from functools import cached_property, partial, wraps 

10from heapq import heapify, heapreplace 

11from itertools import ( 

12 chain, 

13 combinations, 

14 compress, 

15 count, 

16 cycle, 

17 dropwhile, 

18 groupby, 

19 islice, 

20 permutations, 

21 repeat, 

22 starmap, 

23 takewhile, 

24 tee, 

25 zip_longest, 

26 product, 

27) 

28from math import comb, e, exp, floor, fsum, log, log1p, perm, tau 

29from math import ceil, prod 

30from queue import Empty, Queue 

31from random import random, randrange, shuffle, uniform 

32from operator import ( 

33 attrgetter, 

34 getitem, 

35 is_not, 

36 itemgetter, 

37 lt, 

38 neg, 

39 sub, 

40 gt, 

41) 

42from sys import maxsize 

43from time import monotonic 

44from threading import Lock 

45 

46from .recipes import ( 

47 _marker, 

48 consume, 

49 first_true, 

50 flatten, 

51 is_prime, 

52 nth, 

53 powerset, 

54 sieve, 

55 take, 

56 unique_everseen, 

57 all_equal, 

58 batched, 

59) 

60 

61__all__ = [ 

62 'AbortThread', 

63 'SequenceView', 

64 'adjacent', 

65 'all_unique', 

66 'always_iterable', 

67 'always_reversible', 

68 'argmax', 

69 'argmin', 

70 'bucket', 

71 'callback_iter', 

72 'chunked', 

73 'chunked_even', 

74 'circular_shifts', 

75 'classify_unique', 

76 'collapse', 

77 'combination_index', 

78 'combination_with_replacement_index', 

79 'concurrent_tee', 

80 'consecutive_groups', 

81 'constrained_batches', 

82 'consumer', 

83 'count_cycle', 

84 'countable', 

85 'derangements', 

86 'dft', 

87 'difference', 

88 'distinct_combinations', 

89 'distinct_permutations', 

90 'distribute', 

91 'divide', 

92 'doublestarmap', 

93 'duplicates_everseen', 

94 'duplicates_justseen', 

95 'exactly_n', 

96 'extract', 

97 'filter_except', 

98 'filter_map', 

99 'first', 

100 'gray_product', 

101 'groupby_transform', 

102 'ichunked', 

103 'idft', 

104 'iequals', 

105 'ilen', 

106 'interleave', 

107 'interleave_evenly', 

108 'interleave_longest', 

109 'interleave_randomly', 

110 'intersperse', 

111 'is_sorted', 

112 'islice_extended', 

113 'iter_suppress', 

114 'iterate', 

115 'join_mappings', 

116 'last', 

117 'locate', 

118 'longest_common_prefix', 

119 'lstrip', 

120 'make_decorator', 

121 'map_except', 

122 'map_if', 

123 'map_reduce', 

124 'mark_ends', 

125 'minmax', 

126 'nth_combination_with_replacement', 

127 'nth_or_last', 

128 'nth_permutation', 

129 'nth_prime', 

130 'nth_product', 

131 'numeric_range', 

132 'one', 

133 'only', 

134 'outer_product', 

135 'padded', 

136 'partial_product', 

137 'partitions', 

138 'peekable', 

139 'permutation_index', 

140 'powerset_of_sets', 

141 'product_index', 

142 'raise_', 

143 'random_ordered_range', 

144 'repeat_each', 

145 'repeat_last', 

146 'replace', 

147 'rlocate', 

148 'rstrip', 

149 'run_length', 

150 'sample', 

151 'seekable', 

152 'serialize', 

153 'set_partitions', 

154 'side_effect', 

155 'sized_iterator', 

156 'sliced', 

157 'sort_together', 

158 'split_after', 

159 'split_at', 

160 'split_before', 

161 'split_into', 

162 'split_when', 

163 'spy', 

164 'stagger', 

165 'strictly_n', 

166 'strip', 

167 'subfactorial', 

168 'substrings', 

169 'substrings_indexes', 

170 'synchronized', 

171 'takewhile_inclusive', 

172 'time_limited', 

173 'unique_in_window', 

174 'unique_to_each', 

175 'unzip', 

176 'value_chain', 

177 'windowed', 

178 'windowed_complete', 

179 'with_iter', 

180 'zip_broadcast', 

181 'zip_offset', 

182] 

183 

184# math.sumprod is available for Python 3.12+ 

185try: 

186 from math import sumprod as _fsumprod 

187 

188except ImportError: # pragma: no cover 

189 # Extended precision algorithms from T. J. Dekker, 

190 # "A Floating-Point Technique for Extending the Available Precision" 

191 # https://csclub.uwaterloo.ca/~pbarfuss/dekker1971.pdf 

192 # Formulas: (5.5) (5.6) and (5.8). Code: mul12() 

193 

194 def dl_split(x: float): 

195 "Split a float into two half-precision components." 

196 t = x * 134217729.0 # Veltkamp constant = 2.0 ** 27 + 1 

197 hi = t - (t - x) 

198 lo = x - hi 

199 return hi, lo 

200 

201 def dl_mul(x, y): 

202 "Lossless multiplication." 

203 xx_hi, xx_lo = dl_split(x) 

204 yy_hi, yy_lo = dl_split(y) 

205 p = xx_hi * yy_hi 

206 q = xx_hi * yy_lo + xx_lo * yy_hi 

207 z = p + q 

208 zz = p - z + q + xx_lo * yy_lo 

209 return z, zz 

210 

211 def _fsumprod(p, q): 

212 return fsum(chain.from_iterable(map(dl_mul, p, q))) 

213 

214 

215def chunked(iterable, n, strict=False): 

216 """Break *iterable* into lists of length *n*: 

217 

218 >>> list(chunked([1, 2, 3, 4, 5, 6], 3)) 

219 [[1, 2, 3], [4, 5, 6]] 

220 

221 By the default, the last yielded list will have fewer than *n* elements 

222 if the length of *iterable* is not divisible by *n*: 

223 

224 >>> list(chunked([1, 2, 3, 4, 5, 6, 7, 8], 3)) 

225 [[1, 2, 3], [4, 5, 6], [7, 8]] 

226 

227 To use a fill-in value instead, see the :func:`grouper` recipe. 

228 

229 If the length of *iterable* is not divisible by *n* and *strict* is 

230 ``True``, then ``ValueError`` will be raised before the last 

231 list is yielded. 

232 

233 """ 

234 if n is not None and n < 0: 

235 raise ValueError('n must be at least 0') 

236 

237 iterator = iter(partial(take, n, iter(iterable)), []) 

238 if strict: 

239 if n is None: 

240 raise ValueError('n must not be None when using strict mode.') 

241 

242 def ret(): 

243 for chunk in iterator: 

244 if len(chunk) != n: 

245 raise ValueError('iterable is not divisible by n.') 

246 yield chunk 

247 

248 return ret() 

249 else: 

250 return iterator 

251 

252 

253def first(iterable, default=_marker): 

254 """Return the first item of *iterable*, or *default* if *iterable* is 

255 empty. 

256 

257 >>> first([0, 1, 2, 3]) 

258 0 

259 >>> first([], 'some default') 

260 'some default' 

261 

262 If *default* is not provided and there are no items in the iterable, 

263 raise ``ValueError``. 

264 

265 :func:`first` is useful when you have a generator of expensive-to-retrieve 

266 values and want any arbitrary one. It is marginally shorter than 

267 ``next(iter(iterable), default)``. 

268 

269 """ 

270 for item in iterable: 

271 return item 

272 if default is _marker: 

273 raise ValueError( 

274 'first() was called on an empty iterable, ' 

275 'and no default value was provided.' 

276 ) 

277 return default 

278 

279 

280def last(iterable, default=_marker): 

281 """Return the last item of *iterable*, or *default* if *iterable* is 

282 empty. 

283 

284 >>> last([0, 1, 2, 3]) 

285 3 

286 >>> last([], 'some default') 

287 'some default' 

288 

289 If *default* is not provided and there are no items in the iterable, 

290 raise ``ValueError``. 

291 """ 

292 try: 

293 if getattr(iterable, '__reversed__', None): 

294 return next(reversed(iterable)) 

295 return deque(iterable, maxlen=1)[-1] 

296 except (IndexError, StopIteration): 

297 if default is _marker: 

298 raise ValueError( 

299 'last() was called on an empty iterable, ' 

300 'and no default value was provided.' 

301 ) 

302 return default 

303 

304 

305def nth_or_last(iterable, n, default=_marker): 

306 """Return the nth or the last item of *iterable*, 

307 or *default* if *iterable* is empty. 

308 

309 >>> nth_or_last([0, 1, 2, 3], 2) 

310 2 

311 >>> nth_or_last([0, 1], 2) 

312 1 

313 >>> nth_or_last([], 0, 'some default') 

314 'some default' 

315 

316 If *default* is not provided and there are no items in the iterable, 

317 raise ``ValueError``. 

318 """ 

319 return last(islice(iterable, n + 1), default=default) 

320 

321 

322class peekable: 

323 """Wrap an iterator to allow lookahead and prepending elements. 

324 

325 Call :meth:`peek` on the result to get the value that will be returned 

326 by :func:`next`. This won't advance the iterator: 

327 

328 >>> p = peekable(['a', 'b']) 

329 >>> p.peek() 

330 'a' 

331 >>> next(p) 

332 'a' 

333 

334 Pass :meth:`peek` a default value to return that instead of raising 

335 ``StopIteration`` when the iterator is exhausted. 

336 

337 >>> p = peekable([]) 

338 >>> p.peek('hi') 

339 'hi' 

340 

341 peekables also offer a :meth:`prepend` method, which "inserts" items 

342 at the head of the iterable: 

343 

344 >>> p = peekable([1, 2, 3]) 

345 >>> p.prepend(10, 11, 12) 

346 >>> next(p) 

347 10 

348 >>> p.peek() 

349 11 

350 >>> list(p) 

351 [11, 12, 1, 2, 3] 

352 

353 peekables can be indexed. Index 0 is the item that will be returned by 

354 :func:`next`, index 1 is the item after that, and so on: 

355 The values up to the given index will be cached. 

356 

357 >>> p = peekable(['a', 'b', 'c', 'd']) 

358 >>> p[0] 

359 'a' 

360 >>> p[1] 

361 'b' 

362 >>> next(p) 

363 'a' 

364 

365 Negative indexes are supported, but be aware that they will cache the 

366 remaining items in the source iterator, which may require significant 

367 storage. 

368 

369 To check whether a peekable is exhausted, check its truth value: 

370 

371 >>> p = peekable(['a', 'b']) 

372 >>> if p: # peekable has items 

373 ... list(p) 

374 ['a', 'b'] 

375 >>> if not p: # peekable is exhausted 

376 ... list(p) 

377 [] 

378 

379 """ 

380 

381 def __init__(self, iterable): 

382 self._it = iter(iterable) 

383 self._cache = deque() 

384 

385 def __iter__(self): 

386 return self 

387 

388 def __bool__(self): 

389 try: 

390 self.peek() 

391 except StopIteration: 

392 return False 

393 return True 

394 

395 def peek(self, default=_marker): 

396 """Return the item that will be next returned from ``next()``. 

397 

398 Return ``default`` if there are no items left. If ``default`` is not 

399 provided, raise ``StopIteration``. 

400 

401 """ 

402 if not self._cache: 

403 try: 

404 self._cache.append(next(self._it)) 

405 except StopIteration: 

406 if default is _marker: 

407 raise 

408 return default 

409 return self._cache[0] 

410 

411 def prepend(self, *items): 

412 """Stack up items to be the next ones returned from ``next()`` or 

413 ``self.peek()``. The items will be returned in 

414 first in, first out order:: 

415 

416 >>> p = peekable([1, 2, 3]) 

417 >>> p.prepend(10, 11, 12) 

418 >>> next(p) 

419 10 

420 >>> list(p) 

421 [11, 12, 1, 2, 3] 

422 

423 It is possible, by prepending items, to "resurrect" a peekable that 

424 previously raised ``StopIteration``. 

425 

426 >>> p = peekable([]) 

427 >>> next(p) 

428 Traceback (most recent call last): 

429 ... 

430 StopIteration 

431 >>> p.prepend(1) 

432 >>> next(p) 

433 1 

434 >>> next(p) 

435 Traceback (most recent call last): 

436 ... 

437 StopIteration 

438 

439 """ 

440 self._cache.extendleft(reversed(items)) 

441 

442 __class_getitem__ = classmethod(types.GenericAlias) 

443 

444 def __next__(self): 

445 if self._cache: 

446 return self._cache.popleft() 

447 

448 return next(self._it) 

449 

450 def _get_slice(self, index): 

451 # Normalize the slice's arguments 

452 step = 1 if (index.step is None) else index.step 

453 if step > 0: 

454 start = 0 if (index.start is None) else index.start 

455 stop = maxsize if (index.stop is None) else index.stop 

456 elif step < 0: 

457 start = -1 if (index.start is None) else index.start 

458 stop = (-maxsize - 1) if (index.stop is None) else index.stop 

459 else: 

460 raise ValueError('slice step cannot be zero') 

461 

462 # If either the start or stop index is negative, we'll need to cache 

463 # the rest of the iterable in order to slice from the right side. 

464 # When step < 0 and stop is None, the slice stops at index 0 rather than 

465 # indexing from the right, so only items up to start must be cached. 

466 has_negative_index = ( 

467 (index.start is not None and index.start < 0) 

468 or (index.stop is not None and index.stop < 0) 

469 or (step < 0 and index.start is None) 

470 ) 

471 if has_negative_index: 

472 self._cache.extend(self._it) 

473 # Otherwise we'll need to find the rightmost index and cache to that 

474 # point. 

475 else: 

476 rightmost = ( 

477 start 

478 if (step < 0 and index.stop is None) 

479 else max(start, stop) 

480 ) 

481 n = min(rightmost + 1, maxsize) 

482 cache_len = len(self._cache) 

483 if n >= cache_len: 

484 self._cache.extend(islice(self._it, n - cache_len)) 

485 

486 return list(self._cache)[index] 

487 

488 def __getitem__(self, index): 

489 if isinstance(index, slice): 

490 return self._get_slice(index) 

491 

492 cache_len = len(self._cache) 

493 if index < 0: 

494 self._cache.extend(self._it) 

495 elif index >= cache_len: 

496 self._cache.extend(islice(self._it, index + 1 - cache_len)) 

497 

498 return self._cache[index] 

499 

500 

501def consumer(func): 

502 """Decorator that automatically advances a PEP-342-style "reverse iterator" 

503 to its first yield point so you don't have to call ``next()`` on it 

504 manually. 

505 

506 >>> @consumer 

507 ... def tally(): 

508 ... i = 0 

509 ... while True: 

510 ... print('Thing number %s is %s.' % (i, (yield))) 

511 ... i += 1 

512 ... 

513 >>> t = tally() 

514 >>> t.send('red') 

515 Thing number 0 is red. 

516 >>> t.send('fish') 

517 Thing number 1 is fish. 

518 

519 Without the decorator, you would have to call ``next(t)`` before 

520 ``t.send()`` could be used. 

521 

522 """ 

523 

524 @wraps(func) 

525 def wrapper(*args, **kwargs): 

526 gen = func(*args, **kwargs) 

527 next(gen) 

528 return gen 

529 

530 return wrapper 

531 

532 

533def ilen(iterable): 

534 """Return the number of items in *iterable*. 

535 

536 For example, there are 168 prime numbers below 1,000: 

537 

538 >>> ilen(sieve(1000)) 

539 168 

540 

541 Equivalent to, but faster than:: 

542 

543 def ilen(iterable): 

544 count = 0 

545 for _ in iterable: 

546 count += 1 

547 return count 

548 

549 This fully consumes the iterable, so handle with care. 

550 

551 """ 

552 # This is the "most beautiful of the fast variants" of this function. 

553 # If you think you can improve on it, please ensure that your version 

554 # is both 10x faster and 10x more beautiful. 

555 return sum(compress(repeat(1), zip(iterable))) 

556 

557 

558def iterate(func, start): 

559 """Return ``start``, ``func(start)``, ``func(func(start))``, ... 

560 

561 Produces an infinite iterator. To add a stopping condition, 

562 use :func:`take`, ``takewhile``, or :func:`takewhile_inclusive`:. 

563 

564 >>> take(10, iterate(lambda x: 2*x, 1)) 

565 [1, 2, 4, 8, 16, 32, 64, 128, 256, 512] 

566 

567 >>> collatz = lambda x: 3*x + 1 if x%2==1 else x // 2 

568 >>> list(takewhile_inclusive(lambda x: x!=1, iterate(collatz, 10))) 

569 [10, 5, 16, 8, 4, 2, 1] 

570 

571 """ 

572 with suppress(StopIteration): 

573 while True: 

574 yield start 

575 start = func(start) 

576 

577 

578def with_iter(context_manager): 

579 """Wrap an iterable in a ``with`` statement, so it closes once exhausted. 

580 

581 For example, this will close the file when the iterator is exhausted:: 

582 

583 upper_lines = (line.upper() for line in with_iter(open('foo'))) 

584 

585 Note that you have to actually exhaust the iterator for opened files to be closed. 

586 

587 Any context manager which returns an iterable is a candidate for 

588 ``with_iter``. 

589 

590 """ 

591 with context_manager as iterable: 

592 yield from iterable 

593 

594 

595class sized_iterator: 

596 """Wrapper for *iterable* that implements ``__len__``. 

597 

598 >>> it = map(str, range(5)) 

599 >>> sized_it = sized_iterator(it, 5) 

600 >>> len(sized_it) 

601 5 

602 >>> list(sized_it) 

603 ['0', '1', '2', '3', '4'] 

604 

605 This is useful for tools that use :func:`len`, like 

606 `tqdm <https://pypi.org/project/tqdm/>`__ . 

607 

608 The wrapper doesn't validate the provided *length*, so be sure to choose 

609 a value that reflects reality. 

610 """ 

611 

612 def __init__(self, iterable, length): 

613 self._iterator = iter(iterable) 

614 self._length = length 

615 

616 def __next__(self): 

617 return next(self._iterator) 

618 

619 def __iter__(self): 

620 return self 

621 

622 def __len__(self): 

623 return self._length 

624 

625 

626def one(iterable, too_short=None, too_long=None): 

627 """Return the first item from *iterable*, which is expected to contain only 

628 that item. Raise an exception if *iterable* is empty or has more than one 

629 item. 

630 

631 :func:`one` is useful for ensuring that an iterable contains only one item. 

632 For example, it can be used to retrieve the result of a database query 

633 that is expected to return a single row. 

634 

635 If *iterable* is empty, ``ValueError`` will be raised. You may specify a 

636 different exception with the *too_short* keyword: 

637 

638 >>> it = [] 

639 >>> one(it) # doctest: +IGNORE_EXCEPTION_DETAIL 

640 Traceback (most recent call last): 

641 ... 

642 ValueError: too few items in iterable (expected 1)' 

643 >>> too_short = IndexError('too few items') 

644 >>> one(it, too_short=too_short) # doctest: +IGNORE_EXCEPTION_DETAIL 

645 Traceback (most recent call last): 

646 ... 

647 IndexError: too few items 

648 

649 Similarly, if *iterable* contains more than one item, ``ValueError`` will 

650 be raised. You may specify a different exception with the *too_long* 

651 keyword: 

652 

653 >>> it = ['too', 'many'] 

654 >>> one(it) # doctest: +IGNORE_EXCEPTION_DETAIL 

655 Traceback (most recent call last): 

656 ... 

657 ValueError: Expected exactly one item in iterable, but got 'too', 

658 'many', and perhaps more. 

659 >>> too_long = RuntimeError 

660 >>> one(it, too_long=too_long) # doctest: +IGNORE_EXCEPTION_DETAIL 

661 Traceback (most recent call last): 

662 ... 

663 RuntimeError 

664 

665 Note that :func:`one` attempts to advance *iterable* twice to ensure there 

666 is only one item. See :func:`spy` or :func:`peekable` to check iterable 

667 contents less destructively. 

668 

669 """ 

670 iterator = iter(iterable) 

671 for first in iterator: 

672 for second in iterator: 

673 if too_long is not None: 

674 raise too_long 

675 raise ValueError( 

676 f'Expected exactly one item in iterable, but got {first!r}, ' 

677 f'{second!r}, and perhaps more.' 

678 ) 

679 return first 

680 if too_short is not None: 

681 raise too_short 

682 raise ValueError('too few items in iterable (expected 1)') 

683 

684 

685def raise_(exception, *args): 

686 raise exception(*args) 

687 

688 

689def strictly_n(iterable, n, too_short=None, too_long=None): 

690 """Validate that *iterable* has exactly *n* items and return them if 

691 it does. If it has fewer than *n* items, call function *too_short* 

692 with the actual number of items. If it has more than *n* items, call function 

693 *too_long* with the number ``n + 1``. 

694 

695 >>> iterable = ['a', 'b', 'c', 'd'] 

696 >>> n = 4 

697 >>> list(strictly_n(iterable, n)) 

698 ['a', 'b', 'c', 'd'] 

699 

700 Note that the returned iterable must be consumed in order for the check to 

701 be made. 

702 

703 By default, *too_short* and *too_long* are functions that raise 

704 ``ValueError``. 

705 

706 >>> list(strictly_n('ab', 3)) # doctest: +IGNORE_EXCEPTION_DETAIL 

707 Traceback (most recent call last): 

708 ... 

709 ValueError: too few items in iterable (got 2) 

710 

711 >>> list(strictly_n('abc', 2)) # doctest: +IGNORE_EXCEPTION_DETAIL 

712 Traceback (most recent call last): 

713 ... 

714 ValueError: too many items in iterable (got at least 3) 

715 

716 You can instead supply functions that do something else. 

717 *too_short* will be called with the number of items in *iterable*. 

718 *too_long* will be called with `n + 1`. 

719 

720 >>> def too_short(item_count): 

721 ... raise RuntimeError 

722 >>> it = strictly_n('abcd', 6, too_short=too_short) 

723 >>> list(it) # doctest: +IGNORE_EXCEPTION_DETAIL 

724 Traceback (most recent call last): 

725 ... 

726 RuntimeError 

727 

728 >>> def too_long(item_count): 

729 ... print('The boss is going to hear about this') 

730 >>> it = strictly_n('abcdef', 4, too_long=too_long) 

731 >>> list(it) 

732 The boss is going to hear about this 

733 ['a', 'b', 'c', 'd'] 

734 

735 """ 

736 if too_short is None: 

737 too_short = lambda item_count: raise_( 

738 ValueError, 

739 f'Too few items in iterable (got {item_count})', 

740 ) 

741 

742 if too_long is None: 

743 too_long = lambda item_count: raise_( 

744 ValueError, 

745 f'Too many items in iterable (got at least {item_count})', 

746 ) 

747 

748 it = iter(iterable) 

749 

750 sent = 0 

751 for item in islice(it, n): 

752 yield item 

753 sent += 1 

754 

755 if sent < n: 

756 too_short(sent) 

757 return 

758 

759 for item in it: 

760 too_long(n + 1) 

761 return 

762 

763 

764def distinct_permutations(iterable, r=None): 

765 """Yield successive distinct permutations of the elements in *iterable*. 

766 

767 >>> sorted(distinct_permutations([1, 0, 1])) 

768 [(0, 1, 1), (1, 0, 1), (1, 1, 0)] 

769 

770 Equivalent to yielding from ``set(permutations(iterable))``, except 

771 duplicates are not generated and thrown away. For larger input sequences 

772 this is much more efficient. 

773 

774 If the elements of the input iterable are sortable, the output tuples are 

775 produced in sorted order. 

776 

777 Duplicate permutations arise when there are duplicated elements in the 

778 input iterable. The number of items returned is 

779 `n! / (x_1! * x_2! * ... * x_n!)`, where `n` is the total number of 

780 items input, and each `x_i` is the count of a distinct item in the input 

781 sequence. The function :func:`multinomial` computes this directly. 

782 

783 If *r* is given, only the *r*-length permutations are yielded. 

784 

785 >>> sorted(distinct_permutations([1, 0, 1], r=2)) 

786 [(0, 1), (1, 0), (1, 1)] 

787 >>> sorted(distinct_permutations(range(3), r=2)) 

788 [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)] 

789 

790 *iterable* need not be sortable, but note that using equal (``x == y``) 

791 but non-identical (``id(x) != id(y)``) elements may produce surprising 

792 behavior. For example, ``1`` and ``True`` are equal but non-identical: 

793 

794 >>> list(distinct_permutations([1, True, '3'])) # doctest: +SKIP 

795 [ 

796 (1, True, '3'), 

797 (1, '3', True), 

798 ('3', 1, True) 

799 ] 

800 >>> list(distinct_permutations([1, 2, '3'])) # doctest: +SKIP 

801 [ 

802 (1, 2, '3'), 

803 (1, '3', 2), 

804 (2, 1, '3'), 

805 (2, '3', 1), 

806 ('3', 1, 2), 

807 ('3', 2, 1) 

808 ] 

809 """ 

810 

811 # Algorithm: https://w.wiki/Qai 

812 def _full(A): 

813 while True: 

814 # Yield the permutation we have 

815 yield tuple(A) 

816 

817 # Find the largest index i such that A[i] < A[i + 1] 

818 for i in range(size - 2, -1, -1): 

819 if A[i] < A[i + 1]: 

820 break 

821 # If no such index exists, this permutation is the last one 

822 else: 

823 return 

824 

825 # Find the largest index j greater than j such that A[i] < A[j] 

826 for j in range(size - 1, i, -1): 

827 if A[i] < A[j]: 

828 break 

829 

830 # Swap the value of A[i] with that of A[j], then reverse the 

831 # sequence from A[i + 1] to form the new permutation 

832 A[i], A[j] = A[j], A[i] 

833 A[i + 1 :] = A[: i - size : -1] # A[i + 1:][::-1] 

834 

835 # Algorithm: modified from the above 

836 def _partial(A, r): 

837 # Split A into the first r items and the last r items 

838 head, tail = A[:r], A[r:] 

839 right_head_indexes = range(r - 1, -1, -1) 

840 left_tail_indexes = range(len(tail)) 

841 

842 while True: 

843 # Yield the permutation we have 

844 yield tuple(head) 

845 

846 # Starting from the right, find the first index of the head with 

847 # value smaller than the maximum value of the tail - call it i. 

848 pivot = tail[-1] 

849 for i in right_head_indexes: 

850 if head[i] < pivot: 

851 break 

852 pivot = head[i] 

853 else: 

854 return 

855 

856 # Starting from the left, find the first value of the tail 

857 # with a value greater than head[i] and swap. 

858 for j in left_tail_indexes: 

859 if tail[j] > head[i]: 

860 head[i], tail[j] = tail[j], head[i] 

861 break 

862 # If we didn't find one, start from the right and find the first 

863 # index of the head with a value greater than head[i] and swap. 

864 else: 

865 for j in right_head_indexes: 

866 if head[j] > head[i]: 

867 head[i], head[j] = head[j], head[i] 

868 break 

869 

870 # Reverse head[i + 1:] and swap it with tail[:r - (i + 1)] 

871 tail += head[: i - r : -1] # head[i + 1:][::-1] 

872 i += 1 

873 head[i:], tail[:] = tail[: r - i], tail[r - i :] 

874 

875 items = list(iterable) 

876 

877 try: 

878 items.sort() 

879 sortable = True 

880 except TypeError: 

881 sortable = False 

882 

883 indices_dict = defaultdict(list) 

884 

885 for item in items: 

886 indices_dict[items.index(item)].append(item) 

887 

888 indices = [items.index(item) for item in items] 

889 indices.sort() 

890 

891 equivalent_items = {k: cycle(v) for k, v in indices_dict.items()} 

892 

893 def permuted_items(permuted_indices): 

894 return tuple( 

895 next(equivalent_items[index]) for index in permuted_indices 

896 ) 

897 

898 size = len(items) 

899 if r is None: 

900 r = size 

901 

902 # functools.partial(_partial, ... ) 

903 algorithm = _full if (r == size) else partial(_partial, r=r) 

904 

905 if 0 < r <= size: 

906 if sortable: 

907 return algorithm(items) 

908 else: 

909 return ( 

910 permuted_items(permuted_indices) 

911 for permuted_indices in algorithm(indices) 

912 ) 

913 

914 return iter(() if r else ((),)) 

915 

916 

917def derangements(iterable, r=None): 

918 """Yield successive derangements of the elements in *iterable*. 

919 

920 A derangement is a permutation in which no element appears at its original 

921 index. In other words, a derangement is a permutation that has no fixed points. 

922 

923 Suppose Alice, Bob, Carol, and Dave are playing Secret Santa. 

924 The code below outputs all of the different ways to assign gift recipients 

925 such that nobody is assigned to himself or herself: 

926 

927 >>> for d in derangements(['Alice', 'Bob', 'Carol', 'Dave']): 

928 ... print(', '.join(d)) 

929 Bob, Alice, Dave, Carol 

930 Bob, Carol, Dave, Alice 

931 Bob, Dave, Alice, Carol 

932 Carol, Alice, Dave, Bob 

933 Carol, Dave, Alice, Bob 

934 Carol, Dave, Bob, Alice 

935 Dave, Alice, Bob, Carol 

936 Dave, Carol, Alice, Bob 

937 Dave, Carol, Bob, Alice 

938 

939 If *r* is given, only the *r*-length derangements are yielded. 

940 

941 >>> sorted(derangements(range(3), 2)) 

942 [(1, 0), (1, 2), (2, 0)] 

943 >>> sorted(derangements([0, 2, 3], 2)) 

944 [(2, 0), (2, 3), (3, 0)] 

945 

946 Elements are treated as unique based on their position, not on their value. 

947 

948 Consider the Secret Santa example with two *different* people who have 

949 the *same* name. Then there are two valid gift assignments even though 

950 it might appear that a person is assigned to themselves: 

951 

952 >>> names = ['Alice', 'Bob', 'Bob'] 

953 >>> list(derangements(names)) 

954 [('Bob', 'Bob', 'Alice'), ('Bob', 'Alice', 'Bob')] 

955 

956 To avoid confusion, make the inputs distinct: 

957 

958 >>> deduped = [f'{name}{index}' for index, name in enumerate(names)] 

959 >>> list(derangements(deduped)) 

960 [('Bob1', 'Bob2', 'Alice0'), ('Bob2', 'Alice0', 'Bob1')] 

961 

962 The number of derangements of a set of size *n* is known as the 

963 "subfactorial of n". For n > 0, the subfactorial is: 

964 ``round(math.factorial(n) / math.e)``. The more-itertools function 

965 :func:`subfactorial` computes this directly. 

966 

967 References: 

968 

969 * Article: https://www.numberanalytics.com/blog/ultimate-guide-to-derangements-in-combinatorics 

970 * Sizes: https://oeis.org/A000166 

971 """ 

972 xs = tuple(iterable) 

973 ys = tuple(range(len(xs))) 

974 return compress( 

975 permutations(xs, r=r), 

976 map(all, map(map, repeat(is_not), repeat(ys), permutations(ys, r=r))), 

977 ) 

978 

979 

980def intersperse(e, iterable, n=1): 

981 """Intersperse filler element *e* among the items in *iterable*, leaving 

982 *n* items between each filler element. 

983 

984 >>> list(intersperse('!', [1, 2, 3, 4, 5])) 

985 [1, '!', 2, '!', 3, '!', 4, '!', 5] 

986 

987 >>> list(intersperse(None, [1, 2, 3, 4, 5], n=2)) 

988 [1, 2, None, 3, 4, None, 5] 

989 

990 """ 

991 if n == 0: 

992 raise ValueError('n must be > 0') 

993 elif n == 1: 

994 # interleave(repeat(e), iterable) -> e, x_0, e, x_1, e, x_2... 

995 # islice(..., 1, None) -> x_0, e, x_1, e, x_2... 

996 return islice(interleave(repeat(e), iterable), 1, None) 

997 else: 

998 # interleave(filler, chunks) -> [e], [x_0, x_1], [e], [x_2, x_3]... 

999 # islice(..., 1, None) -> [x_0, x_1], [e], [x_2, x_3]... 

1000 # flatten(...) -> x_0, x_1, e, x_2, x_3... 

1001 filler = repeat([e]) 

1002 chunks = chunked(iterable, n) 

1003 return flatten(islice(interleave(filler, chunks), 1, None)) 

1004 

1005 

1006def unique_to_each(*iterables): 

1007 """Return the elements from each of the input iterables that aren't in the 

1008 other input iterables. 

1009 

1010 For example, suppose you have a set of packages, each with a set of 

1011 dependencies:: 

1012 

1013 {'pkg_1': {'A', 'B'}, 'pkg_2': {'B', 'C'}, 'pkg_3': {'B', 'D'}} 

1014 

1015 If you remove one package, which dependencies can also be removed? 

1016 

1017 If ``pkg_1`` is removed, then ``A`` is no longer necessary - it is not 

1018 associated with ``pkg_2`` or ``pkg_3``. Similarly, ``C`` is only needed for 

1019 ``pkg_2``, and ``D`` is only needed for ``pkg_3``:: 

1020 

1021 >>> unique_to_each({'A', 'B'}, {'B', 'C'}, {'B', 'D'}) 

1022 [['A'], ['C'], ['D']] 

1023 

1024 If there are duplicates in one input iterable that aren't in the others 

1025 they will be duplicated in the output. Input order is preserved:: 

1026 

1027 >>> unique_to_each("mississippi", "missouri") 

1028 [['p', 'p'], ['o', 'u', 'r']] 

1029 

1030 It is assumed that the elements of each iterable are hashable. 

1031 

1032 """ 

1033 pool = [list(it) for it in iterables] 

1034 counts = Counter(chain.from_iterable(map(set, pool))) 

1035 uniques = {element for element in counts if counts[element] == 1} 

1036 return [list(filter(uniques.__contains__, it)) for it in pool] 

1037 

1038 

1039def windowed(seq, n, fillvalue=None, step=1): 

1040 """Return a sliding window of width *n* over the given iterable. 

1041 

1042 >>> all_windows = windowed([1, 2, 3, 4, 5], 3) 

1043 >>> list(all_windows) 

1044 [(1, 2, 3), (2, 3, 4), (3, 4, 5)] 

1045 

1046 When the window is larger than the iterable, *fillvalue* is used in place 

1047 of missing values: 

1048 

1049 >>> list(windowed([1, 2, 3], 4)) 

1050 [(1, 2, 3, None)] 

1051 

1052 Each window will advance in increments of *step*: 

1053 

1054 >>> list(windowed([1, 2, 3, 4, 5, 6], 3, fillvalue='!', step=2)) 

1055 [(1, 2, 3), (3, 4, 5), (5, 6, '!')] 

1056 

1057 To slide into the iterable's items, use :func:`chain` to add filler items 

1058 to the left: 

1059 

1060 >>> iterable = [1, 2, 3, 4] 

1061 >>> n = 3 

1062 >>> padding = [None] * (n - 1) 

1063 >>> list(windowed(chain(padding, iterable), 3)) 

1064 [(None, None, 1), (None, 1, 2), (1, 2, 3), (2, 3, 4)] 

1065 """ 

1066 if n <= 0: 

1067 raise ValueError('n must be > 0') 

1068 if step < 1: 

1069 raise ValueError('step must be >= 1') 

1070 

1071 iterator = iter(seq) 

1072 

1073 # Generate first window 

1074 window = deque(islice(iterator, n), maxlen=n) 

1075 

1076 # Deal with the first window not being full 

1077 if not window: 

1078 return 

1079 if len(window) < n: 

1080 yield tuple(window) + ((fillvalue,) * (n - len(window))) 

1081 return 

1082 yield tuple(window) 

1083 

1084 # Create the filler for the next windows. The padding ensures 

1085 # we have just enough elements to fill the last window. 

1086 padding = (fillvalue,) * (n - 1 if step >= n else step - 1) 

1087 filler = map(window.append, chain(iterator, padding)) 

1088 

1089 # Generate the rest of the windows 

1090 for _ in islice(filler, step - 1, None, step): 

1091 yield tuple(window) 

1092 

1093 

1094def substrings(iterable): 

1095 """Yield all of the substrings of *iterable*. 

1096 

1097 >>> [''.join(s) for s in substrings('more')] 

1098 ['m', 'o', 'r', 'e', 'mo', 'or', 're', 'mor', 'ore', 'more'] 

1099 

1100 Note that non-string iterables can also be subdivided. 

1101 

1102 >>> list(substrings([0, 1, 2])) 

1103 [(0,), (1,), (2,), (0, 1), (1, 2), (0, 1, 2)] 

1104 

1105 Like subslices() but returns tuples instead of lists 

1106 and returns the shortest substrings first. 

1107 

1108 """ 

1109 seq = tuple(iterable) 

1110 item_count = len(seq) 

1111 for n in range(1, item_count + 1): 

1112 slices = map(slice, range(item_count), range(n, item_count + 1)) 

1113 yield from map(getitem, repeat(seq), slices) 

1114 

1115 

1116def substrings_indexes(seq, reverse=False): 

1117 """Yield all substrings and their positions in *seq* 

1118 

1119 The items yielded will be a tuple of the form ``(substr, i, j)``, where 

1120 ``substr == seq[i:j]``. 

1121 

1122 This function only works for iterables that support slicing, such as 

1123 ``str`` objects. 

1124 

1125 >>> for item in substrings_indexes('more'): 

1126 ... print(item) 

1127 ('m', 0, 1) 

1128 ('o', 1, 2) 

1129 ('r', 2, 3) 

1130 ('e', 3, 4) 

1131 ('mo', 0, 2) 

1132 ('or', 1, 3) 

1133 ('re', 2, 4) 

1134 ('mor', 0, 3) 

1135 ('ore', 1, 4) 

1136 ('more', 0, 4) 

1137 

1138 Set *reverse* to ``True`` to yield the same items in the opposite order. 

1139 

1140 

1141 """ 

1142 r = range(1, len(seq) + 1) 

1143 if reverse: 

1144 r = reversed(r) 

1145 return ( 

1146 (seq[i : i + L], i, i + L) for L in r for i in range(len(seq) - L + 1) 

1147 ) 

1148 

1149 

1150class bucket: 

1151 """Wrap *iterable* and return an object that buckets the iterable into 

1152 child iterables based on a *key* function. 

1153 

1154 >>> iterable = ['a1', 'b1', 'c1', 'a2', 'b2', 'c2', 'b3'] 

1155 >>> s = bucket(iterable, key=lambda x: x[0]) # Bucket by 1st character 

1156 >>> sorted(list(s)) # Get the keys 

1157 ['a', 'b', 'c'] 

1158 >>> a_iterable = s['a'] 

1159 >>> next(a_iterable) 

1160 'a1' 

1161 >>> next(a_iterable) 

1162 'a2' 

1163 >>> list(s['b']) 

1164 ['b1', 'b2', 'b3'] 

1165 

1166 The original iterable will be advanced and its items will be cached until 

1167 they are used by the child iterables. This may require significant storage. 

1168 

1169 By default, attempting to select a bucket to which no items belong will 

1170 exhaust the iterable and cache all values. 

1171 If you specify a *validator* function, selected buckets will instead be 

1172 checked against it. 

1173 

1174 >>> from itertools import count 

1175 >>> it = count(1, 2) # Infinite sequence of odd numbers 

1176 >>> key = lambda x: x % 10 # Bucket by last digit 

1177 >>> validator = lambda x: x in {1, 3, 5, 7, 9} # Odd digits only 

1178 >>> s = bucket(it, key=key, validator=validator) 

1179 >>> 2 in s 

1180 False 

1181 >>> list(s[2]) 

1182 [] 

1183 

1184 .. seealso:: :func:`map_reduce`, :func:`groupby_transform` 

1185 

1186 If storage is not a concern, :func:`map_reduce` returns a Python 

1187 dictionary, which is generally easier to work with. If the elements 

1188 with the same key are already adjacent, :func:`groupby_transform` 

1189 or :func:`itertools.groupby` can be used without any caching overhead. 

1190 

1191 """ 

1192 

1193 def __init__(self, iterable, key, validator=None): 

1194 self._it = iter(iterable) 

1195 self._key = key 

1196 self._cache = defaultdict(deque) 

1197 # Use ``is None`` rather than truthiness: a valid validator may be a 

1198 # callable object that is falsey (e.g. an empty ``set`` subclass with 

1199 # ``__call__``), and ``validator or ...`` would silently replace it. 

1200 self._validator = (lambda x: True) if validator is None else validator 

1201 

1202 def __contains__(self, value): 

1203 if not self._validator(value): 

1204 return False 

1205 

1206 try: 

1207 item = next(self[value]) 

1208 except StopIteration: 

1209 return False 

1210 else: 

1211 self._cache[value].appendleft(item) 

1212 

1213 return True 

1214 

1215 def _get_values(self, value): 

1216 """ 

1217 Helper to yield items from the parent iterator that match *value*. 

1218 Items that don't match are stored in the local cache as they 

1219 are encountered. 

1220 """ 

1221 while True: 

1222 # If we've cached some items that match the target value, emit 

1223 # the first one and evict it from the cache. 

1224 if self._cache.get(value): 

1225 yield self._cache[value].popleft() 

1226 # Otherwise we need to advance the parent iterator to search for 

1227 # a matching item, caching the rest. 

1228 else: 

1229 while True: 

1230 try: 

1231 item = next(self._it) 

1232 except StopIteration: 

1233 return 

1234 item_value = self._key(item) 

1235 if item_value == value: 

1236 if value not in self._cache: 

1237 self._cache[value] = deque() 

1238 yield item 

1239 break 

1240 elif self._validator(item_value): 

1241 self._cache[item_value].append(item) 

1242 

1243 def __iter__(self): 

1244 for item in self._it: 

1245 item_value = self._key(item) 

1246 if self._validator(item_value): 

1247 self._cache[item_value].append(item) 

1248 

1249 return iter(self._cache) 

1250 

1251 def __getitem__(self, value): 

1252 if not self._validator(value): 

1253 return iter(()) 

1254 

1255 return self._get_values(value) 

1256 

1257 

1258def spy(iterable, n=1): 

1259 """Return a 2-tuple with a list containing the first *n* elements of 

1260 *iterable*, and an iterator with the same items as *iterable*. 

1261 This allows you to "look ahead" at the items in the iterable without 

1262 advancing it. 

1263 

1264 There is one item in the list by default: 

1265 

1266 >>> iterable = 'abcdefg' 

1267 >>> head, iterable = spy(iterable) 

1268 >>> head 

1269 ['a'] 

1270 >>> list(iterable) 

1271 ['a', 'b', 'c', 'd', 'e', 'f', 'g'] 

1272 

1273 You may use unpacking to retrieve items instead of lists: 

1274 

1275 >>> (head,), iterable = spy('abcdefg') 

1276 >>> head 

1277 'a' 

1278 >>> (first, second), iterable = spy('abcdefg', 2) 

1279 >>> first 

1280 'a' 

1281 >>> second 

1282 'b' 

1283 

1284 The number of items requested can be larger than the number of items in 

1285 the iterable: 

1286 

1287 >>> iterable = [1, 2, 3, 4, 5] 

1288 >>> head, iterable = spy(iterable, 10) 

1289 >>> head 

1290 [1, 2, 3, 4, 5] 

1291 >>> list(iterable) 

1292 [1, 2, 3, 4, 5] 

1293 

1294 """ 

1295 p, q = tee(iterable) 

1296 return take(n, q), p 

1297 

1298 

1299def interleave(*iterables): 

1300 """Return a new iterable yielding from each iterable in turn, 

1301 until the shortest is exhausted. 

1302 

1303 >>> list(interleave([1, 2, 3], [4, 5], [6, 7, 8])) 

1304 [1, 4, 6, 2, 5, 7] 

1305 

1306 For a version that doesn't terminate after the shortest iterable is 

1307 exhausted, see :func:`interleave_longest`. 

1308 

1309 """ 

1310 return chain.from_iterable(zip(*iterables)) 

1311 

1312 

1313def interleave_longest(*iterables): 

1314 """Return a new iterable yielding from each iterable in turn, 

1315 skipping any that are exhausted. 

1316 

1317 >>> list(interleave_longest([1, 2, 3], [4, 5], [6, 7, 8])) 

1318 [1, 4, 6, 2, 5, 7, 3, 8] 

1319 

1320 This function produces the same output as :func:`roundrobin`, but may 

1321 perform better for some inputs (in particular when the number of iterables 

1322 is large). 

1323 

1324 """ 

1325 i = flatten(zip_longest(*iterables, fillvalue=_marker)) 

1326 return filter(partial(is_not, _marker), i) 

1327 

1328 

1329def interleave_evenly(iterables, lengths=None): 

1330 """ 

1331 Interleave multiple iterables so that their elements are evenly distributed 

1332 throughout the output sequence. 

1333 

1334 >>> iterables = [1, 2, 3, 4, 5], ['a', 'b'] 

1335 >>> list(interleave_evenly(iterables)) 

1336 [1, 2, 'a', 3, 4, 'b', 5] 

1337 

1338 >>> iterables = [[1, 2, 3], [4, 5], [6, 7, 8]] 

1339 >>> list(interleave_evenly(iterables)) 

1340 [1, 6, 4, 2, 7, 3, 8, 5] 

1341 

1342 This function requires iterables of known length. Iterables without 

1343 ``__len__()`` can be used by manually specifying lengths with *lengths*: 

1344 

1345 >>> from itertools import combinations, repeat 

1346 >>> iterables = [combinations(range(4), 2), ['a', 'b', 'c']] 

1347 >>> lengths = [4 * (4 - 1) // 2, 3] 

1348 >>> list(interleave_evenly(iterables, lengths=lengths)) 

1349 [(0, 1), (0, 2), 'a', (0, 3), (1, 2), 'b', (1, 3), (2, 3), 'c'] 

1350 

1351 Based on Bresenham's algorithm. 

1352 """ 

1353 if lengths is None: 

1354 try: 

1355 lengths = [len(it) for it in iterables] 

1356 except TypeError: 

1357 raise ValueError( 

1358 'Iterable lengths could not be determined automatically. ' 

1359 'Specify them with the lengths keyword.' 

1360 ) 

1361 elif len(iterables) != len(lengths): 

1362 raise ValueError('Mismatching number of iterables and lengths.') 

1363 

1364 dims = len(lengths) 

1365 

1366 if not dims: 

1367 return 

1368 

1369 # sort iterables by length, descending 

1370 lengths_permute = sorted( 

1371 range(dims), key=lambda i: lengths[i], reverse=True 

1372 ) 

1373 lengths_desc = [lengths[i] for i in lengths_permute] 

1374 iters_desc = [iter(iterables[i]) for i in lengths_permute] 

1375 

1376 # the longest iterable is the primary one (Bresenham: the longest 

1377 # distance along an axis) 

1378 delta_primary, deltas_secondary = lengths_desc[0], lengths_desc[1:] 

1379 iter_primary, iters_secondary = iters_desc[0], iters_desc[1:] 

1380 errors = [delta_primary // dims] * len(deltas_secondary) 

1381 

1382 to_yield = sum(lengths) 

1383 while to_yield: 

1384 yield next(iter_primary) 

1385 to_yield -= 1 

1386 # update errors for each secondary iterable 

1387 errors = [e - delta for e, delta in zip(errors, deltas_secondary)] 

1388 

1389 # those iterables for which the error is negative are yielded 

1390 # ("diagonal step" in Bresenham) 

1391 for i, e_ in enumerate(errors): 

1392 if e_ < 0: 

1393 yield next(iters_secondary[i]) 

1394 to_yield -= 1 

1395 errors[i] += delta_primary 

1396 

1397 

1398def interleave_randomly(*iterables): 

1399 """Repeatedly select one of the input *iterables* at random and yield the next 

1400 item from it. 

1401 

1402 >>> iterables = [1, 2, 3], 'abc', (True, False, None) 

1403 >>> list(interleave_randomly(*iterables)) # doctest: +SKIP 

1404 ['a', 'b', 1, 'c', True, False, None, 2, 3] 

1405 

1406 The relative order of the items in each input iterable will preserved. Note the 

1407 sequences of items with this property are not equally likely to be generated. 

1408 

1409 """ 

1410 iterators = [iter(e) for e in iterables] 

1411 while iterators: 

1412 idx = randrange(len(iterators)) 

1413 try: 

1414 yield next(iterators[idx]) 

1415 except StopIteration: 

1416 # equivalent to `list.pop` but slightly faster 

1417 iterators[idx] = iterators[-1] 

1418 del iterators[-1] 

1419 

1420 

1421def collapse(iterable, base_type=None, levels=None): 

1422 """Flatten an iterable with multiple levels of nesting (e.g., a list of 

1423 lists of tuples) into non-iterable types. 

1424 

1425 >>> iterable = [(1, 2), ([3, 4], [[5], [6]])] 

1426 >>> list(collapse(iterable)) 

1427 [1, 2, 3, 4, 5, 6] 

1428 

1429 Binary and text strings are not considered iterable and 

1430 will not be collapsed. 

1431 

1432 To avoid collapsing other types, specify *base_type*: 

1433 

1434 >>> iterable = ['ab', ('cd', 'ef'), ['gh', 'ij']] 

1435 >>> list(collapse(iterable, base_type=tuple)) 

1436 ['ab', ('cd', 'ef'), 'gh', 'ij'] 

1437 

1438 Specify *levels* to stop flattening after a certain level: 

1439 

1440 >>> iterable = [('a', ['b']), ('c', ['d'])] 

1441 >>> list(collapse(iterable)) # Fully flattened 

1442 ['a', 'b', 'c', 'd'] 

1443 >>> list(collapse(iterable, levels=1)) # Only one level flattened 

1444 ['a', ['b'], 'c', ['d']] 

1445 

1446 """ 

1447 stack = deque() 

1448 # Add our first node group, treat the iterable as a single node 

1449 stack.appendleft((0, repeat(iterable, 1))) 

1450 

1451 while stack: 

1452 node_group = stack.popleft() 

1453 level, nodes = node_group 

1454 

1455 # Check if beyond max level 

1456 if levels is not None and level > levels: 

1457 yield from nodes 

1458 continue 

1459 

1460 for node in nodes: 

1461 # Check if done iterating 

1462 if isinstance(node, (str, bytes)) or ( 

1463 (base_type is not None) and isinstance(node, base_type) 

1464 ): 

1465 yield node 

1466 # Otherwise try to create child nodes 

1467 else: 

1468 try: 

1469 tree = iter(node) 

1470 except TypeError: 

1471 yield node 

1472 else: 

1473 # Save our current location 

1474 stack.appendleft(node_group) 

1475 # Append the new child node 

1476 stack.appendleft((level + 1, tree)) 

1477 # Break to process child node 

1478 break 

1479 

1480 

1481def side_effect(func, iterable, chunk_size=None, before=None, after=None): 

1482 """Invoke *func* on each item in *iterable* (or on each *chunk_size* group 

1483 of items) before yielding the item. 

1484 

1485 `func` must be a function that takes a single argument. Its return value 

1486 will be discarded. 

1487 

1488 *before* and *after* are optional functions that take no arguments. They 

1489 will be executed before iteration starts and after it ends, respectively. 

1490 

1491 `side_effect` can be used for logging, updating progress bars, or anything 

1492 that is not functionally "pure." 

1493 

1494 Emitting a status message: 

1495 

1496 >>> from more_itertools import consume 

1497 >>> func = lambda item: print('Received {}'.format(item)) 

1498 >>> consume(side_effect(func, range(2))) 

1499 Received 0 

1500 Received 1 

1501 

1502 Operating on chunks of items: 

1503 

1504 >>> pair_sums = [] 

1505 >>> func = lambda chunk: pair_sums.append(sum(chunk)) 

1506 >>> list(side_effect(func, [0, 1, 2, 3, 4, 5], 2)) 

1507 [0, 1, 2, 3, 4, 5] 

1508 >>> list(pair_sums) 

1509 [1, 5, 9] 

1510 

1511 Writing to a file-like object: 

1512 

1513 >>> from io import StringIO 

1514 >>> from more_itertools import consume 

1515 >>> f = StringIO() 

1516 >>> func = lambda x: print(x, file=f) 

1517 >>> before = lambda: print('HEADER', file=f) 

1518 >>> after = f.close 

1519 >>> it = ['a', 'b', 'c'] 

1520 >>> consume(side_effect(func, it, before=before, after=after)) 

1521 >>> f.closed 

1522 True 

1523 

1524 """ 

1525 try: 

1526 if before is not None: 

1527 before() 

1528 

1529 if chunk_size is None: 

1530 for item in iterable: 

1531 func(item) 

1532 yield item 

1533 else: 

1534 for chunk in chunked(iterable, chunk_size): 

1535 func(chunk) 

1536 yield from chunk 

1537 finally: 

1538 if after is not None: 

1539 after() 

1540 

1541 

1542def sliced(seq, n, strict=False): 

1543 """Yield slices of length *n* from the sequence *seq*. 

1544 

1545 >>> list(sliced((1, 2, 3, 4, 5, 6), 3)) 

1546 [(1, 2, 3), (4, 5, 6)] 

1547 

1548 By the default, the last yielded slice will have fewer than *n* elements 

1549 if the length of *seq* is not divisible by *n*: 

1550 

1551 >>> list(sliced((1, 2, 3, 4, 5, 6, 7, 8), 3)) 

1552 [(1, 2, 3), (4, 5, 6), (7, 8)] 

1553 

1554 If the length of *seq* is not divisible by *n* and *strict* is 

1555 ``True``, then ``ValueError`` will be raised before the last 

1556 slice is yielded. 

1557 

1558 This function will only work for iterables that support slicing. 

1559 For non-sliceable iterables, see :func:`chunked`. 

1560 

1561 """ 

1562 if n < 0: 

1563 raise ValueError('n must be at least 0') 

1564 

1565 iterator = takewhile(len, (seq[i : i + n] for i in count(0, n))) 

1566 if strict: 

1567 

1568 def ret(): 

1569 for _slice in iterator: 

1570 if len(_slice) != n: 

1571 raise ValueError("seq is not divisible by n.") 

1572 yield _slice 

1573 

1574 return ret() 

1575 else: 

1576 return iterator 

1577 

1578 

1579def split_at(iterable, pred, maxsplit=-1, keep_separator=False): 

1580 """Yield lists of items from *iterable*, where each list is delimited by 

1581 an item where callable *pred* returns ``True``. 

1582 

1583 >>> list(split_at('abcdcba', lambda x: x == 'b')) 

1584 [['a'], ['c', 'd', 'c'], ['a']] 

1585 

1586 >>> list(split_at(range(10), lambda n: n % 2 == 1)) 

1587 [[0], [2], [4], [6], [8], []] 

1588 

1589 At most *maxsplit* splits are done. If *maxsplit* is not specified or -1, 

1590 then there is no limit on the number of splits: 

1591 

1592 >>> list(split_at(range(10), lambda n: n % 2 == 1, maxsplit=2)) 

1593 [[0], [2], [4, 5, 6, 7, 8, 9]] 

1594 

1595 By default, the delimiting items are not included in the output. 

1596 To include them, set *keep_separator* to ``True``. 

1597 

1598 >>> list(split_at('abcdcba', lambda x: x == 'b', keep_separator=True)) 

1599 [['a'], ['b'], ['c', 'd', 'c'], ['b'], ['a']] 

1600 

1601 """ 

1602 if maxsplit == 0: 

1603 yield list(iterable) 

1604 return 

1605 

1606 buf = [] 

1607 it = iter(iterable) 

1608 for item in it: 

1609 if pred(item): 

1610 yield buf 

1611 if keep_separator: 

1612 yield [item] 

1613 if maxsplit == 1: 

1614 yield list(it) 

1615 return 

1616 buf = [] 

1617 maxsplit -= 1 

1618 else: 

1619 buf.append(item) 

1620 yield buf 

1621 

1622 

1623def split_before(iterable, pred, maxsplit=-1): 

1624 """Yield lists of items from *iterable*, where each list ends just before 

1625 an item for which callable *pred* returns ``True``: 

1626 

1627 >>> list(split_before('OneTwo', lambda s: s.isupper())) 

1628 [['O', 'n', 'e'], ['T', 'w', 'o']] 

1629 

1630 >>> list(split_before(range(10), lambda n: n % 3 == 0)) 

1631 [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]] 

1632 

1633 At most *maxsplit* splits are done. If *maxsplit* is not specified or -1, 

1634 then there is no limit on the number of splits: 

1635 

1636 >>> list(split_before(range(10), lambda n: n % 3 == 0, maxsplit=2)) 

1637 [[0, 1, 2], [3, 4, 5], [6, 7, 8, 9]] 

1638 """ 

1639 if maxsplit == 0: 

1640 buf = list(iterable) 

1641 if buf: 

1642 yield buf 

1643 return 

1644 

1645 buf = [] 

1646 it = iter(iterable) 

1647 for item in it: 

1648 if pred(item) and buf: 

1649 yield buf 

1650 if maxsplit == 1: 

1651 yield [item, *it] 

1652 return 

1653 buf = [] 

1654 maxsplit -= 1 

1655 buf.append(item) 

1656 if buf: 

1657 yield buf 

1658 

1659 

1660def split_after(iterable, pred, maxsplit=-1): 

1661 """Yield lists of items from *iterable*, where each list ends with an 

1662 item where callable *pred* returns ``True``: 

1663 

1664 >>> list(split_after('one1two2', lambda s: s.isdigit())) 

1665 [['o', 'n', 'e', '1'], ['t', 'w', 'o', '2']] 

1666 

1667 >>> list(split_after(range(10), lambda n: n % 3 == 0)) 

1668 [[0], [1, 2, 3], [4, 5, 6], [7, 8, 9]] 

1669 

1670 At most *maxsplit* splits are done. If *maxsplit* is not specified or -1, 

1671 then there is no limit on the number of splits: 

1672 

1673 >>> list(split_after(range(10), lambda n: n % 3 == 0, maxsplit=2)) 

1674 [[0], [1, 2, 3], [4, 5, 6, 7, 8, 9]] 

1675 

1676 """ 

1677 if maxsplit == 0: 

1678 buf = list(iterable) 

1679 if buf: 

1680 yield buf 

1681 return 

1682 

1683 buf = [] 

1684 it = iter(iterable) 

1685 for item in it: 

1686 buf.append(item) 

1687 if pred(item) and buf: 

1688 yield buf 

1689 if maxsplit == 1: 

1690 buf = list(it) 

1691 if buf: 

1692 yield buf 

1693 return 

1694 buf = [] 

1695 maxsplit -= 1 

1696 if buf: 

1697 yield buf 

1698 

1699 

1700def split_when(iterable, pred, maxsplit=-1): 

1701 """Split *iterable* into pieces based on the output of *pred*. 

1702 *pred* should be a function that takes successive pairs of items and 

1703 returns ``True`` if the iterable should be split in between them. 

1704 

1705 For example, to find runs of increasing numbers, split the iterable when 

1706 element ``i`` is larger than element ``i + 1``: 

1707 

1708 >>> list(split_when([1, 2, 3, 3, 2, 5, 2, 4, 2], lambda x, y: x > y)) 

1709 [[1, 2, 3, 3], [2, 5], [2, 4], [2]] 

1710 

1711 At most *maxsplit* splits are done. If *maxsplit* is not specified or -1, 

1712 then there is no limit on the number of splits: 

1713 

1714 >>> list(split_when([1, 2, 3, 3, 2, 5, 2, 4, 2], 

1715 ... lambda x, y: x > y, maxsplit=2)) 

1716 [[1, 2, 3, 3], [2, 5], [2, 4, 2]] 

1717 

1718 """ 

1719 if maxsplit == 0: 

1720 buf = list(iterable) 

1721 if buf: 

1722 yield buf 

1723 return 

1724 

1725 it = iter(iterable) 

1726 try: 

1727 cur_item = next(it) 

1728 except StopIteration: 

1729 return 

1730 

1731 buf = [cur_item] 

1732 for next_item in it: 

1733 if pred(cur_item, next_item): 

1734 yield buf 

1735 if maxsplit == 1: 

1736 yield [next_item, *it] 

1737 return 

1738 buf = [] 

1739 maxsplit -= 1 

1740 

1741 buf.append(next_item) 

1742 cur_item = next_item 

1743 

1744 yield buf 

1745 

1746 

1747def split_into(iterable, sizes): 

1748 """Yield a list of sequential items from *iterable* of length 'n' for each 

1749 integer 'n' in *sizes*. 

1750 

1751 >>> list(split_into([1,2,3,4,5,6], [1,2,3])) 

1752 [[1], [2, 3], [4, 5, 6]] 

1753 

1754 If the sum of *sizes* is smaller than the length of *iterable*, then the 

1755 remaining items of *iterable* will not be returned. 

1756 

1757 >>> list(split_into([1,2,3,4,5,6], [2,3])) 

1758 [[1, 2], [3, 4, 5]] 

1759 

1760 If the sum of *sizes* is larger than the length of *iterable*, fewer items 

1761 will be returned in the iteration that overruns the *iterable* and further 

1762 lists will be empty: 

1763 

1764 >>> list(split_into([1,2,3,4], [1,2,3,4])) 

1765 [[1], [2, 3], [4], []] 

1766 

1767 When a ``None`` object is encountered in *sizes*, the returned list will 

1768 contain items up to the end of *iterable* the same way that 

1769 :func:`itertools.slice` does: 

1770 

1771 >>> list(split_into([1,2,3,4,5,6,7,8,9,0], [2,3,None])) 

1772 [[1, 2], [3, 4, 5], [6, 7, 8, 9, 0]] 

1773 

1774 :func:`split_into` can be useful for grouping a series of items where the 

1775 sizes of the groups are not uniform. An example would be where in a row 

1776 from a table, multiple columns represent elements of the same feature 

1777 (e.g. a point represented by x,y,z) but, the format is not the same for 

1778 all columns. 

1779 """ 

1780 # convert the iterable argument into an iterator so its contents can 

1781 # be consumed by islice in case it is a generator 

1782 it = iter(iterable) 

1783 

1784 for size in sizes: 

1785 if size is None: 

1786 yield list(it) 

1787 return 

1788 else: 

1789 yield list(islice(it, size)) 

1790 

1791 

1792def padded(iterable, fillvalue=None, n=None, next_multiple=False): 

1793 """Yield the elements from *iterable*, followed by *fillvalue*, such that 

1794 at least *n* items are emitted. 

1795 

1796 >>> list(padded([1, 2, 3], '?', 5)) 

1797 [1, 2, 3, '?', '?'] 

1798 

1799 If *next_multiple* is ``True``, *fillvalue* will be emitted until the 

1800 number of items emitted is a multiple of *n*: 

1801 

1802 >>> list(padded([1, 2, 3, 4], n=3, next_multiple=True)) 

1803 [1, 2, 3, 4, None, None] 

1804 

1805 If *n* is ``None``, *fillvalue* will be emitted indefinitely. 

1806 

1807 To create an *iterable* of exactly size *n*, you can truncate with 

1808 :func:`islice`. 

1809 

1810 >>> list(islice(padded([1, 2, 3], '?'), 5)) 

1811 [1, 2, 3, '?', '?'] 

1812 >>> list(islice(padded([1, 2, 3, 4, 5, 6, 7, 8], '?'), 5)) 

1813 [1, 2, 3, 4, 5] 

1814 

1815 """ 

1816 iterator = iter(iterable) 

1817 iterator_with_repeat = chain(iterator, repeat(fillvalue)) 

1818 

1819 if n is None: 

1820 return iterator_with_repeat 

1821 elif n < 1: 

1822 raise ValueError('n must be at least 1') 

1823 elif next_multiple: 

1824 

1825 def slice_generator(): 

1826 for first in iterator: 

1827 yield (first,) 

1828 yield islice(iterator_with_repeat, n - 1) 

1829 

1830 # While elements exist produce slices of size n 

1831 return chain.from_iterable(slice_generator()) 

1832 else: 

1833 # Ensure the first batch is at least size n then iterate 

1834 return chain(islice(iterator_with_repeat, n), iterator) 

1835 

1836 

1837def repeat_each(iterable, n=2): 

1838 """Repeat each element in *iterable* *n* times. 

1839 

1840 >>> list(repeat_each('ABC', 3)) 

1841 ['A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C'] 

1842 """ 

1843 return chain.from_iterable(map(repeat, iterable, repeat(n))) 

1844 

1845 

1846def repeat_last(iterable, default=None): 

1847 """After the *iterable* is exhausted, keep yielding its last element. 

1848 

1849 >>> list(islice(repeat_last(range(3)), 5)) 

1850 [0, 1, 2, 2, 2] 

1851 

1852 If the iterable is empty, yield *default* forever:: 

1853 

1854 >>> list(islice(repeat_last(range(0), 42), 5)) 

1855 [42, 42, 42, 42, 42] 

1856 

1857 """ 

1858 item = _marker 

1859 for item in iterable: 

1860 yield item 

1861 final = default if item is _marker else item 

1862 yield from repeat(final) 

1863 

1864 

1865def distribute(n, iterable): 

1866 """Distribute the items from *iterable* among *n* smaller iterables. 

1867 

1868 >>> group_1, group_2 = distribute(2, [1, 2, 3, 4, 5, 6]) 

1869 >>> list(group_1) 

1870 [1, 3, 5] 

1871 >>> list(group_2) 

1872 [2, 4, 6] 

1873 

1874 If the length of *iterable* is not evenly divisible by *n*, then the 

1875 length of the returned iterables will not be identical: 

1876 

1877 >>> children = distribute(3, [1, 2, 3, 4, 5, 6, 7]) 

1878 >>> [list(c) for c in children] 

1879 [[1, 4, 7], [2, 5], [3, 6]] 

1880 

1881 If the length of *iterable* is smaller than *n*, then the last returned 

1882 iterables will be empty: 

1883 

1884 >>> children = distribute(5, [1, 2, 3]) 

1885 >>> [list(c) for c in children] 

1886 [[1], [2], [3], [], []] 

1887 

1888 This function uses :func:`itertools.tee` and may require significant 

1889 storage. 

1890 

1891 If you need the order items in the smaller iterables to match the 

1892 original iterable, see :func:`divide`. 

1893 

1894 """ 

1895 if n < 1: 

1896 raise ValueError('n must be at least 1') 

1897 

1898 children = tee(iterable, n) 

1899 return [islice(it, index, None, n) for index, it in enumerate(children)] 

1900 

1901 

1902def stagger(iterable, offsets=(-1, 0, 1), longest=False, fillvalue=None): 

1903 """Yield tuples whose elements are offset from *iterable*. 

1904 The amount by which the `i`-th item in each tuple is offset is given by 

1905 the `i`-th item in *offsets*. 

1906 

1907 >>> list(stagger([0, 1, 2, 3])) 

1908 [(None, 0, 1), (0, 1, 2), (1, 2, 3)] 

1909 >>> list(stagger(range(8), offsets=(0, 2, 4))) 

1910 [(0, 2, 4), (1, 3, 5), (2, 4, 6), (3, 5, 7)] 

1911 

1912 By default, the sequence will end when the final element of a tuple is the 

1913 last item in the iterable. To continue until the first element of a tuple 

1914 is the last item in the iterable, set *longest* to ``True``:: 

1915 

1916 >>> list(stagger([0, 1, 2, 3], longest=True)) 

1917 [(None, 0, 1), (0, 1, 2), (1, 2, 3), (2, 3, None), (3, None, None)] 

1918 

1919 By default, ``None`` will be used to replace offsets beyond the end of the 

1920 sequence. Specify *fillvalue* to use some other value. 

1921 

1922 """ 

1923 children = tee(iterable, len(offsets)) 

1924 

1925 return zip_offset( 

1926 *children, offsets=offsets, longest=longest, fillvalue=fillvalue 

1927 ) 

1928 

1929 

1930def zip_offset(*iterables, offsets, longest=False, fillvalue=None): 

1931 """``zip`` the input *iterables* together, but offset the `i`-th iterable 

1932 by the `i`-th item in *offsets*. 

1933 

1934 >>> list(zip_offset('0123', 'abcdef', offsets=(0, 1))) 

1935 [('0', 'b'), ('1', 'c'), ('2', 'd'), ('3', 'e')] 

1936 

1937 This can be used as a lightweight alternative to SciPy or pandas to analyze 

1938 data sets in which some series have a lead or lag relationship. 

1939 

1940 By default, the sequence will end when the shortest iterable is exhausted. 

1941 To continue until the longest iterable is exhausted, set *longest* to 

1942 ``True``. 

1943 

1944 >>> list(zip_offset('0123', 'abcdef', offsets=(0, 1), longest=True)) 

1945 [('0', 'b'), ('1', 'c'), ('2', 'd'), ('3', 'e'), (None, 'f')] 

1946 

1947 By default, ``None`` will be used to replace offsets beyond the end of the 

1948 sequence. Specify *fillvalue* to use some other value. 

1949 

1950 """ 

1951 if len(iterables) != len(offsets): 

1952 raise ValueError("Number of iterables and offsets didn't match") 

1953 

1954 staggered = [] 

1955 for it, n in zip(iterables, offsets): 

1956 if n < 0: 

1957 staggered.append(chain(repeat(fillvalue, -n), it)) 

1958 elif n > 0: 

1959 staggered.append(islice(it, n, None)) 

1960 else: 

1961 staggered.append(it) 

1962 

1963 if longest: 

1964 return zip_longest(*staggered, fillvalue=fillvalue) 

1965 

1966 return zip(*staggered) 

1967 

1968 

1969def sort_together( 

1970 iterables, key_list=(0,), key=None, reverse=False, strict=False 

1971): 

1972 """Return the input iterables sorted together, with *key_list* as the 

1973 priority for sorting. All iterables are trimmed to the length of the 

1974 shortest one. 

1975 

1976 This can be used like the sorting function in a spreadsheet. If each 

1977 iterable represents a column of data, the key list determines which 

1978 columns are used for sorting. 

1979 

1980 By default, all iterables are sorted using the ``0``-th iterable:: 

1981 

1982 >>> iterables = [(4, 3, 2, 1), ('a', 'b', 'c', 'd')] 

1983 >>> sort_together(iterables) 

1984 [(1, 2, 3, 4), ('d', 'c', 'b', 'a')] 

1985 

1986 Set a different key list to sort according to another iterable. 

1987 Specifying multiple keys dictates how ties are broken:: 

1988 

1989 >>> iterables = [(3, 1, 2), (0, 1, 0), ('c', 'b', 'a')] 

1990 >>> sort_together(iterables, key_list=(1, 2)) 

1991 [(2, 3, 1), (0, 0, 1), ('a', 'c', 'b')] 

1992 

1993 To sort by a function of the elements of the iterable, pass a *key* 

1994 function. Its arguments are the elements of the iterables corresponding to 

1995 the key list:: 

1996 

1997 >>> names = ('a', 'b', 'c') 

1998 >>> lengths = (1, 2, 3) 

1999 >>> widths = (5, 2, 1) 

2000 >>> def area(length, width): 

2001 ... return length * width 

2002 >>> sort_together([names, lengths, widths], key_list=(1, 2), key=area) 

2003 [('c', 'b', 'a'), (3, 2, 1), (1, 2, 5)] 

2004 

2005 Set *reverse* to ``True`` to sort in descending order. 

2006 

2007 >>> sort_together([(1, 2, 3), ('c', 'b', 'a')], reverse=True) 

2008 [(3, 2, 1), ('a', 'b', 'c')] 

2009 

2010 If the *strict* keyword argument is ``True``, then 

2011 ``ValueError`` will be raised if any of the iterables have 

2012 different lengths. 

2013 

2014 """ 

2015 if key is None: 

2016 # if there is no key function, the key argument to sorted is an 

2017 # itemgetter 

2018 key_argument = itemgetter(*key_list) 

2019 else: 

2020 # if there is a key function, call it with the items at the offsets 

2021 # specified by the key function as arguments 

2022 key_list = list(key_list) 

2023 if len(key_list) == 1: 

2024 # if key_list contains a single item, pass the item at that offset 

2025 # as the only argument to the key function 

2026 key_offset = key_list[0] 

2027 key_argument = lambda zipped_items: key(zipped_items[key_offset]) 

2028 else: 

2029 # if key_list contains multiple items, use itemgetter to return a 

2030 # tuple of items, which we pass as *args to the key function 

2031 get_key_items = itemgetter(*key_list) 

2032 key_argument = lambda zipped_items: key( 

2033 *get_key_items(zipped_items) 

2034 ) 

2035 

2036 transposed = zip(*iterables, strict=strict) 

2037 reordered = sorted(transposed, key=key_argument, reverse=reverse) 

2038 untransposed = zip(*reordered, strict=strict) 

2039 return list(untransposed) 

2040 

2041 

2042def unzip(iterable): 

2043 """The inverse of :func:`zip`, this function disaggregates the elements 

2044 of the zipped *iterable*. 

2045 

2046 The ``i``-th iterable contains the ``i``-th element from each element 

2047 of the zipped iterable. The first element is used to determine the 

2048 length of the remaining elements. 

2049 

2050 >>> iterable = [('a', 1), ('b', 2), ('c', 3), ('d', 4)] 

2051 >>> letters, numbers = unzip(iterable) 

2052 >>> list(letters) 

2053 ['a', 'b', 'c', 'd'] 

2054 >>> list(numbers) 

2055 [1, 2, 3, 4] 

2056 

2057 This is similar to using ``zip(*iterable)``, but it avoids reading 

2058 *iterable* into memory. Note, however, that this function uses 

2059 :func:`itertools.tee` and thus may require significant storage. 

2060 

2061 """ 

2062 head, iterable = spy(iterable) 

2063 if not head: 

2064 # empty iterable, e.g. zip([], [], []) 

2065 return () 

2066 # spy returns a one-length iterable as head 

2067 head = head[0] 

2068 iterables = tee(iterable, len(head)) 

2069 

2070 # If we have an iterable like iter([(1, 2, 3), (4, 5), (6,)]), 

2071 # the second unzipped iterable fails at the third tuple since 

2072 # it tries to access (6,)[1]. 

2073 # Same with the third unzipped iterable and the second tuple. 

2074 # To support these "improperly zipped" iterables, we suppress 

2075 # the IndexError, which just stops the unzipped iterables at 

2076 # first length mismatch. 

2077 return tuple( 

2078 iter_suppress(map(itemgetter(i), it), IndexError) 

2079 for i, it in enumerate(iterables) 

2080 ) 

2081 

2082 

2083def divide(n, iterable): 

2084 """Divide the elements from *iterable* into *n* parts, maintaining 

2085 order. 

2086 

2087 >>> group_1, group_2 = divide(2, [1, 2, 3, 4, 5, 6]) 

2088 >>> list(group_1) 

2089 [1, 2, 3] 

2090 >>> list(group_2) 

2091 [4, 5, 6] 

2092 

2093 If the length of *iterable* is not evenly divisible by *n*, then the 

2094 length of the returned iterables will not be identical: 

2095 

2096 >>> children = divide(3, [1, 2, 3, 4, 5, 6, 7]) 

2097 >>> [list(c) for c in children] 

2098 [[1, 2, 3], [4, 5], [6, 7]] 

2099 

2100 If the length of the iterable is smaller than n, then the last returned 

2101 iterables will be empty: 

2102 

2103 >>> children = divide(5, [1, 2, 3]) 

2104 >>> [list(c) for c in children] 

2105 [[1], [2], [3], [], []] 

2106 

2107 This function will exhaust the iterable before returning. 

2108 If order is not important, see :func:`distribute`, which does not first 

2109 pull the iterable into memory. 

2110 

2111 """ 

2112 if n < 1: 

2113 raise ValueError('n must be at least 1') 

2114 

2115 try: 

2116 iterable[:0] 

2117 except TypeError: 

2118 seq = tuple(iterable) 

2119 else: 

2120 seq = iterable 

2121 

2122 q, r = divmod(len(seq), n) 

2123 

2124 ret = [] 

2125 stop = 0 

2126 for i in range(1, n + 1): 

2127 start = stop 

2128 stop += q + 1 if i <= r else q 

2129 ret.append(iter(seq[start:stop])) 

2130 

2131 return ret 

2132 

2133 

2134def always_iterable(obj, base_type=(str, bytes)): 

2135 """If *obj* is iterable, return an iterator over its items:: 

2136 

2137 >>> obj = (1, 2, 3) 

2138 >>> list(always_iterable(obj)) 

2139 [1, 2, 3] 

2140 

2141 If *obj* is not iterable, return a one-item iterable containing *obj*:: 

2142 

2143 >>> obj = 1 

2144 >>> list(always_iterable(obj)) 

2145 [1] 

2146 

2147 If *obj* is ``None``, return an empty iterable: 

2148 

2149 >>> obj = None 

2150 >>> list(always_iterable(None)) 

2151 [] 

2152 

2153 By default, binary and text strings are not considered iterable:: 

2154 

2155 >>> obj = 'foo' 

2156 >>> list(always_iterable(obj)) 

2157 ['foo'] 

2158 

2159 If *base_type* is set, objects for which ``isinstance(obj, base_type)`` 

2160 returns ``True`` won't be considered iterable. 

2161 

2162 >>> obj = {'a': 1} 

2163 >>> list(always_iterable(obj)) # Iterate over the dict's keys 

2164 ['a'] 

2165 >>> list(always_iterable(obj, base_type=dict)) # Treat dicts as a unit 

2166 [{'a': 1}] 

2167 

2168 Set *base_type* to ``None`` to avoid any special handling and treat objects 

2169 Python considers iterable as iterable: 

2170 

2171 >>> obj = 'foo' 

2172 >>> list(always_iterable(obj, base_type=None)) 

2173 ['f', 'o', 'o'] 

2174 """ 

2175 if obj is None: 

2176 return iter(()) 

2177 

2178 if (base_type is not None) and isinstance(obj, base_type): 

2179 return iter((obj,)) 

2180 

2181 try: 

2182 return iter(obj) 

2183 except TypeError: 

2184 return iter((obj,)) 

2185 

2186 

2187def adjacent(predicate, iterable, distance=1): 

2188 """Return an iterable over `(bool, item)` tuples where the `item` is 

2189 drawn from *iterable* and the `bool` indicates whether 

2190 that item satisfies the *predicate* or is adjacent to an item that does. 

2191 

2192 For example, to find whether items are adjacent to a ``3``:: 

2193 

2194 >>> list(adjacent(lambda x: x == 3, range(6))) 

2195 [(False, 0), (False, 1), (True, 2), (True, 3), (True, 4), (False, 5)] 

2196 

2197 Set *distance* to change what counts as adjacent. For example, to find 

2198 whether items are two places away from a ``3``: 

2199 

2200 >>> list(adjacent(lambda x: x == 3, range(6), distance=2)) 

2201 [(False, 0), (True, 1), (True, 2), (True, 3), (True, 4), (True, 5)] 

2202 

2203 This is useful for contextualizing the results of a search function. 

2204 For example, a code comparison tool might want to identify lines that 

2205 have changed, but also surrounding lines to give the viewer of the diff 

2206 context. 

2207 

2208 The predicate function will only be called once for each item in the 

2209 iterable. 

2210 

2211 See also :func:`groupby_transform`, which can be used with this function 

2212 to group ranges of items with the same `bool` value. 

2213 

2214 """ 

2215 # Allow distance=0 mainly for testing that it reproduces results with map() 

2216 if distance < 0: 

2217 raise ValueError('distance must be at least 0') 

2218 

2219 i1, i2 = tee(iterable) 

2220 padding = [False] * distance 

2221 selected = chain(padding, map(predicate, i1), padding) 

2222 adjacent_to_selected = map(any, windowed(selected, 2 * distance + 1)) 

2223 return zip(adjacent_to_selected, i2) 

2224 

2225 

2226def groupby_transform(iterable, keyfunc=None, valuefunc=None, reducefunc=None): 

2227 """An extension of :func:`itertools.groupby` that can apply transformations 

2228 to the grouped data. 

2229 

2230 * *keyfunc* is a function computing a key value for each item in *iterable* 

2231 * *valuefunc* is a function that transforms the individual items from 

2232 *iterable* after grouping 

2233 * *reducefunc* is a function that transforms each group of items 

2234 

2235 >>> iterable = 'aAAbBBcCC' 

2236 >>> keyfunc = lambda k: k.upper() 

2237 >>> valuefunc = lambda v: v.lower() 

2238 >>> reducefunc = lambda g: ''.join(g) 

2239 >>> list(groupby_transform(iterable, keyfunc, valuefunc, reducefunc)) 

2240 [('A', 'aaa'), ('B', 'bbb'), ('C', 'ccc')] 

2241 

2242 Each optional argument defaults to an identity function if not specified. 

2243 

2244 :func:`groupby_transform` is useful when grouping elements of an iterable 

2245 using a separate iterable as the key. To do this, :func:`zip` the iterables 

2246 and pass a *keyfunc* that extracts the first element and a *valuefunc* 

2247 that extracts the second element:: 

2248 

2249 >>> from operator import itemgetter 

2250 >>> keys = [0, 0, 1, 1, 1, 2, 2, 2, 3] 

2251 >>> values = 'abcdefghi' 

2252 >>> iterable = zip(keys, values) 

2253 >>> grouper = groupby_transform(iterable, itemgetter(0), itemgetter(1)) 

2254 >>> [(k, ''.join(g)) for k, g in grouper] 

2255 [(0, 'ab'), (1, 'cde'), (2, 'fgh'), (3, 'i')] 

2256 

2257 Note that the order of items in the iterable is significant. 

2258 Only adjacent items are grouped together, so if you don't want any 

2259 duplicate groups, you should sort the iterable by the key function 

2260 or consider :func:`bucket` or :func:`map_reduce`. :func:`map_reduce` 

2261 consumes the iterable immediately and returns a dictionary, while 

2262 :func:`bucket` does not. 

2263 

2264 .. seealso:: :func:`bucket`, :func:`map_reduce` 

2265 

2266 """ 

2267 ret = groupby(iterable, keyfunc) 

2268 if valuefunc: 

2269 ret = ((k, map(valuefunc, g)) for k, g in ret) 

2270 if reducefunc: 

2271 ret = ((k, reducefunc(g)) for k, g in ret) 

2272 

2273 return ret 

2274 

2275 

2276class numeric_range(Sequence): 

2277 """An extension of the built-in ``range()`` function whose arguments can 

2278 be any orderable numeric type. 

2279 

2280 With only *stop* specified, *start* defaults to ``0`` and *step* 

2281 defaults to ``1``. The output items will match the type of *stop*: 

2282 

2283 >>> list(numeric_range(3.5)) 

2284 [0.0, 1.0, 2.0, 3.0] 

2285 

2286 With only *start* and *stop* specified, *step* defaults to ``1``, typed 

2287 to match *stop* - *start*. The output items will match the type of 

2288 ``start + step``: 

2289 

2290 >>> from decimal import Decimal 

2291 >>> start = Decimal('2.1') 

2292 >>> stop = Decimal('5.1') 

2293 >>> list(numeric_range(start, stop)) 

2294 [Decimal('2.1'), Decimal('3.1'), Decimal('4.1')] 

2295 

2296 With *start*, *stop*, and *step* specified the output items will match 

2297 the type of ``start + step``: 

2298 

2299 >>> from fractions import Fraction 

2300 >>> start = Fraction(1, 2) # Start at 1/2 

2301 >>> stop = Fraction(5, 2) # End at 5/2 

2302 >>> step = Fraction(1, 2) # Count by 1/2 

2303 >>> list(numeric_range(start, stop, step)) 

2304 [Fraction(1, 2), Fraction(1, 1), Fraction(3, 2), Fraction(2, 1)] 

2305 

2306 If *step* is zero, ``ValueError`` is raised. Negative steps are supported: 

2307 

2308 >>> list(numeric_range(3, -1, -1.0)) 

2309 [3.0, 2.0, 1.0, 0.0] 

2310 

2311 Be aware of the limitations of floating-point numbers; the representation 

2312 of the yielded numbers may be surprising. 

2313 

2314 ``datetime.datetime`` objects can be used for *start* and *stop*, if *step* 

2315 is a ``datetime.timedelta`` object: 

2316 

2317 >>> import datetime 

2318 >>> start = datetime.datetime(2019, 1, 1) 

2319 >>> stop = datetime.datetime(2019, 1, 3) 

2320 >>> step = datetime.timedelta(days=1) 

2321 >>> items = iter(numeric_range(start, stop, step)) 

2322 >>> next(items) 

2323 datetime.datetime(2019, 1, 1, 0, 0) 

2324 >>> next(items) 

2325 datetime.datetime(2019, 1, 2, 0, 0) 

2326 

2327 """ 

2328 

2329 _EMPTY_HASH = hash(range(0, 0)) 

2330 

2331 def __init__(self, *args): 

2332 argc = len(args) 

2333 if argc == 1: 

2334 (self._stop,) = args 

2335 self._start = type(self._stop)(0) 

2336 self._step = type(self._stop - self._start)(1) 

2337 elif argc == 2: 

2338 self._start, self._stop = args 

2339 self._step = type(self._stop - self._start)(1) 

2340 elif argc == 3: 

2341 self._start, self._stop, self._step = args 

2342 elif argc == 0: 

2343 raise TypeError( 

2344 f'numeric_range expected at least 1 argument, got {argc}' 

2345 ) 

2346 else: 

2347 raise TypeError( 

2348 f'numeric_range expected at most 3 arguments, got {argc}' 

2349 ) 

2350 

2351 self._zero = type(self._step)(0) 

2352 if self._step == self._zero: 

2353 raise ValueError('numeric_range() arg 3 must not be zero') 

2354 self._growing = self._step > self._zero 

2355 

2356 def __bool__(self): 

2357 if self._growing: 

2358 return self._start < self._stop 

2359 else: 

2360 return self._start > self._stop 

2361 

2362 def __contains__(self, elem): 

2363 try: 

2364 self.index(elem) 

2365 except ValueError: 

2366 return False 

2367 return True 

2368 

2369 def __eq__(self, other): 

2370 # numeric_range object equality is intended to mirror the built-in range 

2371 # object's equality. 

2372 # https://github.com/python/cpython/blob/f5c4880151b609e0a0a0b05c292d36b18038c061/Objects/rangeobject.c#L499 

2373 if not isinstance(other, numeric_range): 

2374 return False 

2375 

2376 if self is other: 

2377 return True 

2378 

2379 len_self = self._len 

2380 if len_self != other._len: 

2381 return False 

2382 

2383 if not len_self: 

2384 return True 

2385 

2386 if self._start != other._start: 

2387 return False 

2388 

2389 if len_self == 1: 

2390 return True 

2391 

2392 return self._step == other._step 

2393 

2394 def __getitem__(self, key): 

2395 if isinstance(key, int): 

2396 return self._get_by_index(key) 

2397 elif isinstance(key, slice): 

2398 start_idx, stop_idx, step_idx = key.indices(self._len) 

2399 return numeric_range( 

2400 self._start + start_idx * self._step, 

2401 self._start + stop_idx * self._step, 

2402 self._step * step_idx, 

2403 ) 

2404 else: 

2405 raise TypeError( 

2406 'numeric range indices must be ' 

2407 f'integers or slices, not {type(key).__name__}' 

2408 ) 

2409 

2410 def __hash__(self): 

2411 # numeric_range hashing is intended to mirror the built-in range object's 

2412 # hashing. 

2413 # https://github.com/python/cpython/blob/f5c4880151b609e0a0a0b05c292d36b18038c061/Objects/rangeobject.c#L570 

2414 len_self = self._len 

2415 if not len_self: 

2416 return hash((len_self, None, None)) 

2417 if len_self == 1: 

2418 return hash((len_self, self._start, None)) 

2419 return hash((len_self, self._start, self._step)) 

2420 

2421 def __iter__(self): 

2422 values = (self._start + (n * self._step) for n in count()) 

2423 if self._growing: 

2424 return takewhile(partial(gt, self._stop), values) 

2425 else: 

2426 return takewhile(partial(lt, self._stop), values) 

2427 

2428 def __len__(self): 

2429 return self._len 

2430 

2431 @cached_property 

2432 def _len(self): 

2433 if self._growing: 

2434 start = self._start 

2435 stop = self._stop 

2436 step = self._step 

2437 else: 

2438 start = self._stop 

2439 stop = self._start 

2440 step = -self._step 

2441 distance = stop - start 

2442 if distance <= self._zero: 

2443 return 0 

2444 else: # distance > 0 and step > 0: regular euclidean division 

2445 q, r = divmod(distance, step) 

2446 n = int(q) + int(r != self._zero) 

2447 # The division above measures the distance to cover, but the items 

2448 # are produced by repeated multiplication (see `__iter__`). With 

2449 # inexact arithmetic the two disagree at the boundary, so settle 

2450 # the count against the items themselves. 

2451 while n and not self._before_stop(n - 1): 

2452 n -= 1 

2453 while self._before_stop(n): 

2454 n += 1 

2455 return n 

2456 

2457 def _before_stop(self, i): 

2458 value = self._start + i * self._step 

2459 return value < self._stop if self._growing else value > self._stop 

2460 

2461 def __reduce__(self): 

2462 return numeric_range, (self._start, self._stop, self._step) 

2463 

2464 def __repr__(self): 

2465 if self._step == 1: 

2466 return f"numeric_range({self._start!r}, {self._stop!r})" 

2467 return ( 

2468 f"numeric_range({self._start!r}, {self._stop!r}, {self._step!r})" 

2469 ) 

2470 

2471 def __reversed__(self): 

2472 start = self._start 

2473 step = self._step 

2474 for i in reversed(range(self._len)): 

2475 yield start + i * step 

2476 

2477 def count(self, value): 

2478 return int(value in self) 

2479 

2480 def index(self, value): 

2481 if self._growing: 

2482 if self._start <= value < self._stop: 

2483 q, _ = divmod(value - self._start, self._step) 

2484 return self._index_near(int(q), value) 

2485 else: 

2486 if self._start >= value > self._stop: 

2487 q, _ = divmod(self._start - value, -self._step) 

2488 return self._index_near(int(q), value) 

2489 

2490 raise ValueError(f"{value} is not in numeric range") 

2491 

2492 def _index_near(self, i, value): 

2493 # `i` is the quotient of the division of `value` by the step, which 

2494 # locates the value on the grid of items this range produces. For 

2495 # exact types that quotient is the index. For inexact ones (floats) 

2496 # it can land one short, and the remainder of the division is not a 

2497 # reliable membership test either: `numeric_range(0.0, 1.0, 0.1)` 

2498 # yields 0.30000000000000004, which leaves a non-zero remainder. 

2499 # So compare against the item the range actually produces there. 

2500 for candidate in (i, i + 1): 

2501 if 0 <= candidate < self._len: 

2502 if self._start + candidate * self._step == value: 

2503 return candidate 

2504 

2505 raise ValueError(f"{value} is not in numeric range") 

2506 

2507 def _get_by_index(self, i): 

2508 if i < 0: 

2509 i += self._len 

2510 if i < 0 or i >= self._len: 

2511 raise IndexError("numeric range object index out of range") 

2512 return self._start + i * self._step 

2513 

2514 

2515def count_cycle(iterable, n=None): 

2516 """Cycle through the items from *iterable* up to *n* times, yielding 

2517 the number of completed cycles along with each item. If *n* is omitted the 

2518 process repeats indefinitely. 

2519 

2520 >>> list(count_cycle('AB', 3)) 

2521 [(0, 'A'), (0, 'B'), (1, 'A'), (1, 'B'), (2, 'A'), (2, 'B')] 

2522 

2523 """ 

2524 if n is not None: 

2525 return product(range(n), iterable) 

2526 seq = tuple(iterable) 

2527 if not seq: 

2528 return iter(()) 

2529 return zip(repeat_each(count(), len(seq)), cycle(seq)) 

2530 

2531 

2532def mark_ends(iterable): 

2533 """Yield 3-tuples of the form ``(is_first, is_last, item)``. 

2534 

2535 >>> list(mark_ends('ABC')) 

2536 [(True, False, 'A'), (False, False, 'B'), (False, True, 'C')] 

2537 

2538 Use this when looping over an iterable to take special action on its first 

2539 and/or last items: 

2540 

2541 >>> iterable = ['Header', 100, 200, 'Footer'] 

2542 >>> total = 0 

2543 >>> for is_first, is_last, item in mark_ends(iterable): 

2544 ... if is_first: 

2545 ... continue # Skip the header 

2546 ... if is_last: 

2547 ... continue # Skip the footer 

2548 ... total += item 

2549 >>> print(total) 

2550 300 

2551 """ 

2552 it = iter(iterable) 

2553 for a in it: 

2554 first = True 

2555 for b in it: 

2556 yield first, False, a 

2557 a = b 

2558 first = False 

2559 yield first, True, a 

2560 

2561 

2562def locate(iterable, pred=bool, window_size=None): 

2563 """Yield the index of each item in *iterable* for which *pred* returns 

2564 ``True``. 

2565 

2566 *pred* defaults to :func:`bool`, which will select truthy items: 

2567 

2568 >>> list(locate([0, 1, 1, 0, 1, 0, 0])) 

2569 [1, 2, 4] 

2570 

2571 Set *pred* to a custom function to, e.g., find the indexes for a particular 

2572 item. 

2573 

2574 >>> list(locate(['a', 'b', 'c', 'b'], lambda x: x == 'b')) 

2575 [1, 3] 

2576 

2577 If *window_size* is given, then the *pred* function will be called with 

2578 the values in each window. This enables searching for sub-sequences. 

2579 Note that *pred* may receive fewer than *window_size* arguments at the end of 

2580 the iterable. 

2581 

2582 >>> iterable = [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3] 

2583 >>> pred = lambda *args: args == (1, 2, 3) 

2584 >>> list(locate(iterable, pred=pred, window_size=3)) 

2585 [1, 5, 9] 

2586 

2587 Use with :func:`seekable` to find indexes and then retrieve the associated 

2588 items: 

2589 

2590 >>> from itertools import count 

2591 >>> from more_itertools import seekable 

2592 >>> source = (3 * n + 1 if (n % 2) else n // 2 for n in count()) 

2593 >>> it = seekable(source) 

2594 >>> pred = lambda x: x > 100 

2595 >>> indexes = locate(it, pred=pred) 

2596 >>> i = next(indexes) 

2597 >>> it.seek(i) 

2598 >>> next(it) 

2599 106 

2600 

2601 """ 

2602 if window_size is None: 

2603 return compress(count(), map(pred, iterable)) 

2604 

2605 if window_size < 1: 

2606 raise ValueError('window size must be at least 1') 

2607 

2608 it = windowed(iterable, window_size, fillvalue=_marker) 

2609 return compress( 

2610 count(), 

2611 (pred(*(x for x in w if x is not _marker)) for w in it), 

2612 ) 

2613 

2614 

2615def longest_common_prefix(iterables): 

2616 """Yield elements of the longest common prefix among given *iterables*. 

2617 

2618 >>> ''.join(longest_common_prefix(['abcd', 'abc', 'abf'])) 

2619 'ab' 

2620 

2621 """ 

2622 return (c[0] for c in takewhile(all_equal, zip(*iterables))) 

2623 

2624 

2625def lstrip(iterable, pred): 

2626 """Yield the items from *iterable*, but strip any from the beginning 

2627 for which *pred* returns ``True``. 

2628 

2629 For example, to remove a set of items from the start of an iterable: 

2630 

2631 >>> iterable = (None, False, None, 1, 2, None, 3, False, None) 

2632 >>> pred = lambda x: x in {None, False, ''} 

2633 >>> list(lstrip(iterable, pred)) 

2634 [1, 2, None, 3, False, None] 

2635 

2636 This function is analogous to :func:`str.lstrip`, and is essentially 

2637 a wrapper for :func:`itertools.dropwhile`. 

2638 

2639 """ 

2640 return dropwhile(pred, iterable) 

2641 

2642 

2643def rstrip(iterable, pred): 

2644 """Yield the items from *iterable*, but strip any from the end 

2645 for which *pred* returns ``True``. 

2646 

2647 For example, to remove a set of items from the end of an iterable: 

2648 

2649 >>> iterable = (None, False, None, 1, 2, None, 3, False, None) 

2650 >>> pred = lambda x: x in {None, False, ''} 

2651 >>> list(rstrip(iterable, pred)) 

2652 [None, False, None, 1, 2, None, 3] 

2653 

2654 This function is analogous to :func:`str.rstrip`. 

2655 

2656 """ 

2657 cache = [] 

2658 cache_append = cache.append 

2659 cache_clear = cache.clear 

2660 for x in iterable: 

2661 if pred(x): 

2662 cache_append(x) 

2663 else: 

2664 yield from cache 

2665 cache_clear() 

2666 yield x 

2667 

2668 

2669def strip(iterable, pred): 

2670 """Yield the items from *iterable*, but strip any from the 

2671 beginning and end for which *pred* returns ``True``. 

2672 

2673 For example, to remove a set of items from both ends of an iterable: 

2674 

2675 >>> iterable = (None, False, None, 1, 2, None, 3, False, None) 

2676 >>> pred = lambda x: x in {None, False, ''} 

2677 >>> list(strip(iterable, pred)) 

2678 [1, 2, None, 3] 

2679 

2680 This function is analogous to :func:`str.strip`. 

2681 

2682 """ 

2683 return rstrip(lstrip(iterable, pred), pred) 

2684 

2685 

2686class islice_extended: 

2687 """An extension of :func:`itertools.islice` that supports negative values 

2688 for *stop*, *start*, and *step*. 

2689 

2690 >>> iterator = iter('abcdefgh') 

2691 >>> list(islice_extended(iterator, -4, -1)) 

2692 ['e', 'f', 'g'] 

2693 

2694 Slices with negative values require some caching of *iterable*, but this 

2695 function takes care to minimize the amount of memory required. 

2696 

2697 For example, you can use a negative step with an infinite iterator: 

2698 

2699 >>> from itertools import count 

2700 >>> list(islice_extended(count(), 110, 99, -2)) 

2701 [110, 108, 106, 104, 102, 100] 

2702 

2703 You can also use slice notation directly: 

2704 

2705 >>> iterator = map(str, count()) 

2706 >>> it = islice_extended(iterator)[10:20:2] 

2707 >>> list(it) 

2708 ['10', '12', '14', '16', '18'] 

2709 

2710 """ 

2711 

2712 def __init__(self, iterable, *args): 

2713 it = iter(iterable) 

2714 if args: 

2715 self._iterator = _islice_helper(it, slice(*args)) 

2716 else: 

2717 self._iterator = it 

2718 

2719 def __iter__(self): 

2720 return self 

2721 

2722 def __next__(self): 

2723 return next(self._iterator) 

2724 

2725 def __getitem__(self, key): 

2726 if isinstance(key, slice): 

2727 return islice_extended(_islice_helper(self._iterator, key)) 

2728 

2729 raise TypeError('islice_extended.__getitem__ argument must be a slice') 

2730 

2731 

2732def _islice_helper(it, s): 

2733 start = s.start 

2734 stop = s.stop 

2735 if s.step == 0: 

2736 raise ValueError('step argument must be a non-zero integer or None.') 

2737 step = s.step or 1 

2738 

2739 if step > 0: 

2740 start = 0 if (start is None) else start 

2741 

2742 if start < 0: 

2743 # Consume all but the last -start items 

2744 counter = count(1) 

2745 wrapper = compress(it, counter) 

2746 cache = deque(wrapper, maxlen=-start) 

2747 len_iter = next(counter) - 1 

2748 

2749 # Adjust start to be positive 

2750 i = max(len_iter + start, 0) 

2751 

2752 # Adjust stop to be positive 

2753 if stop is None: 

2754 j = len_iter 

2755 elif stop >= 0: 

2756 j = min(stop, len_iter) 

2757 else: 

2758 j = max(len_iter + stop, 0) 

2759 

2760 # Slice the cache 

2761 n = j - i 

2762 if n <= 0: 

2763 return 

2764 

2765 for index in range(n): 

2766 if index % step == 0: 

2767 # pop and yield the item. 

2768 # We don't want to use an intermediate variable 

2769 # it would extend the lifetime of the current item 

2770 yield cache.popleft() 

2771 else: 

2772 # just pop and discard the item 

2773 cache.popleft() 

2774 elif (stop is not None) and (stop < 0): 

2775 # Advance to the start position 

2776 next(islice(it, start, start), None) 

2777 

2778 # When stop is negative, we have to carry -stop items while 

2779 # iterating 

2780 cache = deque(islice(it, -stop), maxlen=-stop) 

2781 

2782 for index, item in enumerate(it): 

2783 if index % step == 0: 

2784 # pop and yield the item. 

2785 # We don't want to use an intermediate variable 

2786 # it would extend the lifetime of the current item 

2787 yield cache.popleft() 

2788 else: 

2789 # just pop and discard the item 

2790 cache.popleft() 

2791 cache.append(item) 

2792 else: 

2793 # When both start and stop are positive we have the normal case 

2794 yield from islice(it, start, stop, step) 

2795 else: 

2796 start = -1 if (start is None) else start 

2797 

2798 if (stop is not None) and (stop < 0): 

2799 # Consume all but the last items 

2800 n = -stop - 1 

2801 counter = count(1) 

2802 wrapper = compress(it, counter) 

2803 cache = deque(wrapper, maxlen=n) 

2804 len_iter = next(counter) - 1 

2805 

2806 # If start and stop are both negative they are comparable and 

2807 # we can just slice. Otherwise we can adjust start to be negative 

2808 # and then slice. 

2809 if start < 0: 

2810 i, j = start, stop 

2811 else: 

2812 i, j = min(start - len_iter, -1), None 

2813 

2814 yield from list(cache)[i:j:step] 

2815 else: 

2816 # Advance to the stop position 

2817 if stop is not None: 

2818 m = stop + 1 

2819 next(islice(it, m, m), None) 

2820 

2821 # stop is positive, so if start is negative they are not comparable 

2822 # and we need the rest of the items. 

2823 if start < 0: 

2824 i = start 

2825 n = None 

2826 # stop is None and start is positive, so we just need items up to 

2827 # the start index. 

2828 elif stop is None: 

2829 i = None 

2830 n = start + 1 

2831 # Both stop and start are positive, so they are comparable. 

2832 else: 

2833 i = None 

2834 n = start - stop 

2835 if n <= 0: 

2836 return 

2837 

2838 cache = list(islice(it, n)) 

2839 

2840 yield from cache[i::step] 

2841 

2842 

2843def always_reversible(iterable): 

2844 """An extension of :func:`reversed` that supports all iterables, not 

2845 just those which implement the ``Reversible`` or ``Sequence`` protocols. 

2846 

2847 >>> print(*always_reversible(x for x in range(3))) 

2848 2 1 0 

2849 

2850 If the iterable is already reversible, this function returns the 

2851 result of :func:`reversed()`. If the iterable is not reversible, 

2852 this function will cache the remaining items in the iterable and 

2853 yield them in reverse order, which may require significant storage. 

2854 """ 

2855 try: 

2856 return reversed(iterable) 

2857 except TypeError: 

2858 return reversed(list(iterable)) 

2859 

2860 

2861def consecutive_groups(iterable, ordering=None): 

2862 """Yield groups of consecutive items using :func:`itertools.groupby`. 

2863 The *ordering* function determines whether two items are adjacent by 

2864 returning their position. 

2865 

2866 By default, the ordering function is the identity function. This is 

2867 suitable for finding runs of numbers: 

2868 

2869 >>> iterable = [1, 10, 11, 12, 20, 30, 31, 32, 33, 40] 

2870 >>> for group in consecutive_groups(iterable): 

2871 ... print(list(group)) 

2872 [1] 

2873 [10, 11, 12] 

2874 [20] 

2875 [30, 31, 32, 33] 

2876 [40] 

2877 

2878 To find runs of adjacent letters, apply :func:`ord` function 

2879 to convert letters to ordinals. 

2880 

2881 >>> iterable = 'abcdfgilmnop' 

2882 >>> ordering = ord 

2883 >>> for group in consecutive_groups(iterable, ordering): 

2884 ... print(list(group)) 

2885 ['a', 'b', 'c', 'd'] 

2886 ['f', 'g'] 

2887 ['i'] 

2888 ['l', 'm', 'n', 'o', 'p'] 

2889 

2890 Each group of consecutive items is an iterator that shares its source with 

2891 *iterable*. When an output group is advanced, the previous group is 

2892 no longer available unless its elements are copied (e.g., into a ``list``). 

2893 

2894 >>> iterable = [1, 2, 11, 12, 21, 22] 

2895 >>> saved_groups = [] 

2896 >>> for group in consecutive_groups(iterable): 

2897 ... saved_groups.append(list(group)) # Copy group elements 

2898 >>> saved_groups 

2899 [[1, 2], [11, 12], [21, 22]] 

2900 

2901 """ 

2902 if ordering is None: 

2903 key = lambda x: x[0] - x[1] 

2904 else: 

2905 key = lambda x: x[0] - ordering(x[1]) 

2906 

2907 for k, g in groupby(enumerate(iterable), key=key): 

2908 yield map(itemgetter(1), g) 

2909 

2910 

2911def difference(iterable, func=sub, *, initial=None): 

2912 """This function is the inverse of :func:`itertools.accumulate`. By default 

2913 it will compute the first difference of *iterable* using 

2914 :func:`operator.sub`: 

2915 

2916 >>> from itertools import accumulate 

2917 >>> iterable = accumulate([0, 1, 2, 3, 4]) # produces 0, 1, 3, 6, 10 

2918 >>> list(difference(iterable)) 

2919 [0, 1, 2, 3, 4] 

2920 

2921 *func* defaults to :func:`operator.sub`, but other functions can be 

2922 specified. They will be applied as follows:: 

2923 

2924 A, B, C, D, ... --> A, func(B, A), func(C, B), func(D, C), ... 

2925 

2926 For example, to do progressive division: 

2927 

2928 >>> iterable = [1, 2, 6, 24, 120] 

2929 >>> func = lambda x, y: x // y 

2930 >>> list(difference(iterable, func)) 

2931 [1, 2, 3, 4, 5] 

2932 

2933 If the *initial* keyword is set, the first element will be skipped when 

2934 computing successive differences. 

2935 

2936 >>> it = [10, 11, 13, 16] # from accumulate([1, 2, 3], initial=10) 

2937 >>> list(difference(it, initial=10)) 

2938 [1, 2, 3] 

2939 

2940 """ 

2941 a, b = tee(iterable) 

2942 try: 

2943 first = [next(b)] 

2944 except StopIteration: 

2945 return iter([]) 

2946 

2947 if initial is not None: 

2948 return map(func, b, a) 

2949 

2950 return chain(first, map(func, b, a)) 

2951 

2952 

2953class SequenceView(Sequence): 

2954 """Return a read-only view of the sequence object *target*. 

2955 

2956 :class:`SequenceView` objects are analogous to Python's built-in 

2957 "dictionary view" types. They provide a dynamic view of a sequence's items, 

2958 meaning that when the sequence updates, so does the view. 

2959 

2960 >>> seq = ['0', '1', '2'] 

2961 >>> view = SequenceView(seq) 

2962 >>> view 

2963 SequenceView(['0', '1', '2']) 

2964 >>> seq.append('3') 

2965 >>> view 

2966 SequenceView(['0', '1', '2', '3']) 

2967 

2968 Sequence views support indexing, slicing, and length queries. They act 

2969 like the underlying sequence, except they don't allow assignment: 

2970 

2971 >>> view[1] 

2972 '1' 

2973 >>> view[1:-1] 

2974 ['1', '2'] 

2975 >>> len(view) 

2976 4 

2977 

2978 Sequence views are useful as an alternative to copying, as they don't 

2979 require (much) extra storage. 

2980 

2981 """ 

2982 

2983 def __init__(self, target): 

2984 if not isinstance(target, Sequence): 

2985 raise TypeError 

2986 self._target = target 

2987 

2988 def __getitem__(self, index): 

2989 return self._target[index] 

2990 

2991 def __len__(self): 

2992 return len(self._target) 

2993 

2994 def __repr__(self): 

2995 return f'{self.__class__.__name__}({self._target!r})' 

2996 

2997 

2998class seekable: 

2999 """Wrap an iterator to allow for seeking backward and forward. This 

3000 progressively caches the items in the source iterable so they can be 

3001 re-visited. 

3002 

3003 Call :meth:`seek` with an index to seek to that position in the source 

3004 iterable. 

3005 

3006 To "reset" an iterator, seek to ``0``: 

3007 

3008 >>> from itertools import count 

3009 >>> it = seekable((str(n) for n in count())) 

3010 >>> next(it), next(it), next(it) 

3011 ('0', '1', '2') 

3012 >>> it.seek(0) 

3013 >>> next(it), next(it), next(it) 

3014 ('0', '1', '2') 

3015 

3016 You can also seek forward: 

3017 

3018 >>> it = seekable((str(n) for n in range(20))) 

3019 >>> it.seek(10) 

3020 >>> next(it) 

3021 '10' 

3022 >>> it.seek(20) # Seeking past the end of the source isn't a problem 

3023 >>> list(it) 

3024 [] 

3025 >>> it.seek(0) # Resetting works even after hitting the end 

3026 >>> next(it) 

3027 '0' 

3028 

3029 Call :meth:`relative_seek` to seek relative to the source iterator's 

3030 current position. 

3031 

3032 >>> it = seekable((str(n) for n in range(20))) 

3033 >>> next(it), next(it), next(it) 

3034 ('0', '1', '2') 

3035 >>> it.relative_seek(2) 

3036 >>> next(it) 

3037 '5' 

3038 >>> it.relative_seek(-3) # Source is at '6', we move back to '3' 

3039 >>> next(it) 

3040 '3' 

3041 >>> it.relative_seek(-3) # Source is at '4', we move back to '1' 

3042 >>> next(it) 

3043 '1' 

3044 

3045 

3046 Call :meth:`peek` to look ahead one item without advancing the iterator: 

3047 

3048 >>> it = seekable('1234') 

3049 >>> it.peek() 

3050 '1' 

3051 >>> list(it) 

3052 ['1', '2', '3', '4'] 

3053 >>> it.peek(default='empty') 

3054 'empty' 

3055 

3056 Before the iterator is at its end, calling :func:`bool` on it will return 

3057 ``True``. After it will return ``False``: 

3058 

3059 >>> it = seekable('5678') 

3060 >>> bool(it) 

3061 True 

3062 >>> list(it) 

3063 ['5', '6', '7', '8'] 

3064 >>> bool(it) 

3065 False 

3066 

3067 You may view the contents of the cache with the :meth:`elements` method. 

3068 That returns a :class:`SequenceView`, a view that updates automatically: 

3069 

3070 >>> it = seekable((str(n) for n in range(10))) 

3071 >>> next(it), next(it), next(it) 

3072 ('0', '1', '2') 

3073 >>> elements = it.elements() 

3074 >>> elements 

3075 SequenceView(['0', '1', '2']) 

3076 >>> next(it) 

3077 '3' 

3078 >>> elements 

3079 SequenceView(['0', '1', '2', '3']) 

3080 

3081 Indexing the :class:`seekable` directly returns items from the cache: 

3082 

3083 >>> it = seekable((str(n) for n in range(10))) 

3084 >>> next(it), next(it), next(it) 

3085 ('0', '1', '2') 

3086 >>> it[-1] 

3087 '2' 

3088 >>> it[0] 

3089 '0' 

3090 

3091 By default, the cache grows as the source iterable progresses, so beware of 

3092 wrapping very large or infinite iterables. Supply *maxlen* to limit the 

3093 size of the cache (this of course limits how far back you can seek). 

3094 

3095 >>> from itertools import count 

3096 >>> it = seekable((str(n) for n in count()), maxlen=2) 

3097 >>> next(it), next(it), next(it), next(it) 

3098 ('0', '1', '2', '3') 

3099 >>> list(it.elements()) 

3100 ['2', '3'] 

3101 >>> it.seek(0) 

3102 >>> next(it), next(it), next(it), next(it) 

3103 ('2', '3', '4', '5') 

3104 >>> next(it) 

3105 '6' 

3106 

3107 """ 

3108 

3109 def __init__(self, iterable, maxlen=None): 

3110 self._maxlen_zero = maxlen == 0 

3111 self._source = ( 

3112 peekable(iterable) if self._maxlen_zero else iter(iterable) 

3113 ) 

3114 if maxlen is None: 

3115 self._cache = [] 

3116 else: 

3117 self._cache = deque([], maxlen) 

3118 self._index = None 

3119 

3120 def __iter__(self): 

3121 return self 

3122 

3123 def __next__(self): 

3124 if self._index is not None: 

3125 try: 

3126 item = self._cache[self._index] 

3127 except IndexError: 

3128 self._index = None 

3129 else: 

3130 self._index += 1 

3131 return item 

3132 

3133 item = next(self._source) 

3134 self._cache.append(item) 

3135 return item 

3136 

3137 def __bool__(self): 

3138 try: 

3139 self.peek() 

3140 except StopIteration: 

3141 return False 

3142 return True 

3143 

3144 def peek(self, default=_marker): 

3145 if self._maxlen_zero: 

3146 return self._source.peek(default) 

3147 try: 

3148 peeked = next(self) 

3149 except StopIteration: 

3150 if default is _marker: 

3151 raise 

3152 return default 

3153 if self._index is None: 

3154 self._index = len(self._cache) 

3155 self._index -= 1 

3156 return peeked 

3157 

3158 def elements(self): 

3159 return SequenceView(self._cache) 

3160 

3161 def seek(self, index): 

3162 self._index = index 

3163 remainder = index - len(self._cache) 

3164 if remainder > 0: 

3165 consume(self, remainder) 

3166 

3167 def relative_seek(self, count): 

3168 if self._index is None: 

3169 self._index = len(self._cache) 

3170 

3171 self.seek(max(self._index + count, 0)) 

3172 

3173 def __getitem__(self, index): 

3174 return self._cache[index] 

3175 

3176 

3177class run_length: 

3178 """ 

3179 :func:`run_length.encode` compresses an iterable with run-length encoding. 

3180 It yields groups of repeated items with the count of how many times they 

3181 were repeated: 

3182 

3183 >>> uncompressed = 'abbcccdddd' 

3184 >>> list(run_length.encode(uncompressed)) 

3185 [('a', 1), ('b', 2), ('c', 3), ('d', 4)] 

3186 

3187 :func:`run_length.decode` decompresses an iterable that was previously 

3188 compressed with run-length encoding. It yields the items of the 

3189 decompressed iterable: 

3190 

3191 >>> compressed = [('a', 1), ('b', 2), ('c', 3), ('d', 4)] 

3192 >>> list(run_length.decode(compressed)) 

3193 ['a', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'd', 'd'] 

3194 

3195 """ 

3196 

3197 @staticmethod 

3198 def encode(iterable): 

3199 return ((k, ilen(g)) for k, g in groupby(iterable)) 

3200 

3201 @staticmethod 

3202 def decode(iterable): 

3203 return chain.from_iterable(starmap(repeat, iterable)) 

3204 

3205 

3206def exactly_n(iterable, n, predicate=bool): 

3207 """Return ``True`` if exactly ``n`` items in the iterable are ``True`` 

3208 according to the *predicate* function. 

3209 

3210 >>> exactly_n([True, True, False], 2) 

3211 True 

3212 >>> exactly_n([True, True, False], 1) 

3213 False 

3214 >>> exactly_n([0, 1, 2, 3, 4, 5], 3, lambda x: x < 3) 

3215 True 

3216 

3217 The iterable will be advanced until ``n + 1`` truthy items are encountered, 

3218 so avoid calling it on infinite iterables. 

3219 

3220 """ 

3221 iterator = filter(predicate, iterable) 

3222 if n <= 0: 

3223 if n < 0: 

3224 return False 

3225 for _ in iterator: 

3226 return False 

3227 return True 

3228 

3229 iterator = islice(iterator, n - 1, None) 

3230 for _ in iterator: 

3231 for _ in iterator: 

3232 return False 

3233 return True 

3234 return False 

3235 

3236 

3237def circular_shifts(iterable, steps=1): 

3238 """Yield the circular shifts of *iterable*. 

3239 

3240 >>> list(circular_shifts(range(4))) 

3241 [(0, 1, 2, 3), (1, 2, 3, 0), (2, 3, 0, 1), (3, 0, 1, 2)] 

3242 

3243 Set *steps* to the number of places to rotate to the left 

3244 (or to the right if negative). Defaults to 1. 

3245 

3246 >>> list(circular_shifts(range(4), 2)) 

3247 [(0, 1, 2, 3), (2, 3, 0, 1)] 

3248 

3249 >>> list(circular_shifts(range(4), -1)) 

3250 [(0, 1, 2, 3), (3, 0, 1, 2), (2, 3, 0, 1), (1, 2, 3, 0)] 

3251 

3252 """ 

3253 buffer = deque(iterable) 

3254 if steps == 0: 

3255 raise ValueError('Steps should be a non-zero integer') 

3256 

3257 buffer.rotate(steps) 

3258 steps = -steps 

3259 n = len(buffer) 

3260 n //= math.gcd(n, steps) 

3261 

3262 for _ in repeat(None, n): 

3263 buffer.rotate(steps) 

3264 yield tuple(buffer) 

3265 

3266 

3267def make_decorator(wrapping_func, result_index=0): 

3268 """Return a decorator version of *wrapping_func*, which is a function that 

3269 modifies an iterable. *result_index* is the position in that function's 

3270 signature where the iterable goes. 

3271 

3272 This lets you use itertools on the "production end," i.e. at function 

3273 definition. This can augment what the function returns without changing the 

3274 function's code. 

3275 

3276 For example, to produce a decorator version of :func:`chunked`: 

3277 

3278 >>> from more_itertools import chunked 

3279 >>> chunker = make_decorator(chunked, result_index=0) 

3280 >>> @chunker(3) 

3281 ... def iter_range(n): 

3282 ... return iter(range(n)) 

3283 ... 

3284 >>> list(iter_range(9)) 

3285 [[0, 1, 2], [3, 4, 5], [6, 7, 8]] 

3286 

3287 To only allow truthy items to be returned: 

3288 

3289 >>> truth_serum = make_decorator(filter, result_index=1) 

3290 >>> @truth_serum(bool) 

3291 ... def boolean_test(): 

3292 ... return [0, 1, '', ' ', False, True] 

3293 ... 

3294 >>> list(boolean_test()) 

3295 [1, ' ', True] 

3296 

3297 The :func:`peekable` and :func:`seekable` wrappers make for practical 

3298 decorators: 

3299 

3300 >>> from more_itertools import peekable 

3301 >>> peekable_function = make_decorator(peekable) 

3302 >>> @peekable_function() 

3303 ... def str_range(*args): 

3304 ... return (str(x) for x in range(*args)) 

3305 ... 

3306 >>> it = str_range(1, 20, 2) 

3307 >>> next(it), next(it), next(it) 

3308 ('1', '3', '5') 

3309 >>> it.peek() 

3310 '7' 

3311 >>> next(it) 

3312 '7' 

3313 

3314 """ 

3315 

3316 # See https://sites.google.com/site/bbayles/index/decorator_factory for 

3317 # notes on how this works. 

3318 def decorator(*wrapping_args, **wrapping_kwargs): 

3319 def outer_wrapper(f): 

3320 def inner_wrapper(*args, **kwargs): 

3321 result = f(*args, **kwargs) 

3322 wrapping_args_ = list(wrapping_args) 

3323 wrapping_args_.insert(result_index, result) 

3324 return wrapping_func(*wrapping_args_, **wrapping_kwargs) 

3325 

3326 return inner_wrapper 

3327 

3328 return outer_wrapper 

3329 

3330 return decorator 

3331 

3332 

3333def map_reduce(iterable, keyfunc, valuefunc=None, reducefunc=None): 

3334 """Return a dictionary that maps the items in *iterable* to categories 

3335 defined by *keyfunc*, transforms them with *valuefunc*, and 

3336 then summarizes them by category with *reducefunc*. 

3337 

3338 *valuefunc* defaults to the identity function if it is unspecified. 

3339 If *reducefunc* is unspecified, no summarization takes place: 

3340 

3341 >>> keyfunc = lambda x: x.upper() 

3342 >>> result = map_reduce('abbccc', keyfunc) 

3343 >>> sorted(result.items()) 

3344 [('A', ['a']), ('B', ['b', 'b']), ('C', ['c', 'c', 'c'])] 

3345 

3346 Specifying *valuefunc* transforms the categorized items: 

3347 

3348 >>> keyfunc = lambda x: x.upper() 

3349 >>> valuefunc = lambda x: 1 

3350 >>> result = map_reduce('abbccc', keyfunc, valuefunc) 

3351 >>> sorted(result.items()) 

3352 [('A', [1]), ('B', [1, 1]), ('C', [1, 1, 1])] 

3353 

3354 Specifying *reducefunc* summarizes the categorized items: 

3355 

3356 >>> keyfunc = lambda x: x.upper() 

3357 >>> valuefunc = lambda x: 1 

3358 >>> reducefunc = sum 

3359 >>> result = map_reduce('abbccc', keyfunc, valuefunc, reducefunc) 

3360 >>> sorted(result.items()) 

3361 [('A', 1), ('B', 2), ('C', 3)] 

3362 

3363 You may want to filter the input iterable before applying the map/reduce 

3364 procedure: 

3365 

3366 >>> all_items = range(30) 

3367 >>> items = [x for x in all_items if 10 <= x <= 20] # Filter 

3368 >>> keyfunc = lambda x: x % 2 # Evens map to 0; odds to 1 

3369 >>> categories = map_reduce(items, keyfunc=keyfunc) 

3370 >>> sorted(categories.items()) 

3371 [(0, [10, 12, 14, 16, 18, 20]), (1, [11, 13, 15, 17, 19])] 

3372 >>> summaries = map_reduce(items, keyfunc=keyfunc, reducefunc=sum) 

3373 >>> sorted(summaries.items()) 

3374 [(0, 90), (1, 75)] 

3375 

3376 Note that all items in the iterable are gathered into a list before the 

3377 summarization step, which may require significant storage. 

3378 

3379 The returned object is a :obj:`collections.defaultdict` with the 

3380 ``default_factory`` set to ``None``, such that it behaves like a normal 

3381 dictionary. 

3382 

3383 .. seealso:: :func:`bucket`, :func:`groupby_transform` 

3384 

3385 If storage is a concern, :func:`bucket` can be used without consuming the 

3386 entire iterable right away. If the elements with the same key are already 

3387 adjacent, :func:`groupby_transform` or :func:`itertools.groupby` can be 

3388 used without any caching overhead. 

3389 

3390 """ 

3391 

3392 ret = defaultdict(list) 

3393 

3394 if valuefunc is None: 

3395 for item in iterable: 

3396 key = keyfunc(item) 

3397 ret[key].append(item) 

3398 

3399 else: 

3400 for item in iterable: 

3401 key = keyfunc(item) 

3402 value = valuefunc(item) 

3403 ret[key].append(value) 

3404 

3405 if reducefunc is not None: 

3406 for key, value_list in ret.items(): 

3407 ret[key] = reducefunc(value_list) 

3408 

3409 ret.default_factory = None 

3410 return ret 

3411 

3412 

3413def rlocate(iterable, pred=bool, window_size=None): 

3414 """Yield the index of each item in *iterable* for which *pred* returns 

3415 ``True``, starting from the right and moving left. 

3416 

3417 *pred* defaults to :func:`bool`, which will select truthy items: 

3418 

3419 >>> list(rlocate([0, 1, 1, 0, 1, 0, 0])) # Truthy at 1, 2, and 4 

3420 [4, 2, 1] 

3421 

3422 Set *pred* to a custom function to, e.g., find the indexes for a particular 

3423 item: 

3424 

3425 >>> iterator = iter('abcb') 

3426 >>> pred = lambda x: x == 'b' 

3427 >>> list(rlocate(iterator, pred)) 

3428 [3, 1] 

3429 

3430 If *window_size* is given, then the *pred* function will be called with 

3431 that many items. This enables searching for sub-sequences: 

3432 

3433 >>> iterable = [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3] 

3434 >>> pred = lambda *args: args == (1, 2, 3) 

3435 >>> list(rlocate(iterable, pred=pred, window_size=3)) 

3436 [9, 5, 1] 

3437 

3438 Beware, this function won't return anything for infinite iterables. 

3439 If *iterable* is reversible, ``rlocate`` will reverse it and search from 

3440 the right. Otherwise, it will search from the left and return the results 

3441 in reverse order. 

3442 

3443 See :func:`locate` to for other example applications. 

3444 

3445 """ 

3446 if window_size is None: 

3447 try: 

3448 len_iter = len(iterable) 

3449 return (len_iter - i - 1 for i in locate(reversed(iterable), pred)) 

3450 except TypeError: 

3451 pass 

3452 

3453 return reversed(list(locate(iterable, pred, window_size))) 

3454 

3455 

3456def replace(iterable, pred, substitutes, count=None, window_size=1): 

3457 """Yield the items from *iterable*, replacing the items for which *pred* 

3458 returns ``True`` with the items from the iterable *substitutes*. 

3459 

3460 >>> iterable = [1, 1, 0, 1, 1, 0, 1, 1] 

3461 >>> pred = lambda x: x == 0 

3462 >>> substitutes = (2, 3) 

3463 >>> list(replace(iterable, pred, substitutes)) 

3464 [1, 1, 2, 3, 1, 1, 2, 3, 1, 1] 

3465 

3466 If *count* is given, the number of replacements will be limited: 

3467 

3468 >>> iterable = [1, 1, 0, 1, 1, 0, 1, 1, 0] 

3469 >>> pred = lambda x: x == 0 

3470 >>> substitutes = [None] 

3471 >>> list(replace(iterable, pred, substitutes, count=2)) 

3472 [1, 1, None, 1, 1, None, 1, 1, 0] 

3473 

3474 Use *window_size* to control the number of items passed as arguments to 

3475 *pred*. This allows for locating and replacing subsequences. 

3476 

3477 >>> iterable = [0, 1, 2, 5, 0, 1, 2, 5] 

3478 >>> window_size = 3 

3479 >>> pred = lambda *args: args == (0, 1, 2) # 3 items passed to pred 

3480 >>> substitutes = [3, 4] # Splice in these items 

3481 >>> list(replace(iterable, pred, substitutes, window_size=window_size)) 

3482 [3, 4, 5, 3, 4, 5] 

3483 

3484 *pred* may receive fewer than *window_size* arguments at the end of 

3485 the iterable and should be able to handle this. 

3486 

3487 """ 

3488 if window_size < 1: 

3489 raise ValueError('window_size must be at least 1') 

3490 

3491 # Save the substitutes iterable, since it's used more than once 

3492 substitutes = tuple(substitutes) 

3493 

3494 # Add padding such that the number of windows matches the length of the 

3495 # iterable 

3496 it = chain(iterable, repeat(_marker, window_size - 1)) 

3497 windows = windowed(it, window_size) 

3498 

3499 n = 0 

3500 for w in windows: 

3501 # Strip any _marker padding so pred never sees internal sentinels. 

3502 # Near the end of the iterable, pred will receive fewer arguments. 

3503 args = tuple(x for x in w if x is not _marker) 

3504 

3505 # If the current window matches our predicate (and we haven't hit 

3506 # our maximum number of replacements), splice in the substitutes 

3507 # and then consume the following windows that overlap with this one. 

3508 # For example, if the iterable is (0, 1, 2, 3, 4...) 

3509 # and the window size is 2, we have (0, 1), (1, 2), (2, 3)... 

3510 # If the predicate matches on (0, 1), we need to zap (0, 1) and (1, 2) 

3511 if args and pred(*args): 

3512 if (count is None) or (n < count): 

3513 n += 1 

3514 yield from substitutes 

3515 consume(windows, window_size - 1) 

3516 continue 

3517 

3518 # If there was no match (or we've reached the replacement limit), 

3519 # yield the first item from the window. 

3520 if args: 

3521 yield args[0] 

3522 

3523 

3524def partitions(iterable): 

3525 """Yield all possible order-preserving partitions of *iterable*. 

3526 

3527 >>> iterable = 'abc' 

3528 >>> for part in partitions(iterable): 

3529 ... print([''.join(p) for p in part]) 

3530 ['abc'] 

3531 ['a', 'bc'] 

3532 ['ab', 'c'] 

3533 ['a', 'b', 'c'] 

3534 

3535 This is unrelated to :func:`partition`. 

3536 

3537 """ 

3538 sequence = list(iterable) 

3539 n = len(sequence) 

3540 for i in powerset(range(1, n)): 

3541 yield [sequence[i:j] for i, j in zip((0,) + i, i + (n,))] 

3542 

3543 

3544def set_partitions(iterable, k=None, min_size=None, max_size=None): 

3545 """ 

3546 Yield the set partitions of *iterable* into *k* parts. Set partitions are 

3547 not order-preserving. 

3548 

3549 >>> iterable = 'abc' 

3550 >>> for part in set_partitions(iterable, 2): 

3551 ... print([''.join(p) for p in part]) 

3552 ['a', 'bc'] 

3553 ['ab', 'c'] 

3554 ['b', 'ac'] 

3555 

3556 

3557 If *k* is not given, every set partition is generated. 

3558 

3559 >>> iterable = 'abc' 

3560 >>> for part in set_partitions(iterable): 

3561 ... print([''.join(p) for p in part]) 

3562 ['abc'] 

3563 ['a', 'bc'] 

3564 ['ab', 'c'] 

3565 ['b', 'ac'] 

3566 ['a', 'b', 'c'] 

3567 

3568 if *min_size* and/or *max_size* are given, the minimum and/or maximum size 

3569 per block in partition is set. 

3570 

3571 >>> iterable = 'abc' 

3572 >>> for part in set_partitions(iterable, min_size=2): 

3573 ... print([''.join(p) for p in part]) 

3574 ['abc'] 

3575 >>> for part in set_partitions(iterable, max_size=2): 

3576 ... print([''.join(p) for p in part]) 

3577 ['a', 'bc'] 

3578 ['ab', 'c'] 

3579 ['b', 'ac'] 

3580 ['a', 'b', 'c'] 

3581 

3582 An empty *iterable* yields no partitions. 

3583 

3584 >>> list(set_partitions([])) 

3585 [] 

3586 

3587 """ 

3588 L = list(iterable) 

3589 n = len(L) 

3590 if k is not None: 

3591 if k < 1: 

3592 raise ValueError( 

3593 "Can't partition in a negative or zero number of groups" 

3594 ) 

3595 elif k > n: 

3596 return 

3597 

3598 min_size = min_size if min_size is not None else 0 

3599 max_size = max_size if max_size is not None else n 

3600 if min_size > max_size: 

3601 return 

3602 

3603 def set_partitions_helper(L, k): 

3604 n = len(L) 

3605 if k == 1: 

3606 yield [L] 

3607 elif n == k: 

3608 yield [[s] for s in L] 

3609 else: 

3610 e, *M = L 

3611 for p in set_partitions_helper(M, k - 1): 

3612 yield [[e], *p] 

3613 for p in set_partitions_helper(M, k): 

3614 for i in range(len(p)): 

3615 yield p[:i] + [[e] + p[i]] + p[i + 1 :] 

3616 

3617 if k is None: 

3618 for k in range(1, n + 1): 

3619 yield from filter( 

3620 lambda z: all(min_size <= len(bk) <= max_size for bk in z), 

3621 set_partitions_helper(L, k), 

3622 ) 

3623 else: 

3624 yield from filter( 

3625 lambda z: all(min_size <= len(bk) <= max_size for bk in z), 

3626 set_partitions_helper(L, k), 

3627 ) 

3628 

3629 

3630class time_limited: 

3631 """ 

3632 Yield items from *iterable* until *limit_seconds* have passed. 

3633 If the time limit expires before all items have been yielded, the 

3634 ``timed_out`` parameter will be set to ``True``. 

3635 

3636 >>> from time import sleep 

3637 >>> def generator(): 

3638 ... yield 1 

3639 ... yield 2 

3640 ... sleep(0.2) 

3641 ... yield 3 

3642 >>> iterable = time_limited(0.1, generator()) 

3643 >>> list(iterable) 

3644 [1, 2] 

3645 >>> iterable.timed_out 

3646 True 

3647 

3648 Note that the time is checked before each item is yielded, and iteration 

3649 stops if the time elapsed is greater than *limit_seconds*. If your time 

3650 limit is 1 second, but it takes 2 seconds to generate the first item from 

3651 the iterable, the function will run for 2 seconds and not yield anything. 

3652 As a special case, when *limit_seconds* is zero, the iterator never 

3653 returns anything. 

3654 

3655 """ 

3656 

3657 def __init__(self, limit_seconds, iterable): 

3658 if limit_seconds < 0: 

3659 raise ValueError('limit_seconds must be positive') 

3660 self.limit_seconds = limit_seconds 

3661 self._iterator = iter(iterable) 

3662 self._start_time = monotonic() 

3663 self.timed_out = False 

3664 

3665 def __iter__(self): 

3666 return self 

3667 

3668 def __next__(self): 

3669 if self.limit_seconds == 0: 

3670 self.timed_out = True 

3671 raise StopIteration 

3672 item = next(self._iterator) 

3673 if monotonic() - self._start_time > self.limit_seconds: 

3674 self.timed_out = True 

3675 raise StopIteration 

3676 

3677 return item 

3678 

3679 

3680def only(iterable, default=None, too_long=None): 

3681 """If *iterable* has only one item, return it. 

3682 If it has zero items, return *default*. 

3683 If it has more than one item, raise the exception given by *too_long*, 

3684 which is ``ValueError`` by default. 

3685 

3686 >>> only([], default='missing') 

3687 'missing' 

3688 >>> only([1]) 

3689 1 

3690 >>> only([1, 2]) # doctest: +IGNORE_EXCEPTION_DETAIL 

3691 Traceback (most recent call last): 

3692 ... 

3693 ValueError: Expected exactly one item in iterable, but got 1, 2, 

3694 and perhaps more.' 

3695 >>> only([1, 2], too_long=TypeError) # doctest: +IGNORE_EXCEPTION_DETAIL 

3696 Traceback (most recent call last): 

3697 ... 

3698 TypeError 

3699 

3700 Note that :func:`only` attempts to advance *iterable* twice to ensure there 

3701 is only one item. See :func:`spy` or :func:`peekable` to check 

3702 iterable contents less destructively. 

3703 

3704 """ 

3705 iterator = iter(iterable) 

3706 for first in iterator: 

3707 for second in iterator: 

3708 if too_long is not None: 

3709 raise too_long 

3710 raise ValueError( 

3711 f'Expected exactly one item in iterable, but got {first!r}, ' 

3712 f'{second!r}, and perhaps more.' 

3713 ) 

3714 return first 

3715 return default 

3716 

3717 

3718def ichunked(iterable, n): 

3719 """Break *iterable* into sub-iterables with *n* elements each. 

3720 :func:`ichunked` is like :func:`chunked`, but it yields iterables 

3721 instead of lists. 

3722 

3723 If the sub-iterables are read in order, the elements of *iterable* 

3724 won't be stored in memory. 

3725 If they are read out of order, :func:`itertools.tee` is used to cache 

3726 elements as necessary. 

3727 

3728 >>> from itertools import count 

3729 >>> all_chunks = ichunked(count(), 4) 

3730 >>> c_1, c_2, c_3 = next(all_chunks), next(all_chunks), next(all_chunks) 

3731 >>> list(c_2) # c_1's elements have been cached; c_3's haven't been 

3732 [4, 5, 6, 7] 

3733 >>> list(c_1) 

3734 [0, 1, 2, 3] 

3735 >>> list(c_3) 

3736 [8, 9, 10, 11] 

3737 

3738 """ 

3739 if n is not None and n < 0: 

3740 raise ValueError('n must be at least 0') 

3741 if n == 0: 

3742 return 

3743 

3744 iterator = iter(iterable) 

3745 for first in iterator: 

3746 rest = islice(iterator, n - 1) 

3747 cache, cacher = tee(rest) 

3748 yield chain([first], rest, cache) 

3749 consume(cacher) 

3750 

3751 

3752def iequals(*iterables): 

3753 """Return ``True`` if all given *iterables* are equal to each other, 

3754 which means that they contain the same elements in the same order. 

3755 

3756 The function is useful for comparing iterables of different data types 

3757 or iterables that do not support equality checks. 

3758 

3759 >>> iequals("abc", ['a', 'b', 'c'], ('a', 'b', 'c'), iter("abc")) 

3760 True 

3761 

3762 >>> iequals("abc", "acb") 

3763 False 

3764 

3765 Not to be confused with :func:`all_equal`, which checks whether all 

3766 elements of iterable are equal to each other. 

3767 

3768 """ 

3769 try: 

3770 return all(map(all_equal, zip(*iterables, strict=True))) 

3771 except ValueError: 

3772 return False 

3773 

3774 

3775def distinct_combinations(iterable, r): 

3776 """Yield the distinct combinations of *r* items taken from *iterable*. 

3777 

3778 >>> list(distinct_combinations([0, 0, 1], 2)) 

3779 [(0, 0), (0, 1)] 

3780 

3781 Equivalent to ``set(combinations(iterable))``, except duplicates are not 

3782 generated and thrown away. For larger input sequences this is much more 

3783 efficient. 

3784 

3785 """ 

3786 if r < 0: 

3787 raise ValueError('r must be non-negative') 

3788 elif r == 0: 

3789 yield () 

3790 return 

3791 pool = tuple(iterable) 

3792 generators = [unique_everseen(enumerate(pool), key=itemgetter(1))] 

3793 current_combo = [None] * r 

3794 level = 0 

3795 while generators: 

3796 try: 

3797 cur_idx, p = next(generators[-1]) 

3798 except StopIteration: 

3799 generators.pop() 

3800 level -= 1 

3801 continue 

3802 current_combo[level] = p 

3803 if level + 1 == r: 

3804 yield tuple(current_combo) 

3805 else: 

3806 generators.append( 

3807 unique_everseen( 

3808 enumerate(pool[cur_idx + 1 :], cur_idx + 1), 

3809 key=itemgetter(1), 

3810 ) 

3811 ) 

3812 level += 1 

3813 

3814 

3815def filter_except(validator, iterable, *exceptions): 

3816 """Yield the items from *iterable* for which the *validator* function does 

3817 not raise one of the specified *exceptions*. 

3818 

3819 *validator* is called for each item in *iterable*. 

3820 It should be a function that accepts one argument and raises an exception 

3821 if that item is not valid. 

3822 

3823 >>> iterable = ['1', '2', 'three', '4', None] 

3824 >>> list(filter_except(int, iterable, ValueError, TypeError)) 

3825 ['1', '2', '4'] 

3826 

3827 If an exception other than one given by *exceptions* is raised by 

3828 *validator*, it is raised like normal. 

3829 """ 

3830 for item in iterable: 

3831 try: 

3832 validator(item) 

3833 except exceptions: 

3834 pass 

3835 else: 

3836 yield item 

3837 

3838 

3839def map_except(function, iterable, *exceptions): 

3840 """Transform each item from *iterable* with *function* and yield the 

3841 result, unless *function* raises one of the specified *exceptions*. 

3842 

3843 *function* is called to transform each item in *iterable*. 

3844 It should accept one argument. 

3845 

3846 >>> iterable = ['1', '2', 'three', '4', None] 

3847 >>> list(map_except(int, iterable, ValueError, TypeError)) 

3848 [1, 2, 4] 

3849 

3850 If an exception other than one given by *exceptions* is raised by 

3851 *function*, it is raised like normal. 

3852 """ 

3853 for item in iterable: 

3854 try: 

3855 yield function(item) 

3856 except exceptions: 

3857 pass 

3858 

3859 

3860def map_if(iterable, pred, func, func_else=None): 

3861 """Evaluate each item from *iterable* using *pred*. If the result is 

3862 equivalent to ``True``, transform the item with *func* and yield it. 

3863 Otherwise, transform the item with *func_else* and yield it. 

3864 

3865 *pred*, *func*, and *func_else* should each be functions that accept 

3866 one argument. By default, *func_else* is the identity function. 

3867 

3868 >>> from math import sqrt 

3869 >>> iterable = list(range(-5, 5)) 

3870 >>> iterable 

3871 [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4] 

3872 >>> list(map_if(iterable, lambda x: x > 3, lambda x: 'toobig')) 

3873 [-5, -4, -3, -2, -1, 0, 1, 2, 3, 'toobig'] 

3874 >>> list(map_if(iterable, lambda x: x >= 0, 

3875 ... lambda x: f'{sqrt(x):.2f}', lambda x: None)) 

3876 [None, None, None, None, None, '0.00', '1.00', '1.41', '1.73', '2.00'] 

3877 """ 

3878 

3879 if func_else is None: 

3880 for item in iterable: 

3881 yield func(item) if pred(item) else item 

3882 

3883 else: 

3884 for item in iterable: 

3885 yield func(item) if pred(item) else func_else(item) 

3886 

3887 

3888def _sample_unweighted(iterator, k, strict): 

3889 # Algorithm L in the 1994 paper by Kim-Hung Li: 

3890 # "Reservoir-Sampling Algorithms of Time Complexity O(n(1+log(N/n)))". 

3891 

3892 reservoir = list(islice(iterator, k)) 

3893 if strict and len(reservoir) < k: 

3894 raise ValueError('Sample larger than population') 

3895 W = 1.0 

3896 

3897 with suppress(StopIteration): 

3898 while True: 

3899 W *= random() ** (1 / k) 

3900 skip = floor(log(random()) / log1p(-W)) 

3901 element = next(islice(iterator, skip, None)) 

3902 reservoir[randrange(k)] = element 

3903 

3904 shuffle(reservoir) 

3905 return reservoir 

3906 

3907 

3908def _sample_weighted(iterator, k, weights, strict): 

3909 # Implementation of "A-ExpJ" from the 2006 paper by Efraimidis et al. : 

3910 # "Weighted random sampling with a reservoir". 

3911 

3912 # Log-transform for numerical stability for weights that are small/large 

3913 weight_keys = (log(random()) / weight for weight in weights) 

3914 

3915 # Fill up the reservoir (collection of samples) with the first `k` 

3916 # weight-keys and elements, then heapify the list. 

3917 reservoir = take(k, zip(weight_keys, iterator)) 

3918 if strict and len(reservoir) < k: 

3919 raise ValueError('Sample larger than population') 

3920 

3921 heapify(reservoir) 

3922 

3923 # The number of jumps before changing the reservoir is a random variable 

3924 # with an exponential distribution. Sample it using random() and logs. 

3925 smallest_weight_key, _ = reservoir[0] 

3926 weights_to_skip = log(random()) / smallest_weight_key 

3927 

3928 for weight, element in zip(weights, iterator): 

3929 if weight >= weights_to_skip: 

3930 # The notation here is consistent with the paper, but we store 

3931 # the weight-keys in log-space for better numerical stability. 

3932 smallest_weight_key, _ = reservoir[0] 

3933 t_w = exp(weight * smallest_weight_key) 

3934 r_2 = uniform(t_w, 1) # generate U(t_w, 1) 

3935 weight_key = log(r_2) / weight 

3936 heapreplace(reservoir, (weight_key, element)) 

3937 smallest_weight_key, _ = reservoir[0] 

3938 weights_to_skip = log(random()) / smallest_weight_key 

3939 else: 

3940 weights_to_skip -= weight 

3941 

3942 ret = [element for weight_key, element in reservoir] 

3943 shuffle(ret) 

3944 return ret 

3945 

3946 

3947def _sample_counted(population, k, counts, strict): 

3948 element = None 

3949 remaining = 0 

3950 

3951 def feed(i): 

3952 # Advance *i* steps ahead and consume an element 

3953 nonlocal element, remaining 

3954 

3955 while i + 1 > remaining: 

3956 i = i - remaining 

3957 element = next(population) 

3958 remaining = next(counts) 

3959 remaining -= i + 1 

3960 return element 

3961 

3962 with suppress(StopIteration): 

3963 reservoir = [] 

3964 for _ in range(k): 

3965 reservoir.append(feed(0)) 

3966 

3967 if strict and len(reservoir) < k: 

3968 raise ValueError('Sample larger than population') 

3969 

3970 with suppress(StopIteration): 

3971 W = 1.0 

3972 while True: 

3973 W *= random() ** (1 / k) 

3974 skip = floor(log(random()) / log1p(-W)) 

3975 element = feed(skip) 

3976 reservoir[randrange(k)] = element 

3977 

3978 shuffle(reservoir) 

3979 return reservoir 

3980 

3981 

3982def sample(iterable, k, weights=None, *, counts=None, strict=False): 

3983 """Return a *k*-length list of elements chosen (without replacement) 

3984 from the *iterable*. 

3985 

3986 Similar to :func:`random.sample`, but works on inputs that aren't 

3987 indexable (such as sets and dictionaries) and on inputs where the 

3988 size isn't known in advance (such as generators). 

3989 

3990 >>> iterable = range(100) 

3991 >>> sample(iterable, 5) # doctest: +SKIP 

3992 [81, 60, 96, 16, 4] 

3993 

3994 For iterables with repeated elements, you may supply *counts* to 

3995 indicate the repeats. 

3996 

3997 >>> iterable = ['a', 'b'] 

3998 >>> counts = [3, 4] # Equivalent to 'a', 'a', 'a', 'b', 'b', 'b', 'b' 

3999 >>> sample(iterable, k=3, counts=counts) # doctest: +SKIP 

4000 ['a', 'a', 'b'] 

4001 

4002 An iterable with *weights* may be given: 

4003 

4004 >>> iterable = range(100) 

4005 >>> weights = (i * i + 1 for i in range(100)) 

4006 >>> sampled = sample(iterable, 5, weights=weights) 

4007 >>> len(sampled), len(set(sampled)) 

4008 (5, 5) 

4009 

4010 Weighted selections are made without replacement. 

4011 After an element is selected, it is removed from the pool and the 

4012 relative weights of the other elements increase (this 

4013 does not match the behavior of :func:`random.sample`'s *counts* 

4014 parameter). Note that *weights* may not be used with *counts*. 

4015 

4016 If the length of *iterable* is less than *k*, 

4017 ``ValueError`` is raised if *strict* is ``True`` and 

4018 all elements are returned (in shuffled order) if *strict* is ``False``. 

4019 

4020 By default, the `Algorithm L <https://w.wiki/ANrM>`__ reservoir sampling 

4021 technique is used. When *weights* are provided, 

4022 `Algorithm A-ExpJ <https://w.wiki/ANrS>`__ is used instead. 

4023 

4024 Notes on reproducibility: 

4025 

4026 * The algorithms rely on inexact floating-point functions provided 

4027 by the underlying math library (e.g. ``log``, ``log1p``, and ``pow``). 

4028 Those functions can `produce slightly different results 

4029 <https://members.loria.fr/PZimmermann/papers/accuracy.pdf>`_ on 

4030 different builds. Accordingly, selections can vary across builds 

4031 even for the same seed. 

4032 

4033 * The algorithms loop over the input and make selections based on 

4034 ordinal position, so selections from unordered collections (such as 

4035 sets) won't reproduce across sessions on the same platform using the 

4036 same seed. For example, this won't reproduce:: 

4037 

4038 >> seed(8675309) 

4039 >> sample(set('abcdefghijklmnopqrstuvwxyz'), 10) 

4040 ['c', 'p', 'e', 'w', 's', 'a', 'j', 'd', 'n', 't'] 

4041 

4042 """ 

4043 iterator = iter(iterable) 

4044 

4045 if k < 0: 

4046 raise ValueError('k must be non-negative') 

4047 

4048 if k == 0: 

4049 return [] 

4050 

4051 if weights is not None and counts is not None: 

4052 raise TypeError('weights and counts are mutually exclusive') 

4053 

4054 elif weights is not None: 

4055 weights = iter(weights) 

4056 return _sample_weighted(iterator, k, weights, strict) 

4057 

4058 elif counts is not None: 

4059 counts = iter(counts) 

4060 return _sample_counted(iterator, k, counts, strict) 

4061 

4062 else: 

4063 return _sample_unweighted(iterator, k, strict) 

4064 

4065 

4066def is_sorted(iterable, key=None, reverse=False, strict=False): 

4067 """Returns ``True`` if the items of iterable are in sorted order, and 

4068 ``False`` otherwise. *key* and *reverse* have the same meaning that they do 

4069 in the built-in :func:`sorted` function. 

4070 

4071 >>> is_sorted(['1', '2', '3', '4', '5'], key=int) 

4072 True 

4073 >>> is_sorted([5, 4, 3, 1, 2], reverse=True) 

4074 False 

4075 

4076 If *strict*, tests for strict sorting, that is, returns ``False`` if equal 

4077 elements are found: 

4078 

4079 >>> is_sorted([1, 2, 2]) 

4080 True 

4081 >>> is_sorted([1, 2, 2], strict=True) 

4082 False 

4083 

4084 The function returns ``False`` after encountering the first out-of-order 

4085 item, which means it may produce results that differ from the built-in 

4086 :func:`sorted` function for objects with unusual comparison dynamics 

4087 (like ``math.nan``). If there are no out-of-order items, the iterable is 

4088 exhausted. 

4089 """ 

4090 it = iterable if (key is None) else map(key, iterable) 

4091 a, b = tee(it) 

4092 next(b, None) 

4093 if reverse: 

4094 b, a = a, b 

4095 return all(map(lt, a, b)) if strict else not any(map(lt, b, a)) 

4096 

4097 

4098class AbortThread(BaseException): 

4099 pass 

4100 

4101 

4102class callback_iter: 

4103 """Convert a function that uses callbacks to an iterator. 

4104 

4105 .. deprecated:: 11.0.0 

4106 Will be removed in a future major release. 

4107 

4108 Let *func* be a function that takes a `callback` keyword argument. 

4109 For example: 

4110 

4111 >>> def func(callback=None): 

4112 ... for i, c in [(1, 'a'), (2, 'b'), (3, 'c')]: 

4113 ... if callback: 

4114 ... callback(i, c) 

4115 ... return 4 

4116 

4117 

4118 Use ``with callback_iter(func)`` to get an iterator over the parameters 

4119 that are delivered to the callback. 

4120 

4121 >>> with callback_iter(func) as it: 

4122 ... for args, kwargs in it: 

4123 ... print(args) 

4124 (1, 'a') 

4125 (2, 'b') 

4126 (3, 'c') 

4127 

4128 The function will be called in a background thread. The ``done`` property 

4129 indicates whether it has completed execution. 

4130 

4131 >>> it.done 

4132 True 

4133 

4134 If it completes successfully, its return value will be available 

4135 in the ``result`` property. 

4136 

4137 >>> it.result 

4138 4 

4139 

4140 Notes: 

4141 

4142 * If the function uses some keyword argument besides ``callback``, supply 

4143 *callback_kwd*. 

4144 * If it finished executing, but raised an exception, accessing the 

4145 ``result`` property will raise the same exception. 

4146 * If it hasn't finished executing, accessing the ``result`` 

4147 property from within the ``with`` block will raise ``RuntimeError``. 

4148 * If it hasn't finished executing, accessing the ``result`` property from 

4149 outside the ``with`` block will raise a 

4150 ``more_itertools.AbortThread`` exception. 

4151 * Provide *wait_seconds* to adjust how frequently the it is polled for 

4152 output. 

4153 

4154 """ 

4155 

4156 def __init__(self, func, callback_kwd='callback', wait_seconds=0.1): 

4157 self._func = func 

4158 self._callback_kwd = callback_kwd 

4159 self._aborted = False 

4160 self._future = None 

4161 self._wait_seconds = wait_seconds 

4162 

4163 # Lazily import concurrent.future 

4164 self._module = __import__('concurrent.futures').futures 

4165 self._executor = self._module.ThreadPoolExecutor(max_workers=1) 

4166 self._iterator = self._reader() 

4167 

4168 def __enter__(self): 

4169 return self 

4170 

4171 def __exit__(self, exc_type, exc_value, traceback): 

4172 self._aborted = True 

4173 self._executor.shutdown() 

4174 

4175 def __iter__(self): 

4176 return self 

4177 

4178 def __next__(self): 

4179 return next(self._iterator) 

4180 

4181 @property 

4182 def done(self): 

4183 if self._future is None: 

4184 return False 

4185 return self._future.done() 

4186 

4187 @property 

4188 def result(self): 

4189 if self._future: 

4190 try: 

4191 return self._future.result(timeout=0) 

4192 except self._module.TimeoutError: 

4193 pass 

4194 

4195 raise RuntimeError('Function has not yet completed') 

4196 

4197 def _reader(self): 

4198 q = Queue() 

4199 

4200 def callback(*args, **kwargs): 

4201 if self._aborted: 

4202 raise AbortThread('canceled by user') 

4203 

4204 q.put((args, kwargs)) 

4205 

4206 self._future = self._executor.submit( 

4207 self._func, **{self._callback_kwd: callback} 

4208 ) 

4209 

4210 while True: 

4211 try: 

4212 item = q.get(timeout=self._wait_seconds) 

4213 except Empty: 

4214 pass 

4215 else: 

4216 q.task_done() 

4217 yield item 

4218 

4219 if self._future.done(): 

4220 break 

4221 

4222 remaining = [] 

4223 while True: 

4224 try: 

4225 item = q.get_nowait() 

4226 except Empty: 

4227 break 

4228 else: 

4229 q.task_done() 

4230 remaining.append(item) 

4231 q.join() 

4232 yield from remaining 

4233 

4234 

4235def windowed_complete(iterable, n): 

4236 """ 

4237 Yield ``(beginning, middle, end)`` tuples, where: 

4238 

4239 * Each ``middle`` has *n* items from *iterable* 

4240 * Each ``beginning`` has the items before the ones in ``middle`` 

4241 * Each ``end`` has the items after the ones in ``middle`` 

4242 

4243 >>> iterable = range(7) 

4244 >>> n = 3 

4245 >>> for beginning, middle, end in windowed_complete(iterable, n): 

4246 ... print(beginning, middle, end) 

4247 () (0, 1, 2) (3, 4, 5, 6) 

4248 (0,) (1, 2, 3) (4, 5, 6) 

4249 (0, 1) (2, 3, 4) (5, 6) 

4250 (0, 1, 2) (3, 4, 5) (6,) 

4251 (0, 1, 2, 3) (4, 5, 6) () 

4252 

4253 Note that *n* must be at least 0 and most equal to the length of 

4254 *iterable*. 

4255 

4256 This function will exhaust the iterable and may require significant 

4257 storage. 

4258 """ 

4259 if n < 0: 

4260 raise ValueError('n must be >= 0') 

4261 

4262 seq = tuple(iterable) 

4263 size = len(seq) 

4264 

4265 if n > size: 

4266 raise ValueError('n must be <= len(seq)') 

4267 

4268 for i in range(size - n + 1): 

4269 beginning = seq[:i] 

4270 middle = seq[i : i + n] 

4271 end = seq[i + n :] 

4272 yield beginning, middle, end 

4273 

4274 

4275def all_unique(iterable, key=None): 

4276 """ 

4277 Returns ``True`` if all the elements of *iterable* are unique (no two 

4278 elements are equal). 

4279 

4280 >>> all_unique('ABCB') 

4281 False 

4282 

4283 If a *key* function is specified, it will be used to make comparisons. 

4284 

4285 >>> all_unique('ABCb') 

4286 True 

4287 >>> all_unique('ABCb', str.lower) 

4288 False 

4289 

4290 The function returns as soon as the first non-unique element is 

4291 encountered. Iterables with a mix of hashable and unhashable items can 

4292 be used, but the function will be slower for unhashable items. 

4293 """ 

4294 seenset = set() 

4295 seenset_add = seenset.add 

4296 seenlist = [] 

4297 seenlist_add = seenlist.append 

4298 for element in iterable if key is None else map(key, iterable): 

4299 try: 

4300 if element in seenset: 

4301 return False 

4302 seenset_add(element) 

4303 except TypeError: 

4304 if element in seenlist: 

4305 return False 

4306 seenlist_add(element) 

4307 return True 

4308 

4309 

4310def nth_product(index, *iterables, repeat=1): 

4311 """Equivalent to ``list(product(*iterables, repeat=repeat))[index]``. 

4312 

4313 The products of *iterables* can be ordered lexicographically. 

4314 :func:`nth_product` computes the product at sort position *index* without 

4315 computing the previous products. 

4316 

4317 >>> nth_product(8, range(2), range(2), range(2), range(2)) 

4318 (1, 0, 0, 0) 

4319 

4320 The *repeat* keyword argument specifies the number of repetitions 

4321 of the iterables. The above example is equivalent to:: 

4322 

4323 >>> nth_product(8, range(2), repeat=4) 

4324 (1, 0, 0, 0) 

4325 

4326 ``IndexError`` will be raised if the given *index* is invalid. 

4327 """ 

4328 pools = tuple(map(tuple, reversed(iterables))) * repeat 

4329 ns = tuple(map(len, pools)) 

4330 

4331 c = prod(ns) 

4332 

4333 if index < 0: 

4334 index += c 

4335 if not 0 <= index < c: 

4336 raise IndexError 

4337 

4338 result = [] 

4339 for pool, n in zip(pools, ns): 

4340 result.append(pool[index % n]) 

4341 index //= n 

4342 

4343 return tuple(reversed(result)) 

4344 

4345 

4346def nth_permutation(iterable, r, index): 

4347 """Equivalent to ``list(permutations(iterable, r))[index]``` 

4348 

4349 The subsequences of *iterable* that are of length *r* where order is 

4350 important can be ordered lexicographically. :func:`nth_permutation` 

4351 computes the subsequence at sort position *index* directly, without 

4352 computing the previous subsequences. 

4353 

4354 >>> nth_permutation('ghijk', 2, 5) 

4355 ('h', 'i') 

4356 

4357 ``ValueError`` will be raised if *r* is negative. 

4358 ``IndexError`` will be raised if the given *index* is invalid. 

4359 """ 

4360 pool = list(iterable) 

4361 n = len(pool) 

4362 if r is None: 

4363 r = n 

4364 c = perm(n, r) 

4365 

4366 if index < 0: 

4367 index += c 

4368 if not 0 <= index < c: 

4369 raise IndexError 

4370 

4371 result = [0] * r 

4372 q = index 

4373 for d in range(n - r + 1, n + 1): 

4374 q, i = divmod(q, d) 

4375 result[n - d] = i 

4376 if q == 0: 

4377 break 

4378 

4379 return tuple(map(pool.pop, result)) 

4380 

4381 

4382def nth_combination_with_replacement(iterable, r, index): 

4383 """Equivalent to 

4384 ``list(combinations_with_replacement(iterable, r))[index]``. 

4385 

4386 

4387 The subsequences with repetition of *iterable* that are of length *r* can 

4388 be ordered lexicographically. :func:`nth_combination_with_replacement` 

4389 computes the subsequence at sort position *index* directly, without 

4390 computing the previous subsequences with replacement. 

4391 

4392 >>> nth_combination_with_replacement(range(5), 3, 5) 

4393 (0, 1, 1) 

4394 

4395 ``ValueError`` will be raised if *r* is negative. 

4396 ``IndexError`` will be raised if the given *index* is invalid. 

4397 """ 

4398 pool = tuple(iterable) 

4399 n = len(pool) 

4400 if r < 0: 

4401 raise ValueError 

4402 c = comb(n + r - 1, r) if n else 0 if r else 1 

4403 

4404 if index < 0: 

4405 index += c 

4406 if not 0 <= index < c: 

4407 raise IndexError 

4408 

4409 result = [] 

4410 i = 0 

4411 while r: 

4412 r -= 1 

4413 while n >= 0: 

4414 num_combs = comb(n + r - 1, r) 

4415 if index < num_combs: 

4416 break 

4417 n -= 1 

4418 i += 1 

4419 index -= num_combs 

4420 result.append(pool[i]) 

4421 

4422 return tuple(result) 

4423 

4424 

4425def value_chain(*args): 

4426 """Yield all arguments passed to the function in the same order in which 

4427 they were passed. If an argument itself is iterable then iterate over its 

4428 values. 

4429 

4430 >>> list(value_chain(1, 2, 3, [4, 5, 6])) 

4431 [1, 2, 3, 4, 5, 6] 

4432 

4433 Binary and text strings are not considered iterable and are emitted 

4434 as-is: 

4435 

4436 >>> list(value_chain('12', '34', ['56', '78'])) 

4437 ['12', '34', '56', '78'] 

4438 

4439 Pre- or postpend a single element to an iterable: 

4440 

4441 >>> list(value_chain(1, [2, 3, 4, 5, 6])) 

4442 [1, 2, 3, 4, 5, 6] 

4443 >>> list(value_chain([1, 2, 3, 4, 5], 6)) 

4444 [1, 2, 3, 4, 5, 6] 

4445 

4446 Multiple levels of nesting are not flattened. 

4447 

4448 """ 

4449 scalar_types = (str, bytes) 

4450 for value in args: 

4451 if isinstance(value, scalar_types): 

4452 yield value 

4453 continue 

4454 try: 

4455 it = iter(value) 

4456 except TypeError: 

4457 yield value 

4458 else: 

4459 yield from it 

4460 

4461 

4462def product_index(element, *iterables, repeat=1): 

4463 """Equivalent to ``list(product(*iterables, repeat=repeat)).index(tuple(element))`` 

4464 

4465 The products of *iterables* can be ordered lexicographically. 

4466 :func:`product_index` computes the first index of *element* without 

4467 computing the previous products. 

4468 

4469 >>> product_index([8, 2], range(10), range(5)) 

4470 42 

4471 

4472 The *repeat* keyword argument specifies the number of repetitions 

4473 of the iterables:: 

4474 

4475 >>> product_index([8, 0, 7], range(10), repeat=3) 

4476 807 

4477 

4478 ``ValueError`` will be raised if the given *element* isn't in the product 

4479 of *args*. 

4480 """ 

4481 elements = tuple(element) 

4482 pools = tuple(map(tuple, iterables)) * repeat 

4483 if len(elements) != len(pools): 

4484 raise ValueError('element is not a product of args') 

4485 

4486 index = 0 

4487 for elem, pool in zip(elements, pools): 

4488 index = index * len(pool) + pool.index(elem) 

4489 return index 

4490 

4491 

4492def combination_index(element, iterable): 

4493 """Equivalent to ``list(combinations(iterable, r)).index(element)`` 

4494 

4495 The subsequences of *iterable* that are of length *r* can be ordered 

4496 lexicographically. :func:`combination_index` computes the index of the 

4497 first *element*, without computing the previous combinations. 

4498 

4499 >>> combination_index('adf', 'abcdefg') 

4500 10 

4501 

4502 ``ValueError`` will be raised if the given *element* isn't one of the 

4503 combinations of *iterable*. 

4504 """ 

4505 element = enumerate(element) 

4506 k, y = next(element, (None, None)) 

4507 if k is None: 

4508 return 0 

4509 

4510 indexes = [] 

4511 pool = enumerate(iterable) 

4512 for n, x in pool: 

4513 if x == y: 

4514 indexes.append(n) 

4515 tmp, y = next(element, (None, None)) 

4516 if tmp is None: 

4517 break 

4518 else: 

4519 k = tmp 

4520 else: 

4521 raise ValueError('element is not a combination of iterable') 

4522 

4523 n, _ = last(pool, default=(n, None)) 

4524 

4525 index = 1 

4526 for i, j in enumerate(reversed(indexes), start=1): 

4527 j = n - j 

4528 if i <= j: 

4529 index += comb(j, i) 

4530 

4531 return comb(n + 1, k + 1) - index 

4532 

4533 

4534def combination_with_replacement_index(element, iterable): 

4535 """Equivalent to 

4536 ``list(combinations_with_replacement(iterable, r)).index(element)`` 

4537 

4538 The subsequences with repetition of *iterable* that are of length *r* can 

4539 be ordered lexicographically. :func:`combination_with_replacement_index` 

4540 computes the index of the first *element*, without computing the previous 

4541 combinations with replacement. 

4542 

4543 >>> combination_with_replacement_index('adf', 'abcdefg') 

4544 20 

4545 

4546 ``ValueError`` will be raised if the given *element* isn't one of the 

4547 combinations with replacement of *iterable*. 

4548 """ 

4549 element = tuple(element) 

4550 r = len(element) 

4551 pool = tuple(iterable) 

4552 n = len(pool) 

4553 

4554 occupations = [0] * n 

4555 try: 

4556 i = 0 

4557 for e in element: 

4558 i = pool.index(e, i) 

4559 occupations[i] += 1 

4560 except ValueError: 

4561 raise ValueError( 

4562 'element is not a combination with replacement of iterable' 

4563 ) 

4564 

4565 index = 0 

4566 cumulative_sum = 0 

4567 for k in range(1, n): 

4568 cumulative_sum += occupations[k - 1] 

4569 j = (r - cumulative_sum) + (n - k) - 1 

4570 i = n - k 

4571 if i <= j: 

4572 index += comb(j, i) 

4573 

4574 return index 

4575 

4576 

4577def permutation_index(element, iterable): 

4578 """Equivalent to ``list(permutations(iterable, r)).index(element)``` 

4579 

4580 The subsequences of *iterable* that are of length *r* where order is 

4581 important can be ordered lexicographically. :func:`permutation_index` 

4582 computes the index of the first *element* directly, without computing 

4583 the previous permutations. 

4584 

4585 >>> permutation_index([1, 3, 2], range(5)) 

4586 19 

4587 

4588 ``ValueError`` will be raised if the given *element* isn't one of the 

4589 permutations of *iterable*. 

4590 """ 

4591 index = 0 

4592 pool = list(iterable) 

4593 for i, x in zip(range(len(pool), -1, -1), element): 

4594 r = pool.index(x) 

4595 index = index * i + r 

4596 del pool[r] 

4597 

4598 return index 

4599 

4600 

4601class countable: 

4602 """Wrap *iterable* and keep a count of how many items have been consumed. 

4603 

4604 The ``items_seen`` attribute starts at ``0`` and increments as the iterable 

4605 is consumed: 

4606 

4607 >>> iterable = map(str, range(10)) 

4608 >>> it = countable(iterable) 

4609 >>> it.items_seen 

4610 0 

4611 >>> next(it), next(it) 

4612 ('0', '1') 

4613 >>> list(it) 

4614 ['2', '3', '4', '5', '6', '7', '8', '9'] 

4615 >>> it.items_seen 

4616 10 

4617 """ 

4618 

4619 def __init__(self, iterable): 

4620 self._iterator = iter(iterable) 

4621 self.items_seen = 0 

4622 

4623 def __iter__(self): 

4624 return self 

4625 

4626 def __next__(self): 

4627 item = next(self._iterator) 

4628 self.items_seen += 1 

4629 

4630 return item 

4631 

4632 

4633def chunked_even(iterable, n): 

4634 """Break *iterable* into lists of approximately length *n*. 

4635 Items are distributed such the lengths of the lists differ by at most 

4636 1 item. 

4637 

4638 >>> iterable = [1, 2, 3, 4, 5, 6, 7] 

4639 >>> n = 3 

4640 >>> list(chunked_even(iterable, n)) # List lengths: 3, 2, 2 

4641 [[1, 2, 3], [4, 5], [6, 7]] 

4642 >>> list(chunked(iterable, n)) # List lengths: 3, 3, 1 

4643 [[1, 2, 3], [4, 5, 6], [7]] 

4644 

4645 """ 

4646 if n < 0: 

4647 raise ValueError('n must be at least 0') 

4648 if n == 0: 

4649 return 

4650 

4651 iterator = iter(iterable) 

4652 

4653 # Initialize a buffer to process the chunks while keeping 

4654 # some back to fill any underfilled chunks 

4655 min_buffer = (n - 1) * (n - 2) 

4656 buffer = list(islice(iterator, min_buffer)) 

4657 

4658 # Append items until we have a completed chunk 

4659 for _ in islice(map(buffer.append, iterator), n, None, n): 

4660 yield buffer[:n] 

4661 del buffer[:n] 

4662 

4663 # Check if any chunks need addition processing 

4664 if not buffer: 

4665 return 

4666 length = len(buffer) 

4667 

4668 # Chunks are either size `full_size <= n` or `partial_size = full_size - 1` 

4669 q, r = divmod(length, n) 

4670 num_lists = q + (1 if r > 0 else 0) 

4671 q, r = divmod(length, num_lists) 

4672 full_size = q + (1 if r > 0 else 0) 

4673 partial_size = full_size - 1 

4674 num_full = length - partial_size * num_lists 

4675 

4676 # Yield chunks of full size 

4677 partial_start_idx = num_full * full_size 

4678 if full_size > 0: 

4679 for i in range(0, partial_start_idx, full_size): 

4680 yield buffer[i : i + full_size] 

4681 

4682 # Yield chunks of partial size 

4683 if partial_size > 0: 

4684 for i in range(partial_start_idx, length, partial_size): 

4685 yield buffer[i : i + partial_size] 

4686 

4687 

4688def zip_broadcast(*objects, scalar_types=(str, bytes), strict=False): 

4689 """A version of :func:`zip` that "broadcasts" any scalar 

4690 (i.e., non-iterable) items into output tuples. 

4691 

4692 >>> iterable_1 = [1, 2, 3] 

4693 >>> iterable_2 = ['a', 'b', 'c'] 

4694 >>> scalar = '_' 

4695 >>> list(zip_broadcast(iterable_1, iterable_2, scalar)) 

4696 [(1, 'a', '_'), (2, 'b', '_'), (3, 'c', '_')] 

4697 

4698 The *scalar_types* keyword argument determines what types are considered 

4699 scalar. It is set to ``(str, bytes)`` by default. Set it to ``None`` to 

4700 treat strings and byte strings as iterable: 

4701 

4702 >>> list(zip_broadcast('abc', 0, 'xyz', scalar_types=None)) 

4703 [('a', 0, 'x'), ('b', 0, 'y'), ('c', 0, 'z')] 

4704 

4705 If the *strict* keyword argument is ``True``, then 

4706 ``ValueError`` will be raised if any of the iterables have 

4707 different lengths. 

4708 """ 

4709 

4710 def get_iterator(obj): 

4711 if scalar_types and isinstance(obj, scalar_types): 

4712 return None 

4713 try: 

4714 return iter(obj) 

4715 except TypeError: 

4716 return None 

4717 

4718 size = len(objects) 

4719 if not size: 

4720 return 

4721 

4722 new_item = [None] * size 

4723 iterables, iterable_positions = [], [] 

4724 for i, obj in enumerate(objects): 

4725 iterator = get_iterator(obj) 

4726 if iterator is None: 

4727 new_item[i] = obj 

4728 else: 

4729 iterables.append(iterator) 

4730 iterable_positions.append(i) 

4731 

4732 if not iterables: 

4733 yield tuple(objects) 

4734 return 

4735 

4736 for item in zip(*iterables, strict=strict): 

4737 for i, new_item[i] in zip(iterable_positions, item): 

4738 pass 

4739 yield tuple(new_item) 

4740 

4741 

4742def unique_in_window(iterable, n, key=None): 

4743 """Yield the items from *iterable* that haven't been seen recently. 

4744 *n* is the size of the sliding window. 

4745 

4746 >>> iterable = [0, 1, 0, 2, 3, 0] 

4747 >>> n = 3 

4748 >>> list(unique_in_window(iterable, n)) 

4749 [0, 1, 2, 3, 0] 

4750 

4751 The *key* function, if provided, will be used to determine uniqueness: 

4752 

4753 >>> list(unique_in_window('abAcda', 3, key=lambda x: x.lower())) 

4754 ['a', 'b', 'c', 'd', 'a'] 

4755 

4756 Updates a sliding window no larger than n and yields a value 

4757 if the item only occurs once in the updated window. 

4758 

4759 When `n == 1`, *unique_in_window* is memoryless: 

4760 

4761 >>> list(unique_in_window('aab', n=1)) 

4762 ['a', 'a', 'b'] 

4763 

4764 The items in *iterable* must be hashable. 

4765 

4766 """ 

4767 if n <= 0: 

4768 raise ValueError('n must be greater than 0') 

4769 

4770 window = deque(maxlen=n) 

4771 counts = Counter() 

4772 use_key = key is not None 

4773 

4774 for item in iterable: 

4775 if len(window) == n: 

4776 to_discard = window[0] 

4777 if counts[to_discard] == 1: 

4778 del counts[to_discard] 

4779 else: 

4780 counts[to_discard] -= 1 

4781 

4782 k = key(item) if use_key else item 

4783 if k not in counts: 

4784 yield item 

4785 counts[k] += 1 

4786 window.append(k) 

4787 

4788 

4789def duplicates_everseen(iterable, key=None): 

4790 """Yield duplicate elements after their first appearance. 

4791 

4792 >>> list(duplicates_everseen('mississippi')) 

4793 ['s', 'i', 's', 's', 'i', 'p', 'i'] 

4794 >>> list(duplicates_everseen('AaaBbbCccAaa', str.lower)) 

4795 ['a', 'a', 'b', 'b', 'c', 'c', 'A', 'a', 'a'] 

4796 

4797 This function is analogous to :func:`unique_everseen` and is subject to 

4798 the same performance considerations. 

4799 

4800 If you would like each duplicate to only appear once, much like ``uniq -d`` 

4801 in the Unix shell or ``Itertools::duplicates`` from the Rust ``itertools`` 

4802 crate, pass the return value of this function into :func:`unique_everseen` 

4803 with the same ``key``. 

4804 

4805 """ 

4806 seen_set = set() 

4807 seen_list = [] 

4808 use_key = key is not None 

4809 

4810 for element in iterable: 

4811 k = key(element) if use_key else element 

4812 try: 

4813 if k not in seen_set: 

4814 seen_set.add(k) 

4815 else: 

4816 yield element 

4817 except TypeError: 

4818 if k not in seen_list: 

4819 seen_list.append(k) 

4820 else: 

4821 yield element 

4822 

4823 

4824def duplicates_justseen(iterable, key=None): 

4825 """Yields serially-duplicate elements after their first appearance. 

4826 

4827 >>> list(duplicates_justseen('mississippi')) 

4828 ['s', 's', 'p'] 

4829 >>> list(duplicates_justseen('AaaBbbCccAaa', str.lower)) 

4830 ['a', 'a', 'b', 'b', 'c', 'c', 'a', 'a'] 

4831 

4832 This function is analogous to :func:`unique_justseen`. 

4833 

4834 """ 

4835 return flatten(g for _, g in groupby(iterable, key) for _ in g) 

4836 

4837 

4838def classify_unique(iterable, key=None): 

4839 """Classify each element in terms of its uniqueness. 

4840 

4841 For each element in the input iterable, return a 3-tuple consisting of: 

4842 

4843 1. The element itself 

4844 2. ``False`` if the element is equal to the one preceding it in the input, 

4845 ``True`` otherwise (i.e. the equivalent of :func:`unique_justseen`) 

4846 3. ``False`` if this element has been seen anywhere in the input before, 

4847 ``True`` otherwise (i.e. the equivalent of :func:`unique_everseen`) 

4848 

4849 >>> list(classify_unique('otto')) # doctest: +NORMALIZE_WHITESPACE 

4850 [('o', True, True), 

4851 ('t', True, True), 

4852 ('t', False, False), 

4853 ('o', True, False)] 

4854 

4855 This function is analogous to :func:`unique_everseen` and is subject to 

4856 the same performance considerations. 

4857 

4858 """ 

4859 seen_set = set() 

4860 seen_list = [] 

4861 use_key = key is not None 

4862 previous = None 

4863 

4864 for i, element in enumerate(iterable): 

4865 k = key(element) if use_key else element 

4866 is_unique_justseen = not i or previous != k 

4867 previous = k 

4868 is_unique_everseen = False 

4869 try: 

4870 if k not in seen_set: 

4871 seen_set.add(k) 

4872 is_unique_everseen = True 

4873 except TypeError: 

4874 if k not in seen_list: 

4875 seen_list.append(k) 

4876 is_unique_everseen = True 

4877 yield element, is_unique_justseen, is_unique_everseen 

4878 

4879 

4880def minmax(iterable_or_value, *others, key=None, default=_marker): 

4881 """Returns both the smallest and largest items from an iterable 

4882 or from two or more arguments. 

4883 

4884 >>> minmax([3, 1, 5]) 

4885 (1, 5) 

4886 

4887 >>> minmax(4, 2, 6) 

4888 (2, 6) 

4889 

4890 If a *key* function is provided, it will be used to transform the input 

4891 items for comparison. 

4892 

4893 >>> minmax([5, 30], key=str) # '30' sorts before '5' 

4894 (30, 5) 

4895 

4896 If a *default* value is provided, it will be returned if there are no 

4897 input items. 

4898 

4899 >>> minmax([], default=(0, 0)) 

4900 (0, 0) 

4901 

4902 Otherwise ``ValueError`` is raised. 

4903 

4904 This function makes a single pass over the input elements and takes care to 

4905 minimize the number of comparisons made during processing. 

4906 

4907 Note that unlike the builtin ``max`` function, which always returns the first 

4908 item with the maximum value, this function may return another item when there are 

4909 ties. 

4910 

4911 This function is based on the 

4912 `recipe <https://code.activestate.com/recipes/577916-fast-minmax-function>`__ by 

4913 Raymond Hettinger. 

4914 """ 

4915 iterable = (iterable_or_value, *others) if others else iterable_or_value 

4916 

4917 it = iter(iterable) 

4918 

4919 try: 

4920 lo = hi = next(it) 

4921 except StopIteration as exc: 

4922 if default is _marker: 

4923 raise ValueError( 

4924 '`minmax()` argument is an empty iterable. ' 

4925 'Provide a `default` value to suppress this error.' 

4926 ) from exc 

4927 return default 

4928 

4929 # Different branches depending on the presence of key. This saves a lot 

4930 # of unimportant copies which would slow the "key=None" branch 

4931 # significantly down. 

4932 if key is None: 

4933 for x, y in zip_longest(it, it, fillvalue=lo): 

4934 if y < x: 

4935 if y < lo: 

4936 lo = y 

4937 if hi < x: 

4938 hi = x 

4939 else: 

4940 if x < lo: 

4941 lo = x 

4942 if hi < y: 

4943 hi = y 

4944 

4945 else: 

4946 lo_key = hi_key = key(lo) 

4947 

4948 for x, y in zip_longest(it, it, fillvalue=lo): 

4949 x_key, y_key = key(x), key(y) 

4950 

4951 if y_key < x_key: 

4952 if y_key < lo_key: 

4953 lo, lo_key = y, y_key 

4954 if hi_key < x_key: 

4955 hi, hi_key = x, x_key 

4956 else: 

4957 if x_key < lo_key: 

4958 lo, lo_key = x, x_key 

4959 if hi_key < y_key: 

4960 hi, hi_key = y, y_key 

4961 

4962 return lo, hi 

4963 

4964 

4965def constrained_batches( 

4966 iterable, max_size, max_count=None, get_len=len, strict=True 

4967): 

4968 """Yield batches of items from *iterable* with a combined size limited by 

4969 *max_size*. 

4970 

4971 >>> iterable = [b'12345', b'123', b'12345678', b'1', b'1', b'12', b'1'] 

4972 >>> list(constrained_batches(iterable, 10)) 

4973 [(b'12345', b'123'), (b'12345678', b'1', b'1'), (b'12', b'1')] 

4974 

4975 If a *max_count* is supplied, the number of items per batch is also 

4976 limited. It must be greater than zero: 

4977 

4978 >>> iterable = [b'12345', b'123', b'12345678', b'1', b'1', b'12', b'1'] 

4979 >>> list(constrained_batches(iterable, 10, max_count = 2)) 

4980 [(b'12345', b'123'), (b'12345678', b'1'), (b'1', b'12'), (b'1',)] 

4981 

4982 If a *get_len* function is supplied, use that instead of :func:`len` to 

4983 determine item size. 

4984 

4985 If *strict* is ``True``, raise ``ValueError`` if any single item is bigger 

4986 than *max_size*. Otherwise, allow single items to exceed *max_size*. 

4987 """ 

4988 if max_size <= 0: 

4989 raise ValueError('maximum size must be greater than zero') 

4990 if max_count is not None and max_count <= 0: 

4991 raise ValueError('maximum count must be greater than zero') 

4992 

4993 batch = [] 

4994 batch_size = 0 

4995 batch_count = 0 

4996 for item in iterable: 

4997 item_len = get_len(item) 

4998 if strict and item_len > max_size: 

4999 raise ValueError('item size exceeds maximum size') 

5000 

5001 reached_count = batch_count == max_count 

5002 reached_size = item_len + batch_size > max_size 

5003 if batch_count and (reached_size or reached_count): 

5004 yield tuple(batch) 

5005 batch.clear() 

5006 batch_size = 0 

5007 batch_count = 0 

5008 

5009 batch.append(item) 

5010 batch_size += item_len 

5011 batch_count += 1 

5012 

5013 if batch: 

5014 yield tuple(batch) 

5015 

5016 

5017def gray_product(*iterables, repeat=1): 

5018 """Like :func:`itertools.product`, but return tuples in an order such 

5019 that only one element in the generated tuple changes from one iteration 

5020 to the next. 

5021 

5022 >>> list(gray_product('AB','CD')) 

5023 [('A', 'C'), ('B', 'C'), ('B', 'D'), ('A', 'D')] 

5024 

5025 The *repeat* keyword argument specifies the number of repetitions 

5026 of the iterables. For example, ``gray_product('AB', repeat=3)`` is 

5027 equivalent to ``gray_product('AB', 'AB', 'AB')``. 

5028 

5029 This function consumes all of the input iterables before producing output. 

5030 If any of the input iterables have fewer than two items, ``ValueError`` 

5031 is raised. 

5032 

5033 For information on the algorithm, see 

5034 `this section <https://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz>`__ 

5035 of Donald Knuth's *The Art of Computer Programming*. 

5036 """ 

5037 all_iterables = tuple(map(tuple, iterables)) * repeat 

5038 iterable_count = len(all_iterables) 

5039 for iterable in all_iterables: 

5040 if len(iterable) < 2: 

5041 raise ValueError("each iterable must have two or more items") 

5042 

5043 # This is based on "Algorithm H" from section 7.2.1.1, page 20. 

5044 # a holds the indexes of the source iterables for the n-tuple to be yielded 

5045 # f is the array of "focus pointers" 

5046 # o is the array of "directions" 

5047 a = [0] * iterable_count 

5048 f = list(range(iterable_count + 1)) 

5049 o = [1] * iterable_count 

5050 while True: 

5051 yield tuple(all_iterables[i][a[i]] for i in range(iterable_count)) 

5052 j = f[0] 

5053 f[0] = 0 

5054 if j == iterable_count: 

5055 break 

5056 a[j] = a[j] + o[j] 

5057 if a[j] == 0 or a[j] == len(all_iterables[j]) - 1: 

5058 o[j] = -o[j] 

5059 f[j] = f[j + 1] 

5060 f[j + 1] = j + 1 

5061 

5062 

5063def partial_product(*iterables, repeat=1): 

5064 """Yields tuples containing one item from each iterator, with subsequent 

5065 tuples changing a single item at a time by advancing each iterator until it 

5066 is exhausted. This sequence guarantees every value in each iterable is 

5067 output at least once without generating all possible combinations. 

5068 

5069 This may be useful, for example, when testing an expensive function. 

5070 

5071 >>> list(partial_product('AB', 'C', 'DEF')) 

5072 [('A', 'C', 'D'), ('B', 'C', 'D'), ('B', 'C', 'E'), ('B', 'C', 'F')] 

5073 

5074 The *repeat* keyword argument specifies the number of repetitions 

5075 of the iterables. For example, ``partial_product('AB', repeat=3)`` is 

5076 equivalent to ``partial_product('AB', 'AB', 'AB')``. 

5077 """ 

5078 

5079 all_iterables = tuple(map(tuple, iterables)) * repeat 

5080 iterators = tuple(map(iter, all_iterables)) 

5081 

5082 try: 

5083 prod = [next(it) for it in iterators] 

5084 except StopIteration: 

5085 return 

5086 yield tuple(prod) 

5087 

5088 for i, it in enumerate(iterators): 

5089 for prod[i] in it: 

5090 yield tuple(prod) 

5091 

5092 

5093def takewhile_inclusive(predicate, iterable): 

5094 """A variant of :func:`takewhile` that yields one additional element. 

5095 

5096 >>> list(takewhile_inclusive(lambda x: x < 5, [1, 4, 6, 4, 1])) 

5097 [1, 4, 6] 

5098 

5099 :func:`takewhile` would return ``[1, 4]``. 

5100 """ 

5101 for x in iterable: 

5102 yield x 

5103 if not predicate(x): 

5104 break 

5105 

5106 

5107def outer_product(func, xs, ys, *args, **kwargs): 

5108 """A generalized outer product that applies a binary function to all 

5109 pairs of items. Returns a 2D matrix with ``len(xs)`` rows and ``len(ys)`` 

5110 columns. 

5111 Also accepts ``*args`` and ``**kwargs`` that are passed to ``func``. 

5112 

5113 *ys* must not be empty; if it is, ``ValueError`` is raised. 

5114 

5115 Multiplication table: 

5116 

5117 >>> from operator import mul 

5118 >>> list(outer_product(mul, range(1, 4), range(1, 6))) 

5119 [(1, 2, 3, 4, 5), (2, 4, 6, 8, 10), (3, 6, 9, 12, 15)] 

5120 

5121 Cross tabulation: 

5122 

5123 >>> xs = ['A', 'B', 'A', 'A', 'B', 'B', 'A', 'A', 'B', 'B'] 

5124 >>> ys = ['X', 'X', 'X', 'Y', 'Z', 'Z', 'Y', 'Y', 'Z', 'Z'] 

5125 >>> pair_counts = Counter(zip(xs, ys)) 

5126 >>> count_rows = lambda x, y: pair_counts[x, y] 

5127 >>> list(outer_product(count_rows, sorted(set(xs)), sorted(set(ys)))) 

5128 [(2, 3, 0), (1, 0, 4)] 

5129 

5130 Usage with ``*args`` and ``**kwargs``: 

5131 

5132 >>> animals = ['cat', 'wolf', 'mouse'] 

5133 >>> list(outer_product(min, animals, animals, key=len)) 

5134 [('cat', 'cat', 'cat'), ('cat', 'wolf', 'wolf'), ('cat', 'wolf', 'mouse')] 

5135 """ 

5136 ys = tuple(ys) 

5137 return batched( 

5138 starmap(lambda x, y: func(x, y, *args, **kwargs), product(xs, ys)), 

5139 n=len(ys), 

5140 ) 

5141 

5142 

5143def iter_suppress(iterable, *exceptions): 

5144 """Yield each of the items from *iterable*. If the iteration raises one of 

5145 the specified *exceptions*, that exception will be suppressed and iteration 

5146 will stop. 

5147 

5148 >>> from itertools import chain 

5149 >>> def breaks_at_five(x): 

5150 ... while True: 

5151 ... if x >= 5: 

5152 ... raise RuntimeError 

5153 ... yield x 

5154 ... x += 1 

5155 >>> it_1 = iter_suppress(breaks_at_five(1), RuntimeError) 

5156 >>> it_2 = iter_suppress(breaks_at_five(2), RuntimeError) 

5157 >>> list(chain(it_1, it_2)) 

5158 [1, 2, 3, 4, 2, 3, 4] 

5159 """ 

5160 try: 

5161 yield from iterable 

5162 except exceptions: 

5163 return 

5164 

5165 

5166def filter_map(func, iterable): 

5167 """Apply *func* to every element of *iterable*, yielding only those which 

5168 are not ``None``. 

5169 

5170 >>> elems = ['1', 'a', '2', 'b', '3'] 

5171 >>> list(filter_map(lambda s: int(s) if s.isnumeric() else None, elems)) 

5172 [1, 2, 3] 

5173 """ 

5174 for x in iterable: 

5175 y = func(x) 

5176 if y is not None: 

5177 yield y 

5178 

5179 

5180def powerset_of_sets(iterable, *, baseset=set): 

5181 """Yields all possible subsets of the iterable. 

5182 

5183 >>> list(powerset_of_sets([1, 2, 3])) # doctest: +SKIP 

5184 [set(), {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}] 

5185 >>> list(powerset_of_sets([1, 1, 0])) # doctest: +SKIP 

5186 [set(), {1}, {0}, {0, 1}] 

5187 

5188 :func:`powerset_of_sets` takes care to minimize the number 

5189 of hash operations performed. 

5190 

5191 The *baseset* parameter determines what kind of sets are 

5192 constructed, either *set* or *frozenset*. 

5193 """ 

5194 sets = tuple(dict.fromkeys(map(frozenset, zip(iterable)))) 

5195 union = baseset().union 

5196 return chain.from_iterable( 

5197 starmap(union, combinations(sets, r)) for r in range(len(sets) + 1) 

5198 ) 

5199 

5200 

5201def join_mappings(**field_to_map): 

5202 """ 

5203 Joins multiple mappings together using their common keys. 

5204 

5205 >>> user_scores = {'elliot': 50, 'claris': 60} 

5206 >>> user_times = {'elliot': 30, 'claris': 40} 

5207 >>> join_mappings(score=user_scores, time=user_times) 

5208 {'elliot': {'score': 50, 'time': 30}, 'claris': {'score': 60, 'time': 40}} 

5209 """ 

5210 ret = defaultdict(dict) 

5211 

5212 for field_name, mapping in field_to_map.items(): 

5213 for key, value in mapping.items(): 

5214 ret[key][field_name] = value 

5215 

5216 return dict(ret) 

5217 

5218 

5219def _complex_sumprod(v1, v2): 

5220 """High precision sumprod() for complex numbers. 

5221 Used by :func:`dft` and :func:`idft`. 

5222 """ 

5223 

5224 real = attrgetter('real') 

5225 imag = attrgetter('imag') 

5226 r1 = chain(map(real, v1), map(neg, map(imag, v1))) 

5227 r2 = chain(map(real, v2), map(imag, v2)) 

5228 i1 = chain(map(real, v1), map(imag, v1)) 

5229 i2 = chain(map(imag, v2), map(real, v2)) 

5230 return complex(_fsumprod(r1, r2), _fsumprod(i1, i2)) 

5231 

5232 

5233def dft(xarr): 

5234 """Discrete Fourier Transform. *xarr* is a sequence of complex numbers. 

5235 Yields the components of the corresponding transformed output vector. 

5236 

5237 >>> import cmath 

5238 >>> xarr = [1, 2-1j, -1j, -1+2j] # time domain 

5239 >>> Xarr = [2, -2-2j, -2j, 4+4j] # frequency domain 

5240 >>> magnitudes, phases = zip(*map(cmath.polar, Xarr)) 

5241 >>> all(map(cmath.isclose, dft(xarr), Xarr)) 

5242 True 

5243 

5244 Inputs are restricted to numeric types that can add and multiply 

5245 with a complex number. This includes int, float, complex, and 

5246 Fraction, but excludes Decimal. 

5247 

5248 See :func:`idft` for the inverse Discrete Fourier Transform. 

5249 """ 

5250 N = len(xarr) 

5251 roots_of_unity = [e ** (n / N * tau * -1j) for n in range(N)] 

5252 for k in range(N): 

5253 coeffs = [roots_of_unity[k * n % N] for n in range(N)] 

5254 yield _complex_sumprod(xarr, coeffs) 

5255 

5256 

5257def idft(Xarr): 

5258 """Inverse Discrete Fourier Transform. *Xarr* is a sequence of 

5259 complex numbers. Yields the components of the corresponding 

5260 inverse-transformed output vector. 

5261 

5262 >>> import cmath 

5263 >>> xarr = [1, 2-1j, -1j, -1+2j] # time domain 

5264 >>> Xarr = [2, -2-2j, -2j, 4+4j] # frequency domain 

5265 >>> all(map(cmath.isclose, idft(Xarr), xarr)) 

5266 True 

5267 

5268 Inputs are restricted to numeric types that can add and multiply 

5269 with a complex number. This includes int, float, complex, and 

5270 Fraction, but excludes Decimal. 

5271 

5272 See :func:`dft` for the Discrete Fourier Transform. 

5273 """ 

5274 N = len(Xarr) 

5275 roots_of_unity = [e ** (n / N * tau * 1j) for n in range(N)] 

5276 for k in range(N): 

5277 coeffs = [roots_of_unity[k * n % N] for n in range(N)] 

5278 yield _complex_sumprod(Xarr, coeffs) / N 

5279 

5280 

5281def doublestarmap(func, iterable): 

5282 """Apply *func* to every item of *iterable* by dictionary unpacking 

5283 the item into *func*. 

5284 

5285 The difference between :func:`itertools.starmap` and :func:`doublestarmap` 

5286 parallels the distinction between ``func(*a)`` and ``func(**a)``. 

5287 

5288 >>> iterable = [{'a': 1, 'b': 2}, {'a': 40, 'b': 60}] 

5289 >>> list(doublestarmap(lambda a, b: a + b, iterable)) 

5290 [3, 100] 

5291 

5292 ``TypeError`` will be raised if *func*'s signature doesn't match the 

5293 mapping contained in *iterable* or if *iterable* does not contain mappings. 

5294 """ 

5295 for item in iterable: 

5296 yield func(**item) 

5297 

5298 

5299def _nth_prime_bounds(n): 

5300 """Bounds for the nth prime (counting from 1): lb < p_n < ub.""" 

5301 # At and above 688,383, the lb/ub spread is under 0.003 * p_n. 

5302 

5303 if n < 1: 

5304 raise ValueError 

5305 

5306 if n < 6: 

5307 return (n, 2.25 * n) 

5308 

5309 # https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities 

5310 upper_bound = n * log(n * log(n)) 

5311 lower_bound = upper_bound - n 

5312 if n >= 688_383: 

5313 upper_bound -= n * (1.0 - (log(log(n)) - 2.0) / log(n)) 

5314 

5315 return lower_bound, upper_bound 

5316 

5317 

5318def nth_prime(n, *, approximate=False): 

5319 """Return the nth prime (counting from 0). 

5320 

5321 >>> nth_prime(0) 

5322 2 

5323 >>> nth_prime(100) 

5324 547 

5325 

5326 If *approximate* is set to True, will return a prime close 

5327 to the nth prime. The estimation is much faster than computing 

5328 an exact result. 

5329 

5330 >>> nth_prime(200_000_000, approximate=True) # Exact result is 4222234763 

5331 4217820427 

5332 

5333 """ 

5334 lb, ub = _nth_prime_bounds(n + 1) 

5335 

5336 if not approximate or n <= 1_000_000: 

5337 return nth(sieve(ceil(ub)), n) 

5338 

5339 # Search from the midpoint and return the first odd prime 

5340 odd = floor((lb + ub) / 2) | 1 

5341 return first_true(count(odd, step=2), pred=is_prime) 

5342 

5343 

5344def argmin(iterable, *, key=None): 

5345 """ 

5346 Index of the first occurrence of a minimum value in an iterable. 

5347 

5348 >>> argmin('efghabcdijkl') 

5349 4 

5350 >>> argmin([3, 2, 1, 0, 4, 2, 1, 0]) 

5351 3 

5352 

5353 For example, look up a label corresponding to the position 

5354 of a value that minimizes a cost function:: 

5355 

5356 >>> def cost(x): 

5357 ... "Days for a wound to heal given a subject's age." 

5358 ... return x**2 - 20*x + 150 

5359 ... 

5360 >>> labels = ['homer', 'marge', 'bart', 'lisa', 'maggie'] 

5361 >>> ages = [ 35, 30, 10, 9, 1 ] 

5362 

5363 # Fastest healing family member 

5364 >>> labels[argmin(ages, key=cost)] 

5365 'bart' 

5366 

5367 # Age with fastest healing 

5368 >>> min(ages, key=cost) 

5369 10 

5370 

5371 """ 

5372 if key is not None: 

5373 iterable = map(key, iterable) 

5374 return min(enumerate(iterable), key=itemgetter(1))[0] 

5375 

5376 

5377def argmax(iterable, *, key=None): 

5378 """ 

5379 Index of the first occurrence of a maximum value in an iterable. 

5380 

5381 >>> argmax('abcdefghabcd') 

5382 7 

5383 >>> argmax([0, 1, 2, 3, 3, 2, 1, 0]) 

5384 3 

5385 

5386 For example, identify the best machine learning model:: 

5387 

5388 >>> models = ['svm', 'random forest', 'knn', 'naïve bayes'] 

5389 >>> accuracy = [ 68, 61, 84, 72 ] 

5390 

5391 # Most accurate model 

5392 >>> models[argmax(accuracy)] 

5393 'knn' 

5394 

5395 # Best accuracy 

5396 >>> max(accuracy) 

5397 84 

5398 

5399 """ 

5400 if key is not None: 

5401 iterable = map(key, iterable) 

5402 return max(enumerate(iterable), key=itemgetter(1))[0] 

5403 

5404 

5405def _extract_monotonic(iterator, indices): 

5406 'Non-decreasing indices, lazily consumed' 

5407 num_read = 0 

5408 for index in indices: 

5409 advance = index - num_read 

5410 try: 

5411 value = next(islice(iterator, advance, None)) 

5412 except ValueError: 

5413 if advance != -1 or index < 0: 

5414 raise ValueError(f'Invalid index: {index}') from None 

5415 except StopIteration: 

5416 raise IndexError(index) from None 

5417 else: 

5418 num_read += advance + 1 

5419 yield value 

5420 

5421 

5422def _extract_buffered(iterator, index_and_position): 

5423 'Arbitrary index order, greedily consumed' 

5424 buffer = {} 

5425 iterator_position = -1 

5426 next_to_emit = 0 

5427 

5428 for index, order in index_and_position: 

5429 advance = index - iterator_position 

5430 if advance: 

5431 try: 

5432 value = next(islice(iterator, advance - 1, None)) 

5433 except StopIteration: 

5434 raise IndexError(index) from None 

5435 iterator_position = index 

5436 

5437 buffer[order] = value 

5438 

5439 while next_to_emit in buffer: 

5440 yield buffer.pop(next_to_emit) 

5441 next_to_emit += 1 

5442 

5443 

5444def extract(iterable, indices, *, monotonic=False): 

5445 """Yield values at the specified indices. 

5446 

5447 Example: 

5448 

5449 >>> data = 'abcdefghijklmnopqrstuvwxyz' 

5450 >>> list(extract(data, [7, 4, 11, 11, 14])) 

5451 ['h', 'e', 'l', 'l', 'o'] 

5452 

5453 The *iterable* is consumed lazily and can be infinite. 

5454 

5455 When *monotonic* is false, the *indices* are consumed immediately 

5456 and must be finite. When *monotonic* is true, *indices* are consumed 

5457 lazily and can be infinite but must be non-decreasing. 

5458 

5459 Raises ``IndexError`` if an index lies beyond the iterable. 

5460 Raises ``ValueError`` for a negative index or for a decreasing 

5461 index when *monotonic* is true. 

5462 """ 

5463 

5464 iterator = iter(iterable) 

5465 indices = iter(indices) 

5466 

5467 if monotonic: 

5468 return _extract_monotonic(iterator, indices) 

5469 

5470 index_and_position = sorted(zip(indices, count())) 

5471 if index_and_position and index_and_position[0][0] < 0: 

5472 raise ValueError('Indices must be non-negative') 

5473 return _extract_buffered(iterator, index_and_position) 

5474 

5475 

5476class serialize: 

5477 """Wrap a non-concurrent iterator with a lock to enforce sequential access. 

5478 

5479 Applies a non-reentrant lock around calls to ``__next__``, allowing 

5480 iterator and generator instances to be shared by multiple consumer 

5481 threads. 

5482 """ 

5483 

5484 __slots__ = ('_iterator', '_lock') 

5485 

5486 def __init__(self, iterable): 

5487 self._iterator = iter(iterable) 

5488 self._lock = Lock() 

5489 

5490 def __iter__(self): 

5491 return self 

5492 

5493 def __next__(self): 

5494 with self._lock: 

5495 return next(self._iterator) 

5496 

5497 def send(self, value, /): 

5498 """Send a value to a generator. 

5499 

5500 Raises AttributeError if not a generator. 

5501 """ 

5502 with self._lock: 

5503 return self._iterator.send(value) 

5504 

5505 def throw(self, *args): 

5506 """Call throw() on a generator. 

5507 

5508 Raises AttributeError if not a generator. 

5509 """ 

5510 with self._lock: 

5511 return self._iterator.throw(*args) 

5512 

5513 def close(self): 

5514 """Call close() on a generator. 

5515 

5516 Raises AttributeError if not a generator. 

5517 """ 

5518 with self._lock: 

5519 return self._iterator.close() 

5520 

5521 

5522def synchronized(func): 

5523 """Wrap an iterator-returning callable to make its iterators thread-safe. 

5524 

5525 Existing itertools and more-itertools can be wrapped so that their 

5526 iterator instances are serialized. 

5527 

5528 For example, ``itertools.count`` does not make thread-safe instances, 

5529 but that is easily fixed with:: 

5530 

5531 atomic_counter = synchronized(itertools.count) 

5532 

5533 Can also be used as a decorator for generator functions definitions 

5534 so that the generator instances are serialized:: 

5535 

5536 @synchronized 

5537 def enumerate_and_timestamp(iterable): 

5538 for count, value in enumerate(iterable): 

5539 yield count, time_ns(), value 

5540 

5541 """ 

5542 

5543 @wraps(func) 

5544 def inner(*args, **kwargs): 

5545 iterator = func(*args, **kwargs) 

5546 return serialize(iterator) 

5547 

5548 return inner 

5549 

5550 

5551def concurrent_tee(iterable, n=2): 

5552 """Variant of itertools.tee() but with guaranteed threading semantics. 

5553 

5554 Takes a non-threadsafe iterator as an input and creates concurrent 

5555 tee objects for other threads to have reliable independent copies of 

5556 the data stream. 

5557 

5558 The new iterators are only thread-safe if consumed within a single thread. 

5559 To share just one of the new iterators across multiple threads, wrap it 

5560 with :func:`serialize`. 

5561 """ 

5562 

5563 if n < 0: 

5564 raise ValueError 

5565 if n == 0: 

5566 return () 

5567 iterator = _concurrent_tee(iterable) 

5568 result = [iterator] 

5569 for _ in range(n - 1): 

5570 result.append(_concurrent_tee(iterator)) 

5571 return tuple(result) 

5572 

5573 

5574class _concurrent_tee: 

5575 __slots__ = ('iterator', 'link', 'lock') 

5576 

5577 def __init__(self, iterable): 

5578 if isinstance(iterable, _concurrent_tee): 

5579 self.iterator = iterable.iterator 

5580 self.link = iterable.link 

5581 self.lock = iterable.lock 

5582 else: 

5583 self.iterator = iter(iterable) 

5584 self.link = [None, None] 

5585 self.lock = Lock() 

5586 

5587 def __iter__(self): 

5588 return self 

5589 

5590 def __next__(self): 

5591 link = self.link 

5592 if link[1] is None: 

5593 with self.lock: 

5594 if link[1] is None: 

5595 link[0] = next(self.iterator) 

5596 link[1] = [None, None] 

5597 value, self.link = link 

5598 return value 

5599 

5600 

5601def subfactorial(n): 

5602 """Number of permutations of *n* elements with no fixed points. 

5603 

5604 The :func:`subfactorial` function computes the length of 

5605 :func:`derangements`. For example, there are 1,854 ways to 

5606 rearrange the letters in word "epsilon" without leaving any 

5607 letter in its original position: 

5608 

5609 >>> from more_itertools import derangements, ilen 

5610 >>> ilen(derangements('epsilon')) 

5611 1854 

5612 >>> subfactorial(len('epsilon')) 

5613 1854 

5614 

5615 Reference: https://oeis.org/A000166 

5616 

5617 """ 

5618 if n < 0: 

5619 raise ValueError 

5620 sf = adj = 1 

5621 for i in range(n + 1): 

5622 sf = sf * i + adj 

5623 adj = -adj 

5624 return sf 

5625 

5626 

5627def _full_period_lcg(n): 

5628 "Returns values from range(n) in randomly shuffled order." 

5629 

5630 # The algorithm is a fluxed, full period linear congruential generator. 

5631 # Size *m* is a power of two. The *mask* speeds-up modulo calculations. 

5632 # The multiplier *a* and addend *c* are Hull-Dobell constants. See: 

5633 # https://jackgiffin.com/main/pdfs/Random-Number-Generators-T-E-Hull-and-A-R-Dobell.pdf 

5634 # The value *x* is a random starting point. 

5635 # The *flux* bitfield breaks-up patterns in the LCG. 

5636 

5637 m = 1 << n.bit_length() 

5638 mask = m - 1 

5639 a = randrange(5, m, 4) if m > 4 else 1 

5640 c = randrange(1, m, 2) if m > 1 else 1 

5641 x = randrange(m) 

5642 flux = randrange(m) 

5643 

5644 for _ in repeat(None, m): 

5645 index = x ^ flux 

5646 if index < n: 

5647 yield index 

5648 x = (a * x + c) & mask 

5649 

5650 

5651def _random_ordered_indices(n): 

5652 "Shuffle batches to mitigate the small state space of the LCG." 

5653 

5654 # Batched variation of Knuth's Algorithm M in §3.2.2 of TAOCP. 

5655 batch_size = 1024 

5656 iterable = range(n) if n <= batch_size else _full_period_lcg(n) 

5657 for batch in map(list, batched(iterable, batch_size)): 

5658 shuffle(batch) 

5659 yield from batch 

5660 

5661 

5662def random_ordered_range(*args): 

5663 "Return :func:`range` values in randomly shuffled order." 

5664 range_object = range(*args) 

5665 n = len(range_object) 

5666 for index in _random_ordered_indices(n): 

5667 yield range_object[index]