intrusive/detail/iterator.hpp

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga  2014-2014
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/intrusive for documentation.
0010 //
0011 /////////////////////////////////////////////////////////////////////////////
0012
0013 #ifndef BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP
0014 #define BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP
0015
0016 #ifndef BOOST_CONFIG_HPP
0017 #  include <boost/config.hpp>
0018 #endif
0019
0020 #if defined(BOOST_HAS_PRAGMA_ONCE)
0021 #  pragma once
0022 #endif
0023
0024 #include <cstddef>
0025 #include <boost/intrusive/detail/std_fwd.hpp>
0026 #include <boost/intrusive/detail/workaround.hpp>
0027 #include <boost/move/detail/iterator_traits.hpp>
0028 #include <boost/move/detail/meta_utils_core.hpp>
0029
0030 namespace boost{
0031 namespace iterators{
0032
0033 struct incrementable_traversal_tag;
0034 struct single_pass_traversal_tag;
0035 struct forward_traversal_tag;
0036 struct bidirectional_traversal_tag;
0037 struct random_access_traversal_tag;
0038
0039 namespace detail{
0040
0041 template <class Category, class Traversal>
0042 struct iterator_category_with_traversal;
0043
0044 } //namespace boost{
0045 } //namespace iterators{
0046 } //namespace detail{
0047
0048 namespace boost {
0049 namespace intrusive {
0050
0051 using boost::movelib::iterator_traits;
0052 using boost::movelib::iter_difference;
0053 using boost::movelib::iter_value;
0054 using boost::movelib::iter_category;
0055 using boost::movelib::iter_size;
0056
0057
0058 ////////////////////
0059 //    iterator
0060 ////////////////////
0061 template<class Category, class T, class Difference, class Pointer, class Reference>
0062 struct iterator
0063 {
0064    typedef Category     iterator_category;
0065    typedef T            value_type;
0066    typedef Difference   difference_type;
0067    typedef Pointer      pointer;
0068    typedef Reference    reference;
0069 };
0070
0071 ////////////////////////////////////////////////////////////////////////////////
0072 //    Conversion from boost::iterator traversals to std tags
0073 ////////////////////////////////////////////////////////////////////////////////
0074
0075 template<class Tag>
0076 struct get_std_category_from_tag
0077 {
0078    typedef Tag type;
0079 };
0080
0081 template <class Category>
0082 struct get_std_category_from_tag
0083    <boost::iterators::detail::iterator_category_with_traversal
0084       <Category, boost::iterators::incrementable_traversal_tag> >
0085 {
0086    typedef std::input_iterator_tag type;
0087 };
0088
0089 template <class Category>
0090 struct get_std_category_from_tag
0091    <boost::iterators::detail::iterator_category_with_traversal
0092       <Category, boost::iterators::single_pass_traversal_tag> >
0093 {
0094    typedef std::input_iterator_tag type;
0095 };
0096
0097 template <class Category>
0098 struct get_std_category_from_tag
0099    <boost::iterators::detail::iterator_category_with_traversal
0100       <Category, boost::iterators::forward_traversal_tag> >
0101 {
0102    typedef std::input_iterator_tag type;
0103 };
0104
0105 template <class Category>
0106 struct get_std_category_from_tag
0107    <boost::iterators::detail::iterator_category_with_traversal
0108       <Category, boost::iterators::bidirectional_traversal_tag> >
0109 {
0110    typedef std::bidirectional_iterator_tag type;
0111 };
0112
0113 template <class Category>
0114 struct get_std_category_from_tag
0115    <boost::iterators::detail::iterator_category_with_traversal
0116       <Category, boost::iterators::random_access_traversal_tag> >
0117 {
0118    typedef std::random_access_iterator_tag type;
0119 };
0120
0121 template<class It>
0122 struct get_std_category_from_it
0123    : get_std_category_from_tag< typename boost::intrusive::iter_category<It>::type >
0124 {};
0125
0126 ////////////////////////////////////////
0127 //    iterator_[dis|en]able_if_tag
0128 ////////////////////////////////////////
0129 template<class I, class Tag, class R = void>
0130 struct iterator_enable_if_tag
0131    : ::boost::move_detail::enable_if_c
0132       < ::boost::move_detail::is_same
0133          < typename get_std_category_from_it<I>::type
0134          , Tag
0135          >::value
0136          , R>
0137 {};
0138
0139 template<class I, class Tag, class R = void>
0140 struct iterator_disable_if_tag
0141    : ::boost::move_detail::enable_if_c
0142       < !::boost::move_detail::is_same
0143          < typename get_std_category_from_it<I>::type
0144          , Tag
0145          >::value
0146          , R>
0147 {};
0148
0149 ////////////////////////////////////////
0150 //    iterator_[dis|en]able_if_tag
0151 ////////////////////////////////////////
0152 template<class I, class Tag, class Tag2, class R = void>
0153 struct iterator_enable_if_convertible_tag
0154    : ::boost::move_detail::enable_if_c
0155       < ::boost::move_detail::is_same_or_convertible
0156          < typename get_std_category_from_it<I>::type
0157          , Tag
0158          >::value &&
0159         !::boost::move_detail::is_same_or_convertible
0160          < typename get_std_category_from_it<I>::type
0161          , Tag2
0162          >::value
0163          , R>
0164 {};
0165
0166 ////////////////////////////////////////
0167 //    iterator_[dis|en]able_if_tag_difference_type
0168 ////////////////////////////////////////
0169 template<class I, class Tag>
0170 struct iterator_enable_if_tag_difference_type
0171    : iterator_enable_if_tag<I, Tag, typename boost::intrusive::iter_difference<I>::type>
0172 {};
0173
0174 template<class I, class Tag>
0175 struct iterator_disable_if_tag_difference_type
0176    : iterator_disable_if_tag<I, Tag, typename boost::intrusive::iter_difference<I>::type>
0177 {};
0178
0179 ////////////////////
0180 //    advance
0181 ////////////////////
0182
0183 template<class InputIt>
0184 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::input_iterator_tag>::type
0185    iterator_advance(InputIt& it, typename iter_difference<InputIt>::type n)
0186 {
0187    while(n--)
0188       ++it;
0189 }
0190
0191 template<class InputIt>
0192 typename iterator_enable_if_tag<InputIt, std::forward_iterator_tag>::type
0193    iterator_advance(InputIt& it, typename iter_difference<InputIt>::type n)
0194 {
0195    while(n--)
0196       ++it;
0197 }
0198
0199 template<class InputIt>
0200 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::bidirectional_iterator_tag>::type
0201    iterator_advance(InputIt& it, typename iter_difference<InputIt>::type n)
0202 {
0203    for (; 0 < n; --n)
0204       ++it;
0205    for (; n < 0; ++n)
0206       --it;
0207 }
0208
0209 template<class InputIt, class Distance>
0210 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::random_access_iterator_tag>::type
0211    iterator_advance(InputIt& it, Distance n)
0212 {
0213    it += n;
0214 }
0215
0216 template<class InputIt, class Distance>
0217 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::random_access_iterator_tag, InputIt>::type
0218    make_iterator_advance(InputIt it, Distance n)
0219 {
0220    (iterator_advance)(it, n);
0221    return it;
0222 }
0223
0224 template<class It>
0225 BOOST_INTRUSIVE_FORCEINLINE
0226    void iterator_uadvance(It& it, typename iter_size<It>::type n)
0227 {
0228    (iterator_advance)(it, (typename iterator_traits<It>::difference_type)n);
0229 }
0230
0231 template<class It>
0232 BOOST_INTRUSIVE_FORCEINLINE
0233 It make_iterator_uadvance(It it, typename iter_size<It>::type n)
0234 {
0235    (iterator_uadvance)(it, n);
0236    return it;
0237 }
0238
0239 ////////////////////////////////////////
0240 //    iterator_distance
0241 ////////////////////////////////////////
0242 template<class InputIt> inline
0243 typename iterator_disable_if_tag_difference_type
0244    <InputIt, std::random_access_iterator_tag>::type
0245       iterator_distance(InputIt first, InputIt last)
0246 {
0247    typename iter_difference<InputIt>::type off = 0;
0248    while(first != last){
0249       ++off;
0250       ++first;
0251    }
0252    return off;
0253 }
0254
0255 template<class InputIt>
0256 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag_difference_type
0257    <InputIt, std::random_access_iterator_tag>::type
0258       iterator_distance(InputIt first, InputIt last)
0259 {
0260    typename iter_difference<InputIt>::type off = last - first;
0261    return off;
0262 }
0263
0264 ////////////////////////////////////////
0265 //    iterator_udistance
0266 ////////////////////////////////////////
0267
0268 template<class It>
0269 BOOST_INTRUSIVE_FORCEINLINE typename iter_size<It>::type
0270    iterator_udistance(It first, It last)
0271 {
0272    return (typename iter_size<It>::type)(iterator_distance)(first, last);
0273 }
0274
0275 ////////////////////////////////////////
0276 //    iterator_next
0277 ////////////////////////////////////////
0278
0279 template<class InputIt>
0280 BOOST_INTRUSIVE_FORCEINLINE InputIt iterator_next(InputIt it, typename iter_difference<InputIt>::type n)
0281 {
0282    (iterator_advance)(it, n);
0283    return it;
0284 }
0285
0286 template<class InputIt>
0287 BOOST_INTRUSIVE_FORCEINLINE InputIt iterator_unext(InputIt it, typename iterator_traits<InputIt>::size_type n)
0288 {
0289    (iterator_uadvance)(it, n);
0290    return it;
0291 }
0292
0293 ////////////////////////////////////////
0294 // iterator_arrow_result
0295 ////////////////////////////////////////
0296
0297 template<class I>
0298 BOOST_INTRUSIVE_FORCEINLINE typename iterator_traits<I>::pointer iterator_arrow_result(const I &i)
0299 {  return i.operator->();  }
0300
0301 template<class T>
0302 BOOST_INTRUSIVE_FORCEINLINE T * iterator_arrow_result(T *p)
0303 {  return p;   }
0304
0305 } //namespace intrusive
0306 } //namespace boost
0307
0308 #endif //BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP