//  A possible implementation of lazy streams in C++
//
//  This code is pretty much self-explanatory. If you've ever seen a similar
//  thing implemented in Scheme, that is.
//
//  Mauro Persano - m at fzort dot org
//
//  GPL v2

//  Revision history:
//
//  2006-03-07 19:23  Unleashed unto an unsuspecting world.
//  2006-03-08 08:12  Minor clean-up.
//  2006-03-10 12:22  Eliminated some useless heap-allocation
//                    (thanks bicoherent).

//---------------------------------------------------------------------------
//
//	s t r e a m
//

struct stream;

struct abstract_stream {
	virtual ~abstract_stream() { }
	stream *nth(int n);
	virtual stream *force() = 0;
};

struct stream : abstract_stream {
	int car;
	abstract_stream *cdr;

  	stream(int car_ = 0, abstract_stream *cdr_ = 0)
	  : car(car_), cdr(cdr_) { }
	virtual ~stream() { if (cdr) delete cdr; }
	virtual stream *force() { return this; }
};

stream *
abstract_stream::nth(int n)
{
	stream *l = force();
	return n == 0 ? l : l->cdr->nth(n - 1);
}

//---------------------------------------------------------------------------
//
//	p r o m i s e
//

struct promise : abstract_stream {
	bool evaled;
	stream *value;

	promise() : evaled(false), value(0) { }
	virtual ~promise() { if (value) delete value; }
	virtual stream *force();
	virtual stream *eval() = 0;
};

stream *
promise::force()
{
	if (!evaled)
		value = eval(), evaled = true;
	return value;
}

template <class T>
struct promise0 : promise
{
	virtual stream *eval() { return new T; }
};

template <class T, typename Ta>
struct promise1 : promise
{
	promise1(const Ta& a_) : a(a_) { }
	virtual stream *eval() { return new T(a); }
	Ta a;
};

template <class T, typename Ta, typename Tb>
struct promise2 : promise
{
	promise2(const Ta& a_, const Tb& b_) : a(a_), b(b_) { }
	virtual stream *eval() { return new T(a, b); }
	Ta a;
	Tb b;
};

template <class T, typename Ta, typename Tb, typename Tc>
struct promise3 : promise
{
	promise3(const Ta& a_, const Tb& b_, const Tc& c_)
	  : a(a_), b(b_), c(c_) { }
	virtual stream *eval() { return new T(a, b, c); }
	Ta a;
	Tb b;
	Tc c;
};

template <class T, typename Ta, typename Tb, typename Tc>
promise3<T, Ta, Tb, Tc> *
delay(const Ta& a_, const Tb& b_, const Tc& c_)
{
	return new promise3<T, Ta, Tb, Tc>(a_, b_, c_);
}

template <class T, typename Ta, typename Tb>
promise2<T, Ta, Tb> *
delay(const Ta& a_, const Tb& b_)
{
	return new promise2<T, Ta, Tb>(a_, b_);
}

template <class T, typename Ta>
promise1<T, Ta> *
delay(const Ta& a_)
{
	return new promise1<T, Ta>(a_);
}

template <class T>
promise0<T> *
delay()
{
	return new promise0<T>;
}


//---------------------------------------------------------------------------
//
//	f i l t e r
//

template <class C>
struct predicate {
	virtual ~predicate() { }
	bool operator()(int a) const
	{ return dynamic_cast<const C&>(*this)(a); }
};

template <class P>
struct filter : stream {
	filter(const P& p_, abstract_stream *l_);
	const P& p;
};

template <class P>
filter<P>::filter(const P& p_, abstract_stream *l_)
  : p(p_)
{
	stream *l;

	while (l = l_->force(), !p_(l->car))
		l_ = l->cdr;

	car = l->car;
	cdr = delay<filter>(p_, l->cdr);
}


//---------------------------------------------------------------------------
//
//	s i e v e
//

struct not_divisible_by : predicate<not_divisible_by> {
	int x;
	not_divisible_by(int x_) : x(x_) { }
	bool operator()(int a) const { return a%x != 0; }
};

struct sieve : stream {
	sieve(abstract_stream *s_);

	const not_divisible_by p;
	filter<not_divisible_by> f;
};

sieve::sieve(abstract_stream *s_)
  : stream(s_->force()->car)
  , p(not_divisible_by(car))
  , f(filter<not_divisible_by>(p, s_->force()->cdr))
{
	cdr = delay<sieve>(&f);
}

struct add : stream {
	add(abstract_stream *s1_, abstract_stream *s2_);
};

add::add(abstract_stream *s1_, abstract_stream *s2_)
{
	stream *s1 = s1_->force();
	stream *s2 = s2_->force();

	car = s1->car + s2->car;
	cdr = delay<add>(s1->cdr, s2->cdr);
}

struct ones : stream {
	ones() : stream(1, delay<ones>()) { }
};

#include <iostream>

int
main(int argc, char *argv[])
{
#if 0
	// the infinite stream of fibonacci numbers
	stream fibs(1, new stream(1));
	fibs.cdr->force()->cdr = delay<add>(&fibs, fibs.cdr);

	// this would have looked much nicer:
	//
	//   fibs = new stream(1, new stream(1, delay<add>(fibs, fibs->cdr)))
	// 
	// alas, not possible.

	for (int i = 0; i < 20; i++)
		std::cout << fibs.nth(i)->car << "\n";
#else
	// an infinite stream of ones
	ones onez;

	// the infinite stream of positive integers
	stream ints(1);
	ints.cdr = delay<add>(&onez, &ints);

	// the infinite stream of prime numbers
	sieve primes(ints.cdr);
	
	for (int i = 0; i < 100; i++)
		std::cout << primes.nth(i)->car << "\n";
#endif

	return 0;
}