src/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 //  Revision History
  10 //  26 Apr 2003 thw
  11 //       Adapted to new iterator concepts
  12 //  22 Nov 2002 Thomas Witt
  13 //       Added interoperable concept.
  14
  15 #include <boost/concept_check.hpp>
  16 #include <boost/iterator/iterator_categories.hpp>
  17
  18 // Use boost::detail::iterator_traits to work around some MSVC/Dinkumware problems.
  19 #include <boost/detail/iterator.hpp>
  20
  21 #include <boost/type_traits/is_same.hpp>
  22 #include <boost/type_traits/is_integral.hpp>
  23 #include <boost/type_traits/is_convertible.hpp>
  24
  25 #include <boost/mpl/bool.hpp>
  26 #include <boost/mpl/if.hpp>
  27 #include <boost/mpl/and.hpp>
  28 #include <boost/mpl/or.hpp>
  29
  30 #include <boost/static_assert.hpp>
  31
  32 // Use boost/limits to work around missing limits headers on some compilers
  33 #include <boost/limits.hpp>
  34 #include <boost/config.hpp>
  35
  36 #include <algorithm>
  37
  38 namespace boost_concepts {
  39   // Used a different namespace here (instead of "boost") so that the
  40   // concept descriptions do not take for granted the names in
  41   // namespace boost.
  42
  43   // We use this in place of STATIC_ASSERT((is_convertible<...>))
  44   // because some compilers (CWPro7.x) can't detect convertibility.
  45   //
  46   // Of course, that just gets us a different error at the moment with
  47   // some tests, since new iterator category deduction still depends
  48   // on convertibility detection. We might need some specializations
  49   // to support this compiler.
  50   template <class Target, class Source>
  51   struct static_assert_base_and_derived
  52   {
  53       static_assert_base_and_derived(Target* = (Source*)0) {}
  54   };
  55
  56   //===========================================================================
  57   // Iterator Access Concepts
  58
  59   template <typename Iterator>
  60   class ReadableIteratorConcept {
  61   public:
  62     typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type value_type;
  63
  64     void constraints() {
  65       boost::function_requires< boost::AssignableConcept<Iterator> >();
  66       boost::function_requires< boost::CopyConstructibleConcept<Iterator> >();
  67
  68       value_type v = *i;
  69       boost::ignore_unused_variable_warning(v);
  70     }
  71     Iterator i;
  72   };
  73
  74   template <
  75       typename Iterator
  76     , typename ValueType = BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type
  77   >
  78   class WritableIteratorConcept {
  79   public:
  80
  81     void constraints() {
  82       boost::function_requires< boost::CopyConstructibleConcept<Iterator> >();
  83       *i = v;
  84     }
  85     ValueType v;
  86     Iterator i;
  87   };
  88
  89   template <typename Iterator>
  90   class SwappableIteratorConcept {
  91   public:
  92
  93     void constraints() {
  94       std::iter_swap(i1, i2);
  95     }
  96     Iterator i1;
  97     Iterator i2;
  98   };
  99
 100   template <typename Iterator>
 101   class LvalueIteratorConcept
 102   {
 103    public:
 104       typedef typename boost::detail::iterator_traits<Iterator>::value_type value_type;
 105       void constraints()
 106       {
 107         value_type& r = const_cast<value_type&>(*i);
 108         boost::ignore_unused_variable_warning(r);
 109       }
 110     Iterator i;
 111   };
 112
 113
 114   //===========================================================================
 115   // Iterator Traversal Concepts
 116
 117   template <typename Iterator>
 118   class IncrementableIteratorConcept {
 119   public:
 120     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
 121
 122     void constraints() {
 123       boost::function_requires< boost::AssignableConcept<Iterator> >();
 124       boost::function_requires< boost::CopyConstructibleConcept<Iterator> >();
 125
 126       BOOST_STATIC_ASSERT(
 127           (boost::is_convertible<
 128                 traversal_category
 129               , boost::incrementable_traversal_tag
 130            >::value
 131           ));
 132
 133       ++i;
 134       (void)i++;
 135     }
 136     Iterator i;
 137   };
 138
 139   template <typename Iterator>
 140   class SinglePassIteratorConcept {
 141   public:
 142     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
 143     typedef typename boost::detail::iterator_traits<Iterator>::difference_type difference_type;
 144
 145     void constraints() {
 146       boost::function_requires< IncrementableIteratorConcept<Iterator> >();
 147       boost::function_requires< boost::EqualityComparableConcept<Iterator> >();
 148
 149       BOOST_STATIC_ASSERT(
 150           (boost::is_convertible<
 151                 traversal_category
 152               , boost::single_pass_traversal_tag
 153            >::value
 154           ));
 155     }
 156   };
 157
 158   template <typename Iterator>
 159   class ForwardTraversalConcept {
 160   public:
 161     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
 162     typedef typename boost::detail::iterator_traits<Iterator>::difference_type difference_type;
 163
 164     void constraints() {
 165       boost::function_requires< SinglePassIteratorConcept<Iterator> >();
 166       boost::function_requires<
 167         boost::DefaultConstructibleConcept<Iterator> >();
 168
 169       typedef boost::mpl::and_<
 170         boost::is_integral<difference_type>,
 171         boost::mpl::bool_< std::numeric_limits<difference_type>::is_signed >
 172         > difference_type_is_signed_integral;
 173
 174       BOOST_STATIC_ASSERT(difference_type_is_signed_integral::value);
 175       BOOST_STATIC_ASSERT(
 176           (boost::is_convertible<
 177                 traversal_category
 178               , boost::forward_traversal_tag
 179            >::value
 180           ));
 181     }
 182   };
 183
 184   template <typename Iterator>
 185   class BidirectionalTraversalConcept {
 186   public:
 187     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
 188
 189     void constraints() {
 190       boost::function_requires< ForwardTraversalConcept<Iterator> >();
 191
 192       BOOST_STATIC_ASSERT(
 193           (boost::is_convertible<
 194                 traversal_category
 195               , boost::bidirectional_traversal_tag
 196            >::value
 197           ));
 198
 199       --i;
 200       (void)i--;
 201     }
 202     Iterator i;
 203   };
 204
 205   template <typename Iterator>
 206   class RandomAccessTraversalConcept {
 207   public:
 208     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
 209     typedef typename boost::detail::iterator_traits<Iterator>::difference_type
 210       difference_type;
 211
 212     void constraints() {
 213       boost::function_requires< BidirectionalTraversalConcept<Iterator> >();
 214
 215       BOOST_STATIC_ASSERT(
 216           (boost::is_convertible<
 217                 traversal_category
 218               , boost::random_access_traversal_tag
 219            >::value
 220           ));
 221
 222       i += n;
 223       i = i + n;
 224       i = n + i;
 225       i -= n;
 226       i = i - n;
 227       n = i - j;
 228     }
 229     difference_type n;
 230     Iterator i, j;
 231   };
 232
 233   //===========================================================================
 234   // Iterator Interoperability Concept
 235
 236   namespace detail
 237   {
 238
 239     template <typename Iterator1, typename Iterator2>
 240     void interop_single_pass_constraints(Iterator1 const& i1, Iterator2 const& i2)
 241     {
 242       bool b;
 243       b = i1 == i2;
 244       b = i1 != i2;
 245
 246       b = i2 == i1;
 247       b = i2 != i1;
 248     }
 249
 250     template <typename Iterator1, typename Iterator2>
 251     void interop_rand_access_constraints(Iterator1 const& i1, Iterator2 const& i2,
 252                                          boost::random_access_traversal_tag, boost::random_access_traversal_tag)
 253     {
 254       bool b;
 255       typename boost::detail::iterator_traits<Iterator2>::difference_type n;
 256       b = i1 <  i2;
 257       b = i1 <= i2;
 258       b = i1 >  i2;
 259       b = i1 >= i2;
 260       n = i1 -  i2;
 261
 262       b = i2 <  i1;
 263       b = i2 <= i1;
 264       b = i2 >  i1;
 265       b = i2 >= i1;
 266       n = i2 -  i1;
 267     }
 268     template <typename Iterator1, typename Iterator2>
 269     void interop_rand_access_constraints(Iterator1 const& i1, Iterator2 const& i2,
 270                                          boost::single_pass_traversal_tag, boost::single_pass_traversal_tag)
 271     { }
 272
 273   } // namespace detail
 274
 275   template <typename Iterator, typename ConstIterator>
 276   class InteroperableIteratorConcept
 277   {
 278   public:
 279       typedef typename boost::detail::pure_traversal_tag<
 280           typename boost::iterator_traversal<
 281               Iterator
 282           >::type
 283       >::type traversal_category;
 284
 285       typedef typename boost::detail::pure_traversal_tag<
 286           typename boost::iterator_traversal<
 287               ConstIterator
 288           >::type
 289       >::type const_traversal_category;
 290
 291       void constraints()
 292       {
 293           boost::function_requires< SinglePassIteratorConcept<Iterator> >();
 294           boost::function_requires< SinglePassIteratorConcept<ConstIterator> >();
 295
 296           detail::interop_single_pass_constraints(i, ci);
 297           detail::interop_rand_access_constraints(i, ci, traversal_category(), const_traversal_category());
 298
 299           ci = i;
 300       }
 301       Iterator      i;
 302       ConstIterator ci;
 303   };
 304
 305 } // namespace boost_concepts
 306
 307
 308 #endif // BOOST_ITERATOR_CONCEPTS_HPP