#ifndef _INIT_ITERATOR_GUARD
#define _INIT_ITERATOR_GUARD

#include <vector>
#include <utility>
#include <boost/shared_ptr.hpp>
#include <boost/call_traits.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/mpl/empty.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/int_c.hpp>
#include "boost/mpl/if.hpp"

namespace detail {

  template <class ValueType>
    struct compile_time_init_iterator_data
  {
    ValueType value;
    compile_time_init_iterator_data<ValueType>* next;
    compile_time_init_iterator_data<ValueType>* prev;
    bool at_end;
    unsigned index;
  };

  template <class ValueType>
  struct empty_sequence_ct_iterator_data
  {
    static compile_time_init_iterator_data<ValueType> data;
    typedef empty_sequence_ct_iterator_data sequence_type;
  };

  template <class ValueType>
  compile_time_init_iterator_data<ValueType> 
    empty_sequence_ct_iterator_data<ValueType>::data = 
  {
    0, /* value - dummy */
    0, /* next */
    0, /* prev */
    true, /* at end */
    0, /* index */
  };

  template <class Sequence, class ValueType>
  struct begin_sequence_ct_iterator_data
  {
    static compile_time_init_iterator_data<ValueType> data;
    typedef begin_sequence_ct_iterator_data sequence_type;
  };

  template <class Sequence, class ValueType>
  struct end_sequence_ct_iterator_data
  {
    static compile_time_init_iterator_data<ValueType> data;
    typedef end_sequence_ct_iterator_data sequence_type;
  };

  template <unsigned Index, class Sequence, class ValueType>
  struct middle_sequence_ct_iterator_data
  {
    static compile_time_init_iterator_data<ValueType> data;
    typedef middle_sequence_ct_iterator_data sequence_type;
  };

  template <class Sequence, class ValueType>
  compile_time_init_iterator_data<ValueType> 
    begin_sequence_ct_iterator_data<Sequence, ValueType>::data = 
  {
    boost::mpl::at<Sequence, boost::mpl::int_c<0> >::type::value, /* value */
    &sequence_ct_iterator_data<1, Sequence, ValueType>::sequence_type::data, /* next */
    0, /* prev */
    false, /* at end */
    0, /* index */
  };

  template <class Sequence, class ValueType>
  compile_time_init_iterator_data<ValueType>
    end_sequence_ct_iterator_data<Sequence, ValueType>::data = 
  {
    0, /* value - dummy */
    0, /* next */
    &sequence_ct_iterator_data<boost::mpl::size<Sequence>::value - 1, Sequence, ValueType>::sequence_type::data, /* prev */
    true, /* at end */
    boost::mpl::size<Sequence>::value, /* index */
  };

  template <unsigned Index, class Sequence, class ValueType>
  compile_time_init_iterator_data<ValueType> 
    middle_sequence_ct_iterator_data<Index, Sequence, ValueType>::data = 
  {
    boost::mpl::at<Sequence, boost::mpl::int_c<Index> >::type::value, /* value */
    &sequence_ct_iterator_data<Index + 1, Sequence, ValueType>::sequence_type::data, /* next */
    &sequence_ct_iterator_data<Index - 1, Sequence, ValueType>::sequence_type::data, /* next */
    false, /* at end */
    Index, /* index */
  };

  template <unsigned Index, class Sequence, class ValueType>
    struct not_empty_sequence_ct_iterator_data
  {
    enum { sequence_size = boost::mpl::size<Sequence>::type::value };
    typedef boost::mpl::if_c<
        Index == 0,
        begin_sequence_ct_iterator_data<Sequence, ValueType>,
        boost::mpl::if_c<
          Index == sequence_size,
          end_sequence_ct_iterator_data<Sequence, ValueType>,
          middle_sequence_ct_iterator_data<Index, Sequence, ValueType>
        >::type
      >::type::sequence_type sequence_type;
  };

  template <unsigned Index, class Sequence, class ValueType>
    struct sequence_ct_iterator_data
  {
    enum { sequence_empty = boost::mpl::empty<Sequence>::type::value };
    typedef boost::mpl::if_c<
        sequence_empty,
        empty_sequence_ct_iterator_data<ValueType>,
        not_empty_sequence_ct_iterator_data<Index, Sequence, ValueType>
      >::type::sequence_type sequence_type;
  };

  template <class Sequence>
    struct sequence_type
  {
    enum { sequence_empty = boost::mpl::empty<Sequence>::type::value };
    typedef boost::mpl::if_c<
        sequence_empty,
        int,
        boost::mpl::at<Sequence, boost::mpl::int_c<0> >::value_type
      >::type type;
  };

  template <class T>
  class init_iterator_base
  {
  public:
    init_iterator_base()
    {
    }

    init_iterator_base(std::vector<T> const& a_rhs)
      : values(new std::vector<T>(a_rhs))
      , current(values->begin())
    {
    }

    bool operator==(const init_iterator_base& a_rhs) const
    {
      const bool am_at_end(at_end());
      const bool rhs_at_end(a_rhs.at_end());
      if (am_at_end || rhs_at_end) return am_at_end && rhs_at_end;
      return current == a_rhs.current;
    }

