1// (C) Copyright Jeremy Siek 2002.
2// Distributed under the Boost Software License, Version 1.0. (See
3// accompanying file LICENSE_1_0.txt or copy at
4// http://www.boost.org/LICENSE_1_0.txt)
5
6#ifndef BOOST_ITERATOR_CONCEPTS_HPP
7#define BOOST_ITERATOR_CONCEPTS_HPP
8
9#include <boost/concept_check.hpp>
10#include <boost/iterator/iterator_categories.hpp>
11
12#include <boost/type_traits/is_same.hpp>
13#include <boost/type_traits/is_integral.hpp>
14
15#include <boost/mpl/bool.hpp>
16#include <boost/mpl/if.hpp>
17#include <boost/mpl/and.hpp>
18#include <boost/mpl/or.hpp>
19
20#include <boost/static_assert.hpp>
21
22// Use boost/limits to work around missing limits headers on some compilers
23#include <boost/limits.hpp>
24#include <boost/config.hpp>
25
26#include <algorithm>
27#include <iterator>
28
29#include <boost/concept/detail/concept_def.hpp>
30
31namespace boost_concepts
32{
33 // Used a different namespace here (instead of "boost") so that the
34 // concept descriptions do not take for granted the names in
35 // namespace boost.
36
37 //===========================================================================
38 // Iterator Access Concepts
39
40 BOOST_concept(ReadableIterator,(Iterator))
41 : boost::Assignable<Iterator>
42 , boost::CopyConstructible<Iterator>
43
44 {
45 typedef BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::value_type value_type;
46 typedef BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::reference reference;
47
48 BOOST_CONCEPT_USAGE(ReadableIterator)
49 {
50
51 value_type v = *i;
52 boost::ignore_unused_variable_warning(v);
53 }
54 private:
55 Iterator i;
56 };
57
58 template <
59 typename Iterator
60 , typename ValueType = BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::value_type
61 >
62 struct WritableIterator
63 : boost::CopyConstructible<Iterator>
64 {
65 BOOST_CONCEPT_USAGE(WritableIterator)
66 {
67 *i = v;
68 }
69 private:
70 ValueType v;
71 Iterator i;
72 };
73
74 template <
75 typename Iterator
76 , typename ValueType = BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::value_type
77 >
78 struct WritableIteratorConcept : WritableIterator<Iterator,ValueType> {};
79
80 BOOST_concept(SwappableIterator,(Iterator))
81 {
82 BOOST_CONCEPT_USAGE(SwappableIterator)
83 {
84 std::iter_swap(i1, i2);
85 }
86 private:
87 Iterator i1;
88 Iterator i2;
89 };
90
91 BOOST_concept(LvalueIterator,(Iterator))
92 {
93 typedef typename std::iterator_traits<Iterator>::value_type value_type;
94
95 BOOST_CONCEPT_USAGE(LvalueIterator)
96 {
97 value_type& r = const_cast<value_type&>(*i);
98 boost::ignore_unused_variable_warning(r);
99 }
100 private:
101 Iterator i;
102 };
103
104
105 //===========================================================================
106 // Iterator Traversal Concepts
107
108 BOOST_concept(IncrementableIterator,(Iterator))
109 : boost::Assignable<Iterator>
110 , boost::CopyConstructible<Iterator>
111 {
112 typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
113
114 BOOST_CONCEPT_ASSERT((
115 boost::Convertible<
116 traversal_category
117 , boost::incrementable_traversal_tag
118 >));
119
120 BOOST_CONCEPT_USAGE(IncrementableIterator)
121 {
122 ++i;
123 (void)i++;
124 }
125 private:
126 Iterator i;
127 };
128
129 BOOST_concept(SinglePassIterator,(Iterator))
130 : IncrementableIterator<Iterator>
131 , boost::EqualityComparable<Iterator>
132
133 {
134 BOOST_CONCEPT_ASSERT((
135 boost::Convertible<
136 BOOST_DEDUCED_TYPENAME SinglePassIterator::traversal_category
137 , boost::single_pass_traversal_tag
138 > ));
139 };
140
141 BOOST_concept(ForwardTraversal,(Iterator))
142 : SinglePassIterator<Iterator>
143 , boost::DefaultConstructible<Iterator>
144 {
145 typedef typename std::iterator_traits<Iterator>::difference_type difference_type;
146
147 BOOST_MPL_ASSERT((boost::is_integral<difference_type>));
148 BOOST_MPL_ASSERT_RELATION(std::numeric_limits<difference_type>::is_signed, ==, true);
149
150 BOOST_CONCEPT_ASSERT((
151 boost::Convertible<
152 BOOST_DEDUCED_TYPENAME ForwardTraversal::traversal_category
153 , boost::forward_traversal_tag
154 > ));
155 };
156
157 BOOST_concept(BidirectionalTraversal,(Iterator))
158 : ForwardTraversal<Iterator>
159 {
160 BOOST_CONCEPT_ASSERT((
161 boost::Convertible<
162 BOOST_DEDUCED_TYPENAME BidirectionalTraversal::traversal_category
163 , boost::bidirectional_traversal_tag
164 > ));
165
166 BOOST_CONCEPT_USAGE(BidirectionalTraversal)
167 {
168 --i;
169 (void)i--;
170 }
171 private:
172 Iterator i;
173 };
174
175 BOOST_concept(RandomAccessTraversal,(Iterator))
176 : BidirectionalTraversal<Iterator>
177 {
178 BOOST_CONCEPT_ASSERT((
179 boost::Convertible<
180 BOOST_DEDUCED_TYPENAME RandomAccessTraversal::traversal_category
181 , boost::random_access_traversal_tag
182 > ));
183
184 BOOST_CONCEPT_USAGE(RandomAccessTraversal)
185 {
186 i += n;
187 i = i + n;
188 i = n + i;
189 i -= n;
190 i = i - n;
191 n = i - j;
192 }
193
194 private:
195 typename BidirectionalTraversal<Iterator>::difference_type n;
196 Iterator i, j;
197 };
198
199 //===========================================================================
200 // Iterator Interoperability
201
202 namespace detail
203 {
204 template <typename Iterator1, typename Iterator2>
205 void interop_single_pass_constraints(Iterator1 const& i1, Iterator2 const& i2)
206 {
207 bool b;
208 b = i1 == i2;
209 b = i1 != i2;
210
211 b = i2 == i1;
212 b = i2 != i1;
213 boost::ignore_unused_variable_warning(b);
214 }
215
216 template <typename Iterator1, typename Iterator2>
217 void interop_rand_access_constraints(
218 Iterator1 const& i1, Iterator2 const& i2,
219 boost::random_access_traversal_tag, boost::random_access_traversal_tag)
220 {
221 bool b;
222 typename std::iterator_traits<Iterator2>::difference_type n;
223 b = i1 < i2;
224 b = i1 <= i2;
225 b = i1 > i2;
226 b = i1 >= i2;
227 n = i1 - i2;
228
229 b = i2 < i1;
230 b = i2 <= i1;
231 b = i2 > i1;
232 b = i2 >= i1;
233 n = i2 - i1;
234 boost::ignore_unused_variable_warning(b);
235 boost::ignore_unused_variable_warning(n);
236 }
237
238 template <typename Iterator1, typename Iterator2>
239 void interop_rand_access_constraints(
240 Iterator1 const&, Iterator2 const&,
241 boost::single_pass_traversal_tag, boost::single_pass_traversal_tag)
242 { }
243
244 } // namespace detail
245
246 BOOST_concept(InteroperableIterator,(Iterator)(ConstIterator))
247 {
248 private:
249 typedef typename boost::iterators::pure_iterator_traversal<Iterator>::type traversal_category;
250 typedef typename boost::iterators::pure_iterator_traversal<ConstIterator>::type const_traversal_category;
251
252 public:
253 BOOST_CONCEPT_ASSERT((SinglePassIterator<Iterator>));
254 BOOST_CONCEPT_ASSERT((SinglePassIterator<ConstIterator>));
255
256 BOOST_CONCEPT_USAGE(InteroperableIterator)
257 {
258 detail::interop_single_pass_constraints(i, ci);
259 detail::interop_rand_access_constraints(i, ci, traversal_category(), const_traversal_category());
260
261 ci = i;
262 }
263
264 private:
265 Iterator i;
266 ConstIterator ci;
267 };
268
269} // namespace boost_concepts
270
271#include <boost/concept/detail/concept_undef.hpp>
272
273#endif // BOOST_ITERATOR_CONCEPTS_HPP
274