#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/spirit/home/phoenix/bind.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 T>
T range_get_end(const T& range) {
    return(T(boost::end(range), boost::end(range)));
}

template<class R, class F>
class filter_range;

struct range_begin_tag {};
struct range_end_tag {};

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;
    typedef filter_range<typename associated_range<Iter>::type, F> associated_range_type;
    filter_iterator(Iter b, Iter e, F f ) :
        m_range(b,e,f) {}
    template<class R>
    filter_iterator(filter_range<R, F>& range, range_begin_tag) :
        m_range(range) {}
    template<class R>
    filter_iterator(filter_range<R, F>& range, range_end_tag) :
        m_range(range_get_end(range)) {}
    template<class R>
    filter_iterator(const filter_range<R, F>& range, range_begin_tag) :
        m_range(range) {}
    template<class R>
    filter_iterator(const filter_range<R, F>& range, range_end_tag) :
        m_range(range_get_end(range)) {}
private:
    void increment() {
        increment_range_begin(m_range);
    }

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

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

    associated_range_type m_range;
};

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.m_range), boost::begin(e.m_range.m_range)),
          m_f(b.m_range.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(*this, range_begin_tag());
    }
    iterator end() {
        return iterator(*this, range_end_tag());
    }


    const_iterator begin() const {
        return const_iterator(*this, range_begin_tag());
    }
    const_iterator end() const {
        return const_iterator(*this, range_end_tag());
    }
    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));
    }
    friend bool range_begin_equal(const filter_range& lhs, const filter_range& rhs) {
        return(range_begin_equal(lhs.m_range, rhs.m_range));
    }
    friend filter_range range_get_end(const filter_range& range) {
        return(filter_range(range_get_end(range.m_range), range.m_f));
    }

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 {
    typedef bool result_type;
    template<class T>
    struct result { typedef bool type; };
    bool operator()(int n) const {
        return(n % N != 0);
    }
};

struct is_not_divisible_by_2_3_5_or_7 {
    bool operator()(int n) const {
        return(n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && n % 7 != 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));
}

void force_calculation(int i) {
    static int count = 0;
    static volatile int value;
    if(count && value != i) {
        std::cerr << "error in run " << count << std::endl;
    }
    value = i;
    ++count;
}

int main() {
    std::vector<unsigned> data;
    std::srand(10);
    std::generate_n(std::back_inserter(data), 100000000, &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);
    }
    {
        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);
    }

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

    {
        boost::timer timer;
        namespace fusion = boost::fusion;
        using boost::phoenix::arg_names::_1;
        int i = sum(make_filter_range()(is_not_divisible_by_2_3_5_or_7(), data_range));
        std::cout << timer.elapsed() << " seconds\n";
        force_calculation(i);
    }

    {
        boost::timer timer;
        unsigned 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);
    }

    {
        boost::timer timer;
        unsigned i = 0;
        for(const unsigned *begin = &data[0], *end = &data[0] + data.size(); 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);
    }
}