1 /*-----------------------------------------------------------------------------+ 2 Copyright (c) 2009-2009: Joachim Faulhaber 3 +------------------------------------------------------------------------------+ 4 Distributed under the Boost Software License, Version 1.0. 5 (See accompanying file LICENCE.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt) 7 +-----------------------------------------------------------------------------*/ 8 #ifndef BOOST_ICL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104 9 #define BOOST_ICL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104 10 11 #include <boost/mpl/if.hpp> 12 #include <boost/iterator/iterator_facade.hpp> 13 #include <boost/config/warning_disable.hpp> 14 #include <boost/icl/type_traits/succ_pred.hpp> 15 #include <boost/icl/detail/mapped_reference.hpp> 16 17 namespace boost{namespace icl 18 { 19 20 //------------------------------------------------------------------------------ 21 template<class Type> 22 struct is_std_pair 23 { 24 typedef is_std_pair<Type> type; 25 BOOST_STATIC_CONSTANT(bool, value = false); 26 }; 27 28 template<class FirstT, class SecondT> 29 struct is_std_pair<std::pair<FirstT, SecondT> > 30 { 31 typedef is_std_pair<std::pair<FirstT, SecondT> > type; 32 BOOST_STATIC_CONSTANT(bool, value = true); 33 }; 34 35 36 //------------------------------------------------------------------------------ 37 template<class Type> 38 struct first_element 39 { 40 typedef Type type; 41 }; 42 43 template<class FirstT, class SecondT> 44 struct first_element<std::pair<FirstT, SecondT> > 45 { 46 typedef FirstT type; 47 }; 48 49 //------------------------------------------------------------------------------ 50 template <class SegmentIteratorT> class element_iterator; 51 52 template<class IteratorT> 53 struct is_reverse 54 { 55 typedef is_reverse type; 56 BOOST_STATIC_CONSTANT(bool, value = false); 57 }; 58 59 template<class BaseIteratorT> 60 struct is_reverse<std::reverse_iterator<BaseIteratorT> > 61 { 62 typedef is_reverse<std::reverse_iterator<BaseIteratorT> > type; 63 BOOST_STATIC_CONSTANT(bool, value = true); 64 }; 65 66 template<class BaseIteratorT> 67 struct is_reverse<icl::element_iterator<BaseIteratorT> > 68 { 69 typedef is_reverse<icl::element_iterator<BaseIteratorT> > type; 70 BOOST_STATIC_CONSTANT(bool, value = is_reverse<BaseIteratorT>::value); 71 }; 72 73 //------------------------------------------------------------------------------ 74 template<class SegmentT> 75 struct elemental; 76 77 #ifdef ICL_USE_INTERVAL_TEMPLATE_TEMPLATE 78 79 template<class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval> 80 struct elemental<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) > 81 { 82 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type; 83 typedef segment_type interval_type; 84 typedef DomainT type; 85 typedef DomainT domain_type; 86 typedef DomainT codomain_type; 87 typedef DomainT transit_type; 88 }; 89 90 template< class DomainT, class CodomainT, 91 ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval > 92 struct elemental<std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) const, CodomainT> > 93 { 94 typedef std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare), CodomainT> segment_type; 95 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type; 96 typedef std::pair<DomainT, CodomainT> type; 97 typedef DomainT domain_type; 98 typedef CodomainT codomain_type; 99 typedef mapped_reference<DomainT, CodomainT> transit_type; 100 }; 101 102 #else //ICL_USE_INTERVAL_TEMPLATE_TYPE 103 104 template<ICL_INTERVAL(ICL_COMPARE) Interval> 105 struct elemental 106 { 107 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type; 108 typedef segment_type interval_type; 109 typedef typename interval_traits<interval_type>::domain_type domain_type; 110 typedef domain_type type; 111 typedef domain_type codomain_type; 112 typedef domain_type transit_type; 113 }; 114 115 template< class CodomainT, ICL_INTERVAL(ICL_COMPARE) Interval > 116 struct elemental<std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) const, CodomainT> > 117 { 118 typedef std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare), CodomainT> segment_type; 119 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type; 120 typedef typename interval_traits<interval_type>::domain_type domain_type; 121 typedef CodomainT codomain_type; 122 typedef std::pair<domain_type, codomain_type> type; 123 typedef mapped_reference<domain_type, codomain_type> transit_type; 124 }; 125 126 #endif //ICL_USE_INTERVAL_TEMPLATE_TEMPLATE 127 128 129 //------------------------------------------------------------------------------ 130 //- struct segment_adapter 131 //------------------------------------------------------------------------------ 132 template<class SegmentIteratorT, class SegmentT> 133 struct segment_adapter; 134 135 #ifdef ICL_USE_INTERVAL_TEMPLATE_TEMPLATE 136 137 template<class SegmentIteratorT, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval> 138 struct segment_adapter<SegmentIteratorT, ICL_INTERVAL_TYPE(Interval,DomainT,Compare) > 139 { 140 typedef segment_adapter type; 141 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type; 142 typedef segment_type interval_type; 143 typedef typename interval_type::difference_type domain_difference_type; 144 typedef DomainT domain_type; 145 typedef DomainT codomain_type; 146 typedef domain_type element_type; 147 typedef domain_type& transit_type; 148 firstboost::icl::segment_adapter149 static domain_type first (const SegmentIteratorT& leaper){ return leaper->first(); } lastboost::icl::segment_adapter150 static domain_type last (const SegmentIteratorT& leaper){ return leaper->last(); } lengthboost::icl::segment_adapter151 static domain_difference_type length(const SegmentIteratorT& leaper){ return leaper->length();} 152 transient_elementboost::icl::segment_adapter153 static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper, 154 const domain_difference_type& sneaker) 155 { 156 inter_pos = is_reverse<SegmentIteratorT>::value ? leaper->last() - sneaker 157 : leaper->first() + sneaker; 158 return inter_pos; 159 } 160 }; 161 162 template < class SegmentIteratorT, class DomainT, class CodomainT, 163 ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval > 164 struct segment_adapter<SegmentIteratorT, std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) const, CodomainT> > 165 { 166 typedef segment_adapter type; 167 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type; 168 typedef DomainT domain_type; 169 typedef std::pair<DomainT, CodomainT> element_type; 170 typedef CodomainT codomain_type; 171 typedef mapped_reference<DomainT, CodomainT> transit_type; 172 typedef typename difference_type_of<interval_traits<interval_type> >::type 173 domain_difference_type; 174 firstboost::icl::segment_adapter175 static domain_type first (const SegmentIteratorT& leaper){ return leaper->first.first(); } lastboost::icl::segment_adapter176 static domain_type last (const SegmentIteratorT& leaper){ return leaper->first.last(); } lengthboost::icl::segment_adapter177 static domain_difference_type length(const SegmentIteratorT& leaper){ return leaper->first.length();} 178 transient_elementboost::icl::segment_adapter179 static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper, 180 const domain_difference_type& sneaker) 181 { 182 inter_pos = is_reverse<SegmentIteratorT>::value ? leaper->first.last() - sneaker 183 : leaper->first.first() + sneaker; 184 return transit_type(inter_pos, leaper->second); 185 } 186 }; 187 188 #else // ICL_USE_INTERVAL_TEMPLATE_TYPE 189 190 template<class SegmentIteratorT, ICL_INTERVAL(ICL_COMPARE) Interval> 191 struct segment_adapter 192 { 193 typedef segment_adapter type; 194 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) segment_type; 195 typedef segment_type interval_type; 196 typedef typename interval_traits<interval_type>::domain_type domain_type; 197 typedef domain_type codomain_type; 198 typedef domain_type element_type; 199 typedef domain_type& transit_type; 200 typedef typename difference_type_of<interval_traits<interval_type> >::type 201 domain_difference_type; 202 firstboost::icl::segment_adapter203 static domain_type first (const SegmentIteratorT& leaper){ return leaper->first(); } lastboost::icl::segment_adapter204 static domain_type last (const SegmentIteratorT& leaper){ return leaper->last(); } lengthboost::icl::segment_adapter205 static domain_difference_type length(const SegmentIteratorT& leaper){ return icl::length(*leaper);} 206 transient_elementboost::icl::segment_adapter207 static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper, 208 const domain_difference_type& sneaker) 209 { 210 inter_pos = is_reverse<SegmentIteratorT>::value ? icl::last(*leaper) - sneaker 211 : icl::first(*leaper) + sneaker; 212 return inter_pos; 213 } 214 }; 215 216 template < class SegmentIteratorT, class CodomainT, ICL_INTERVAL(ICL_COMPARE) Interval > 217 struct segment_adapter<SegmentIteratorT, std::pair<ICL_INTERVAL_TYPE(Interval,DomainT,Compare) const, CodomainT> > 218 { 219 typedef segment_adapter type; 220 typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type; 221 typedef typename interval_traits<interval_type>::domain_type domain_type; 222 typedef CodomainT codomain_type; 223 typedef std::pair<domain_type, codomain_type> element_type; 224 typedef mapped_reference<domain_type, CodomainT> transit_type; 225 typedef typename difference_type_of<interval_traits<interval_type> >::type 226 domain_difference_type; 227 firstboost::icl::segment_adapter228 static domain_type first (const SegmentIteratorT& leaper){ return leaper->first.first(); } lastboost::icl::segment_adapter229 static domain_type last (const SegmentIteratorT& leaper){ return leaper->first.last(); } lengthboost::icl::segment_adapter230 static domain_difference_type length(const SegmentIteratorT& leaper){ return icl::length(leaper->first);} 231 transient_elementboost::icl::segment_adapter232 static transit_type transient_element(domain_type& inter_pos, const SegmentIteratorT& leaper, 233 const domain_difference_type& sneaker) 234 { 235 inter_pos = is_reverse<SegmentIteratorT>::value ? icl::last(leaper->first) - sneaker 236 : icl::first(leaper->first) + sneaker; 237 return transit_type(inter_pos, leaper->second); 238 } 239 }; 240 241 #endif // ICL_USE_INTERVAL_TEMPLATE_TEMPLATE 242 243 template <class SegmentIteratorT> 244 class element_iterator 245 : public boost::iterator_facade< 246 element_iterator<SegmentIteratorT> 247 , typename elemental<typename SegmentIteratorT::value_type>::transit_type 248 , boost::bidirectional_traversal_tag 249 , typename elemental<typename SegmentIteratorT::value_type>::transit_type 250 > 251 { 252 public: 253 typedef element_iterator type; 254 typedef SegmentIteratorT segment_iterator; 255 typedef typename SegmentIteratorT::value_type segment_type; 256 typedef typename first_element<segment_type>::type interval_type; 257 typedef typename elemental<segment_type>::type element_type; 258 typedef typename elemental<segment_type>::domain_type domain_type; 259 typedef typename elemental<segment_type>::codomain_type codomain_type; 260 typedef typename elemental<segment_type>::transit_type transit_type; 261 typedef transit_type value_type; 262 typedef typename difference_type_of<interval_traits<interval_type> >::type 263 domain_difference_type; 264 265 private: 266 typedef typename segment_adapter<segment_iterator,segment_type>::type adapt; 267 268 struct enabler{}; 269 270 public: element_iterator()271 element_iterator() 272 : _saltator(identity_element<segment_iterator>::value()) 273 , _reptator(identity_element<domain_difference_type>::value()){} 274 element_iterator(segment_iterator jumper)275 explicit element_iterator(segment_iterator jumper) 276 : _saltator(jumper), _reptator(identity_element<domain_difference_type>::value()) {} 277 278 template <class SaltatorT> element_iterator(element_iterator<SaltatorT> const & other,typename enable_if<boost::is_convertible<SaltatorT *,SegmentIteratorT * >,enabler>::type=enabler ())279 element_iterator 280 ( element_iterator<SaltatorT> const& other 281 , typename enable_if<boost::is_convertible<SaltatorT*,SegmentIteratorT*>, enabler>::type = enabler()) 282 : _saltator(other._saltator), _reptator(other._reptator) {} 283 284 private: 285 friend class boost::iterator_core_access; 286 template <class> friend class element_iterator; 287 288 template <class SaltatorT> equal(element_iterator<SaltatorT> const & other) const289 bool equal(element_iterator<SaltatorT> const& other) const 290 { 291 return this->_saltator == other._saltator 292 && this->_reptator == other._reptator; 293 } 294 increment()295 void increment() 296 { 297 if(_reptator < icl::pred(adapt::length(_saltator))) 298 ++_reptator; 299 else 300 { 301 ++_saltator; 302 _reptator = identity_element<domain_difference_type>::value(); 303 } 304 } 305 decrement()306 void decrement() 307 { 308 if(identity_element<domain_difference_type>::value() < _reptator) 309 --_reptator; 310 else 311 { 312 --_saltator; 313 _reptator = adapt::length(_saltator); 314 --_reptator; 315 } 316 } 317 dereference() const318 value_type dereference()const 319 { 320 return adapt::transient_element(_inter_pos, _saltator, _reptator); 321 } 322 323 private: 324 segment_iterator _saltator; // satltare: to jump : the fast moving iterator 325 mutable domain_difference_type _reptator; // reptare: to sneak : the slow moving iterator 0 based 326 mutable domain_type _inter_pos; // inter position : Position within the current segment 327 // _saltator->first.first() <= _inter_pos <= _saltator->first.last() 328 }; 329 330 }} // namespace icl boost 331 332 #endif // BOOST_ICL_DETAIL_ELEMENT_ITERATOR_HPP_JOFA_091104 333 334 335 336