#include <iterator>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <vector>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/next_prior.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/empty.hpp>
#include <boost/range/reference.hpp>
#include <boost/range/iterator.hpp>
#include <boost/fusion/include/fold.hpp>
#include <boost/fusion/include/make_vector.hpp>
#include <boost/spirit/home/phoenix/core.hpp>
#include <boost/spirit/home/phoenix/operator.hpp>
#include <boost/timer.hpp>

template<class T>
struct associated_range {
    typedef std::pair<T, T> type;
};

template<class T>
bool range_empty(const T& range) {
    return(boost::empty(range));
}

template<class T>
bool increment_range_begin_and_test(T& range) {
    range = T(boost::next(boost::begin(range)), boost::end(range));
    return(range_empty(range));
}

template<class T>
void increment_range_begin(T& range) {
    range = T(boost::next(boost::begin(range)), boost::end(range));
}

template<class T>
typename boost::range_reference<T>::type range_front(T& range) {
    return(*boost::begin(range));
}

template<class T>
bool range_begin_equal(const T& lhs, const T& rhs) {
    return(boost::begin(lhs) == boost::begin(rhs));
}

template<class R, class F>
class filter_range;

template<class Iter, class F>
struct filter_iterator :
    boost::iterator_facade<
        filter_iterator<Iter, F>,
        typename std::iterator_traits<Iter>::value_type,
        std::forward_iterator_tag,
        typename std::iterator_traits<Iter>::reference> {
    friend class boost::iterator_core_access;
    template<class R, class F>
    friend class filter_range;
    filter_iterator(Iter b, Iter e, F f ) :
        m_range(b,e), m_f(f) {}
private:
    void increment1() {
        while(!increment_range_begin_and_test(m_range) && !m_f(range_front(m_range))) {}
    }
    void increment2() {
        increment_range_begin(m_range);
        while(!range_empty(m_range) && !m_f(range_front(m_range))) {
            increment_range_begin(m_range);
        }
    }
    void increment() { increment2(); }

    reference dereference() const {
        return range_front(m_range);
    }

    bool equal(filter_iterator const& rhs) const {
        return range_begin_equal(m_range, rhs.m_range);
    }

    typename associated_range<Iter>::type m_range;
    F m_f; // use compressed pair here
};

template<class R, class F>
class filter_range {
public:
    typedef filter_iterator<typename boost::range_iterator<R>::type, F> iterator;
    typedef filter_iterator<typename boost::range_const_iterator<R>::type, F> const_iterator;
    filter_range(iterator b, iterator e)
        : m_range(boost::begin(b.m_range), boost::begin(e.m_range)),
          m_f(b.m_f) {}
    filter_range(typename boost::range_iterator<R>::type b, typename boost::range_iterator<R>::type e, F f)
        : m_range(b, e),
          m_f(f) {}
    filter_range(R r, F f)
        : m_range(r),
          m_f(f) {}

    iterator begin() {
        return iterator(boost::begin(m_range), boost::end(m_range), m_f);
    }
    iterator end() {
        return iterator(boost::end(m_range), boost::end(m_range), m_f);
    }


    const_iterator begin() const {
        return const_iterator(boost::begin(m_range), boost::end(m_range), m_f);
    }
    const_iterator end() const {
        return const_iterator(boost::end(m_range), boost::end(m_range), m_f);
    }

    friend __forceinline bool increment_range_begin_and_test(filter_range& range) {
        while(true) {
            if(increment_range_begin_and_test(range.m_range)) {
                return(true);
            } else if(range.m_f(range_front(range.m_range))) {
                return(false);
            }
        }
    }
    friend __forceinline void increment_range_begin(filter_range& range) {
        increment_range_begin(range.m_range);
        while(!range_empty(range) && !range.m_f(range_front(range.m_range))) {
            increment_range_begin(range.m_range);
        }
    }
    friend bool range_empty(const filter_range& range) {
        return(range_empty(range.m_range));
    }
    friend typename boost::range_reference<R>::type range_front(filter_range& range) {
        return(range_front(range.m_range));
    }
    friend typename boost::range_reference<const R>::type range_front(const filter_range& range) {
        return(range_front(range.m_range));
    }
    bool range_begin_equal(const filter_range& lhs, const filter_range& rhs) {
        return(range_begin_equal(lhs.m_range, rhs.m_range));
    }

private:
    R m_range;
    F m_f;  // use compressed pair
};

// specialization
template<class Iter, class F>
struct associated_range<filter_iterator<Iter, F> >  {
    typedef filter_range<typename associated_range<Iter>::type, F> type;
};

template<int N>
struct is_not_divisible_by {
    bool operator()(int n) {
        return(n % N != 0);
    }
};

struct make_filter_range {
    template<class F>
    struct result {
        typedef boost::function_traits<F> traits;
        typedef typename traits::arg1_type arg1_type;
        typedef typename traits::arg2_type arg2_type;
        typedef filter_range<
            typename boost::remove_cv<
                typename boost::remove_reference<arg2_type>::type
            >::type,
            typename boost::remove_cv<
                typename boost::remove_reference<arg1_type>::type
            >::type
        > type;
    };
    template<class F, class Range>
    typename result<make_filter_range(F, Range)>::type operator()(F f, Range range) {
        return(typename result<make_filter_range(F, Range)>::type(range, f));
    }
};

template<class Range>
unsigned sum(const Range& range) {
    return(std::accumulate(boost::begin(range), boost::end(range), 0u));
}

volatile int force_calculation;

int main() {
    std::vector<unsigned> data;
    std::srand(10);
    std::generate_n(std::back_inserter(data), 10000000, &std::rand);
    std::pair<std::vector<unsigned>::const_iterator, std::vector<unsigned>::const_iterator> data_range(data.begin(), data.end());

    {
        boost::timer timer;
        namespace fusion = boost::fusion;
        using boost::phoenix::arg_names::_1;
        int i = sum(fusion::fold(fusion::make_vector(_1 % 2 != 0, _1 % 3 != 0, _1 % 5 != 0, _1 % 7 != 0), data_range, make_filter_range()));
        std::cout << timer.elapsed() << " seconds\n";
        force_calculation = i;
        std::cout << i << std::endl;
    }
    {
        boost::timer timer;
        namespace fusion = boost::fusion;
        using boost::phoenix::arg_names::_1;
        int i = sum(fusion::fold(fusion::make_vector(is_not_divisible_by<2>(), is_not_divisible_by<3>(), is_not_divisible_by<5>(), is_not_divisible_by<7>()), data_range, make_filter_range()));
        std::cout << timer.elapsed() << " seconds\n";
        force_calculation = i;
        std::cout << i << std::endl;
    }

    {
        boost::timer timer;
        int i = 0;
        for(std::vector<unsigned>::const_iterator begin = data.begin(), end = data.end(); begin != end; ++begin) {
            if(*begin % 2 != 0 && *begin % 3 != 0 && *begin % 5 != 0 && *begin % 7 != 0) {
                i += *begin;
            }
        }
        std::cout << timer.elapsed() << " seconds\n";
        force_calculation = i;
        std::cout << i << std::endl;
    }
}