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