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 
31 namespace 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 
BOOST_CONCEPT_USAGE(ReadableIterator)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   {
BOOST_CONCEPT_USAGEboost_concepts::WritableIterator65       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   {
BOOST_CONCEPT_USAGE(SwappableIterator)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