/ adafruit_itertools / adafruit_itertools.py
adafruit_itertools.py
1 # 1. This LICENSE AGREEMENT is between the Python Software Foundation ("PSF"), and 2 # the Individual or Organization ("Licensee") accessing and otherwise using Python 3 # 3.7.3 software in source or binary form and its associated documentation. 4 5 # 2. Subject to the terms and conditions of this License Agreement, PSF hereby 6 # grants Licensee a nonexclusive, royalty-free, world-wide license to reproduce, 7 # analyze, test, perform and/or display publicly, prepare derivative works, 8 # distribute, and otherwise use Python 3.7.3 alone or in any derivative 9 # version, provided, however, that PSF's License Agreement and PSF's notice of 10 # copyright, i.e., "Copyright © 2001-2019 Python Software Foundation; All Rights 11 # Reserved" are retained in Python 3.7.3 alone or in any derivative version 12 # prepared by Licensee. 13 14 # 3. In the event Licensee prepares a derivative work that is based on or 15 # incorporates Python 3.7.3 or any part thereof, and wants to make the 16 # derivative work available to others as provided herein, then Licensee hereby 17 # agrees to include in any such work a brief summary of the changes made to Python 18 # 3.7.3. 19 20 # 4. PSF is making Python 3.7.3 available to Licensee on an "AS IS" basis. 21 # PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY OF 22 # EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND DISCLAIMS ANY REPRESENTATION OR 23 # WARRANTY OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR THAT THE 24 # USE OF PYTHON 3.7.3 WILL NOT INFRINGE ANY THIRD PARTY RIGHTS. 25 26 # 5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON 3.7.3 27 # FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS A RESULT OF 28 # MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON 3.7.3, OR ANY DERIVATIVE 29 # THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF. 30 31 # 6. This License Agreement will automatically terminate upon a material breach of 32 # its terms and conditions. 33 34 # 7. Nothing in this License Agreement shall be deemed to create any relationship 35 # of agency, partnership, or joint venture between PSF and Licensee. This License 36 # Agreement does not grant permission to use PSF trademarks or trade name in a 37 # trademark sense to endorse or promote products or services of Licensee, or any 38 # third party. 39 40 # 8. By copying, installing or otherwise using Python 3.7.3, Licensee agrees 41 # to be bound by the terms and conditions of this License Agreement. 42 """ 43 `adafruit_itertools` 44 ================================================================================ 45 46 Python's itertools adapted for CircuitPython by Dave Astels 47 48 Copyright 2001-2019 Python Software Foundation; All Rights Reserved 49 50 * Author(s): The PSF and Dave Astels 51 52 Implementation Notes 53 -------------------- 54 55 **Hardware:** 56 57 **Software and Dependencies:** 58 59 * Adafruit CircuitPython firmware for the supported boards: 60 https://github.com/adafruit/circuitpython/releases 61 """ 62 #pylint:disable=invalid-name,redefined-builtin,attribute-defined-outside-init 63 #pylint:disable=stop-iteration-return,anomalous-backslash-in-string 64 65 __version__ = "0.0.0-auto.0" 66 __repo__ = "https://github.com/adafruit/Adafruit_CircuitPython_Itertools.git" 67 68 69 def accumulate(iterable, func=lambda x, y: x + y): 70 """Make an iterator that returns accumulated sums, or accumulated 71 results of other binary functions (specified via the optional func 72 argument). If func is supplied, it should be a function of two 73 arguments that returns a value. Elements of the input iterable may 74 be any type that can be accepted as arguments to func. (For 75 example, with the default operation of addition, elements may be any 76 addable type including Decimal or Fraction.) If the input iterable 77 is empty, the output iterable will also be empty. 78 79 :param iterable: the source of values to be accumulated 80 :param func: the function to combine the accumulated value with the next one 81 """ 82 it = iter(iterable) 83 try: 84 acc = next(it) 85 except StopIteration: 86 return 87 yield acc 88 for element in it: 89 acc = func(acc, element) 90 yield acc 91 92 93 def chain(*iterables): 94 """Make an iterator that returns elements from the first iterable until it 95 is exhausted, then proceeds to the next iterable, until all of the iterables 96 are exhausted. Used for treating consecutive sequences as a single sequence. 97 98 :param p: a list of iterable from which to yield values 99 100 """ 101 # chain('ABC', 'DEF') --> A B C D E F 102 for i in iterables: 103 yield from i 104 105 106 def chain_from_iterable(iterables): 107 """Alternate constructor for chain(). Gets chained inputs from a 108 single iterable argument that is evaluated lazily. 109 110 :param iterables: an iterable of iterables 111 112 """ 113 # chain_from_iterable(['ABC', 'DEF']) --> A B C D E F 114 for it in iterables: 115 for element in it: 116 yield element 117 118 119 def combinations(iterable, r): 120 """Return r length subsequences of elements from the input iterable. 121 Combinations are emitted in lexicographic sort order. So, if the input 122 iterable is sorted, the combination tuples will be produced in sorted order. 123 124 Elements are treated as unique based on their position, not on their value. 125 So if the input elements are unique, there will be no repeat values in each 126 combination. 127 128 :param iterable: the iterable containing the the items to combine 129 :param r: the length of the resulting combinations 130 131 """ 132 # combinations('ABCD', 2) --> AB AC AD BC BD CD 133 # combinations(range(4), 3) --> 012 013 023 123 134 pool = tuple(iterable) 135 n = len(pool) 136 if r > n: 137 return 138 indices = list(range(r)) 139 yield tuple(pool[i] for i in indices) 140 while True: 141 index = 0 142 for i in reversed(range(r)): 143 if indices[i] != i + n - r: 144 index = i 145 break 146 else: 147 return 148 indices[index] += 1 149 for j in range(index+1, r): 150 indices[j] = indices[j-1] + 1 151 yield tuple(pool[i] for i in indices) 152 153 154 def combinations_with_replacement(iterable, r): 155 """Return r length subsequences of elements from the input iterable allowing 156 individual elements to be repeated more than once. 157 158 Combinations are emitted in lexicographic sort order. So, if the input 159 iterable is sorted, the combination tuples will be produced in sorted order. 160 161 Elements are treated as unique based on their position, not on their value. 162 So if the input elements are unique, the generated combinations will also be 163 unique. 164 165 :param iterable: the iterable containing the the items to combine 166 :param r: the length of the resulting combinations 167 168 """ 169 # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC 170 pool = tuple(iterable) 171 n = len(pool) 172 if not n and r: 173 return 174 indices = [0] * r 175 yield tuple(pool[i] for i in indices) 176 while True: 177 index = 0 178 for i in reversed(range(r)): 179 if indices[i] != n - 1: 180 index = i 181 break 182 else: 183 return 184 indices[index:] = [indices[index] + 1] * (r - index) 185 yield tuple(pool[i] for i in indices) 186 187 188 def compress(data, selectors): 189 """Make an iterator that filters elements from data returning only those 190 that have a corresponding element in selectors that evaluates to True. 191 Stops when either the data or selectors iterables has been exhausted. 192 193 :param data: the source of values 194 :param selector: the source of selection values 195 196 """ 197 # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F 198 return (d for d, s in zip(data, selectors) if s) 199 200 201 def count(start=0, step=1): 202 """Make an iterator that returns evenly spaced values starting with number 203 start. Often used as an argument to map() to generate consecutive data 204 points. Also, used with zip() to add sequence numbers. 205 206 :param start: the initial value of the sequence 207 :param step: how far apart subsequent values are 208 209 """ 210 while True: 211 yield start 212 start += step 213 214 215 def cycle(p): 216 """Make an iterator returning elements from the iterable and saving a copy 217 of each. When the iterable is exhausted, return elements from the saved 218 copy. Repeats indefinitely. 219 220 :param p: the iterable from which to yield elements 221 222 """ 223 try: 224 len(p) 225 except TypeError: 226 # len() is not defined for this type. Assume it is 227 # a finite iterable so we must cache the elements. 228 cache = [] 229 for i in p: 230 yield i 231 cache.append(i) 232 p = cache 233 while p: 234 yield from p 235 236 237 def dropwhile(predicate, iterable): 238 """Make an iterator that drops elements from the iterable as long as the 239 predicate is true; afterwards, returns every element. Note, the iterator 240 does not produce any output until the predicate first becomes false, so it 241 may have a lengthy start-up time. 242 243 :param predicate: used to test each element until it returns False 244 :param iterable: source of values 245 246 """ 247 # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1 248 iterable = iter(iterable) 249 for x in iterable: 250 if not predicate(x): 251 yield x 252 break 253 for x in iterable: 254 yield x 255 256 257 def filterfalse(predicate, iterable): 258 """Make an iterator that filters elements from iterable returning only those 259 for which the predicate is False. If predicate is None, return the items 260 that are false. 261 262 :param predicate: used to test each value 263 :param iterable: source of values 264 265 """ 266 # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8 267 if predicate is None: 268 predicate = bool 269 for x in iterable: 270 if not predicate(x): 271 yield x 272 273 274 class groupby: 275 """Make an iterator that returns consecutive keys and groups from the 276 277 iterable. The key is a function computing a key value for each element. If 278 not specified or is None, key defaults to an identity function and returns 279 the element unchanged. Generally, the iterable needs to already be sorted 280 on the same key function. 281 282 The operation of groupby() is similar to the uniq filter in Unix. It 283 generates a break or new group every time the value of the key 284 function changes (which is why it is usually necessary to have 285 sorted the data using the same key function). That behavior differs 286 from SQL’s GROUP BY which aggregates common elements regardless of 287 their input order. 288 289 The returned group is itself an iterator that shares the underlying 290 iterable with groupby(). Because the source is shared, when the 291 groupby() object is advanced, the previous group is no longer 292 visible. So, if that data is needed later, it should be stored as a 293 list. 294 295 :param iterable: the source of values 296 :param key: the key computation function (default is None) 297 298 """ 299 # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B 300 # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D 301 302 def __init__(self, iterable, key=None): 303 if key is None: 304 key = lambda x: x 305 self.keyfunc = key 306 self.it = iter(iterable) 307 self.tgtkey = self.currkey = self.currvalue = object() 308 309 def __iter__(self): 310 return self 311 312 def __next__(self): 313 self.id = object() 314 while self.currkey == self.tgtkey: 315 self.currvalue = next(self.it) # Exit on StopIteration 316 self.currkey = self.keyfunc(self.currvalue) 317 self.tgtkey = self.currkey 318 return (self.currkey, self._grouper(self.tgtkey, self.id)) 319 320 def _grouper(self, tgtkey, id): 321 while self.id is id and self.currkey == tgtkey: 322 yield self.currvalue 323 try: 324 self.currvalue = next(self.it) 325 except StopIteration: 326 return 327 self.currkey = self.keyfunc(self.currvalue) 328 329 330 def islice(p, start, stop=(), step=1): 331 """Make an iterator that returns selected elements from the 332 iterable. If start is non-zero and stop is unspecified, then the 333 value for start is used as end, and start is taken to be 0. Thus the 334 supplied value specifies how many elements are to be generated, 335 starting the the first one.If stop is specified, then elements from 336 iterable are skipped until start is reached. Afterward, elements are 337 returned consecutively unless step is set higher than one which 338 results in items being skipped. If stop is None, then iteration 339 continues until iterable is exhausted, if at all; otherwise, it 340 stops at the specified position. If stop is specified and is not 341 None, and is not greater than start then nothing is returned. Unlike 342 regular slicing, islice() does not support negative values for 343 start, stop, or step. Can be used to extract related fields from 344 data where the internal structure has been flattened (for example, a 345 multi-line report may list a name field on every third line). 346 347 :param p: the iterator items come from 348 :param start: the index of the first item 349 :param stop: the index one past the final item, None (the default) means 350 no end 351 :param step: how far to move to subsequent items (default is 1) 352 353 """ 354 355 if stop == (): 356 stop = start 357 start = 0 358 # TODO: optimizing or breaking semantics? 359 if stop is not None and start >= stop: 360 return 361 it = iter(p) 362 for _ in range(start): 363 next(it) 364 365 while True: 366 yield next(it) 367 for _ in range(step - 1): 368 next(it) 369 start += step 370 if stop is not None and start >= stop: 371 return 372 373 374 def permutations(iterable, r=None): 375 """Return successive r length permutations of elements in the iterable. 376 377 If r is not specified or is None, then r defaults to the length of the 378 iterable and all possible full-length permutations are generated. 379 380 Permutations are emitted in lexicographic sort order. So, if the input 381 iterable is sorted, the permutation tuples will be produced in sorted 382 order. 383 384 Elements are treated as unique based on their position, not on their 385 value. So if the input elements are unique, there will be no repeat 386 values in each permutation. 387 388 :param iterable: the source of values 389 :param r: the permutation length 390 391 """ 392 # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 393 # permutations(range(3)) --> 012 021 102 120 201 210 394 pool = tuple(iterable) 395 n = len(pool) 396 r = n if r is None else r 397 if r > n: 398 return 399 indices = list(range(n)) 400 cycles = list(range(n, n-r, -1)) 401 yield tuple(pool[i] for i in indices[:r]) 402 while n: 403 for i in reversed(range(r)): 404 cycles[i] -= 1 405 if cycles[i] == 0: 406 indices[i:] = indices[i+1:] + indices[i:i+1] 407 cycles[i] = n - i 408 else: 409 j = cycles[i] 410 indices[i], indices[-j] = indices[-j], indices[i] 411 yield tuple(pool[i] for i in indices[:r]) 412 break 413 else: 414 return 415 416 417 def product(*args, r=1): 418 """Cartesian product of input iterables. 419 420 Roughly equivalent to nested for-loops in a generator expression. For 421 example, product(A, B) returns the same as ((x,y) for x in A for y in 422 B). 423 424 The nested loops cycle like an odometer with the rightmost element 425 advancing on every iteration. This pattern creates a lexicographic 426 ordering so that if the input’s iterables are sorted, the product tuples 427 are emitted in sorted order. 428 429 To compute the product of an iterable with itself, specify the number of 430 repetitions with the optional repeat keyword argument. For example, 431 product(A, repeat=4) means the same as product(A, A, A, A). 432 433 :param args: sources of values 434 :param r: number of times to duplicate the (single) arg for taking a 435 product with itself (default is 1) 436 437 """ 438 # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy 439 # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 440 pools = [tuple(pool) for pool in args] * r 441 result = [[]] 442 for pool in pools: 443 result = [x+[y] for x in result for y in pool] 444 for prod in result: 445 yield tuple(prod) 446 447 448 def repeat(el, n=None): 449 """Make an iterator that returns object over and over again. Runs 450 indefinitely unless the times argument is specified. Used as argument to 451 map() for invariant parameters to the called function. Also used with zip() 452 to create an invariant part of a tuple record. 453 454 :param el: the object to yield 455 :param n: the number of time to yield, None (the default) means infinitely. 456 457 """ 458 if n is None: 459 while True: 460 yield el 461 else: 462 for _ in range(n): 463 yield el 464 465 466 def starmap(function, iterable): 467 """Make an iterator that computes the function using arguments obtained from 468 the iterable. Used instead of map() when argument parameters are already 469 grouped in tuples from a single iterable (the data has been “pre-zipped”). 470 The difference between map() and starmap() parallels the distinction between 471 function(a,b) and function(\*c). 472 473 :param function: the function to apply 474 :param iterable: where groups of arguments come from 475 476 """ 477 for args in iterable: 478 yield function(*args) 479 480 481 def takewhile(predicate, iterable): 482 """Make an iterator that returns elements from the iterable as long 483 as the predicate is true. 484 485 :param predicate: used to test values 486 :param iterable: source of values 487 488 """ 489 # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4 490 for x in iterable: 491 if predicate(x): 492 yield x 493 else: 494 break 495 496 497 def tee(iterable, n=2): 498 """Return n independent iterators from a single iterable. 499 500 :param iterable: the iterator from which to make iterators. 501 :param n: the number of iterators to make (default is 2) 502 503 """ 504 return [iter(iterable) for _ in range(n)] 505 506 507 def zip_longest(*args, fillvalue=None): 508 """Make an iterator that aggregates elements from each of the 509 iterables. If the iterables are of uneven length, missing values are 510 filled-in with fillvalue. Iteration continues until the longest 511 iterable is exhausted. 512 513 :param args: the iterables to combine 514 :param fillvalue: value to fill in those missing from shorter iterables 515 """ 516 # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D- 517 iterators = [iter(it) for it in args] 518 num_active = len(iterators) 519 if not num_active: 520 return 521 while True: 522 values = [] 523 for i, it in enumerate(iterators): 524 try: 525 value = next(it) 526 except StopIteration: 527 num_active -= 1 528 if not num_active: 529 return 530 iterators[i] = repeat(fillvalue) 531 value = fillvalue 532 values.append(value) 533 yield tuple(values)