Chris@16: // (C) Copyright Jeremy Siek 2002.
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_ITERATOR_CONCEPTS_HPP
Chris@16: #define BOOST_ITERATOR_CONCEPTS_HPP
Chris@16: 
Chris@16: #include <boost/concept_check.hpp>
Chris@16: #include <boost/iterator/iterator_categories.hpp>
Chris@16: 
Chris@16: // Use boost::detail::iterator_traits to work around some MSVC/Dinkumware problems.
Chris@16: #include <boost/detail/iterator.hpp>
Chris@16: 
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/type_traits/is_integral.hpp>
Chris@16: 
Chris@16: #include <boost/mpl/bool.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/mpl/and.hpp>
Chris@16: #include <boost/mpl/or.hpp>
Chris@16: 
Chris@16: #include <boost/static_assert.hpp>
Chris@16: 
Chris@16: // Use boost/limits to work around missing limits headers on some compilers
Chris@16: #include <boost/limits.hpp>
Chris@16: #include <boost/config.hpp>
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: 
Chris@16: #include <boost/concept/detail/concept_def.hpp>
Chris@16: 
Chris@16: namespace boost_concepts
Chris@16: {
Chris@16:   // Used a different namespace here (instead of "boost") so that the
Chris@16:   // concept descriptions do not take for granted the names in
Chris@16:   // namespace boost.
Chris@16: 
Chris@16:   //===========================================================================
Chris@16:   // Iterator Access Concepts
Chris@16: 
Chris@16:   BOOST_concept(ReadableIterator,(Iterator))
Chris@16:     : boost::Assignable<Iterator>
Chris@16:     , boost::CopyConstructible<Iterator>
Chris@16: 
Chris@16:   {
Chris@16:       typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type value_type;
Chris@16:       typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::reference reference;
Chris@16: 
Chris@16:       BOOST_CONCEPT_USAGE(ReadableIterator)
Chris@16:       {
Chris@16: 
Chris@16:           value_type v = *i;
Chris@16:           boost::ignore_unused_variable_warning(v);
Chris@16:       }
Chris@16:   private:
Chris@16:       Iterator i;
Chris@16:   };
Chris@101: 
Chris@16:   template <
Chris@16:       typename Iterator
Chris@16:     , typename ValueType = BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type
Chris@16:   >
Chris@16:   struct WritableIterator
Chris@16:     : boost::CopyConstructible<Iterator>
Chris@16:   {
Chris@16:       BOOST_CONCEPT_USAGE(WritableIterator)
Chris@16:       {
Chris@16:           *i = v;
Chris@16:       }
Chris@16:   private:
Chris@16:       ValueType v;
Chris@16:       Iterator i;
Chris@16:   };
Chris@16: 
Chris@16:   template <
Chris@16:       typename Iterator
Chris@16:     , typename ValueType = BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::value_type
Chris@16:   >
Chris@16:   struct WritableIteratorConcept : WritableIterator<Iterator,ValueType> {};
Chris@101: 
Chris@16:   BOOST_concept(SwappableIterator,(Iterator))
Chris@16:   {
Chris@16:       BOOST_CONCEPT_USAGE(SwappableIterator)
Chris@16:       {
Chris@16:           std::iter_swap(i1, i2);
Chris@16:       }
Chris@16:   private:
Chris@16:       Iterator i1;
Chris@16:       Iterator i2;
Chris@16:   };
Chris@16: 
Chris@16:   BOOST_concept(LvalueIterator,(Iterator))
Chris@16:   {
Chris@16:       typedef typename boost::detail::iterator_traits<Iterator>::value_type value_type;
Chris@101: 
Chris@16:       BOOST_CONCEPT_USAGE(LvalueIterator)
Chris@16:       {
Chris@16:         value_type& r = const_cast<value_type&>(*i);
Chris@16:         boost::ignore_unused_variable_warning(r);
Chris@16:       }
Chris@16:   private:
Chris@16:       Iterator i;
Chris@16:   };
Chris@16: 
Chris@101: 
Chris@16:   //===========================================================================
Chris@16:   // Iterator Traversal Concepts
Chris@16: 
Chris@16:   BOOST_concept(IncrementableIterator,(Iterator))
Chris@16:     : boost::Assignable<Iterator>
Chris@16:     , boost::CopyConstructible<Iterator>
Chris@16:   {
Chris@16:       typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
Chris@16: 
Chris@16:       BOOST_CONCEPT_ASSERT((
Chris@16:         boost::Convertible<
Chris@16:             traversal_category
Chris@16:           , boost::incrementable_traversal_tag
Chris@16:         >));
Chris@16: 
Chris@16:       BOOST_CONCEPT_USAGE(IncrementableIterator)
Chris@16:       {
Chris@16:           ++i;
Chris@16:           (void)i++;
Chris@16:       }
Chris@16:   private:
Chris@16:       Iterator i;
Chris@16:   };
Chris@16: 
Chris@16:   BOOST_concept(SinglePassIterator,(Iterator))
Chris@16:     : IncrementableIterator<Iterator>
Chris@16:     , boost::EqualityComparable<Iterator>
Chris@16: 
Chris@16:   {
Chris@16:       BOOST_CONCEPT_ASSERT((
Chris@16:           boost::Convertible<
Chris@16:              BOOST_DEDUCED_TYPENAME SinglePassIterator::traversal_category
Chris@16:            , boost::single_pass_traversal_tag
Chris@16:           > ));
Chris@16:   };
Chris@16: 
Chris@16:   BOOST_concept(ForwardTraversal,(Iterator))
Chris@16:     : SinglePassIterator<Iterator>
Chris@16:     , boost::DefaultConstructible<Iterator>
Chris@16:   {
Chris@16:       typedef typename boost::detail::iterator_traits<Iterator>::difference_type difference_type;
Chris@101: 
Chris@16:       BOOST_MPL_ASSERT((boost::is_integral<difference_type>));
Chris@16:       BOOST_MPL_ASSERT_RELATION(std::numeric_limits<difference_type>::is_signed, ==, true);
Chris@16: 
Chris@16:       BOOST_CONCEPT_ASSERT((
Chris@16:           boost::Convertible<
Chris@16:              BOOST_DEDUCED_TYPENAME ForwardTraversal::traversal_category
Chris@16:            , boost::forward_traversal_tag
Chris@16:           > ));
Chris@16:   };
Chris@101: 
Chris@16:   BOOST_concept(BidirectionalTraversal,(Iterator))
Chris@16:     : ForwardTraversal<Iterator>
Chris@16:   {
Chris@16:       BOOST_CONCEPT_ASSERT((
Chris@16:           boost::Convertible<
Chris@16:              BOOST_DEDUCED_TYPENAME BidirectionalTraversal::traversal_category
Chris@16:            , boost::bidirectional_traversal_tag
Chris@16:           > ));
Chris@16: 
Chris@16:       BOOST_CONCEPT_USAGE(BidirectionalTraversal)
Chris@16:       {
Chris@16:           --i;
Chris@16:           (void)i--;
Chris@16:       }
Chris@16:    private:
Chris@16:       Iterator i;
Chris@16:   };
Chris@16: 
Chris@16:   BOOST_concept(RandomAccessTraversal,(Iterator))
Chris@16:     : BidirectionalTraversal<Iterator>
Chris@16:   {
Chris@16:       BOOST_CONCEPT_ASSERT((
Chris@16:           boost::Convertible<
Chris@16:              BOOST_DEDUCED_TYPENAME RandomAccessTraversal::traversal_category
Chris@16:            , boost::random_access_traversal_tag
Chris@16:           > ));
Chris@16: 
Chris@16:       BOOST_CONCEPT_USAGE(RandomAccessTraversal)
Chris@16:       {
Chris@16:           i += n;
Chris@16:           i = i + n;
Chris@16:           i = n + i;
Chris@16:           i -= n;
Chris@16:           i = i - n;
Chris@16:           n = i - j;
Chris@16:       }
Chris@101: 
Chris@16:    private:
Chris@16:       typename BidirectionalTraversal<Iterator>::difference_type n;
Chris@16:       Iterator i, j;
Chris@16:   };
Chris@16: 
Chris@16:   //===========================================================================
Chris@101:   // Iterator Interoperability
Chris@16: 
Chris@16:   namespace detail
Chris@16:   {
Chris@16:     template <typename Iterator1, typename Iterator2>
Chris@16:     void interop_single_pass_constraints(Iterator1 const& i1, Iterator2 const& i2)
Chris@16:     {
Chris@16:         bool b;
Chris@16:         b = i1 == i2;
Chris@16:         b = i1 != i2;
Chris@16: 
Chris@16:         b = i2 == i1;
Chris@16:         b = i2 != i1;
Chris@16:         boost::ignore_unused_variable_warning(b);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Iterator1, typename Iterator2>
Chris@16:     void interop_rand_access_constraints(
Chris@16:         Iterator1 const& i1, Iterator2 const& i2,
Chris@16:         boost::random_access_traversal_tag, boost::random_access_traversal_tag)
Chris@16:     {
Chris@16:         bool b;
Chris@16:         typename boost::detail::iterator_traits<Iterator2>::difference_type n;
Chris@16:         b = i1 <  i2;
Chris@16:         b = i1 <= i2;
Chris@16:         b = i1 >  i2;
Chris@16:         b = i1 >= i2;
Chris@16:         n = i1 -  i2;
Chris@16: 
Chris@16:         b = i2 <  i1;
Chris@16:         b = i2 <= i1;
Chris@16:         b = i2 >  i1;
Chris@16:         b = i2 >= i1;
Chris@16:         n = i2 -  i1;
Chris@16:         boost::ignore_unused_variable_warning(b);
Chris@16:         boost::ignore_unused_variable_warning(n);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Iterator1, typename Iterator2>
Chris@16:     void interop_rand_access_constraints(
Chris@16:         Iterator1 const&, Iterator2 const&,
Chris@16:         boost::single_pass_traversal_tag, boost::single_pass_traversal_tag)
Chris@16:     { }
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   BOOST_concept(InteroperableIterator,(Iterator)(ConstIterator))
Chris@16:   {
Chris@16:    private:
Chris@101:       typedef typename boost::iterators::pure_iterator_traversal<Iterator>::type traversal_category;
Chris@101:       typedef typename boost::iterators::pure_iterator_traversal<ConstIterator>::type const_traversal_category;
Chris@16: 
Chris@101:    public:
Chris@16:       BOOST_CONCEPT_ASSERT((SinglePassIterator<Iterator>));
Chris@16:       BOOST_CONCEPT_ASSERT((SinglePassIterator<ConstIterator>));
Chris@16: 
Chris@16:       BOOST_CONCEPT_USAGE(InteroperableIterator)
Chris@16:       {
Chris@16:           detail::interop_single_pass_constraints(i, ci);
Chris@16:           detail::interop_rand_access_constraints(i, ci, traversal_category(), const_traversal_category());
Chris@16: 
Chris@16:           ci = i;
Chris@16:       }
Chris@101: 
Chris@16:    private:
Chris@16:       Iterator      i;
Chris@16:       ConstIterator ci;
Chris@16:   };
Chris@16: 
Chris@16: } // namespace boost_concepts
Chris@16: 
Chris@16: #include <boost/concept/detail/concept_undef.hpp>
Chris@16: 
Chris@16: #endif // BOOST_ITERATOR_CONCEPTS_HPP