# An implementation of lists via our Specification design pattern
# - It implements functional iterators like we saw in class
#   via the funcIterator() method
# - It also implements a python iterator using the __iter__() method
#   this makes List (and it subclasses) iterable. The result of __iter__() 
#   is a python iterator
# - I also use the __str__() method as a synonym for the toString() method, to 
#   be consistent with the python's conversion-to-string approach

class List:
  def __iter__ (self):
    return ListIterator(self)
  def __str__ (self):
    return self.toString()
  def isEmpty (self):
    raise 'isEmpty() is abstract'
  def first (self):
    raise 'first() is abstract'
  def rest (self):
    raise 'rest() is abstract'
  def toString (self):
    raise 'toString() is abstract'
  def funcIterator (self):
    raise 'funcIterator() is abstract'

class EmptyList (List):
  def isEmpty (self): 
    return True
  def first (self):
    raise 'EmptyList.first()'
  def rest (self):
    raise 'EmptyList.rest()'
  def toString (self):
    return ""
  def funcIterator (self):
    return EmptyListFuncIterator()

class ConsList (List):
  def __init__ (self,f,r):
    self.fst = f
    self.rst = r
  def isEmpty (self): 
    return False
  def first (self):
    return self.fst;
  def rest (self):
    return self.rst;
  def toString (self):
    return str(self.fst) + " " + self.rst.toString()
  def funcIterator (self):
    return ConsListFuncIterator(self.fst,self.rst)

# These are the two functional iterator classes, one per subclass of List
class EmptyListFuncIterator ():
  def hasElement (self): 
    return False
  def element (self): 
    raise 'EmptyListFuncIterator.element()'
  def moveToNext (self): 
    raise 'EmptyListFuncIterator.moveToNext()'

class ConsListFuncIterator ():
  def __init__ (self,f,r):
    self.fst = f
    self.rst = r
  def hasElement (self): 
    return True
  def element (self): 
    return self.fst
  def moveToNext (self): 
    return self.rst.funcIterator()


# This is the implementation of the python iterator for List
class ListIterator:
  def __init__ (self,l):
    self.list = l
  def next (self):
    if (self.list.isEmpty()):
      raise StopIteration
    else:
      value = self.list.first()
      self.list = self.list.rest()
      return value

# Our creators -- living outside the class because we don't have statics
def cons (f,r):
  return ConsList(f,r)

def empty ():
  return EmptyList()


# Your standard length function
def length (L):
  if L.isEmpty():
    return 0
  else:
    return 1 + length(L.rest())

# A function to create a list of values (here, the fibonacci sequence)
def fib (n):
  def fib_aux (n1,n2):
    if (n1<n):
      return cons(n1,fib_aux(n2,n1+n2))
    else:
      return empty()
  return fib_aux(0,1)

# A function to print all the elements from a functional iterator
def printAll (fit):
  temp = fit
  while (temp.hasElement()):
    print("element = " + str(temp.element()))
    temp=temp.moveToNext()

# Convert a functional iterator into a python iterable for use in for-loops
# This is a form of adapter
def fIter (fit):
  temp=fit
  while (temp.hasElement()):
    yield temp.element()
    temp=temp.moveToNext()

# Convert an iterable into one where we apply function f to every element
# produced by the iterable's iterator
def mapIter(f,itbl):
  for x in itbl:
    yield f(x)

# Create an iterable whose iterator provides the elements of two
# iterables' iterators in sequence
def seqIter (itbl1,itbl2):
  for x in itbl1:
    yield x
  for x in itbl2:
    yield x

# Create an iterable whose iterator provides the elements of two
# iterables' iterators paired up pointwise
def zipIter (itbl1,itbl2):
  it1=iter(itbl1)
  for x in itbl2:
    yield (it1.next(),x)

# A bit of a hack: transform an iterator IT into an iterable whose 
# iterator is IT
def iterable (it):
  while True:
    x=it.next()
    yield x

# Create an iterable whose iterator provides the elements of an
# iterable's iterator in reverse order
def revIter (itbl):
  it=iter(itbl)
  temp=it.next()
  for x in revIter(iterable(it)):
    yield x
  yield temp

# Create an iterable whose iterator provides the elements of an
# iterable's iterator, repeating the last element ad infinitum
# (An initial value is provided in case the initial iterable's
# iterator is empty.)
def repeatLast (v,itbl):
  last=v
  for x in itbl:
    yield x
    last=x
  while (True):
    yield last