#ifndef ITERATORS_TUPLEIT_HH
#define ITERATORS_TUPLEIT_HH

#include <iterator>
#include <cstddef>
#include <algorithm>
#include <stdexcept>
#include <new>
#include "boost/tuple/tuple.hpp"
#include "boost/tuple/tuple_comparison.hpp"
#include "boost/utility.hpp"
#include "boost/type_traits.hpp"
#include "boost/optional.hpp" // for aligned_storage
#include <memory>

namespace iterators
{
    namespace detail
    {
        void preincrementTuple(boost::tuples::null_type)
        {
        }

        template<typename TupleType>
        void preincrementTuple(TupleType& lhs)
        {
            preincrementTuple(lhs.get_tail());
            ++(lhs.template get<0>());
        }

        void predecrementTuple(boost::tuples::null_type)
        {
        }

        template<typename TupleType>
        void predecrementTuple(TupleType& lhs)
        {
            predecrementTuple(lhs.get_tail());
            --(lhs.template get<0>());
        }

        template<typename difference_type>
        void addToTuple(boost::tuples::null_type,difference_type)
        {
        }

        template<typename difference_type,typename TupleType>
        void addToTuple(TupleType& lhs,difference_type diff)
        {
            addToTuple(lhs.get_tail(),diff);
            lhs.template get<0>()+=diff;
        }

        template<typename difference_type>
        void subFromTuple(boost::tuples::null_type,difference_type)
        {
        }

        template<typename difference_type,typename TupleType>
        void subFromTuple(TupleType& lhs,difference_type diff)
        {
            subFromTuple(lhs.get_tail(),diff);
            lhs.template get<0>()-=diff;
        }

        template<typename difference_type,typename TupleType>
        difference_type diffTuples(TupleType const& lhs,TupleType const& rhs);

        template<typename difference_type,typename TupleType>
        struct DiffTupleHelper
        {
            static difference_type doDiff(TupleType const& lhs,TupleType const& rhs)
            {
                difference_type res1=lhs.template get<0>()-rhs.template get<0>();
                difference_type res2=diffTuples<difference_type>(lhs.get_tail(),rhs.get_tail());

                if(res1==res2)
                {
                    return res1;
                }

                throw std::logic_error("The iterators in the tuples are mismatched");
            }
        };

        template<typename difference_type,typename ValueType>
        struct DiffTupleHelper<difference_type,boost::tuples::cons<ValueType,boost::tuples::null_type> >
        {
            static difference_type doDiff(boost::tuples::cons<ValueType,boost::tuples::null_type> const& lhs,boost::tuples::cons<ValueType,boost::tuples::null_type>  const& rhs)
            {
                return lhs.template get<0>()-rhs.template get<0>();
            }
        };

        template<typename difference_type,typename TupleType>
        difference_type diffTuples(TupleType const& lhs,TupleType const& rhs)
        {
            return DiffTupleHelper<difference_type,TupleType>::doDiff(lhs,rhs);
        }



        template<typename SourceTuple>
        struct MakeTupleTypeWithReferences
        {
            typedef MakeTupleTypeWithReferences<typename SourceTuple::tail_type> TailTupleTypeBuilder;
            typedef typename TailTupleTypeBuilder::Type TailTupleType;
            typedef boost::tuples::cons<typename boost::add_reference<typename SourceTuple::head_type>::type,
                                        TailTupleType> Type;

            template<typename Tuple>
            static Type makeTuple(Tuple& source)
            {
                return Type(source.get_head(),TailTupleTypeBuilder::makeTuple(source.get_tail()));
            }
        };

        template<>
        struct MakeTupleTypeWithReferences<boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;

            static Type makeTuple(boost::tuples::null_type)
            {
                return Type();
            }
        };

    typedef char Tiny;
    struct Small
    {
        Tiny dummy[2];
    };
    struct Medium
    {
        Small dummy[2];
    };
    struct Large
    {
        Medium dummy[2];
    };
    struct Huge
    {
        Large dummy[2];
    };

    template<unsigned>
    struct CategoryMap
    {
        typedef void Type;
    };



//     Tiny categoryCheck(std::output_iterator_tag*);
    Small categoryCheck(std::input_iterator_tag*);
    Medium categoryCheck(std::forward_iterator_tag*);
    Large categoryCheck(std::bidirectional_iterator_tag*);
    Huge categoryCheck(std::random_access_iterator_tag*);


//     template<>
//     struct CategoryMap<sizeof(Tiny)>
//     {
//  typedef std::output_iterator_tag Type;
//     };

