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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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> |
252 | BOOST_INTRUSIVE_FORCEINLINE typename iterator_traits<I>::pointer iterator_arrow_result(const I &i) |
253 | { return i.operator->(); } |
254 | |
255 | template<class T> |
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 | |