// Copyright  2008 Giovani P. Deretta. Use, modification and distribution is
// subject to the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)


#include <boost/iterator/transform_iterator.hpp>
#include <boost/iterator/filter_iterator.hpp>
#include <boost/iterator/filter_iterator.hpp>
#include <boost/utility/result_of.hpp>
#include <boost/type_traits.hpp>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <boost/range/sub_range.hpp>

/* Using deforestation rules in an attempt to reduce abstraction
   overhead of boost iterator adapters.

   Without any defines, sequences of map and filter won't be
   reduced. It is left to the compiler to optimize the code and reduce
   abstraction overhead.
   
   -  Define PLAIN_FOR to test baseline explicit for based loop. This is
   the theoretical best code attainable.

   - Define DO_REWRITE to enable rewrite rules to simplify sequences of filter/map.
   See below for exact rewrite rules.

   - Define DO_TRAVERSAL to also enable optimized fold/for_each.

   Results: surprisingly, with gcc-4.x I cannot measure any
   significant abstraction penalities by using even long chains of
   {transform,filter}_iterators in integer based
   computations. Enabling rewrite rules or traversal doesn't change
   anything.

   Gcc-3.3, OTOH, has a larger abstraction overhead and the benefit of
   both rewrite and traversal is around 20% (~10% each).

   Note: the test code uses typeof for simplicity. It should be easy
   to remove it to test on compilers which do not have this
   functionality.

   TODO: test abstraction penality on more complex code (not just integers), or with more complex
   mappers and filters.

   TODO: add more iterators (unfold, zip, take) and more rewrite rules.

   
*/

   

namespace mpl =boost::mpl;
namespace xrange {
 
    namespace detail {

        // Why not use boost::range?  We need metafunctions that
        // return const_iterators and iterators according to the
        // {lvalue/const lvalue/rvalue}ness of their parameters. We
        // might as well put everithing we need here.
        template<typename Range>
        struct range_iterator {
            typedef typename Range::const_iterator type;
        };

        template<typename Range>
        struct range_iterator<Range&> {
            typedef typename Range::iterator type;        
        };

        template<typename R>
        typename range_iterator<R>::type
        begin(R const&r) {
            return r.begin();
        }

        template<typename R>
        typename range_iterator<R&>::type
        begin(R&r) {
            return r.begin();
        }

        template<typename R>
        typename range_iterator<R>::type
        end(const R&r) {
            return r.end();
        }

        template<typename R>
        typename range_iterator<R&>::type
        end(R&r) {
            return r.end();
        }
    
        template<typename Range>
        struct range_iterator<const Range&> : range_iterator<Range> {};
    
        template<typename Range>
        struct range_value :
            boost::iterator_value<typename range_iterator<Range>::type> {};
    
        template<typename Range>
        struct range_reference :
            boost::iterator_reference<typename range_iterator<Range>::type> {};    
    
        template<class F, class T>
        struct result_of : boost::result_of<F(T)> {};
    
        template<class T>
        struct remove_rcv
            : boost::mpl::apply<
                  boost::remove_cv<boost::remove_reference<boost::mpl::_> >
                , T
              > {};

        template<typename R, typename M>
        struct make_transform_iterator
            : mpl::apply<
                  boost::transform_iterator<
                      remove_rcv<mpl::_2>,
                      range_iterator<mpl::_1>,
                      result_of<
                          remove_rcv<mpl::_2>,
                          boost::iterator_reference<
                              range_iterator<mpl::_1>
                          >
                          >
                      >
                , R, M
              >{};

        template<typename R, typename F>
        struct make_filter_iterator
            : mpl::apply<boost::filter_iterator<remove_rcv<mpl::_2>, range_iterator<mpl::_1> >, R, F> {};

        // compose(A, B)(x) -> A(B(x))
        template<class F1, class F2>
        struct compose {
            compose(F1 f1_, F2 f2_) : f1(f1_), f2(f2_) {}
            
            template<class> struct result;
            template<class F, class P> struct result<F(P)>
            :  mpl::apply<
                   detail::result_of<
                       F1,
                       detail::result_of<
                           F1,
                           mpl::_1
                       >
                   >, P> {};
    
