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 boost::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 boost_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 boost. 38 39 //=========================================================================== 40 // Iterator Access Concepts 41 42 BOOST_concept(ReadableIterator,(Iterator)) 43 : boost::Assignable<Iterator> 44 , boost::CopyConstructible<Iterator> 45 46 { 47 typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type value_type; 48 typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::reference reference; 49 50 BOOST_CONCEPT_USAGE(ReadableIterator) 51 { 52 53 value_type v = *i; 54 boost::ignore_unused_variable_warning(v); 55 } 56 private: 57 Iterator i; 58 }; 59 60 template < 61 typename Iterator 62 , typename ValueType = BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type 63 > 64 struct WritableIterator 65 : boost::CopyConstructible<Iterator> 66 { 67 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 boost::detail::iterator_traits<Iterator>::value_type 79 > 80 struct WritableIteratorConcept : WritableIterator<Iterator,ValueType> {}; 81 82 BOOST_concept(SwappableIterator,(Iterator)) 83 { 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 boost::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 boost::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 : boost::Assignable<Iterator> 112 , boost::CopyConstructible<Iterator> 113 { 114 typedef typename boost::iterator_traversal<Iterator>::type traversal_category; 115 116 BOOST_CONCEPT_ASSERT(( 117 boost::Convertible< 118 traversal_category 119 , boost::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 , boost::EqualityComparable<Iterator> 134 135 { 136 BOOST_CONCEPT_ASSERT(( 137 boost::Convertible< 138 BOOST_DEDUCED_TYPENAME SinglePassIterator::traversal_category 139 , boost::single_pass_traversal_tag 140 > )); 141 }; 142 143 BOOST_concept(ForwardTraversal,(Iterator)) 144 : SinglePassIterator<Iterator> 145 , boost::DefaultConstructible<Iterator> 146 { 147 typedef typename boost::detail::iterator_traits<Iterator>::difference_type difference_type; 148 149 BOOST_MPL_ASSERT((boost::is_integral<difference_type>)); 150 BOOST_MPL_ASSERT_RELATION(std::numeric_limits<difference_type>::is_signed, ==, true); 151 152 BOOST_CONCEPT_ASSERT(( 153 boost::Convertible< 154 BOOST_DEDUCED_TYPENAME ForwardTraversal::traversal_category 155 , boost::forward_traversal_tag 156 > )); 157 }; 158 159 BOOST_concept(BidirectionalTraversal,(Iterator)) 160 : ForwardTraversal<Iterator> 161 { 162 BOOST_CONCEPT_ASSERT(( 163 boost::Convertible< 164 BOOST_DEDUCED_TYPENAME BidirectionalTraversal::traversal_category 165 , boost::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 boost::Convertible< 182 BOOST_DEDUCED_TYPENAME RandomAccessTraversal::traversal_category 183 , boost::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 boost::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 boost::random_access_traversal_tag, boost::random_access_traversal_tag) 222 { 223 bool b; 224 typename boost::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 boost::ignore_unused_variable_warning(b); 237 boost::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 boost::single_pass_traversal_tag, boost::single_pass_traversal_tag) 244 { } 245 246 } // namespace detail 247 248 BOOST_concept(InteroperableIterator,(Iterator)(ConstIterator)) 249 { 250 private: 251 typedef typename boost::detail::pure_traversal_tag< 252 typename boost::iterator_traversal< 253 Iterator 254 >::type 255 >::type traversal_category; 256 257 typedef typename boost::detail::pure_traversal_tag< 258 typename boost::iterator_traversal< 259 ConstIterator 260 >::type 261 >::type const_traversal_category; 262 263 public: 264 BOOST_CONCEPT_ASSERT((SinglePassIterator<Iterator>)); 265 BOOST_CONCEPT_ASSERT((SinglePassIterator<ConstIterator>)); 266 267 BOOST_CONCEPT_USAGE(InteroperableIterator) 268 { 269 detail::interop_single_pass_constraints(i, ci); 270 detail::interop_rand_access_constraints(i, ci, traversal_category(), const_traversal_category()); 271 272 ci = i; 273 } 274 275 private: 276 Iterator i; 277 ConstIterator ci; 278 }; 279 280 } // namespace boost_concepts 281 282 #include <boost/concept/detail/concept_undef.hpp> 283 284 #endif // BOOST_ITERATOR_CONCEPTS_HPP 285