    template<>
    struct CategoryMap<sizeof(Small)>
    {
        typedef std::input_iterator_tag Type;
    };

    template<>
    struct CategoryMap<sizeof(Medium)>
    {
        typedef std::forward_iterator_tag Type;
    };

    template<>
    struct CategoryMap<sizeof(Large)>
    {
        typedef std::bidirectional_iterator_tag Type;
    };
    template<>
    struct CategoryMap<sizeof(Huge)>
    {
        typedef std::random_access_iterator_tag Type;
    };

    template<typename Cat1,typename Cat2>
    struct CommonCategory
    {
    private:
        enum
        {categorySize=sizeof(::iterators::detail::categoryCheck(false?(Cat1*)0:(Cat2*)0))
        };
    public:
        typedef typename CategoryMap<categorySize>::Type Type;
    };

    // specializations
    template<typename Cat>
    struct CommonCategory<std::output_iterator_tag,Cat>
    {
        typedef std::output_iterator_tag Type;
    };
    template<typename Cat>
    struct CommonCategory<Cat,std::output_iterator_tag>
    {
        typedef std::output_iterator_tag Type;
    };
    template<>
    struct CommonCategory<std::output_iterator_tag,std::output_iterator_tag>
    {
        typedef std::output_iterator_tag Type;
    };
    template<>
    struct CommonCategory<std::input_iterator_tag,std::output_iterator_tag>
    {
        // no Type, because error
    };
    template<>
    struct CommonCategory<std::output_iterator_tag,std::input_iterator_tag>
    {
        // no Type, because error
    };

        void derefAndWrite(boost::tuples::null_type,boost::tuples::null_type)
        {}