            template<class P>
            typename result<compose(P const&)>::type
            operator()(P const& p) const {
                return f1(f2(p));
            }
            template<class P>
            typename result<compose(P&)>::type
            operator()(P& p) const {
                return f1(f2(p));
            }
            
            F1 f1; F2 f2;
        };

        template<class A, class B>
        struct and_ {
            and_(A a_, B b_): a(a_), b(b_) {}
            typedef bool result_type;
            template<class X>
            bool operator()(X const& x) const {
                return a(x) && b(x);
            }
            A a; B b;
        };

    }

    template<class R, class M>
    struct map_range {
        map_range(R const&r_, M m_) : r(r_), m(m_) {}
        
        typedef typename detail::make_transform_iterator<R, M>::type iterator;
        typedef iterator const_iterator;

        iterator begin() const {
            return iterator(detail::begin(r), m);
        }

        iterator end() const {
            return iterator(detail::end(r), m);
        }

        R r;
        M m;           
    };

    template<class R, class P>
    struct filter_range {
        filter_range(R const&r_, P p_) : r(r_), p(p_) {}
        
        typedef typename detail::make_filter_iterator<R, P>::type iterator;
        typedef iterator const_iterator;

        iterator begin() const {
            return iterator(p, detail::begin(r), detail::end(r));
        }

        iterator end() const {
            return iterator(p, detail::end(r), detail::end(r));
        }

        R r;
        P p;           
    };

    ///// Rewrite rules:

    // base cases: identity
    
    template<class R, class M>
    struct map_range_r {
        typedef map_range<R, M> type;
        type operator()(R const& r, M m) { return type(r, m); }
    };

    template<class R, class P>
    struct filter_range_r {
        typedef filter_range<R, P> type;
        type operator()(R const& r, P f) { return type(r, f); };
    };

#if defined(DO_REWRITE) 
    
    // map(map(r, a), b) -> map(r, \x->a(b(x)))
    template<class R, class M1, class M2>
    struct map_range_r<map_range<R, M1>, M2> {
        typedef map_range_r<R, detail::compose<M2, M1> > super;
        typedef typename super::type type;
        
        type operator()(map_range<R, M1> r, M2 m) {
            return super()(r.r, detail::compose<M2, M1>(m, r.m));
        }
    };

    // filter(filter(r, a), b) -> filter(r, \x->a(x) && b(x))
    template<class R, class P1, class P2>
    struct filter_range_r<filter_range<R, P1>, P2> {
        typedef filter_range_r<R, detail::and_<P1, P2> > super;
        typedef typename super::type type;
        
        type operator()(filter_range<R, P1> r, P2 p) {
            return super()(r.r, detail::and_<P1, P2>(r.p, p));
        }
    };

    // filter(map(r, a), b) -> map(filter(r, b), \x->a(b(x)))
    template<class R, class M, class P>
    struct filter_range_r<map_range<R, M>, P> {
        typedef filter_range_r<R, detail::compose<P, M> > filter;
        typedef map_range<typename filter::type, M> type;
        type operator()(map_range<R, M> r, P p) {
            return type(filter()(r.r, detail::compose<P, M>(p, r.m)), r.m);
        }
    };
#endif
    /// note: filter and map by default return a lazy range that closes around its arguments by value.
    /// use boost::sub_range to prevent this.
    /// todo: map and filter should close by reference by default except for lightweight ranges.

    
    // workaround: using map_ to prevent adl collision with std::map
    template<class R, class M>
    typename map_range_r<R, M>::type map_(R const& r, M m) {
        return map_range_r<R, M>()(r, m);
    }

    template<class R, class M>
    typename map_range_r<R, M>::type map(R const& r, M m) {
        return map_(r, m);
    }

    
    template<class R, class F>
    typename filter_range_r<R, F>::type filter(R const& r, F m) {
        return filter_range_r<R, F>()(r, m);
    }

    template<class R, class T, class F>
    T accumulate(R const r, T x, F f) {
        return std::accumulate(detail::begin(r), detail::end(r), x, f);
    }

#ifdef DO_TRAVERSAL


