1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2014-2014
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //
9 // See http://www.boost.org/libs/intrusive for documentation.
10 //
11 /////////////////////////////////////////////////////////////////////////////
12
13 #ifndef BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP
14 #define BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP
15
16 #ifndef BOOST_CONFIG_HPP
17 # include <boost/config.hpp>
18 #endif
19
20 #if defined(BOOST_HAS_PRAGMA_ONCE)
21 # pragma once
22 #endif
23
24 #include <cstddef>
25 #include <boost/intrusive/detail/std_fwd.hpp>
26 #include <boost/intrusive/detail/workaround.hpp>
27 #include <boost/move/detail/iterator_traits.hpp>
28 #include <boost/move/detail/meta_utils_core.hpp>
29
30 namespace boost{
31 namespace iterators{
32
33 struct incrementable_traversal_tag;
34 struct single_pass_traversal_tag;
35 struct forward_traversal_tag;
36 struct bidirectional_traversal_tag;
37 struct random_access_traversal_tag;
38
39 namespace detail{
40
41 template <class Category, class Traversal>
42 struct iterator_category_with_traversal;
43
44 } //namespace boost{
45 } //namespace iterators{
46 } //namespace detail{
47
48 namespace boost {
49 namespace intrusive {
50
51 using boost::movelib::iterator_traits;
52
53 ////////////////////
54 // iterator
55 ////////////////////
56 template<class Category, class T, class Difference, class Pointer, class Reference>
57 struct iterator
58 {
59 typedef Category iterator_category;
60 typedef T value_type;
61 typedef Difference difference_type;
62 typedef Pointer pointer;
63 typedef Reference reference;
64 };
65
66 ////////////////////////////////////////
67 // iterator_[dis|en]able_if_boost_iterator
68 ////////////////////////////////////////
69 template<class I>
70 struct is_boost_iterator
71 {
72 static const bool value = false;
73 };
74
75 template<class Category, class Traversal>
76 struct is_boost_iterator< boost::iterators::detail::iterator_category_with_traversal<Category, Traversal> >
77 {
78 static const bool value = true;
79 };
80
81 template<class I, class R = void>
82 struct iterator_enable_if_boost_iterator
83 : ::boost::move_detail::enable_if_c
84 < is_boost_iterator<typename boost::intrusive::iterator_traits<I>::iterator_category >::value
85 , R>
86 {};
87
88 ////////////////////////////////////////
89 // iterator_[dis|en]able_if_tag
90 ////////////////////////////////////////
91 template<class I, class Tag, class R = void>
92 struct iterator_enable_if_tag
93 : ::boost::move_detail::enable_if_c
94 < ::boost::move_detail::is_same
95 < typename boost::intrusive::iterator_traits<I>::iterator_category
96 , Tag
97 >::value
98 , R>
99 {};
100
101 template<class I, class Tag, class R = void>
102 struct iterator_disable_if_tag
103 : ::boost::move_detail::enable_if_c
104 < !::boost::move_detail::is_same
105 < typename boost::intrusive::iterator_traits<I>::iterator_category
106 , Tag
107 >::value
108 , R>
109 {};
110
111 ////////////////////////////////////////
112 // iterator_[dis|en]able_if_tag
113 ////////////////////////////////////////
114 template<class I, class Tag, class Tag2, class R = void>
115 struct iterator_enable_if_convertible_tag
116 : ::boost::move_detail::enable_if_c
117 < ::boost::move_detail::is_same_or_convertible
118 < typename boost::intrusive::iterator_traits<I>::iterator_category
119 , Tag
120 >::value &&
121 !::boost::move_detail::is_same_or_convertible
122 < typename boost::intrusive::iterator_traits<I>::iterator_category
123 , Tag2
124 >::value
125 , R>
126 {};
127
128 ////////////////////////////////////////
129 // iterator_[dis|en]able_if_tag_difference_type
130 ////////////////////////////////////////
131 template<class I, class Tag>
132 struct iterator_enable_if_tag_difference_type
133 : iterator_enable_if_tag<I, Tag, typename boost::intrusive::iterator_traits<I>::difference_type>
134 {};
135
136 template<class I, class Tag>
137 struct iterator_disable_if_tag_difference_type
138 : iterator_disable_if_tag<I, Tag, typename boost::intrusive::iterator_traits<I>::difference_type>
139 {};
140
141 ////////////////////
142 // advance
143 ////////////////////
144
145 template<class InputIt, class Distance>
146 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::input_iterator_tag>::type
iterator_advance(InputIt & it,Distance n)147 iterator_advance(InputIt& it, Distance n)
148 {
149 while(n--)
150 ++it;
151 }
152
153 template<class InputIt, class Distance>
154 typename iterator_enable_if_tag<InputIt, std::forward_iterator_tag>::type
iterator_advance(InputIt & it,Distance n)155 iterator_advance(InputIt& it, Distance n)
156 {
157 while(n--)
158 ++it;
159 }
160
161 template<class InputIt, class Distance>
162 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::bidirectional_iterator_tag>::type
iterator_advance(InputIt & it,Distance n)163 iterator_advance(InputIt& it, Distance n)
164 {
165 for (; 0 < n; --n)
166 ++it;
167 for (; n < 0; ++n)
168 --it;
169 }
170
171 template<class InputIt, class Distance>
172 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::random_access_iterator_tag>::type
iterator_advance(InputIt & it,Distance n)173 iterator_advance(InputIt& it, Distance n)
174 {
175 it += n;
176 }
177
178 template<class InputIt, class Distance>
179 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag
180 <InputIt, const boost::iterators::incrementable_traversal_tag&, const boost::iterators::single_pass_traversal_tag&>::type
iterator_advance(InputIt & it,Distance n)181 iterator_advance(InputIt& it, Distance n)
182 {
183 while(n--)
184 ++it;
185 }
186
187 template<class InputIt, class Distance>
188 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag
189 <InputIt, const boost::iterators::single_pass_traversal_tag &, const boost::iterators::forward_traversal_tag&>::type
iterator_advance(InputIt & it,Distance n)190 iterator_advance(InputIt& it, Distance n)
191 {
192 while(n--)
193 ++it;
194 }
195
196 template<class InputIt, class Distance>
197 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag
198 <InputIt, const boost::iterators::forward_traversal_tag&, const boost::iterators::bidirectional_traversal_tag&>::type
iterator_advance(InputIt & it,Distance n)199 iterator_advance(InputIt& it, Distance n)
200 {
201 while(n--)
202 ++it;
203 }
204
205 template<class InputIt, class Distance>
206 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag
207 <InputIt, const boost::iterators::bidirectional_traversal_tag&, const boost::iterators::random_access_traversal_tag&>::type
iterator_advance(InputIt & it,Distance n)208 iterator_advance(InputIt& it, Distance n)
209 {
210 for (; 0 < n; --n)
211 ++it;
212 for (; n < 0; ++n)
213 --it;
214 }
215
216 class fake{};
217
218 template<class InputIt, class Distance>
219 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag
220 <InputIt, const boost::iterators::random_access_traversal_tag&, const fake&>::type
iterator_advance(InputIt & it,Distance n)221 iterator_advance(InputIt& it, Distance n)
222 {
223 it += n;
224 }
225
226 ////////////////////
227 // distance
228 ////////////////////
229 template<class InputIt> inline
230 typename iterator_disable_if_tag_difference_type
231 <InputIt, std::random_access_iterator_tag>::type
iterator_distance(InputIt first,InputIt last)232 iterator_distance(InputIt first, InputIt last)
233 {
234 typename iterator_traits<InputIt>::difference_type off = 0;
235 while(first != last){
236 ++off;
237 ++first;
238 }
239 return off;
240 }
241
242 template<class InputIt>
243 BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag_difference_type
244 <InputIt, std::random_access_iterator_tag>::type
iterator_distance(InputIt first,InputIt last)245 iterator_distance(InputIt first, InputIt last)
246 {
247 typename iterator_traits<InputIt>::difference_type off = last - first;
248 return off;
249 }
250
251 template<class I>
iterator_arrow_result(const I & i)252 BOOST_INTRUSIVE_FORCEINLINE typename iterator_traits<I>::pointer iterator_arrow_result(const I &i)
253 { return i.operator->(); }
254
255 template<class T>
iterator_arrow_result(T * p)256 BOOST_INTRUSIVE_FORCEINLINE T * iterator_arrow_result(T *p)
257 { return p; }
258
259 } //namespace intrusive
260 } //namespace boost
261
262 #endif //BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP
263