boost/boost/iterator/iterator_concepts.hpp

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