Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement