williamr@2: // (C) Copyright Jeremy Siek 2002.
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: 
williamr@2: #ifndef BOOST_ITERATOR_CONCEPTS_HPP
williamr@2: #define BOOST_ITERATOR_CONCEPTS_HPP
williamr@2: 
williamr@2: //  Revision History
williamr@2: //  26 Apr 2003 thw
williamr@2: //       Adapted to new iterator concepts
williamr@2: //  22 Nov 2002 Thomas Witt
williamr@2: //       Added interoperable concept.
williamr@2: 
williamr@2: #include <boost/concept_check.hpp>
williamr@2: #include <boost/iterator/iterator_categories.hpp>
williamr@2: 
williamr@2: // Use boost::detail::iterator_traits to work around some MSVC/Dinkumware problems.
williamr@2: #include <boost/detail/iterator.hpp>
williamr@2: 
williamr@2: #include <boost/type_traits/is_same.hpp>
williamr@2: #include <boost/type_traits/is_integral.hpp>
williamr@2: #include <boost/type_traits/is_convertible.hpp>
williamr@2: 
williamr@2: #include <boost/mpl/bool.hpp>
williamr@2: #include <boost/mpl/if.hpp>
williamr@2: #include <boost/mpl/and.hpp>
williamr@2: #include <boost/mpl/or.hpp>
williamr@2: 
williamr@2: #include <boost/static_assert.hpp>
williamr@2: 
williamr@2: // Use boost/limits to work around missing limits headers on some compilers
williamr@2: #include <boost/limits.hpp>
williamr@2: #include <boost/config.hpp>
williamr@2: 
williamr@2: #include <algorithm>
williamr@2: 
williamr@2: namespace boost_concepts {
williamr@2:   // Used a different namespace here (instead of "boost") so that the
williamr@2:   // concept descriptions do not take for granted the names in
williamr@2:   // namespace boost.
williamr@2: 
williamr@2:   // We use this in place of STATIC_ASSERT((is_convertible<...>))
williamr@2:   // because some compilers (CWPro7.x) can't detect convertibility.
williamr@2:   //
williamr@2:   // Of course, that just gets us a different error at the moment with
williamr@2:   // some tests, since new iterator category deduction still depends
williamr@2:   // on convertibility detection. We might need some specializations
williamr@2:   // to support this compiler.
williamr@2:   template <class Target, class Source>
williamr@2:   struct static_assert_base_and_derived
williamr@2:   {
williamr@2:       static_assert_base_and_derived(Target* = (Source*)0) {}
williamr@2:   };
williamr@2: 
williamr@2:   //===========================================================================
williamr@2:   // Iterator Access Concepts
williamr@2: 
williamr@2:   template <typename Iterator>
williamr@2:   class ReadableIteratorConcept {
williamr@2:   public:
williamr@2:     typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type value_type;
williamr@2: 
williamr@2:     void constraints() {
williamr@2:       boost::function_requires< boost::AssignableConcept<Iterator> >();
williamr@2:       boost::function_requires< boost::CopyConstructibleConcept<Iterator> >();
williamr@2: 
williamr@2:       value_type v = *i;
williamr@2:       boost::ignore_unused_variable_warning(v);
williamr@2:     }
williamr@2:     Iterator i;
williamr@2:   };
williamr@2:   
williamr@2:   template <
williamr@2:       typename Iterator
williamr@2:     , typename ValueType = BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type
williamr@2:   >
williamr@2:   class WritableIteratorConcept {
williamr@2:   public:
williamr@2:       
williamr@2:     void constraints() {
williamr@2:       boost::function_requires< boost::CopyConstructibleConcept<Iterator> >();
williamr@2:       *i = v;
williamr@2:     }
williamr@2:     ValueType v;
williamr@2:     Iterator i;
williamr@2:   };
williamr@2:   
williamr@2:   template <typename Iterator>
williamr@2:   class SwappableIteratorConcept {
williamr@2:   public:
williamr@2: 
williamr@2:     void constraints() {
williamr@2:       std::iter_swap(i1, i2);
williamr@2:     }
williamr@2:     Iterator i1;
williamr@2:     Iterator i2;
williamr@2:   };
williamr@2: 
williamr@2:   template <typename Iterator>
williamr@2:   class LvalueIteratorConcept
williamr@2:   {
williamr@2:    public:
williamr@2:       typedef typename boost::detail::iterator_traits<Iterator>::value_type value_type;
williamr@2:       void constraints()
williamr@2:       {
williamr@2:         value_type& r = const_cast<value_type&>(*i);
williamr@2:         boost::ignore_unused_variable_warning(r);
williamr@2:       }
williamr@2:     Iterator i;
williamr@2:   };
williamr@2: 
williamr@2:   
williamr@2:   //===========================================================================
williamr@2:   // Iterator Traversal Concepts
williamr@2: 
williamr@2:   template <typename Iterator>
williamr@2:   class IncrementableIteratorConcept {
williamr@2:   public:
williamr@2:     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
williamr@2: 
williamr@2:     void constraints() {
williamr@2:       boost::function_requires< boost::AssignableConcept<Iterator> >();
williamr@2:       boost::function_requires< boost::CopyConstructibleConcept<Iterator> >();
williamr@2: 
williamr@2:       BOOST_STATIC_ASSERT(
williamr@2:           (boost::is_convertible<
williamr@2:                 traversal_category
williamr@2:               , boost::incrementable_traversal_tag
williamr@2:            >::value
williamr@2:           ));
williamr@2: 
williamr@2:       ++i;
williamr@2:       (void)i++;
williamr@2:     }
williamr@2:     Iterator i;
williamr@2:   };
williamr@2: 
williamr@2:   template <typename Iterator>
williamr@2:   class SinglePassIteratorConcept {
williamr@2:   public:
williamr@2:     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
williamr@2:     typedef typename boost::detail::iterator_traits<Iterator>::difference_type difference_type;
williamr@2: 
williamr@2:     void constraints() {
williamr@2:       boost::function_requires< IncrementableIteratorConcept<Iterator> >();
williamr@2:       boost::function_requires< boost::EqualityComparableConcept<Iterator> >();
williamr@2: 
williamr@2:       BOOST_STATIC_ASSERT(
williamr@2:           (boost::is_convertible<
williamr@2:                 traversal_category
williamr@2:               , boost::single_pass_traversal_tag
williamr@2:            >::value
williamr@2:           ));
williamr@2:     }
williamr@2:   };
williamr@2: 
williamr@2:   template <typename Iterator>
williamr@2:   class ForwardTraversalConcept {
williamr@2:   public:
williamr@2:     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
williamr@2:     typedef typename boost::detail::iterator_traits<Iterator>::difference_type difference_type;
williamr@2: 
williamr@2:     void constraints() {
williamr@2:       boost::function_requires< SinglePassIteratorConcept<Iterator> >();
williamr@2:       boost::function_requires< 
williamr@2:         boost::DefaultConstructibleConcept<Iterator> >();
williamr@2: 
williamr@2:       typedef boost::mpl::and_<
williamr@2:         boost::is_integral<difference_type>,
williamr@2:         boost::mpl::bool_< std::numeric_limits<difference_type>::is_signed >
williamr@2:         > difference_type_is_signed_integral;
williamr@2: 
williamr@2:       BOOST_STATIC_ASSERT(difference_type_is_signed_integral::value);
williamr@2:       BOOST_STATIC_ASSERT(
williamr@2:           (boost::is_convertible<
williamr@2:                 traversal_category
williamr@2:               , boost::forward_traversal_tag
williamr@2:            >::value
williamr@2:           ));
williamr@2:     }
williamr@2:   };
williamr@2:   
williamr@2:   template <typename Iterator>
williamr@2:   class BidirectionalTraversalConcept {
williamr@2:   public:
williamr@2:     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
williamr@2: 
williamr@2:     void constraints() {
williamr@2:       boost::function_requires< ForwardTraversalConcept<Iterator> >();
williamr@2:       
williamr@2:       BOOST_STATIC_ASSERT(
williamr@2:           (boost::is_convertible<
williamr@2:                 traversal_category
williamr@2:               , boost::bidirectional_traversal_tag
williamr@2:            >::value
williamr@2:           ));
williamr@2: 
williamr@2:       --i;
williamr@2:       (void)i--;
williamr@2:     }
williamr@2:     Iterator i;
williamr@2:   };
williamr@2: 
williamr@2:   template <typename Iterator>
williamr@2:   class RandomAccessTraversalConcept {
williamr@2:   public:
williamr@2:     typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
williamr@2:     typedef typename boost::detail::iterator_traits<Iterator>::difference_type
williamr@2:       difference_type;
williamr@2: 
williamr@2:     void constraints() {
williamr@2:       boost::function_requires< BidirectionalTraversalConcept<Iterator> >();
williamr@2: 
williamr@2:       BOOST_STATIC_ASSERT(
williamr@2:           (boost::is_convertible<
williamr@2:                 traversal_category
williamr@2:               , boost::random_access_traversal_tag
williamr@2:            >::value
williamr@2:           ));
williamr@2:       
williamr@2:       i += n;
williamr@2:       i = i + n;
williamr@2:       i = n + i;
williamr@2:       i -= n;
williamr@2:       i = i - n;
williamr@2:       n = i - j;
williamr@2:     }
williamr@2:     difference_type n;
williamr@2:     Iterator i, j;
williamr@2:   };
williamr@2: 
williamr@2:   //===========================================================================
williamr@2:   // Iterator Interoperability Concept
williamr@2: 
williamr@2:   namespace detail
williamr@2:   {
williamr@2: 
williamr@2:     template <typename Iterator1, typename Iterator2>
williamr@2:     void interop_single_pass_constraints(Iterator1 const& i1, Iterator2 const& i2)
williamr@2:     {
williamr@2:       bool b;
williamr@2:       b = i1 == i2;
williamr@2:       b = i1 != i2;
williamr@2:       
williamr@2:       b = i2 == i1;
williamr@2:       b = i2 != i1;
williamr@2:     }
williamr@2:     
williamr@2:     template <typename Iterator1, typename Iterator2>
williamr@2:     void interop_rand_access_constraints(Iterator1 const& i1, Iterator2 const& i2,
williamr@2:                                          boost::random_access_traversal_tag, boost::random_access_traversal_tag)
williamr@2:     {
williamr@2:       bool b;
williamr@2:       typename boost::detail::iterator_traits<Iterator2>::difference_type n;
williamr@2:       b = i1 <  i2;
williamr@2:       b = i1 <= i2;
williamr@2:       b = i1 >  i2;
williamr@2:       b = i1 >= i2;
williamr@2:       n = i1 -  i2;
williamr@2:       
williamr@2:       b = i2 <  i1;
williamr@2:       b = i2 <= i1;
williamr@2:       b = i2 >  i1;
williamr@2:       b = i2 >= i1;
williamr@2:       n = i2 -  i1;
williamr@2:     }
williamr@2:     template <typename Iterator1, typename Iterator2>
williamr@2:     void interop_rand_access_constraints(Iterator1 const& i1, Iterator2 const& i2,
williamr@2:                                          boost::single_pass_traversal_tag, boost::single_pass_traversal_tag)
williamr@2:     { }
williamr@2: 
williamr@2:   } // namespace detail
williamr@2: 
williamr@2:   template <typename Iterator, typename ConstIterator>
williamr@2:   class InteroperableIteratorConcept
williamr@2:   {
williamr@2:   public:
williamr@2:       typedef typename boost::detail::pure_traversal_tag<
williamr@2:           typename boost::iterator_traversal<
williamr@2:               Iterator
williamr@2:           >::type
williamr@2:       >::type traversal_category;
williamr@2: 
williamr@2:       typedef typename boost::detail::pure_traversal_tag<
williamr@2:           typename boost::iterator_traversal<
williamr@2:               ConstIterator
williamr@2:           >::type
williamr@2:       >::type const_traversal_category;
williamr@2: 
williamr@2:       void constraints()
williamr@2:       {
williamr@2:           boost::function_requires< SinglePassIteratorConcept<Iterator> >();
williamr@2:           boost::function_requires< SinglePassIteratorConcept<ConstIterator> >();
williamr@2: 
williamr@2:           detail::interop_single_pass_constraints(i, ci);
williamr@2:           detail::interop_rand_access_constraints(i, ci, traversal_category(), const_traversal_category());
williamr@2: 
williamr@2:           ci = i;
williamr@2:       }
williamr@2:       Iterator      i;
williamr@2:       ConstIterator ci;
williamr@2:   };
williamr@2: 
williamr@2: } // namespace boost_concepts
williamr@2: 
williamr@2: 
williamr@2: #endif // BOOST_ITERATOR_CONCEPTS_HPP