icl/detail/element_iterator.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2009-2009: Joachim Faulhaber
0003 +------------------------------------------------------------------------------+
0004    Distributed under the Boost Software License, Version 1.0.
0005       (See accompanying file LICENCE.txt or copy at
0006            http://www.boost.org/LICENSE_1_0.txt)
0007 +-----------------------------------------------------------------------------*/
0008 #ifndef BOOST_ICL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104
0009 #define BOOST_ICL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104
0010
0011 #include <boost/mpl/if.hpp>
0012 #include <boost/iterator/iterator_facade.hpp>
0013 #include <boost/icl/type_traits/succ_pred.hpp>
0014 #include <boost/icl/detail/mapped_reference.hpp>
0015
0016 namespace boost{namespace icl
0017 {
0018
0019 //------------------------------------------------------------------------------
0020 template<class Type>
0021 struct is_std_pair
0022 {
0023     typedef is_std_pair<Type> type;
0024     BOOST_STATIC_CONSTANT(bool, value = false);
0025 };
0026
0027 template<class FirstT, class SecondT>
0028 struct is_std_pair<std::pair<FirstT, SecondT> >
0029 {
0030     typedef is_std_pair<std::pair<FirstT, SecondT> > type;
0031     BOOST_STATIC_CONSTANT(bool, value = true);
0032 };
0033
0034
0035 //------------------------------------------------------------------------------
0036 template<class Type>
0037 struct first_element
0038 {
0039     typedef Type type;
0040 };
0041
0042 template<class FirstT, class SecondT>
0043 struct first_element<std::pair<FirstT, SecondT> >
0044 {
0045     typedef FirstT type;
0046 };
0047
0048 //------------------------------------------------------------------------------
0049 template <class SegmentIteratorT> class element_iterator;
0050
0051 template<class IteratorT>
0052 struct is_reverse
0053 {
0054     typedef is_reverse type;
0055     BOOST_STATIC_CONSTANT(bool, value = false);
0056 };
0057
0058 template<class BaseIteratorT>
0059 struct is_reverse<std::reverse_iterator<BaseIteratorT> >
0060 {
0061     typedef is_reverse<std::reverse_iterator<BaseIteratorT> > type;
0062     BOOST_STATIC_CONSTANT(bool, value = true);
0063 };
0064
0065 template<class BaseIteratorT>
0066 struct is_reverse<icl::element_iterator<BaseIteratorT> >
0067 {
0068     typedef is_reverse<icl::element_iterator<BaseIteratorT> > type;
0069     BOOST_STATIC_CONSTANT(bool, value = is_reverse<BaseIteratorT>::value);
0070 };
0071
0072 //------------------------------------------------------------------------------
0073 template<class SegmentT>
0074 struct elemental;
0075
0076 #ifdef ICL_USE_INTERVAL_TEMPLATE_TEMPLATE
0077
0078     template<class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval>
0079     struct elemental<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) >
0080     {
0081         typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type;
0082         typedef segment_type              interval_type;
0083         typedef DomainT                   type;
0084         typedef DomainT                   domain_type;
0085         typedef DomainT                   codomain_type;
0086         typedef DomainT                   transit_type;
0087     };
0088
0089     template< class DomainT, class CodomainT,
0090               ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval >
0091     struct elemental<std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) const, CodomainT> >
0092     {
0093         typedef std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare), CodomainT> segment_type;
0094         typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare)                       interval_type;
0095         typedef std::pair<DomainT, CodomainT>                   type;
0096         typedef DomainT                                         domain_type;
0097         typedef CodomainT                                       codomain_type;
0098         typedef mapped_reference<DomainT, CodomainT>            transit_type;
0099     };
0100
0101 #else //ICL_USE_INTERVAL_TEMPLATE_TYPE
0102
0103     template<ICL_INTERVAL(ICL_COMPARE) Interval>
0104     struct elemental
0105     {
0106         typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type;
0107         typedef segment_type                        interval_type;
0108         typedef typename interval_traits<interval_type>::domain_type domain_type;
0109         typedef domain_type                         type;
0110         typedef domain_type                         codomain_type;
0111         typedef domain_type                         transit_type;
0112     };
0113
0114     template< class CodomainT, ICL_INTERVAL(ICL_COMPARE) Interval >
0115     struct elemental<std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) const, CodomainT> >
0116     {
0117         typedef std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare), CodomainT> segment_type;
0118         typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare)                       interval_type;
0119         typedef typename interval_traits<interval_type>::domain_type domain_type;
0120         typedef CodomainT                                       codomain_type;
0121         typedef std::pair<domain_type, codomain_type>           type;
0122         typedef mapped_reference<domain_type, codomain_type>    transit_type;
0123     };
0124
0125 #endif //ICL_USE_INTERVAL_TEMPLATE_TEMPLATE
0126
0127
0128 //------------------------------------------------------------------------------
0129 //- struct segment_adapter
0130 //------------------------------------------------------------------------------
0131 template<class SegmentIteratorT, class SegmentT>
0132 struct segment_adapter;
0133
0134 #ifdef ICL_USE_INTERVAL_TEMPLATE_TEMPLATE
0135
0136 template<class SegmentIteratorT, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval>
0137 struct segment_adapter<SegmentIteratorT, ICL_INTERVAL_TYPE(Interval,DomainT,Compare) >
0138 {
0139     typedef segment_adapter                         type;
0140     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type;
0141     typedef segment_type                            interval_type;
0142     typedef typename interval_type::difference_type domain_difference_type;
0143     typedef DomainT                                 domain_type;
0144     typedef DomainT                                 codomain_type;
0145     typedef domain_type                             element_type;
0146     typedef domain_type&                            transit_type;
0147
0148     static domain_type     first (const SegmentIteratorT& leaper){ return leaper->first(); }
0149     static domain_type     last  (const SegmentIteratorT& leaper){ return leaper->last();  }
0150     static domain_difference_type length(const SegmentIteratorT& leaper){ return leaper->length();}
0151
0152     static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper,
0153                                           const domain_difference_type& sneaker)
0154     {
0155         inter_pos = is_reverse<SegmentIteratorT>::value ? leaper->last()  - sneaker
0156                                                         : leaper->first() + sneaker;
0157         return inter_pos;
0158     }
0159 };
0160
0161 template < class SegmentIteratorT, class DomainT, class CodomainT,
0162            ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval >
0163 struct segment_adapter<SegmentIteratorT, std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) const, CodomainT> >
0164 {
0165     typedef segment_adapter                         type;
0166     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare)               interval_type;
0167     typedef DomainT                                 domain_type;
0168     typedef std::pair<DomainT, CodomainT>           element_type;
0169     typedef CodomainT                               codomain_type;
0170     typedef mapped_reference<DomainT, CodomainT>    transit_type;
0171     typedef typename difference_type_of<interval_traits<interval_type> >::type
0172                                                     domain_difference_type;
0173
0174     static domain_type     first (const SegmentIteratorT& leaper){ return leaper->first.first(); }
0175     static domain_type     last  (const SegmentIteratorT& leaper){ return leaper->first.last();  }
0176     static domain_difference_type length(const SegmentIteratorT& leaper){ return leaper->first.length();}
0177
0178     static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper,
0179                                           const domain_difference_type& sneaker)
0180     {
0181         inter_pos = is_reverse<SegmentIteratorT>::value ? leaper->first.last()  - sneaker
0182                                                         : leaper->first.first() + sneaker;
0183         return transit_type(inter_pos, leaper->second);
0184     }
0185 };
0186
0187 #else // ICL_USE_INTERVAL_TEMPLATE_TYPE
0188
0189 template<class SegmentIteratorT, ICL_INTERVAL(ICL_COMPARE) Interval>
0190 struct segment_adapter
0191 {
0192     typedef segment_adapter                          type;
0193     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type;
0194     typedef segment_type                             interval_type;
0195     typedef typename interval_traits<interval_type>::domain_type domain_type;
0196     typedef domain_type                              codomain_type;
0197     typedef domain_type                              element_type;
0198     typedef domain_type&                             transit_type;
0199     typedef typename difference_type_of<interval_traits<interval_type> >::type
0200                                                      domain_difference_type;
0201
0202     static domain_type     first (const SegmentIteratorT& leaper){ return leaper->first(); }
0203     static domain_type     last  (const SegmentIteratorT& leaper){ return leaper->last();  }
0204     static domain_difference_type length(const SegmentIteratorT& leaper){ return icl::length(*leaper);}
0205
0206     static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper,
0207                                           const domain_difference_type& sneaker)
0208     {
0209         inter_pos = is_reverse<SegmentIteratorT>::value ? icl::last(*leaper)  - sneaker
0210                                                         : icl::first(*leaper) + sneaker;
0211         return inter_pos;
0212     }
0213 };
0214
0215 template < class SegmentIteratorT, class CodomainT, ICL_INTERVAL(ICL_COMPARE) Interval >
0216 struct segment_adapter<SegmentIteratorT, std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) const, CodomainT> >
0217 {
0218     typedef segment_adapter                                type;
0219     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare)    interval_type;
0220     typedef typename interval_traits<interval_type>::domain_type domain_type;
0221     typedef CodomainT                                      codomain_type;
0222     typedef std::pair<domain_type, codomain_type>          element_type;
0223     typedef mapped_reference<domain_type, CodomainT>       transit_type;
0224     typedef typename difference_type_of<interval_traits<interval_type> >::type
0225                                                            domain_difference_type;
0226
0227     static domain_type     first (const SegmentIteratorT& leaper){ return leaper->first.first(); }
0228     static domain_type     last  (const SegmentIteratorT& leaper){ return leaper->first.last();  }
0229     static domain_difference_type length(const SegmentIteratorT& leaper){ return icl::length(leaper->first);}
0230
0231     static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper,
0232                                           const domain_difference_type& sneaker)
0233     {
0234         inter_pos = is_reverse<SegmentIteratorT>::value ? icl::last(leaper->first)  - sneaker
0235                                                         : icl::first(leaper->first) + sneaker;
0236         return transit_type(inter_pos, leaper->second);
0237     }
0238 };
0239
0240 #endif // ICL_USE_INTERVAL_TEMPLATE_TEMPLATE
0241
0242 template <class SegmentIteratorT>
0243 class element_iterator
0244   : public boost::iterator_facade<
0245           element_iterator<SegmentIteratorT>
0246         , typename elemental<typename SegmentIteratorT::value_type>::transit_type
0247         , boost::bidirectional_traversal_tag
0248         , typename elemental<typename SegmentIteratorT::value_type>::transit_type
0249     >
0250 {
0251 public:
0252     typedef element_iterator                                type;
0253     typedef SegmentIteratorT                                segment_iterator;
0254     typedef typename SegmentIteratorT::value_type           segment_type;
0255     typedef typename first_element<segment_type>::type      interval_type;
0256     typedef typename elemental<segment_type>::type          element_type;
0257     typedef typename elemental<segment_type>::domain_type   domain_type;
0258     typedef typename elemental<segment_type>::codomain_type codomain_type;
0259     typedef typename elemental<segment_type>::transit_type  transit_type;
0260     typedef transit_type                                    value_type;
0261     typedef typename difference_type_of<interval_traits<interval_type> >::type
0262                                                             domain_difference_type;
0263
0264 private:
0265     typedef typename segment_adapter<segment_iterator,segment_type>::type adapt;
0266
0267     struct enabler{};
0268
0269 public:
0270     element_iterator()
0271         : _saltator(identity_element<segment_iterator>::value())
0272         , _reptator(identity_element<domain_difference_type>::value()){}
0273
0274     explicit element_iterator(segment_iterator jumper)
0275         : _saltator(jumper), _reptator(identity_element<domain_difference_type>::value()) {}
0276
0277     template <class SaltatorT>
0278     element_iterator
0279         ( element_iterator<SaltatorT> const& other
0280         , typename enable_if<boost::is_convertible<SaltatorT*,SegmentIteratorT*>, enabler>::type = enabler())
0281         : _saltator(other._saltator), _reptator(other._reptator) {}
0282
0283 private:
0284     friend class boost::iterator_core_access;
0285     template <class> friend class element_iterator;
0286
0287     template <class SaltatorT>
0288     bool equal(element_iterator<SaltatorT> const& other) const
0289     {
0290         return this->_saltator == other._saltator
0291             && this->_reptator == other._reptator;
0292     }
0293
0294     void increment()
0295     {
0296         if(_reptator < icl::pred(adapt::length(_saltator)))
0297             ++_reptator;
0298         else
0299         {
0300             ++_saltator;
0301             _reptator = identity_element<domain_difference_type>::value();
0302         }
0303     }
0304
0305     void decrement()
0306     {
0307         if(identity_element<domain_difference_type>::value() < _reptator)
0308             --_reptator;
0309         else
0310         {
0311             --_saltator;
0312             _reptator = adapt::length(_saltator);
0313             --_reptator;
0314         }
0315     }
0316
0317     value_type dereference()const
0318     {
0319         return adapt::transient_element(_inter_pos, _saltator, _reptator);
0320     }
0321
0322 private:
0323     segment_iterator               _saltator;  // satltare: to jump  : the fast moving iterator
0324     mutable domain_difference_type _reptator;  // reptare:  to sneak : the slow moving iterator 0 based
0325     mutable domain_type            _inter_pos; // inter position : Position within the current segment
0326                                                // _saltator->first.first() <= _inter_pos <= _saltator->first.last()
0327 };
0328
0329 }} // namespace icl boost
0330
0331 #endif // BOOST_ICL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104
0332
0333
0334