1 #!/usr/bin/env python
3 """
4 @note Source http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66448
5 """
7 import itertools
8 import functools
9 import datetime
10 import types
13 def ordered_itr(collection):
14         """
15         >>> [v for v in ordered_itr({"a": 1, "b": 2})]
16         [('a', 1), ('b', 2)]
17         >>> [v for v in ordered_itr([3, 1, 10, -20])]
18         [-20, 1, 3, 10]
19         """
20         if isinstance(collection, types.DictType):
21                 keys = list(collection.iterkeys())
22                 keys.sort()
23                 for key in keys:
24                         yield key, collection[key]
25         else:
26                 values = list(collection)
27                 values.sort()
28                 for value in values:
29                         yield value
32 def itercat(*iterators):
33         """
34         Concatenate several iterators into one.
36         >>> [v for v in itercat([1, 2, 3], [4, 1, 3])]
37         [1, 2, 3, 4, 1, 3]
38         """
39         for i in iterators:
40                 for x in i:
41                         yield x
44 def iterwhile(func, iterator):
45         """
46         Iterate for as long as func(value) returns true.
47         >>> through = lambda b: b
48         >>> [v for v in iterwhile(through, [True, True, False])]
49         [True, True]
50         """
51         iterator = iter(iterator)
52         while 1:
53                 next = iterator.next()
54                 if not func(next):
55                         raise StopIteration
56                 yield next
59 def iterfirst(iterator, count=1):
60         """
61         Iterate through 'count' first values.
63         >>> [v for v in iterfirst([1, 2, 3, 4, 5], 3)]
64         [1, 2, 3]
65         """
66         iterator = iter(iterator)
67         for i in xrange(count):
68                 yield iterator.next()
71 def iterstep(iterator, n):
72         """
73         Iterate every nth value.
75         >>> [v for v in iterstep([1, 2, 3, 4, 5], 1)]
76         [1, 2, 3, 4, 5]
77         >>> [v for v in iterstep([1, 2, 3, 4, 5], 2)]
78         [1, 3, 5]
79         >>> [v for v in iterstep([1, 2, 3, 4, 5], 3)]
80         [1, 4]
81         """
82         iterator = iter(iterator)
83         while True:
84                 yield iterator.next()
85                 # skip n-1 values
86                 for dummy in xrange(n-1):
87                         iterator.next()
90 def itergroup(iterator, count, padValue = None):
91         """
92         Iterate in groups of 'count' values. If there
93         aren't enough values, the last result is padded with
94         None.
96         >>> for val in itergroup([1, 2, 3, 4, 5, 6], 3):
97         ...     print tuple(val)
98         (1, 2, 3)
99         (4, 5, 6)
100         >>> for val in itergroup([1, 2, 3, 4, 5, 6], 3):
101         ...     print list(val)
102         [1, 2, 3]
103         [4, 5, 6]
104         >>> for val in itergroup([1, 2, 3, 4, 5, 6, 7], 3):
105         ...     print tuple(val)
106         (1, 2, 3)
107         (4, 5, 6)
108         (7, None, None)
109         >>> for val in itergroup("123456", 3):
110         ...     print tuple(val)
111         ('1', '2', '3')
112         ('4', '5', '6')
113         >>> for val in itergroup("123456", 3):
114         ...     print repr("".join(val))
115         '123'
116         '456'
117         """
119         nIterators = (paddedIterator, ) * count
120         return itertools.izip(*nIterators)
123 def xzip(*iterators):
124         """Iterative version of builtin 'zip'."""
125         iterators = itertools.imap(iter, iterators)
126         while 1:
127                 yield tuple([x.next() for x in iterators])
130 def xmap(func, *iterators):
131         """Iterative version of builtin 'map'."""
132         iterators = itertools.imap(iter, iterators)
133         values_left = [1]
135         def values():
136                 # Emulate map behaviour, i.e. shorter
137                 # sequences are padded with None when
138                 # they run out of values.
139                 values_left[0] = 0
140                 for i in range(len(iterators)):
141                         iterator = iterators[i]
142                         if iterator is None:
143                                 yield None
144                         else:
145                                 try:
146                                         yield iterator.next()
147                                         values_left[0] = 1
148                                 except StopIteration:
149                                         iterators[i] = None
150                                         yield None
151         while 1:
152                 args = tuple(values())
153                 if not values_left[0]:
154                         raise StopIteration
155                 yield func(*args)
158 def xfilter(func, iterator):
159         """Iterative version of builtin 'filter'."""
160         iterator = iter(iterator)
161         while 1:
162                 next = iterator.next()
163                 if func(next):
164                         yield next
167 def xreduce(func, iterator, default=None):
168         """Iterative version of builtin 'reduce'."""
169         iterator = iter(iterator)
170         try:
171                 prev = iterator.next()
172         except StopIteration:
173                 return default
174         single = 1
175         for next in iterator:
176                 single = 0
177                 prev = func(prev, next)
178         if single:
179                 return func(prev, default)
180         return prev
183 def daterange(begin, end, delta = datetime.timedelta(1)):
184         """
185         Form a range of dates and iterate over them.
187         Arguments:
188         begin -- a date (or datetime) object; the beginning of the range.
189         end   -- a date (or datetime) object; the end of the range.
190         delta -- (optional) a datetime.timedelta object; how much to step each iteration.
191                         Default step is 1 day.
193         Usage:
194         """
195         if not isinstance(delta, datetime.timedelta):
196                 delta = datetime.timedelta(delta)
198         ZERO = datetime.timedelta(0)
200         if begin < end:
201                 if delta <= ZERO:
202                         raise StopIteration
203                 test = end.__gt__
204         else:
205                 if delta >= ZERO:
206                         raise StopIteration
207                 test = end.__lt__
209         while test(begin):
210                 yield begin
211                 begin += delta
214 class LazyList(object):
215         """
216         A Sequence whose values are computed lazily by an iterator.
218         Module for the creation and use of iterator-based lazy lists.
219         this module defines a class LazyList which can be used to represent sequences
220         of values generated lazily. One can also create recursively defined lazy lists
221         that generate their values based on ones previously generated.
223         Backport to python 2.5 by Michael Pust
224         """
226         __author__ = 'Dan Spitz'
228         def __init__(self, iterable):
229                 self._exhausted = False
230                 self._iterator = iter(iterable)
231                 self._data = []
233         def __len__(self):
234                 """Get the length of a LazyList's computed data."""
235                 return len(self._data)
237         def __getitem__(self, i):
238                 """Get an item from a LazyList.
239                 i should be a positive integer or a slice object."""
240                 if isinstance(i, int):
241                         #index has not yet been yielded by iterator (or iterator exhausted
242                         #before reaching that index)
243                         if i >= len(self):
244                                 self.exhaust(i)
245                         elif i < 0:
246                                 raise ValueError('cannot index LazyList with negative number')
247                         return self._data[i]
249                 #LazyList slices are iterators over a portion of the list.
250                 elif isinstance(i, slice):
251                         start, stop, step = i.start, i.stop, i.step
252                         if any(x is not None and x < 0 for x in (start, stop, step)):
253                                 raise ValueError('cannot index or step through a LazyList with'
254                                                                 'a negative number')
255                         #set start and step to their integer defaults if they are None.
256                         if start is None:
257                                 start = 0
258                         if step is None:
259                                 step = 1
261                         def LazyListIterator():
262                                 count = start
263                                 predicate = (
264                                         (lambda: True)
265                                         if stop is None
266                                         else (lambda: count < stop)
267                                 )
268                                 while predicate():
269                                         try:
270                                                 yield self[count]
271                                         #slices can go out of actual index range without raising an
272                                         #error
273                                         except IndexError:
274                                                 break
275                                         count += step
276                         return LazyListIterator()
278                 raise TypeError('i must be an integer or slice')
280         def __iter__(self):
281                 """return an iterator over each value in the sequence,
282                 whether it has been computed yet or not."""
283                 return self[:]
285         def computed(self):
286                 """Return an iterator over the values in a LazyList that have
288                 return self[:len(self)]
290         def exhaust(self, index = None):
291                 """Exhaust the iterator generating this LazyList's values.
292                 if index is None, this will exhaust the iterator completely.
293                 Otherwise, it will iterate over the iterator until either the list
294                 has a value for index or the iterator is exhausted.
295                 """
296                 if self._exhausted:
297                         return
298                 if index is None:
299                         ind_range = itertools.count(len(self))
300                 else:
301                         ind_range = range(len(self), index + 1)
303                 for ind in ind_range:
304                         try:
305                                 self._data.append(self._iterator.next())
306                         except StopIteration: #iterator is fully exhausted
307                                 self._exhausted = True
308                                 break
311 class RecursiveLazyList(LazyList):
313         def __init__(self, prod, *args, **kwds):
314                 super(RecursiveLazyList, self).__init__(prod(self, *args, **kwds))
317 class RecursiveLazyListFactory:
319         def __init__(self, producer):
320                 self._gen = producer
322         def __call__(self, *a, **kw):
323                 return RecursiveLazyList(self._gen, *a, **kw)
326 def lazylist(gen):
327         """
328         Decorator for creating a RecursiveLazyList subclass.
329         This should decorate a generator function taking the LazyList object as its
330         first argument which yields the contents of the list in order.
332         >>> #fibonnacci sequence in a lazy list.
333         >>> @lazylist
334         ... def fibgen(lst):
335         ...     yield 0
336         ...     yield 1
337         ...     for a, b in itertools.izip(lst, lst[1:]):
338         ...             yield a + b
339         ...
340         >>> #now fibs can be indexed or iterated over as if it were an infinitely long list containing the fibonnaci sequence
341         >>> fibs = fibgen()
342         >>>
343         >>> #prime numbers in a lazy list.
344         >>> @lazylist
345         ... def primegen(lst):
346         ...     yield 2
347         ...     for candidate in itertools.count(3): #start at next number after 2
348         ...             #if candidate is not divisible by any smaller prime numbers,
349         ...             #it is a prime.
350         ...             if all(candidate % p for p in lst.computed()):
351         ...                     yield candidate
352         ...
353         >>> #same for primes- treat it like an infinitely long list containing all prime numbers.
354         >>> primes = primegen()
355         >>> print fibs[0], fibs[1], fibs[2], primes[0], primes[1], primes[2]
356         0 1 1 2 3 5
357         >>> print list(fibs[:10]), list(primes[:10])
358         [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
359         """
360         return RecursiveLazyListFactory(gen)
363 def map_func(f):
364         """
365         >>> import misc
366         >>> misc.validate_decorator(map_func)
367         """
369         @functools.wraps(f)
370         def wrapper(*args):
371                 result = itertools.imap(f, args)
372                 return result
373         return wrapper
376 def reduce_func(function):
377         """
378         >>> import misc
379         >>> misc.validate_decorator(reduce_func(lambda x: x))
380         """
382         def decorator(f):
384                 @functools.wraps(f)
385                 def wrapper(*args):
386                         result = reduce(function, f(args))
387                         return result
388                 return wrapper
389         return decorator
392 def any_(iterable):
393         """
394         @note Python Version <2.5
396         >>> any_([True, True])
397         True
398         >>> any_([True, False])
399         True
400         >>> any_([False, False])
401         False
402         """
404         for element in iterable:
405                 if element:
406                         return True
407         return False
410 def all_(iterable):
411         """
412         @note Python Version <2.5
414         >>> all_([True, True])
415         True
416         >>> all_([True, False])
417         False
418         >>> all_([False, False])
419         False
420         """
422         for element in iterable:
423                 if not element:
424                         return False
425         return True
428 def for_every(pred, seq):
429         """
430         for_every takes a one argument predicate function and a sequence.
431         @param pred The predicate function should return true or false.
432         @returns true if every element in seq returns true for predicate, else returns false.
434         >>> for_every (lambda c: c > 5,(6,7,8,9))
435         True
437         @author Source:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52907
438         """
440         for i in seq:
441                 if not pred(i):
442                         return False
443         return True
446 def there_exists(pred, seq):
447         """
448         there_exists takes a one argument predicate     function and a sequence.
449         @param pred The predicate function should return true or false.
450         @returns true if any element in seq returns true for predicate, else returns false.
452         >>> there_exists (lambda c: c > 5,(6,7,8,9))
453         True
455         @author Source:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52907
456         """
458         for i in seq:
459                 if pred(i):
460                         return True
461         return False
464 def func_repeat(quantity, func, *args, **kwd):
465         """
466         Meant to be in connection with "reduce"
467         """
468         for i in xrange(quantity):
469                 yield func(*args, **kwd)
472 def function_map(preds, item):
473         """
474         Meant to be in connection with "reduce"
475         """
476         results = (pred(item) for pred in preds)
478         return results
481 def functional_if(combiner, preds, item):
482         """
483         Combines the result of a list of predicates applied to item according to combiner
485         @see any, every for example combiners
486         """
487         pass_bool = lambda b: b
489         bool_results = function_map(preds, item)
490         return combiner(pass_bool, bool_results)
493 def pushback_itr(itr):
494         """
495         >>> list(pushback_itr(xrange(5)))
496         [0, 1, 2, 3, 4]
497         >>>
498         >>> first = True
499         >>> itr = pushback_itr(xrange(5))
500         >>> for i in itr:
501         ...     print i
502         ...     if first and i == 2:
503         ...             first = False
504         ...             print itr.send(i)
505         0
506         1
507         2
508         None
509         2
510         3
511         4
512         >>>
513         >>> first = True
514         >>> itr = pushback_itr(xrange(5))
515         >>> for i in itr:
516         ...     print i
517         ...     if first and i == 2:
518         ...             first = False
519         ...             print itr.send(i)
520         ...             print itr.send(i)
521         0
522         1
523         2
524         None
525         None
526         2
527         2
528         3
529         4
530         >>>
531         >>> itr = pushback_itr(xrange(5))
532         >>> print itr.next()
533         0
534         >>> print itr.next()
535         1
536         >>> print itr.send(10)
537         None
538         >>> print itr.next()
539         10
540         >>> print itr.next()
541         2
542         >>> print itr.send(20)
543         None
544         >>> print itr.send(30)
545         None
546         >>> print itr.send(40)
547         None
548         >>> print itr.next()
549         40
550         >>> print itr.next()
551         30
552         >>> print itr.send(50)
553         None
554         >>> print itr.next()
555         50
556         >>> print itr.next()
557         20
558         >>> print itr.next()
559         3
560         >>> print itr.next()
561         4
562         """
563         for item in itr:
564                 maybePushedBack = yield item
565                 queue = []
566                 while queue or maybePushedBack is not None:
567                         if maybePushedBack is not None:
568                                 queue.append(maybePushedBack)
569                                 maybePushedBack = yield None
570                         else:
571                                 item = queue.pop()
572                                 maybePushedBack = yield item
575 def itr_available(queue, initiallyBlock = False):
576         if initiallyBlock:
577                 yield queue.get()
578         while not queue.empty():
579                 yield queue.get_nowait()
582 if __name__ == "__main__":
583         import doctest
584         print doctest.testmod()