        template<typename IterTuple,typename SourceTuple>
        void derefAndWrite(IterTuple& iters,SourceTuple const& source)
        {
            *iters.get_head()=source.get_head();
            derefAndWrite(iters.get_tail(),source.get_tail());
        }

    }

    // An OutputTuple holds a tuple of references to iterators, and writes to them on assignment
    template<typename IterTuple>
    struct OutputTuple:
        public detail::MakeTupleTypeWithReferences<IterTuple>::Type,
        boost::noncopyable
    {
    private:
        typedef detail::MakeTupleTypeWithReferences<IterTuple> BaseTypeBuilder;
        typedef typename BaseTypeBuilder::Type BaseType;
    public:
    OutputTuple(IterTuple& iters):
            BaseType(BaseTypeBuilder::makeTuple(iters))
    {}

    template<typename SomeTuple>
    OutputTuple& operator=(const SomeTuple& other)
    {
            detail::derefAndWrite(static_cast<BaseType&>(*this),other);
        return *this;
    }
    };

    // An OwningRefTuple holds a tuple of references,
    // which may point to data within the tuple, or external to it

    namespace detail
    {
        struct PreserveReferences
        {};

        template<typename OwnedType>
        struct OwningBase
        {
            std::auto_ptr<OwnedType> tupleBuf;

            OwningBase()
            {}

            template<typename SomeType>
            OwningBase(SomeType &source):
                tupleBuf(new OwnedType(source))
            {}

        };
    }

    template<typename TupleType>
    struct OwningRefTuple:
        private detail::OwningBase<TupleType>,
        public detail::MakeTupleTypeWithReferences<TupleType>::Type
    {
    private:
        typedef detail::MakeTupleTypeWithReferences<TupleType> BaseTypeBuilder;
        typedef typename BaseTypeBuilder::Type BaseType;
        typedef detail::OwningBase<TupleType> OwningBaseType;
    public:

        typedef typename BaseType::head_type head_type;
        typedef typename BaseType::tail_type tail_type;

    private:
        typedef TupleType OwnedTuple;

    OwnedTuple* getTuplePtr()
    {
        return this->tupleBuf.get();
    }
    public:
    // copy from other types of tuples too
    template<typename SomeTuple>
    OwningRefTuple(const SomeTuple& other):
            OwningBaseType(other),BaseType(BaseTypeBuilder::makeTuple(*getTuplePtr()))
    {
    }
    // copying copies values by default
    OwningRefTuple(const OwningRefTuple& other):
            OwningBaseType(other),BaseType(BaseTypeBuilder::makeTuple(*getTuplePtr()))
    {
    }

    // allow user to specify
    // whether to preserve references
    template<typename SomeTuple>
    OwningRefTuple(SomeTuple& other,detail::PreserveReferences const&):
            BaseType(BaseTypeBuilder::makeTuple(other))
    {
    }

    // assignment assigns to referenced values
    template<typename SomeTuple>
    OwningRefTuple& operator=(const SomeTuple& other)
    {
            BaseType::operator=(other);
        return *this;
    }
    OwningRefTuple& operator=(const OwningRefTuple& other)
    {
            BaseType::operator=(other);
        return *this;
    }
    };

    namespace detail
    {
        template<typename IterTuple>
        struct DerefIterTupleHelperKeepRef
        {
            typedef boost::tuples::cons<typename boost::add_reference<typename std::iterator_traits<typename IterTuple::head_type>::value_type>::type,
                                        typename DerefIterTupleHelperKeepRef<typename IterTuple::tail_type>::Type> Type;
        };

        template<>
        struct DerefIterTupleHelperKeepRef<boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;
        };

        template<>
        struct DerefIterTupleHelperKeepRef<const boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;
        };


        template<typename IterTuple>
        struct DerefIterTupleHelperNoRef
        {
            typedef boost::tuples::cons<typename std::iterator_traits<typename IterTuple::head_type>::value_type,
                                        typename DerefIterTupleHelperNoRef<typename IterTuple::tail_type>::Type> Type;
        };

        template<>
        struct DerefIterTupleHelperNoRef<boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;
        };

        template<>
        struct DerefIterTupleHelperNoRef<const boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;
        };

        boost::tuples::null_type derefIterTupleKeepRef(boost::tuples::null_type const& iters)
        {
            return iters;
        }
        template<typename IterTuple>
        const typename DerefIterTupleHelperKeepRef<IterTuple>::Type derefIterTupleKeepRef(IterTuple& iters)
        {
            return typename DerefIterTupleHelperKeepRef<IterTuple>::Type(*iters.template get<0>(),derefIterTupleKeepRef(iters.get_tail()));
        }

        boost::tuples::null_type derefIterTupleNoRef(boost::tuples::null_type const& iters)
        {
            return iters;
        }
        template<typename IterTuple>
        typename DerefIterTupleHelperNoRef<IterTuple>::Type derefIterTupleNoRef(IterTuple& iters)
        {
            return typename DerefIterTupleHelperNoRef<IterTuple>::Type(*iters.template get<0>(),derefIterTupleNoRef(iters.get_tail()));
        }

    // Define, construct and destroy the appropriate value_type for
    // the given iterator category
    template<typename Category,typename IterTuple>
    struct ValueForCategory
    {
        private:
            typedef typename IterTuple::head_type HeadIterType;
            typedef typename IterTuple::tail_type TailTupleType;
        typedef typename std::iterator_traits<HeadIterType>::value_type HeadValueType;
        typedef typename ValueForCategory<Category,TailTupleType>::ValueTuple TailValueTuple;

        public:
            typedef boost::tuples::cons<HeadValueType,TailValueTuple> ValueTuple;

        typedef OwningRefTuple<ValueTuple> value_type;
        typedef value_type Type;

        static void construct(Type* p,IterTuple const& iters)
        {
        // don't copy values, keep as references
        new (p) Type(derefIterTupleKeepRef(iters),::iterators::detail::PreserveReferences());
        }

        static void destruct(Type* p)
        {
        p->~OwningRefTuple<ValueTuple>();
        }
    };

    template<typename Category>
    struct ValueForCategory<Category,boost::tuples::null_type>
    {
        private:
        public:
            typedef boost::tuples::null_type ValueTuple;
    };

    template<typename IterTuple>
    struct ValueForCategory<std::input_iterator_tag,IterTuple>
    {
        private:
            typedef typename IterTuple::head_type HeadIterType;
            typedef typename IterTuple::tail_type TailTupleType;
        typedef typename std::iterator_traits<HeadIterType>::value_type HeadValueType;
        typedef typename ValueForCategory<std::input_iterator_tag,TailTupleType>::ValueTuple TailValueTuple;

        public:
            typedef boost::tuples::cons<HeadValueType,TailValueTuple> ValueTuple;

        typedef OwningRefTuple<ValueTuple> value_type;
        typedef value_type Type;

        static void construct(Type* p,IterTuple const& iters)
        {
        // copy values
        new (p) Type(derefIterTupleNoRef(iters));
        }

        static void destruct(Type* p)
        {
        p->~OwningRefTuple<ValueTuple>();
        }
    };

    template<>
    struct ValueForCategory<std::input_iterator_tag,boost::tuples::null_type>
    {
        private:
        public:
            typedef boost::tuples::null_type ValueTuple;
    };

    template<typename IterTuple>
    struct ValueForCategory<std::output_iterator_tag,IterTuple>
    {
        public:
        typedef OutputTuple<IterTuple> value_type;
        typedef value_type Type;

        static void construct(Type* p,IterTuple& iters)
        {
        // copy values
        new (p) Type(iters);
        }

        static void destruct(Type* p)
        {
        p->~OutputTuple<IterTuple>();
        }
    };

    template<>
    struct ValueForCategory<std::output_iterator_tag,boost::tuples::null_type>
    {
        private:
        public:
    };


    template<typename Category,typename IterTuple>
    struct VFCSelector
    {
        typedef ValueForCategory<Category,IterTuple> Type;
    };

    // Select the iterator_category and value_type for our TupleIt
    template<typename IterTuple>
    struct TupleItHelper
    {
            typedef typename IterTuple::head_type HeadIterType;
            typedef typename IterTuple::tail_type TailTupleType;

        typedef typename std::iterator_traits<HeadIterType>::iterator_category Cat1;
        typedef typename TupleItHelper<TailTupleType>::iterator_category Cat2;

        typedef typename CommonCategory<Cat1,Cat2>::Type iterator_category;
        typedef typename VFCSelector<iterator_category,IterTuple>::Type ValueTypeDef;
        typedef typename ValueTypeDef::value_type value_type;
        typedef typename ValueTypeDef::Type DeRefType;

        typedef DeRefType& reference;
        typedef DeRefType* pointer;

        typedef std::ptrdiff_t difference_type;

        typedef std::iterator<iterator_category,value_type,difference_type,pointer,reference> IteratorType;

        static void construct(DeRefType* p,IterTuple& iters)
        {
        ValueTypeDef::construct(p,iters);
        }

        static void destruct(DeRefType* p)
        {
        ValueTypeDef::destruct(p);
        }
    };

    template<>
    struct TupleItHelper<boost::tuples::null_type>
    {
        typedef std::random_access_iterator_tag iterator_category;
    };
    }

    // the actual Tuple Iterator itself
    template<typename IterTuple>
    struct TupleIt:
    public detail::TupleItHelper<IterTuple>::IteratorType
    {
    private:
    typedef detail::TupleItHelper<IterTuple> TupleDefs;
    public:
    typedef typename TupleDefs::iterator_category iterator_category;
    typedef typename TupleDefs::value_type value_type;
    typedef typename TupleDefs::difference_type difference_type;
    typedef typename TupleDefs::reference reference;
    typedef typename TupleDefs::pointer pointer;
    private:
    pointer getValuePtr() const
    {
        return reinterpret_cast<pointer>(dataCache.address());
    }

    void emptyCache() const
    {
        if(cacheInitialized)
        {
        TupleDefs::destruct(getValuePtr());
        cacheInitialized=false;
        }
    }

    void initCache() const
    {
        emptyCache();
        TupleDefs::construct(getValuePtr(),iters);
        cacheInitialized=true;
    }


    public:

    TupleIt(IterTuple iters_):
        iters(iters_),cacheInitialized(false)
    {}
    template<typename OtherIterTuple>
    TupleIt(const TupleIt<OtherIterTuple>& other):
        iters(other.iters),cacheInitialized(false)
    {}
    TupleIt(const TupleIt& other):
        iters(other.iters),cacheInitialized(false)
    {}
    TupleIt():
        iters(),cacheInitialized(false)
    {}


    ~TupleIt()
    {
        emptyCache();
    }

    void swap(TupleIt& other)
    {
        using std::swap;

        swap(iters,other.iters);
    }

        TupleIt& operator=(TupleIt const& other)
        {
            emptyCache();
            iters=other.iters;
            return *this;
        }

    // Input Iterator requirements
    reference operator*() const
    {
        initCache();
        return *getValuePtr();
    }

    pointer operator->() const
    {
        initCache();
        return getValuePtr();
    }

    friend bool operator==(const TupleIt& lhs,const TupleIt& rhs)
    {
        return lhs.iters==rhs.iters;
    }

    friend bool operator!=(const TupleIt& lhs,const TupleIt& rhs)
    {
        return lhs.iters!=rhs.iters;
    }

    // Forward Iterator requirements
    TupleIt& operator++()
    {
            detail::preincrementTuple(iters);
        return *this;
    }

    TupleIt operator++(int)
    {
        TupleIt temp(*this);
        ++*this;
        return temp;
    }

    // Bidirectional Iterator requirements
    TupleIt& operator--()
    {
            detail::predecrementTuple(iters);
        return *this;
    }

    TupleIt operator--(int)
    {
        TupleIt temp(*this);
        --*this;
        return temp;
    }

    // Random-Access Iterator requirements
    TupleIt& operator+=(difference_type n)
    {
            detail::addToTuple(iters,n);
        return *this;
    }

    TupleIt& operator-=(difference_type n)
    {
            detail::subFromTuple(iters,n);
        return *this;
    }

    friend difference_type operator-(const TupleIt& a,const TupleIt& b)
    {
            return detail::diffTuples<difference_type>(a.iters,b.iters);
    }

    value_type operator[](difference_type n) const
    {
        return *(*this+n);
    }

    private:
    // everything is mutable so we can modify it without affecting const correctness
    // of client code
    mutable IterTuple iters;
    mutable boost::optional_detail::aligned_storage<typename TupleDefs::DeRefType> dataCache;
    mutable bool cacheInitialized;
    };

    // more random-access iterator requirements
    template<typename IterTuple>
    TupleIt<IterTuple> operator+(std::ptrdiff_t n,TupleIt<IterTuple> temp)
    {
    temp+=n;
    return temp;
    }

    template<typename IterTuple>
    TupleIt<IterTuple> operator+(TupleIt<IterTuple> temp,std::ptrdiff_t n)
    {
    temp+=n;
    return temp;
    }

    template<typename IterTuple>
    TupleIt<IterTuple> operator-(TupleIt<IterTuple> temp,std::ptrdiff_t n)
    {
    temp-=n;
    return temp;
    }

    template<typename IterTuple,typename IterTuple2>
    bool operator<(const TupleIt<IterTuple>& a,const TupleIt<IterTuple2>& b)
    {
    return (b-a)>0;
    }

    template<typename IterTuple,typename IterTuple2>
    bool operator>(const TupleIt<IterTuple>& a,const TupleIt<IterTuple2>& b)
    {
    return b<a;
    }

    template<typename IterTuple,typename IterTuple2>
    bool operator>=(const TupleIt<IterTuple>& a,const TupleIt<IterTuple2>& b)
    {
    return !(b<a);
    }

    template<typename IterTuple,typename IterTuple2>
    bool operator<=(const TupleIt<IterTuple>& a,const TupleIt<IterTuple2>& b)
    {
    return !(b>a);
    }

    // implementation of swap and iter_swap
    template<typename IterTuple>
    void swap(TupleIt<IterTuple>& lhs,TupleIt<IterTuple>& rhs)
    {
    lhs.swap(rhs);
    }