    bool at_end() const
    {
      return values.get() == 0 || current == values->end();
    }

    void operator++()
    {
      ++current;
    }

    const T& operator*() const
    {
      return *current;
    }

  private:
    boost::shared_ptr<std::vector<T> > values;
    std::vector<T>::const_iterator current;
  };

  template <class T>
  class ct_init_iterator_base
  {
  public:

    ct_init_iterator_base() : sequence(0) {}

    template <class Sequence>
    ct_init_iterator_base(Sequence*)
      : sequence(&sequence_ct_iterator_data<0, Sequence, T>::sequence_type::data)
    {
    }

    ct_init_iterator_base(const ct_init_iterator_base& a_rhs)
      : sequence(a_rhs.sequence)
    {
    }

    bool operator==(const ct_init_iterator_base& a_rhs) const
    {
      const bool am_at_end(at_end());
      const bool rhs_at_end(a_rhs.at_end());
      if (am_at_end || rhs_at_end) return am_at_end && rhs_at_end;
      return sequence->index == a_rhs.sequence->index;
    }

    bool at_end() const
    {
      return sequence == 0 || sequence->at_end;
    }

    void operator++()
    {
      sequence = sequence->next;
    }

    void operator--()
    {
      sequence = sequence->prev;
    }

    const T& operator*() const
    {
      return sequence->value;
    }

  private:
    compile_time_init_iterator_data<T>* sequence;
  };

  template <class T>
  struct init_iterator_generator
  {
    typedef boost::iterator_adaptor<
    init_iterator_base<T>, 
    boost::default_iterator_policies,
    const T,
    const T&,
    const T*,
    std::forward_iterator_tag,
    ptrdiff_t> type;
  };

  template <class SequenceType, class Sequence>
  struct ct_init_iterator_generator
  {
    typedef SequenceType value_type;
    typedef ct_init_iterator_base<value_type> base_type;
    typedef boost::iterator_adaptor<
    base_type, 
    boost::default_iterator_policies,
    const value_type,
    const value_type&,
    const value_type*,
    std::bidirectional_iterator_tag,
    ptrdiff_t> iter_type;
  };

  char is_pair_helper(...);
  template <class A, class B> double is_pair_helper(const std::pair<A, B>&);

  template <class P> struct is_pair
  {
    static P makeP();
    enum { value = sizeof(double) == sizeof(is_pair_helper(makeP())) };
  };

  template <class T>
  class initializer
  {
  public:
    typedef init_iterator_generator<T>::type iterator;
    initializer(boost::call_traits<T>::param_type a_param)
    {
      values.push_back(a_param);
    }

    iterator operator()() const
    {
      return iterator(init_iterator_base<T>(values));
    }

    initializer& operator()(boost::call_traits<T>::param_type a_param)
    {
      values.push_back(a_param);
      return *this;
    }

  private:
    std::vector<T> values;
  };

  template <class T>
  class pair_initializer
  {
  public:
    typedef init_iterator_generator<T>::type iterator;

    pair_initializer(boost::call_traits<T>::param_type a_param)
    {
      values.push_back(a_param);
    }

    pair_initializer(
      boost::call_traits<T::first_type>::param_type a_first,
      boost::call_traits<T::second_type>::param_type a_second)
    {
      values.push_back(T(a_first, a_second));
    }

    iterator operator()() const
    {
      return iterator(init_iterator_base<T>(values));
    }

    pair_initializer& operator()(boost::call_traits<T>::param_type a_param)
    {
      values.push_back(a_param);
      return *this;
    }

    pair_initializer& operator()(
      boost::call_traits<T::first_type>::param_type a_first,
      boost::call_traits<T::second_type>::param_type a_second)
    {
      values.push_back(T(a_first, a_second));
      return *this;
    }

  private:
    std::vector<T> values;
  };

  template <class T>
  struct make_init_iterator_return
  {
    typedef boost::mpl::if_c<detail::is_pair<T>::value, detail::pair_initializer<T>,
    detail::initializer<T> >::type type;
  };

}

template <class T>
detail::init_iterator_generator<T>::type make_init_iterator()
{
  return detail::init_iterator_generator<T>::type(
    detail::init_iterator_base<T>());
}

template <class Sequence, class SequenceType = long>
struct ct_init_iterator 
{
  typedef detail::ct_init_iterator_generator<SequenceType, Sequence>::iter_type
    iter_type;
  typedef detail::ct_init_iterator_generator<SequenceType, Sequence> 
    generator_type;
  static iter_type type()
  { 
    return iter_type(generator_type::base_type((Sequence*)0));
  }
};

template <class T>
detail::make_init_iterator_return<T>::type make_init_iterator(
  boost::call_traits<T>::param_type a_param)
{
  return detail::make_init_iterator_return<T>::type(a_param);
}

template <class T>
detail::pair_initializer<T> make_init_iterator(
  boost::call_traits<T::first_type>::param_type a_first,
  boost::call_traits<T::second_type>::param_type a_second)
{
  return detail::pair_initializer<T>(a_first, a_second);
}

#endif