#! /usr/bin/env python

"""
A simple demonstration of a lazy list of sorts. Not extensively tested or thought through.

Apologies for the long lines.

*** WARNING: seriously, not at all extensively tested or thought through ***

(c) 2006 Tom Anderson <twic@urchin.earth.li>

Redistribution and use in source and binary forms, with or without modification, are permitted.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

"""

class lazylist(object):
	"""A lazy list is a wrapper round an iterable (not an iterator!) which behaves exactly like a list (where i've implemented it, and done so correctly), but in fact computes its contents lazily, and avoids building a list in memory altogether if you just want to iterate over it.
	
	Currently, this class handles iter, len and [] correctly. Probably.
	
	It would be nice if there was a way to duplicate iterators (an optional dup method on the iterator, say) - then, we could handle iteration over a partially evaluated list by iterating over the evaluated items, then switching to a duplicated main iterator for the rest.
	
	"""
	def __init__(self, source, length=None):
		"""Create a lazy list with a given source iterable, and, optionally, a length specified upfront.
		
		"""
		self.source = source # the source iterable
		self.length = length # the length of the list; None if we don't know it
		self.items = [] # the items we've evaluated so far
		self.it = None # an iterator over the source iterable, where the next item is the item after the last evaluated item; may be None if we haven't evaluated any items yet
	def __iter__(self):
		return iter(self.source)
	def __len__(self):
		if (self.length == None):
			self._intend()
		return self.length
	def __getitem__(self, index):
		if (index < 0):
			raise IndexError, index
		if (self.length != None):
			if (index >= self.length):
				raise IndexError, index
		self._intend((index + 1))
		return self.items[index] # may raise IndexError
	def _intend(self, length=None):
		"""Evaluates as many items of the list as necessary to extend the list of evaluated items to the given length. A value of None for the length is taken to mean infinity. If the end of the source is reached before this length is attained, the method stops there (as a side effect, self.length is set). The length to which the list of evaluated items has been extended is returned.
		
		The name is a bad pun on the fact that this like list.extend, but directed internally.
		
		"""
		if ((length != None) and (len(self.items) >= length)):
			return len(self.items)
		if ((self.length != None) and (len(self.items) == self.length)):
			return self.length
		if (self.it == None):
			assert len(self.items) == 0
			self.it = iter(self.source)
		try:
			if (length == None):
				self.items.extend(self.it)
				raise StopIteration
			else:
				for i in xrange((length - len(self.items))):
					self.items.append(self.it.next())
		except StopIteration:
			self.it = None
			self.length = len(self.items)
		return len(self.items)