#include<iostream>
#include<functional>
#include<optional>
#include<vector>
#include<cmath>
using namespace std;

#define LAMBDA(x,exp) ([](auto& x){return exp;})
#define LAMVAL(x,exp) ([=](auto& x){return exp;})
#define LAMREF(x,exp) ([&](auto& x){return exp;})

template<typename T>
struct stream {
  function<optional<T>()> generate;

  static stream<T> empty_stream() {
    stream<T> s;
    s.generate = [](){return nullopt;};
    return s;
  }

  // casting needed otherwise
  static optional<T> None() { return (optional<T>)nullopt; }
  static optional<T> Some(T x) { return (optional<T>)x; }
  
  stream<T>& limit(unsigned int n) {
    auto gen = generate;
    generate = [=]() mutable {
      if (n--<1) return None(); 
      else return gen();
    };
    return *this;
  }

  template<typename U>
  stream<U> map(function<U(T&)> mapfun) {
    stream<U> su;
    su.generate = [this,mapfun](){
      auto next = generate();
      if (!next.has_value()) return (optional<U>)nullopt;
      else {
        optional<U> nextu = mapfun(next.value());
        return nextu;
      }
    };
    return su;
  }//map

  template<typename U>
  stream<U> bind(function<stream<U>(T&)> binder) {
    stream<U> su;
    auto nextt = generate();
    if (!nextt.has_value()) {
      su.generate = [](){ return None(); };
      return su;
    }
    auto currentu = binder(nextt.value());
    su.generate = [=]() mutable {
      optional<U> next;
      while (1) {
        next = currentu.generate();
        if (next.has_value()) break;
        nextt = generate();
        if (!nextt.has_value()) break;
        currentu = binder(nextt.value());
      }//while
      return next;
    };
    return su;
  }//bind

  stream<T>& filter(function<bool(T&)> predicate) {
    auto gen = generate;
    generate = [=](){
      auto next = gen();
      while (next.has_value() && !predicate(next.value())) next = gen();
      return next;
    };
    return *this;
  }

  stream<T>& take_while(function<bool(T&)> predicate) {
    auto gen = generate;
    generate = [=](){
      auto next = gen();
      if (next.has_value() && predicate(next.value())) return next;
      else return None();
    };
    return *this;    
  }

  stream<T>& until(function<bool(T&)> predicate) {
    auto gen = generate;
    bool islast = true; // this is read-only
    generate = [=]() mutable {
      auto next = gen();
      if (!next.has_value() || !predicate(next.value())) return next;
      if (islast) {
        islast = false;
        return next;
      }
      else return None();
    };
    return *this;    
  }  

  stream<T>& append(stream<T>& other) {
    auto gen = generate;
    generate = [=]{
      optional<T> next = gen();
      if (next.has_value()) return next;
      else return other.generate();
    };
    return *this;
  }

  static stream<T> coinduction(T seed, function<T(T&)> induct) {
    stream<T> s;
    s.generate = [=]() mutable {
      auto tmp = move(seed);
      seed = induct(tmp);
      return tmp;
    };
    return s;
  }

  // this only works if T can be copied.
  static stream<T> seeded_induction(vector<T>& seeds, function<T(vector<T>&)> gen_next) {
    stream<T> s;
    size_t index = 0;
    s.generate = [&seeds,gen_next,index]() mutable {
      if (index<seeds.size()) return Some(seeds[index++]);
      index++;
      T next = gen_next(seeds);
      seeds.push_back(next);
      return Some(next);
    };
    return s;
  }

  // array is externally allocated
  static stream<T> array_stream(T seeds[], const size_t size) {
    stream<T> s;
    size_t index = 0;
    // seeds cannot be captured by value - will deep copy.
    s.generate = [=]() mutable {
      if (index<size) return Some(seeds[index++]);
      else return None();
    };
    return s;
  }

  // vector exists externally
  static stream<T> vector_stream(vector<T>& seeds) {
    stream<T> s;
    size_t index = 0;
    s.generate = [index,&seeds]() mutable {
      if (index<seeds.size()) return Some(seeds[index++]);
      else return None();
    };
    return s;
  }
  

  // vector should be moved when function is called.
  static stream<T> finite_stream(vector<T> seeds) {
    stream<T> s;
    size_t index = 0;
    s.generate = [index,seeds=move(seeds)]() mutable {
      if (index<seeds.size()) return Some(seeds[index++]);
      else return None();
    };
    return s;
  }
  
  void foreach(function<void(T&)> action) {
    while(1) {
      auto next = generate();
      if (!next.has_value()) break;
      action(next.value());
    }//while
  }//foreach

  bool forall(function<bool(T&)> predicate) {
    while (1) {
      auto next = generate();
      if (!next.has_value()) return true;
      else if (!predicate(next.value())) return false;
    }
  }
  bool exists(function<bool(T&)> predicate) {
    return !forall([=](T& x){ return !predicate(x); });
  }

  optional<T> find_first(function<bool(T&)> predicate) {
    while (1) {
      auto next = generate();
      if (!next.has_value()) return None();
      else if (predicate(next.value())) return next;
    }
  }

  optional<T> get_last(function<bool(T&)> predicate) {
    auto last = generate();
    if (!last.has_value()) return last;
    while (1) {
      auto next = generate();
      if (!next.has_value()) return last;
      else last = move(next);
    }
  }
  
}; // struct stream


uint64_t next_prime(vector<uint64_t>& known_primes) {
  if (known_primes.size()==0) return 2;
  auto last_prime = known_primes[known_primes.size()-1];
  if (last_prime==2) return 3;
  auto candidates =
    stream<uint64_t>::coinduction(last_prime+2,
                                  [](auto x){return x+2;});
  return candidates
    .find_first([&](auto& c){
      return
        stream<uint64_t>::vector_stream(known_primes)
        .take_while([&c](auto& p) {return p <= sqrt(c)+1;})
        .forall([&c](auto& p) { return c % p != 0; });
    })
    .value();
}//next_prime

int main() {
  stream<int> odds = stream<int>::coinduction(1, [](int x) {return x+2;});
  odds
    .limit(50)
    .filter(LAMBDA(x,x%5==0))
    .map<double>(LAMBDA(x,sqrt(x)))
    .foreach([](auto& x){cout << x << endl;});

  vector<int> v{2,4,6,8,10};
  //stream<int> s2 = stream<int>::finite_stream(move(v));
  stream<int> s2 = stream<int>::finite_stream({1,3,5,7,9});  
  s2.foreach([](auto& x){cout << x << " ";});  cout << endl;
  cout << v.size() << endl;

  int blah[] = {10,20,30};
  auto s3 = stream<int>::array_stream(blah,3);
  s3.foreach([](auto& x){cout << x << " ";});  cout << endl;


  vector<uint64_t> primes{2,3,5,7,11};
  auto all_primes =
    stream<uint64_t>::seeded_induction(primes,
                                       LAMBDA(kp,next_prime(kp)));
  //                                       [](auto& kp){return next_prime(kp);});
  all_primes
    //.until([](auto& p){return p>1000;})
    .until(LAMBDA(p,p>1000))
    .foreach([](auto& x){cout << x << " ";});  cout << endl;

  cout << "known primes: " << primes.size() << endl;
}//main