boost/iterator/iterator_concepts.hpp

   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