    // Generic traversal:
    // for every i in [begin, end), such as p(i) is true, call
    // f(m(i)). Early exit if c(i) is false.
    // todo: add support for Take and zip.
    template<class I, class F, class P, class M, class C>
    void traversal(I begin, I end, F& f, P& p, M& m, C& c) {
        for(; (begin != end) /*&& c(*begin)*/; ++begin) {
            if(p(*begin)) f(m(*begin));
        }
    }

    struct true_ {
        template<class T>
        bool operator()(T const&) {
            return true;
        }
    };
    
    template<class R, class F, class P, class M>
    F for_each(map_range<filter_range<R, P>, M> r, F f) {
        true_ t;
        //typedef typeof(r.r) r_t;
        traversal(detail::begin(r.r.r), detail::end(r.r.r), f, r.r.p, r.m, t);
        return f;
    }

    template<class Z, class F>
    struct accumulator {
        template<typename T>
        void operator()(T const& x) {
            z = f(z, x);
        }
        Z z;
        F f;
    };
    
    template<class R, class T, class F, class P, class M>
    T accumulate(map_range<filter_range<R, P>, M> r, T x, F f) {
        accumulator<T, F> acc = { x, f };
        return for_each(r, acc).z;
    }

#endif 

    
    template<class R, class F>
    F for_each(R const r, F f) {
        return std::for_each(detail::begin(r), detail::end(r), f);
    }

}

// A bounch of mappers and filters for testing.
// todo: test more complex mappers and filters

struct square { typedef unsigned long result_type; unsigned long operator()(unsigned long x) const { return x*x; } };

template<unsigned long I>
struct times{ typedef unsigned long result_type; unsigned long operator()(unsigned long x) const { return x*I; } };

template<unsigned long I>
struct mod{ typedef bool result_type; bool operator()(unsigned long x) const { return x % I == 0; } };

template<unsigned long I>
struct not_mod{ typedef bool result_type; bool operator()(unsigned long x) const { return x % I != 0; } };

template<unsigned long I>
struct plus { typedef unsigned long result_type; unsigned long operator()(unsigned long x) const { return x + I; } };

template<unsigned long I>
struct less { typedef bool result_type; bool operator()(unsigned long x) const { return x < I; } };

template<unsigned long I>
struct more { typedef bool result_type; bool operator()(unsigned long x) const { return x > I; } };

template<unsigned long I, unsigned long J>
struct between { typedef bool result_type; bool operator()(unsigned long x) const { return x > I && x < J; } };


template<typename T>
struct sum {
    typedef T result_type;
    template<class T2>
    T operator()(T a, T2 b) const {
        return a + b;
    }
};

#define auto(a, b) typeof(b) a = b

template<typename T>
void fail() { T::FAIL(); }

void test1() {
    using namespace xrange;

    std::vector<unsigned long> r ;
    for (int i=0; i < 1024*1024; ++i)
        r.push_back(i);

    auto (sr, boost::sub_range<std::vector<unsigned long> >(r));
    
    auto(r2,
         filter
         (  map_
            (  filter
               ( 
                   map_
                   (  map_
                      (  filter
                         (  map_(sr, times<8>()),
                            less<10000>()
                         )
                         , times<8>()
                      ),
                      times<8>()
                   )
                  ,
                   mod<2>()
               ),
               plus<10>()
            ),
            mod<5>()
         )
    );

    typedef typeof(r2) r2_t;

    // uncomment the following line to have the compiler print the type of r2
    //fail<typeof(r2)>();
    
    struct each { static void _(int i) { std::cout << i <<':'; }};
    //for_each(r2, &each::_);
    //std::cout <<std::endl;

#ifndef PLAIN_FOR
    unsigned long x = 0;
    for(int i = 0; i < 1000; ++i)
        x = accumulate(r2, x, sum<unsigned long>());
#else
    // base line for based code for timing comparisons.
    // the compiler should be able to do a good job with this.
    unsigned long x = 0;
    for (size_t j = 0; j < 1000; ++j) {
        for(size_t i = 0; i != r.size(); ++i) {
            unsigned long k = r[i] * 8;
            if( k % 2 ) {
                unsigned long k1 = k*8;
                unsigned long k2 = k1*8;
                if(k2 % 5 && (k2 + 10) < 100000)
                    x += k2 + 10;
            }
        }
    }
#endif 
    
    std::cout << x <<std::endl;
}



int main() {
    test1();
}