# Emulation of Java style streams in Python,

class Stream:
    def __init__(self,generator):
        self.generator = generator
        self.counter = 0
    # constructor    

    def stream_next(self):
        next = self.generator()
        if next != None:
            self.counter += 1
        return next
    #next

    ### stream qualification functions
    def limit(self,n):  # sets a finite limit to generated items
        gen = self.generator
        def limited():
          if self.counter >= n: return None
          else: return gen()
        #
        self.generator = limited
        return self

    # this would not be type-safe in a better language
    def map(self, mapfun):
        #newseeds = [mapfun(x) for x in self.seeds]
        gen = self.generator
        def mapped():
            next = gen()
            if next == None: return None
            else: return mapfun(next)
        #
        self.generator = mapped
        return self

    # concat a (finite) stream and another stream
    def concat(self, other_stream):
        gen = self.generator()
        def merged():
            next = self.stream_next()
            if next == None: return other_stream.stream_next()
            else: return next
        self.generator = merged
        return self

    def flatten(self): # this assumes self is a stream of streams
        gen = self.generator
        current_stream = gen()
        def flattened():
            nonlocal current_stream
            next = current_stream.stream_next()
            while next==None:
                current_stream = gen()
                if current_stream == None: return None
                next = current_stream.stream_next()
            return next
        self.generator = flattened
        return self  # .map(..).flatten() is equivalent to "bind"

    def filter(self, predicate): # take only items satisfying predicate
        gen = self.generator
        def filtered():
            next = gen()
            while next!=None and not(predicate(next)):
                next = gen()
            return next
        self.generator = filtered
        return self

    def until(self, predicate): # stop streaming when predicate satisfied
        gen = self.generator
        def limited():
            next = gen()
            if next==None or predicate(next): return None
            else: return next
        self.generator = limited
        return self


    #### methods for running the stream
    def foreach(self, action):
        next = self.stream_next()
        while next!=None:
            action(next)
            next = self.stream_next()
    #foreach

    def for_all(self, predicate):
        next = self.stream_next()
        while next!=None:
            if not(predicate(next)): return False
            next = self.stream_next()
        return True
	
    def there_exists(self, predicate):
        return not(self.for_all(lambda x:not(predicate(x))))

    def nth(self, n):
        while n+1 > 0:   # first is 0th
            next = self.stream_next()
            if next==None: return None
            n -= 1
        return next
    
    def find_first(self, predicate):
        next = self.stream_next()
        while next!=None:
            if predicate(next): return next
            next = self.stream_next()
        return None

    # apply left-associative operator to stream with left-identity id
    def reduce(self, id, operator):
        next = self.stream_next()
        while next!=None:
            id = operator(id,next)
            next = self.stream_next()
        return id

    def fold(self, operator):     # uses first in stream as accumulator
        ax = self.stream_next()
        if ax==None: return None
        else: return self.reduce(ax,operator)
#Stream

# global functions:

def finite_stream(seeds):
    index = 0
    def generator():
        nonlocal index
        if index < len(seeds):
            index += 1
            return seeds[index-1]
        else: return None
    return Stream(generator)

def induction(base, inducer):
    first = True
    def generator():
        nonlocal base, first
        if first: first = False
        else: base = inducer(base)
        return base
    return Stream(generator)

def strong_induction(seeds,inducer):
    index = 0
    def generator():
        nonlocal index
        if index<len(seeds):
            index += 1
            return seeds[index-1]
        else:
            next = inducer(seeds)
            if next!=None:
              seeds.append(next)
              index += 1
            return next
    return Stream(generator)
        

######################## testing

# the stream should be re-defined before each use:

def odds(): return induction(1, lambda x:x+2)

odds().limit(10).foreach(lambda x:print(x,end=" "))
print()

largest = finite_stream([5,8,2,1,9,4,3]).fold(max)
product = finite_stream([5,8,2,1,9,4,3]).reduce(1,lambda a,b:a*b)

print("largest:", largest)  # prints 9
print("product:", product)   
    
def Fibonacci():
    def next_two(last2):
       (fib_1, fib_2) = last2
       return (fib_2, fib_1 + fib_2)  # better syntax for pairs
    return induction( (0,1), next_two ).map(lambda p:p[1])

Fibonacci().until(lambda n:n>100).foreach(print)

# n! is surprisingly revealing: must inductively define pair (n, n!)
def factorial(n):
    def next_pair(pair):
        (n, factn) = pair  
        return (n+1, (n+1)*factn)  # if factn is n! then (n+1)*factn is (n+1)!
    return induction((0,1),next_pair).map(lambda pair:pair[1]).nth(n)

print("6! is ", factorial(6))


# Primes

def nextprime(knownprimes):
    if len(knownprimes)==0: return 2
    lastprime = knownprimes[len(knownprimes)-1]
    if lastprime==2: return 3
    candidates = induction(lastprime+2, lambda n:n+2)
    return candidates\
           .find_first(lambda c:\
                       finite_stream(knownprimes)\
                       .until(lambda p: p > 1.0 + c**0.5)\
                       .for_all(lambda p: c%p != 0))

## need the \ to write expression on different lines

Primes = lambda known_primes: strong_induction(known_primes, nextprime)

print("first 100 primes:")
primes100 = []
Primes([]).limit(100)\
          .foreach(primes100.append)
print(primes100)

def prime_factors(n):
    factors = []                 
    Primes(primes100).until(lambda p:p>n)\
                     .filter(lambda p: n%p==0)\
                     .foreach(factors.append)
    return factors

print("\nprime factors of 3000:", prime_factors(3000))


def binary_factors(n):
    factors = []                     
    def next(pair):
        (factor, m) = pair
        return (factor*2, m//2)
    induction((1,n), next)\
        .until(lambda pair:pair[1] < 1)\
        .filter(lambda pair:pair[1] % 2 == 1)\
        .map(lambda pair:pair[0])\
        .foreach(factors.append)
    return factors
        
print("\nbinary factors of 1000:", binary_factors(1000))