//     template<typename IterTuple,IterTuple2>
//     void iter_swap(const TupleIt<IterTuple>& lhs,const TupleIt<IterTuple2>& rhs)
//     {
//  lhs.iter_swap(rhs);
//     }

    template<typename Iter1,typename Iter2>
    TupleIt<typename boost::tuples::tuple<Iter1,Iter2> > makeTupleIterator(Iter1 i1,Iter2 i2)
    {
    return TupleIt<typename boost::tuples::tuple<Iter1,Iter2> >(boost::make_tuple(i1,i2));
    }

    template<typename Iter1,typename Iter2,typename Iter3>
    TupleIt<typename boost::tuples::tuple<Iter1,Iter2,Iter3> > makeTupleIterator(Iter1 i1,Iter2 i2,Iter3 i3)
    {
    return TupleIt<typename boost::tuples::tuple<Iter1,Iter2,Iter3> >(boost::make_tuple(i1,i2,i3));
    }

    template<typename Iter1,typename Iter2,typename Iter3,typename Iter4>
    TupleIt<typename boost::tuples::tuple<Iter1,Iter2,Iter3,Iter4> > makeTupleIterator(Iter1 i1,Iter2 i2,Iter3 i3,Iter4 i4)
    {
    return TupleIt<typename boost::tuples::tuple<Iter1,Iter2,Iter3,Iter4> >(boost::make_tuple(i1,i2,i3,i4));
    }

}

#endif