"""Module for the creation and use of iterator-based lazy lists.
this module defines a class LazyList which can be used to represent sequences
of values generated lazily. One can also create recursively defined lazy lists
that generate their values based on ones previously generated.
Backport to python 2.5 by Michael Pust
"""
__author__ = 'Dan Spitz'
__all__ = ('LazyList', 'RecursiveLazyList', 'lazylist')
import itertools
class LazyList(object):
"""A Sequence whose values are computed lazily by an iterator.
"""
def __init__(self, iterable):
self._exhausted = False
self._iterator = iter(iterable)
self._data = []
def __len__(self):
"""Get the length of a LazyList's computed data."""
return len(self._data)
def __getitem__(self, i):
"""Get an item from a LazyList.
i should be a positive integer or a slice object."""
if isinstance(i, int):
#index has not yet been yielded by iterator (or iterator exhausted
#before reaching that index)
if i >= len(self):
self.exhaust(i)
elif i < 0:
raise ValueError('cannot index LazyList with negative number')
return self._data[i]
#LazyList slices are iterators over a portion of the list.
elif isinstance(i, slice):
start, stop, step = i.start, i.stop, i.step
if any(x is not None and x < 0 for x in (start, stop, step)):
raise ValueError('cannot index or step through a LazyList with'
'a negative number')
#set start and step to their integer defaults if they are None.
if start is None:
start = 0
if step is None:
step = 1
def LazyListIterator():
count = start
predicate = ((lambda: True) if stop is None
else (lambda: count < stop))
while predicate():
try:
yield self[count]
#slices can go out of actual index range without raising an
#error
except IndexError:
break
count += step
return LazyListIterator()
raise TypeError('i must be an integer or slice')
def __iter__(self):
"""return an iterator over each value in the sequence,
whether it has been computed yet or not."""
return self[:]
def computed(self):
"""Return an iterator over the values in a LazyList that have
already been computed."""
return self[:len(self)]
def exhaust(self, index = None):
"""Exhaust the iterator generating this LazyList's values.
if index is None, this will exhaust the iterator completely.
Otherwise, it will iterate over the iterator until either the list
has a value for index or the iterator is exhausted.
"""
if self._exhausted:
return
if index is None:
ind_range = itertools.count(len(self))
else:
ind_range = range(len(self), index + 1)
for ind in ind_range:
try:
self._data.append(self._iterator.next())
except StopIteration: #iterator is fully exhausted
self._exhausted = True
break
class RecursiveLazyList(LazyList):
def __init__(self, prod, *args, **kwds):
super(RecursiveLazyList,self).__init__(prod(self,*args, **kwds))
class RecursiveLazyListFactory:
def __init__(self, producer):
self._gen = producer
def __call__(self,*a,**kw):
return RecursiveLazyList(self._gen,*a,**kw)
def lazylist(gen):
"""Decorator for creating a RecursiveLazyList subclass.
This should decorate a generator function taking the LazyList object as its
first argument which yields the contents of the list in order.
"""
return RecursiveLazyListFactory(gen)
#two examples
if __name__ == '__main__':
#fibonnacci sequence in a lazy list.
@lazylist
def fibgen(lst):
yield 0
yield 1
for a, b in itertools.izip(lst, lst[1:]):
yield a + b
fibs = fibgen() #now fibs can be indexed or iterated over as if it were
#an infinitely long list containing the fibonnaci sequence
#prime numbers in a lazy list.
@lazylist
def primegen(lst):
yield 2
for candidate in itertools.count(3): #start at next number after 2
#if candidate is not divisible by any smaller prime numbers,
#it is a prime.
if all(candidate % p for p in lst.computed()):
yield candidate
primes = primegen() #same for primes- treat it like an infinitely long list
#containing all prime numbers.
print fibs[0], fibs[1], fibs[2], primes[0], primes[1], primes[2]
print list(fibs[:10]), list(primes[:10])
