// transform_iterator.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <vector>
#include <numeric>
#include <iostream>
#include <boost/bind.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/iterator/iterator_concepts.hpp>
#include <boost/iterator/iterator_traits.hpp>
#include <boost/concept/requires.hpp>
#include <boost/utility/result_of.hpp>
#include <boost/type_traits/has_trivial_constructor.hpp>
#include <boost/function.hpp>
#include <windows.h>


// Precision timer
class precision_timer
{
    LARGE_INTEGER freq_, start_;

public:
	precision_timer() {QueryPerformanceFrequency(&freq_);}
	void start() {QueryPerformanceCounter(&start_);}

	double stop()
	{
		// Return duration in seconds...
		LARGE_INTEGER lEnd;
		QueryPerformanceCounter(&lEnd);
		return (double(lEnd.QuadPart - start_.QuadPart) / freq_.QuadPart);
	}
};


// Check the ForwardIterator concept requirements
template <class ForwardIterator>
void check(ForwardIterator _it)
{
	using namespace boost;
	function_requires<boost_concepts::ForwardTraversalConcept<ForwardIterator> >();
}


// A proposed modification of make_transform_iterator
namespace boost_ext {

    template <class UnaryFunc, class Iterator>
    boost::transform_iterator<UnaryFunc, Iterator>
    make_transform_iterator(Iterator it, UnaryFunc fun, typename boost::enable_if<boost::has_trivial_constructor<UnaryFunc> >::type* dummy = 0)
    {
        return boost::transform_iterator<UnaryFunc, Iterator>(it, fun);
    }
      
    template <class UnaryFunc, class Iterator>
    struct function_type
    {
        typedef typename boost::iterator_reference<Iterator>::type argument_type;
        typedef typename boost::result_of<UnaryFunc(argument_type)>::type result_type;

        typedef boost::function<result_type (argument_type)> type;              
    };

    template <class UnaryFunc, class Iterator>
    boost::transform_iterator<typename function_type<UnaryFunc, Iterator>::type, Iterator>
    make_transform_iterator(Iterator it, UnaryFunc fun, typename boost::disable_if<boost::has_trivial_constructor<UnaryFunc> >::type* dummy = 0)
    {
        typedef typename function_type<UnaryFunc, Iterator>::type function_type;

        return boost::transform_iterator<function_type, Iterator>(it, function_type(fun));
    }

} //namespace boost_ext


// A simple class that has a data member and function member
struct foo
{
    foo(const size_t& _id) : id_(_id) {}

	size_t id_;
	const size_t& get_id() const {return id_;}
};


// An hand written member function wrapper
struct hand_written_mem_fn
{
    typedef const size_t& result_type;
    const size_t& operator()(const foo& _f) const {return _f.get_id();}
};


struct compare
{
    double timer_quotient_;
    compare(double _timer1, double _timer2) : timer_quotient_((_timer1 - _timer2) / _timer2) { }
};

inline std::ostream& operator<<(std::ostream& _os, const compare& _c)
{
    if (_c.timer_quotient_ < 0.)
        _os << - _c.timer_quotient_ << " faster than";
    else
        _os << _c.timer_quotient_ << " slower than";

    return _os;
}

int main(int argc, char* argv[])
{
	using namespace boost;

	std::vector<foo> foo_vec;
    
    size_t nb_foo = 100000000;
    foo_vec.reserve(nb_foo);
    for (size_t i = 0 ; i < nb_foo ; i++)
        foo_vec.push_back(foo(i));
/*
    // Fail to compile since mem_fn is not Default Constructible
	check(make_transform_iterator(foo_vec.begin(), mem_fn(&foo::get_id)));
    // Fail to compile since mem_fn is not Default Constructible
	check(make_transform_iterator(foo_vec.begin(), mem_fn(&foo::id_)));
*/
    // boost::function is default constructible, the concept requirement passed
    check(make_transform_iterator(foo_vec.begin(), function<size_t (const foo&)>(mem_fn(&foo::get_id))));
    // hand_written_mem_fn is default constructible, the concept requirement passed
    check(make_transform_iterator(foo_vec.begin(), hand_written_mem_fn()));

    // Test the proposed make_transform_iterator extension
    check(boost_ext::make_transform_iterator(foo_vec.begin(), mem_fn(&foo::get_id)));
    check(boost_ext::make_transform_iterator(foo_vec.begin(), mem_fn(&foo::id_)));

    double timer0 =0, timer1=0, timer2=0, timer3=0, timer4=0, timer5=0;

    size_t nb_loop = 10;
    for (size_t loop = 0 ; loop < nb_loop ; ++loop)
    {
        // Hand written loop
        {
            precision_timer pt;
            pt.start();
            int res = 0;
            for (size_t i = 0 ; i < foo_vec.size() ; ++i)
                res += foo_vec[i].get_id();
            std::cout << "res: " << res << " timer: " << (timer0 += pt.stop()) << std::endl;
        }

        // Hand written member function wrapper
        {
            precision_timer pt;
            pt.start();
            int res = std::accumulate(
                boost_ext::make_transform_iterator(foo_vec.begin(), hand_written_mem_fn()),
                boost_ext::make_transform_iterator(foo_vec.end(), hand_written_mem_fn()),
                0);
            std::cout << "res: " << res << " timer: " << (timer1 += pt.stop()) << std::endl;
        }

        // mem_fn wrapper
        {
            precision_timer pt;
            pt.start();
            int res = std::accumulate(
                make_transform_iterator(foo_vec.begin(), mem_fn(&foo::get_id)),
                make_transform_iterator(foo_vec.end(), mem_fn(&foo::get_id)),
                0);
            std::cout << "res: " << res << " timer: " <<( timer2 += pt.stop()) << std::endl;
        }

        // mem_fn wrapper within boost function
        {
            precision_timer pt;
            pt.start();
            int res = std::accumulate(
                make_transform_iterator(foo_vec.begin(), function<const size_t& (const foo&)>(mem_fn(&foo::get_id))),
                make_transform_iterator(foo_vec.end(), function<const size_t& (const foo&)>(mem_fn(&foo::get_id))),
                0);
            std::cout << "res: " << res << " timer: " << (timer3 += pt.stop()) << std::endl;
        }
    
        // boost_ext::make_transform_iterator
        {
            precision_timer pt;
            pt.start();
            int res = std::accumulate(
                boost_ext::make_transform_iterator(foo_vec.begin(), mem_fn(&foo::get_id)),
                boost_ext::make_transform_iterator(foo_vec.end(), mem_fn(&foo::get_id)),
                0);
            std::cout << "res: " << res << " timer: " << (timer4 += pt.stop()) << std::endl;
        }

        // c0x lambda
        {
            precision_timer pt;
            pt.start();
            int res = 0;
            std::for_each(foo_vec.begin(), foo_vec.end(), [&res](const foo& _x){res +=_x.get_id();});
            std::cout << "res: " << res << " timer: " << (timer5 += pt.stop()) << std::endl;
        }
    }

    std::cout << "\n---\n";
    std::cout << "hand written call wrapper is " << compare(timer1, timer0) << " the hand written loop\n";
    std::cout << "boost::mem_fn is " << compare(timer2, timer0) << " the hand written loop\n";
    std::cout << "boost::function is " << compare(timer3, timer0) << " the hand written loop\n";
    std::cout << "boost_ext::make_transform_iterator is " << compare(timer4, timer0) << " the hand written loop\n";
    std::cout << "c0x lambda is " << compare(timer5, timer0) << " the hand written loop" << std::endl;

	return 0;
}