Chris@16: /*-----------------------------------------------------------------------------+
Chris@16: Copyright (c) 2009-2009: Joachim Faulhaber
Chris@16: +------------------------------------------------------------------------------+
Chris@16:    Distributed under the Boost Software License, Version 1.0.
Chris@16:       (See accompanying file LICENCE.txt or copy at
Chris@16:            http://www.boost.org/LICENSE_1_0.txt)
Chris@16: +-----------------------------------------------------------------------------*/
Chris@16: #ifndef BOOST_ICL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104
Chris@16: #define BOOST_ICL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104
Chris@16: 
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/iterator/iterator_facade.hpp>
Chris@16: #include <boost/config/warning_disable.hpp>
Chris@16: #include <boost/icl/type_traits/succ_pred.hpp>
Chris@16: #include <boost/icl/detail/mapped_reference.hpp>
Chris@16: 
Chris@16: namespace boost{namespace icl
Chris@16: {
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: struct is_std_pair
Chris@16: { 
Chris@16:     typedef is_std_pair<Type> type; 
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = false);
Chris@16: };
Chris@16: 
Chris@16: template<class FirstT, class SecondT>
Chris@16: struct is_std_pair<std::pair<FirstT, SecondT> >
Chris@16: { 
Chris@16:     typedef is_std_pair<std::pair<FirstT, SecondT> > type; 
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true);
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class Type>
Chris@16: struct first_element
Chris@16: { 
Chris@16:     typedef Type type; 
Chris@16: };
Chris@16: 
Chris@16: template<class FirstT, class SecondT>
Chris@16: struct first_element<std::pair<FirstT, SecondT> >
Chris@16: { 
Chris@16:     typedef FirstT type; 
Chris@16: };
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: template <class SegmentIteratorT> class element_iterator;
Chris@16: 
Chris@16: template<class IteratorT>
Chris@16: struct is_reverse
Chris@16: { 
Chris@16:     typedef is_reverse type; 
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = false);
Chris@16: };
Chris@16: 
Chris@16: template<class BaseIteratorT>
Chris@16: struct is_reverse<std::reverse_iterator<BaseIteratorT> >
Chris@16: { 
Chris@16:     typedef is_reverse<std::reverse_iterator<BaseIteratorT> > type; 
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true);
Chris@16: };
Chris@16: 
Chris@16: template<class BaseIteratorT>
Chris@16: struct is_reverse<icl::element_iterator<BaseIteratorT> >
Chris@16: { 
Chris@16:     typedef is_reverse<icl::element_iterator<BaseIteratorT> > type; 
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = is_reverse<BaseIteratorT>::value);
Chris@16: };
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class SegmentT>
Chris@16: struct elemental;
Chris@16: 
Chris@16: #ifdef ICL_USE_INTERVAL_TEMPLATE_TEMPLATE
Chris@16: 
Chris@16:     template<class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval>
Chris@16:     struct elemental<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) >
Chris@16:     {
Chris@16:         typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type;
Chris@16:         typedef segment_type              interval_type;
Chris@16:         typedef DomainT                   type;
Chris@16:         typedef DomainT                   domain_type;
Chris@16:         typedef DomainT                   codomain_type;
Chris@16:         typedef DomainT                   transit_type;
Chris@16:     };
Chris@16: 
Chris@16:     template< class DomainT, class CodomainT, 
Chris@16:               ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval >
Chris@16:     struct elemental<std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare)const, CodomainT> >
Chris@16:     {
Chris@16:         typedef std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare), CodomainT> segment_type;
Chris@16:         typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare)                       interval_type;
Chris@16:         typedef std::pair<DomainT, CodomainT>                   type;
Chris@16:         typedef DomainT                                         domain_type;
Chris@16:         typedef CodomainT                                       codomain_type;
Chris@16:         typedef mapped_reference<DomainT, CodomainT>            transit_type;
Chris@16:     };
Chris@16: 
Chris@16: #else //ICL_USE_INTERVAL_TEMPLATE_TYPE
Chris@16: 
Chris@16:     template<ICL_INTERVAL(ICL_COMPARE) Interval>
Chris@16:     struct elemental
Chris@16:     {
Chris@16:         typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type;
Chris@16:         typedef segment_type                        interval_type;
Chris@16:         typedef typename interval_traits<interval_type>::domain_type domain_type;
Chris@16:         typedef domain_type                         type;
Chris@16:         typedef domain_type                         codomain_type;
Chris@16:         typedef domain_type                         transit_type;
Chris@16:     };
Chris@16: 
Chris@16:     template< class CodomainT, ICL_INTERVAL(ICL_COMPARE) Interval >
Chris@16:     struct elemental<std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare)const, CodomainT> >
Chris@16:     {
Chris@16:         typedef std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare), CodomainT> segment_type;
Chris@16:         typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare)                       interval_type;
Chris@16:         typedef typename interval_traits<interval_type>::domain_type domain_type;
Chris@16:         typedef CodomainT                                       codomain_type;
Chris@16:         typedef std::pair<domain_type, codomain_type>           type;
Chris@16:         typedef mapped_reference<domain_type, codomain_type>    transit_type;
Chris@16:     };
Chris@16: 
Chris@16: #endif //ICL_USE_INTERVAL_TEMPLATE_TEMPLATE
Chris@16: 
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: //- struct segment_adapter
Chris@16: //------------------------------------------------------------------------------
Chris@16: template<class SegmentIteratorT, class SegmentT>
Chris@16: struct segment_adapter;
Chris@16: 
Chris@16: #ifdef ICL_USE_INTERVAL_TEMPLATE_TEMPLATE
Chris@16: 
Chris@16: template<class SegmentIteratorT, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval>
Chris@16: struct segment_adapter<SegmentIteratorT, ICL_INTERVAL_TYPE(Interval,DomainT,Compare) >
Chris@16: {
Chris@16:     typedef segment_adapter                         type;
Chris@16:     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type;
Chris@16:     typedef segment_type                            interval_type;
Chris@16:     typedef typename interval_type::difference_type domain_difference_type;
Chris@16:     typedef DomainT                                 domain_type;
Chris@16:     typedef DomainT                                 codomain_type;
Chris@16:     typedef domain_type                             element_type;
Chris@16:     typedef domain_type&                            transit_type;
Chris@16: 
Chris@16:     static domain_type     first (const SegmentIteratorT& leaper){ return leaper->first(); } 
Chris@16:     static domain_type     last  (const SegmentIteratorT& leaper){ return leaper->last();  } 
Chris@16:     static domain_difference_type length(const SegmentIteratorT& leaper){ return leaper->length();}
Chris@16: 
Chris@16:     static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper, 
Chris@16:                                           const domain_difference_type& sneaker)
Chris@16:     { 
Chris@16:         inter_pos = is_reverse<SegmentIteratorT>::value ? leaper->last()  - sneaker
Chris@16:                                                         : leaper->first() + sneaker;
Chris@16:         return inter_pos; 
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template < class SegmentIteratorT, class DomainT, class CodomainT, 
Chris@16:            ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval >
Chris@16: struct segment_adapter<SegmentIteratorT, std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare)const, CodomainT> >
Chris@16: {
Chris@16:     typedef segment_adapter                         type;
Chris@16:     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare)               interval_type;
Chris@16:     typedef DomainT                                 domain_type;
Chris@16:     typedef std::pair<DomainT, CodomainT>           element_type;
Chris@16:     typedef CodomainT                               codomain_type;
Chris@16:     typedef mapped_reference<DomainT, CodomainT>    transit_type;    
Chris@16:     typedef typename difference_type_of<interval_traits<interval_type> >::type 
Chris@16:                                                     domain_difference_type;
Chris@16: 
Chris@16:     static domain_type     first (const SegmentIteratorT& leaper){ return leaper->first.first(); } 
Chris@16:     static domain_type     last  (const SegmentIteratorT& leaper){ return leaper->first.last();  } 
Chris@16:     static domain_difference_type length(const SegmentIteratorT& leaper){ return leaper->first.length();}
Chris@16: 
Chris@16:     static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper,
Chris@16:                                           const domain_difference_type& sneaker)
Chris@16:     {
Chris@16:         inter_pos = is_reverse<SegmentIteratorT>::value ? leaper->first.last()  - sneaker
Chris@16:                                                         : leaper->first.first() + sneaker;
Chris@16:         return transit_type(inter_pos, leaper->second); 
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: #else // ICL_USE_INTERVAL_TEMPLATE_TYPE
Chris@16: 
Chris@16: template<class SegmentIteratorT, ICL_INTERVAL(ICL_COMPARE) Interval>
Chris@16: struct segment_adapter 
Chris@16: {
Chris@16:     typedef segment_adapter                          type;
Chris@16:     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type;
Chris@16:     typedef segment_type                             interval_type;
Chris@16:     typedef typename interval_traits<interval_type>::domain_type domain_type;
Chris@16:     typedef domain_type                              codomain_type;
Chris@16:     typedef domain_type                              element_type;
Chris@16:     typedef domain_type&                             transit_type;
Chris@16:     typedef typename difference_type_of<interval_traits<interval_type> >::type 
Chris@16:                                                      domain_difference_type;
Chris@16: 
Chris@16:     static domain_type     first (const SegmentIteratorT& leaper){ return leaper->first(); } 
Chris@16:     static domain_type     last  (const SegmentIteratorT& leaper){ return leaper->last();  } 
Chris@16:     static domain_difference_type length(const SegmentIteratorT& leaper){ return icl::length(*leaper);}
Chris@16: 
Chris@16:     static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper, 
Chris@16:                                           const domain_difference_type& sneaker)
Chris@16:     { 
Chris@16:         inter_pos = is_reverse<SegmentIteratorT>::value ? icl::last(*leaper)  - sneaker
Chris@16:                                                         : icl::first(*leaper) + sneaker;
Chris@16:         return inter_pos; 
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template < class SegmentIteratorT, class CodomainT, ICL_INTERVAL(ICL_COMPARE) Interval >
Chris@16: struct segment_adapter<SegmentIteratorT, std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare)const, CodomainT> >
Chris@16: {
Chris@16:     typedef segment_adapter                                type;
Chris@16:     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare)    interval_type;
Chris@16:     typedef typename interval_traits<interval_type>::domain_type domain_type;
Chris@16:     typedef CodomainT                                      codomain_type;
Chris@16:     typedef std::pair<domain_type, codomain_type>          element_type;
Chris@16:     typedef mapped_reference<domain_type, CodomainT>       transit_type;    
Chris@16:     typedef typename difference_type_of<interval_traits<interval_type> >::type 
Chris@16:                                                            domain_difference_type;
Chris@16: 
Chris@16:     static domain_type     first (const SegmentIteratorT& leaper){ return leaper->first.first(); } 
Chris@16:     static domain_type     last  (const SegmentIteratorT& leaper){ return leaper->first.last();  } 
Chris@16:     static domain_difference_type length(const SegmentIteratorT& leaper){ return icl::length(leaper->first);}
Chris@16: 
Chris@16:     static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper,
Chris@16:                                           const domain_difference_type& sneaker)
Chris@16:     {
Chris@16:         inter_pos = is_reverse<SegmentIteratorT>::value ? icl::last(leaper->first)  - sneaker
Chris@16:                                                         : icl::first(leaper->first) + sneaker;
Chris@16:         return transit_type(inter_pos, leaper->second); 
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: #endif // ICL_USE_INTERVAL_TEMPLATE_TEMPLATE
Chris@16: 
Chris@16: template <class SegmentIteratorT>
Chris@16: class element_iterator
Chris@16:   : public boost::iterator_facade<
Chris@16:           element_iterator<SegmentIteratorT>
Chris@16:         , typename elemental<typename SegmentIteratorT::value_type>::transit_type
Chris@16:         , boost::bidirectional_traversal_tag
Chris@16:         , typename elemental<typename SegmentIteratorT::value_type>::transit_type
Chris@16:     >
Chris@16: {
Chris@16: public:
Chris@16:     typedef element_iterator                                type;
Chris@16:     typedef SegmentIteratorT                                segment_iterator;
Chris@16:     typedef typename SegmentIteratorT::value_type           segment_type;
Chris@16:     typedef typename first_element<segment_type>::type      interval_type;
Chris@16:     typedef typename elemental<segment_type>::type          element_type;
Chris@16:     typedef typename elemental<segment_type>::domain_type   domain_type;
Chris@16:     typedef typename elemental<segment_type>::codomain_type codomain_type;
Chris@16:     typedef typename elemental<segment_type>::transit_type  transit_type;
Chris@16:     typedef transit_type                                    value_type;
Chris@16:     typedef typename difference_type_of<interval_traits<interval_type> >::type 
Chris@16:                                                             domain_difference_type;
Chris@16: 
Chris@16: private:
Chris@16:     typedef typename segment_adapter<segment_iterator,segment_type>::type adapt;
Chris@16: 
Chris@16:     struct enabler{};
Chris@16: 
Chris@16: public:
Chris@16:     element_iterator()
Chris@16:         : _saltator(identity_element<segment_iterator>::value())
Chris@16:         , _reptator(identity_element<domain_difference_type>::value()){}
Chris@16: 
Chris@16:     explicit element_iterator(segment_iterator jumper)
Chris@16:         : _saltator(jumper), _reptator(identity_element<domain_difference_type>::value()) {}
Chris@16: 
Chris@16:     template <class SaltatorT>
Chris@16:     element_iterator
Chris@16:         ( element_iterator<SaltatorT> const& other
Chris@16:         , typename enable_if<boost::is_convertible<SaltatorT*,SegmentIteratorT*>, enabler>::type = enabler())
Chris@16:         : _saltator(other._saltator), _reptator(other._reptator) {}
Chris@16: 
Chris@16: private:
Chris@16:     friend class boost::iterator_core_access;
Chris@16:     template <class> friend class element_iterator;
Chris@16: 
Chris@16:     template <class SaltatorT>
Chris@16:     bool equal(element_iterator<SaltatorT> const& other) const
Chris@16:     {
Chris@16:         return this->_saltator == other._saltator
Chris@16:             && this->_reptator == other._reptator;
Chris@16:     }
Chris@16: 
Chris@16:     void increment()
Chris@16:     { 
Chris@16:         if(_reptator < icl::pred(adapt::length(_saltator)))
Chris@16:             ++_reptator; 
Chris@16:         else
Chris@16:         {
Chris@16:             ++_saltator;
Chris@16:             _reptator = identity_element<domain_difference_type>::value();
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void decrement()
Chris@16:     { 
Chris@16:         if(identity_element<domain_difference_type>::value() < _reptator)
Chris@16:             --_reptator; 
Chris@16:         else
Chris@16:         {
Chris@16:             --_saltator;
Chris@16:             _reptator = adapt::length(_saltator);
Chris@16:             --_reptator;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     value_type dereference()const
Chris@16:     {
Chris@16:         return adapt::transient_element(_inter_pos, _saltator, _reptator);
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     segment_iterator               _saltator;  // satltare: to jump  : the fast moving iterator
Chris@16:     mutable domain_difference_type _reptator;  // reptare:  to sneak : the slow moving iterator 0 based
Chris@16:     mutable domain_type            _inter_pos; // inter position : Position within the current segment
Chris@16:                                                // _saltator->first.first() <= _inter_pos <= _saltator->first.last() 
Chris@16: };
Chris@16: 
Chris@16: }} // namespace icl boost
Chris@16: 
Chris@16: #endif // BOOST_ICL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104
Chris@16: 
Chris@16: 
Chris@16: