4 @note Source http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66448
15 def ordered_itr(collection):
17 >>> [v for v in ordered_itr({"a": 1, "b": 2})]
19 >>> [v for v in ordered_itr([3, 1, 10, -20])]
22 if isinstance(collection, types.DictType):
23 keys = list(collection.iterkeys())
26 yield key, collection[key]
28 values = list(collection)
34 def itercat(*iterators):
36 Concatenate several iterators into one.
38 >>> [v for v in itercat([1, 2, 3], [4, 1, 3])]
46 def product(*args, **kwds):
47 # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
48 # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
49 pools = map(tuple, args) * kwds.get('repeat', 1)
52 result = [x+[y] for x in result for y in pool]
57 def iterwhile(func, iterator):
59 Iterate for as long as func(value) returns true.
60 >>> through = lambda b: b
61 >>> [v for v in iterwhile(through, [True, True, False])]
64 iterator = iter(iterator)
66 next = iterator.next()
72 def iterfirst(iterator, count=1):
74 Iterate through 'count' first values.
76 >>> [v for v in iterfirst([1, 2, 3, 4, 5], 3)]
79 iterator = iter(iterator)
80 for i in xrange(count):
84 def iterstep(iterator, n):
86 Iterate every nth value.
88 >>> [v for v in iterstep([1, 2, 3, 4, 5], 1)]
90 >>> [v for v in iterstep([1, 2, 3, 4, 5], 2)]
92 >>> [v for v in iterstep([1, 2, 3, 4, 5], 3)]
95 iterator = iter(iterator)
99 for dummy in xrange(n-1):
103 def itergroup(iterator, count, padValue = None):
105 Iterate in groups of 'count' values. If there
106 aren't enough values, the last result is padded with
109 >>> for val in itergroup([1, 2, 3, 4, 5, 6], 3):
113 >>> for val in itergroup([1, 2, 3, 4, 5, 6], 3):
117 >>> for val in itergroup([1, 2, 3, 4, 5, 6, 7], 3):
122 >>> for val in itergroup("123456", 3):
126 >>> for val in itergroup("123456", 3):
127 ... print repr("".join(val))
131 paddedIterator = itertools.chain(iterator, itertools.repeat(padValue, count-1))
132 nIterators = (paddedIterator, ) * count
133 return itertools.izip(*nIterators)
136 def xzip(*iterators):
137 """Iterative version of builtin 'zip'."""
138 iterators = itertools.imap(iter, iterators)
140 yield tuple([x.next() for x in iterators])
143 def xmap(func, *iterators):
144 """Iterative version of builtin 'map'."""
145 iterators = itertools.imap(iter, iterators)
149 # Emulate map behaviour, i.e. shorter
150 # sequences are padded with None when
151 # they run out of values.
153 for i in range(len(iterators)):
154 iterator = iterators[i]
159 yield iterator.next()
161 except StopIteration:
165 args = tuple(values())
166 if not values_left[0]:
171 def xfilter(func, iterator):
172 """Iterative version of builtin 'filter'."""
173 iterator = iter(iterator)
175 next = iterator.next()
180 def xreduce(func, iterator, default=None):
181 """Iterative version of builtin 'reduce'."""
182 iterator = iter(iterator)
184 prev = iterator.next()
185 except StopIteration:
188 for next in iterator:
190 prev = func(prev, next)
192 return func(prev, default)
196 def daterange(begin, end, delta = datetime.timedelta(1)):
198 Form a range of dates and iterate over them.
201 begin -- a date (or datetime) object; the beginning of the range.
202 end -- a date (or datetime) object; the end of the range.
203 delta -- (optional) a datetime.timedelta object; how much to step each iteration.
204 Default step is 1 day.
208 if not isinstance(delta, datetime.timedelta):
209 delta = datetime.timedelta(delta)
211 ZERO = datetime.timedelta(0)
227 class LazyList(object):
229 A Sequence whose values are computed lazily by an iterator.
231 Module for the creation and use of iterator-based lazy lists.
232 this module defines a class LazyList which can be used to represent sequences
233 of values generated lazily. One can also create recursively defined lazy lists
234 that generate their values based on ones previously generated.
236 Backport to python 2.5 by Michael Pust
239 __author__ = 'Dan Spitz'
241 def __init__(self, iterable):
242 self._exhausted = False
243 self._iterator = iter(iterable)
247 """Get the length of a LazyList's computed data."""
248 return len(self._data)
250 def __getitem__(self, i):
251 """Get an item from a LazyList.
252 i should be a positive integer or a slice object."""
253 if isinstance(i, int):
254 #index has not yet been yielded by iterator (or iterator exhausted
255 #before reaching that index)
259 raise ValueError('cannot index LazyList with negative number')
262 #LazyList slices are iterators over a portion of the list.
263 elif isinstance(i, slice):
264 start, stop, step = i.start, i.stop, i.step
265 if any(x is not None and x < 0 for x in (start, stop, step)):
266 raise ValueError('cannot index or step through a LazyList with'
268 #set start and step to their integer defaults if they are None.
274 def LazyListIterator():
279 else (lambda: count < stop)
284 #slices can go out of actual index range without raising an
289 return LazyListIterator()
291 raise TypeError('i must be an integer or slice')
294 """return an iterator over each value in the sequence,
295 whether it has been computed yet or not."""
299 """Return an iterator over the values in a LazyList that have
300 already been computed."""
301 return self[:len(self)]
303 def exhaust(self, index = None):
304 """Exhaust the iterator generating this LazyList's values.
305 if index is None, this will exhaust the iterator completely.
306 Otherwise, it will iterate over the iterator until either the list
307 has a value for index or the iterator is exhausted.
312 ind_range = itertools.count(len(self))
314 ind_range = range(len(self), index + 1)
316 for ind in ind_range:
318 self._data.append(self._iterator.next())
319 except StopIteration: #iterator is fully exhausted
320 self._exhausted = True
324 class RecursiveLazyList(LazyList):
326 def __init__(self, prod, *args, **kwds):
327 super(RecursiveLazyList, self).__init__(prod(self, *args, **kwds))
330 class RecursiveLazyListFactory:
332 def __init__(self, producer):
335 def __call__(self, *a, **kw):
336 return RecursiveLazyList(self._gen, *a, **kw)
341 Decorator for creating a RecursiveLazyList subclass.
342 This should decorate a generator function taking the LazyList object as its
343 first argument which yields the contents of the list in order.
345 >>> #fibonnacci sequence in a lazy list.
350 ... for a, b in itertools.izip(lst, lst[1:]):
353 >>> #now fibs can be indexed or iterated over as if it were an infinitely long list containing the fibonnaci sequence
356 >>> #prime numbers in a lazy list.
358 ... def primegen(lst):
360 ... for candidate in itertools.count(3): #start at next number after 2
361 ... #if candidate is not divisible by any smaller prime numbers,
363 ... if all(candidate % p for p in lst.computed()):
366 >>> #same for primes- treat it like an infinitely long list containing all prime numbers.
367 >>> primes = primegen()
368 >>> print fibs[0], fibs[1], fibs[2], primes[0], primes[1], primes[2]
370 >>> print list(fibs[:10]), list(primes[:10])
371 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
373 return RecursiveLazyListFactory(gen)
379 >>> misc.validate_decorator(map_func)
384 result = itertools.imap(f, args)
389 def reduce_func(function):
392 >>> misc.validate_decorator(reduce_func(lambda x: x))
399 result = reduce(function, f(args))
407 @note Python Version <2.5
409 >>> any_([True, True])
411 >>> any_([True, False])
413 >>> any_([False, False])
417 for element in iterable:
425 @note Python Version <2.5
427 >>> all_([True, True])
429 >>> all_([True, False])
431 >>> all_([False, False])
435 for element in iterable:
441 def for_every(pred, seq):
443 for_every takes a one argument predicate function and a sequence.
444 @param pred The predicate function should return true or false.
445 @returns true if every element in seq returns true for predicate, else returns false.
447 >>> for_every (lambda c: c > 5,(6,7,8,9))
450 @author Source:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52907
459 def there_exists(pred, seq):
461 there_exists takes a one argument predicate function and a sequence.
462 @param pred The predicate function should return true or false.
463 @returns true if any element in seq returns true for predicate, else returns false.
465 >>> there_exists (lambda c: c > 5,(6,7,8,9))
468 @author Source:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52907
477 def func_repeat(quantity, func, *args, **kwd):
479 Meant to be in connection with "reduce"
481 for i in xrange(quantity):
482 yield func(*args, **kwd)
485 def function_map(preds, item):
487 Meant to be in connection with "reduce"
489 results = (pred(item) for pred in preds)
494 def functional_if(combiner, preds, item):
496 Combines the result of a list of predicates applied to item according to combiner
498 @see any, every for example combiners
500 pass_bool = lambda b: b
502 bool_results = function_map(preds, item)
503 return combiner(pass_bool, bool_results)
506 def pushback_itr(itr):
508 >>> list(pushback_itr(xrange(5)))
512 >>> itr = pushback_itr(xrange(5))
515 ... if first and i == 2:
517 ... print itr.send(i)
527 >>> itr = pushback_itr(xrange(5))
530 ... if first and i == 2:
532 ... print itr.send(i)
533 ... print itr.send(i)
544 >>> itr = pushback_itr(xrange(5))
549 >>> print itr.send(10)
555 >>> print itr.send(20)
557 >>> print itr.send(30)
559 >>> print itr.send(40)
565 >>> print itr.send(50)
577 maybePushedBack = yield item
579 while queue or maybePushedBack is not None:
580 if maybePushedBack is not None:
581 queue.append(maybePushedBack)
582 maybePushedBack = yield None
585 maybePushedBack = yield item
588 def itr_available(queue, initiallyBlock = False):
591 while not queue.empty():
592 yield queue.get_nowait()
595 class BloomFilter(object):
597 http://en.wikipedia.org/wiki/Bloom_filter
599 http://code.activestate.com/recipes/577684-bloom-filter/
600 http://code.activestate.com/recipes/577686-bloom-filter/
602 >>> from random import sample
603 >>> from string import ascii_letters
604 >>> states = '''Alabama Alaska Arizona Arkansas California Colorado Connecticut
605 ... Delaware Florida Georgia Hawaii Idaho Illinois Indiana Iowa Kansas
606 ... Kentucky Louisiana Maine Maryland Massachusetts Michigan Minnesota
607 ... Mississippi Missouri Montana Nebraska Nevada NewHampshire NewJersey
608 ... NewMexico NewYork NorthCarolina NorthDakota Ohio Oklahoma Oregon
609 ... Pennsylvania RhodeIsland SouthCarolina SouthDakota Tennessee Texas Utah
610 ... Vermont Virginia Washington WestVirginia Wisconsin Wyoming'''.split()
611 >>> bf = BloomFilter(num_bits=1000, num_probes=14)
612 >>> for state in states:
614 >>> numStatesFound = sum(state in bf for state in states)
615 >>> numStatesFound, len(states)
618 >>> numGarbageFound = sum(''.join(sample(ascii_letters, 5)) in bf for i in range(trials))
619 >>> numGarbageFound, trials
623 def __init__(self, num_bits, num_probes):
624 num_words = (num_bits + 31) // 32
625 self._arr = array.array('B', [0]) * num_words
626 self._num_probes = num_probes
629 for i, mask in self._get_probes(key):
632 def union(self, bfilter):
633 if self._match_template(bfilter):
634 for i, b in enumerate(bfilter._arr):
637 # Union b/w two unrelated bloom filter raises this
638 raise ValueError("Mismatched bloom filters")
640 def intersection(self, bfilter):
641 if self._match_template(bfilter):
642 for i, b in enumerate(bfilter._arr):
645 # Intersection b/w two unrelated bloom filter raises this
646 raise ValueError("Mismatched bloom filters")
648 def __contains__(self, key):
649 return all(self._arr[i] & mask for i, mask in self._get_probes(key))
651 def _match_template(self, bfilter):
652 return self.num_bits == bfilter.num_bits and self.num_probes == bfilter.num_probes
654 def _get_probes(self, key):
655 hasher = random.Random(key).randrange
656 for _ in range(self._num_probes):
657 array_index = hasher(len(self._arr))
658 bit_index = hasher(32)
659 yield array_index, 1 << bit_index
662 if __name__ == "__main__":
664 print doctest.testmod()