#include <iostream>

template <typename T>
class IStream
{
    public:
        T head()
        { 
            if (_empty) throw "Stream is empty!";
            return _head();
        }
        IStream<T>* tail()
        {
            return _tail();
        }
        bool IsEmpty()
        {
            return _empty;
        }

    protected:
        IStream (bool empty = true)
            : _empty(empty)
        {}
        ~IStream(){}
        virtual const T _head() = 0;
        virtual IStream<T>* _tail() = 0;

        bool _empty;
    public:
        void out(std::ostream& os);
        IStream<T>* map(T (*func)(T, T), IStream<T>*);
        IStream<T>* add(IStream<T>*);
        IStream<T>* filter(bool (*filter)(T));
        IStream<T>* take(int n);
};

template <typename T>
class make_stream : public IStream<T>
{
    public:
        make_stream(T head, IStream<T>* tail)
            : IStream<T>(false), _value(head), _stream(tail)
        {}
        make_stream(T head, T tail)
            : IStream<T>(false), _value(head)
        {
            _stream = new make_stream<T>(tail, static_cast<IStream<T>*>(NULL));
        }

        virtual const T _head() { return _value; }
        virtual IStream<T>* _tail() { return _stream; }
    private:
        T _value;
        IStream<T>* _stream;
};

template <typename T>
class stream_operation : public IStream<T>
{
    protected:
        stream_operation(IStream<T>* s)
            : IStream<T>(s->IsEmpty()), original_stream(s)
        {}
        virtual const T _head() { return original_stream->head(); }
        virtual IStream<T>* _tail() { return original_stream->tail(); }
        IStream<T>* original_stream; 
};

template <typename T>
class stream_filter : public stream_operation<T>
{
    public:
        virtual IStream<T>* _tail()
        {
            IStream<T>* next = stream_operation<T>::_tail();
            while(next != NULL)
            {
                if (_cond(next->head())) 
                    return new stream_filter<T>(next, _cond);
                next = next->tail();
            }
            return NULL;
        }
    protected:
        stream_filter(IStream<T>* s, bool (*cond)(T))
            : stream_operation<T>(s), _cond(cond)
        {
            if (!_cond(this->head()))
                stream_operation<T>::original_stream = _tail(); 
        }
    private:
        bool (*_cond)(T);
        friend IStream<T>* IStream<T>::filter(bool (*cond)(T));
};

template <typename T>
class stream_take : public stream_operation<T>
{
    public:
        virtual IStream<T>* _tail()
        {
            return (_remain <= 1) ? NULL : new stream_take(stream_operation<T>::_tail(), _remain-1);
        }
    protected:
        stream_take(IStream<T>* s, int n) 
            : stream_operation<T>(s), _remain(n)
        {}
    private:
        int _remain;
        friend IStream<T>* IStream<T>::take(int);
};

template <typename T>
class stream_map : public IStream<T>
{
    public:
        stream_map(T (*func)(T, T), IStream<T>* s1, IStream<T>* s2)
            : IStream<T>(s1->IsEmpty() || s2->IsEmpty()), _func(func), _s1(s1), _s2(s2)
        {};

        virtual const T _head() { return _func(_s1->head(), _s2->head()); }
        virtual IStream<T>* _tail()
        {
            return new stream_map(_func, _s1->tail(), _s2->tail());
        }
    private:
        T (*_func)(T, T);
        IStream<T>* _s1;
        IStream<T>* _s2;
        friend IStream<T>* IStream<T>::add(IStream<T>*);
};

class fibo_stream : public make_stream<int>
{
    public:
        fibo_stream()
            : make_stream<int>(1, 1)
        {}
        virtual IStream<int>* _tail()
        {
            IStream<int>* super_tail = make_stream<int>::_tail();
            return new fibo_stream(super_tail->head(), head()+super_tail->head());
        }
    protected:
        fibo_stream(int head, int tail)
            : make_stream<int>(head, tail)
        {}
};

class inc_stream : public make_stream<int>
{
    public:
        inc_stream(int i)
            : make_stream<int>(i, static_cast<IStream<int>*>(NULL))
        {}
        virtual IStream<int>* _tail()
        {
            return new inc_stream(head() + 1);
        }
};

IStream<int>* number() { return new inc_stream(1); }
IStream<int>* fibs() { return new fibo_stream(); }

bool isEven(int i) { return (i%2 == 0); }

int main(int argc, char* argv[])
{
    fibs()->filter(isEven)->take(10)->out(std::cout);

    std::cout << "-----------------" << std::endl;
    int a=1, b=1, index=0;
    while(index < 10)
    {
        int c = a+b;
        if (c%2 == 0) 
        {
            std::cout << c << std::endl;

            index++;
        }
        a = b; b = c;
    }

    return 0;
}

template<typename T>
IStream<T>* IStream<T>::filter(bool (*cond)(T))
{
    return new stream_filter<T>(this, cond);
}

template<typename T>
IStream<T>* IStream<T>::take(int n)
{
    return new stream_take<T>(this, n);
}

template<typename T>
IStream<T>* IStream<T>::map(T (*func)(T, T), IStream<T>* s)
{
    return new stream_map<T>(func, this, s);
}

template<typename T>
T func_add(T a, T b) { return a+b; }

template<typename T>
IStream<T>* IStream<T>::add(IStream<T>* s)
{
    return map(func_add<T>, s);
}

template<typename T>
void IStream<T>::out(std::ostream& os)
{
    if (IsEmpty()) return;
    os << head() << std::endl;
    if (tail() != NULL)
        tail()->out(os);
}