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