boost/iterator/iterator_concepts.hpp

0001 // (C) Copyright Jeremy Siek 2002.
0002 // Distributed under the Boost Software License, Version 1.0. (See
0003 // accompanying file LICENSE_1_0.txt or copy at
0004 // http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef BOOST_ITERATOR_CONCEPTS_HPP
0007 #define BOOST_ITERATOR_CONCEPTS_HPP
0008
0009 #include <boost/concept_check.hpp>
0010 #include <boost/iterator/iterator_categories.hpp>
0011
0012 #include <type_traits>
0013
0014 // Use boost/limits to work around missing limits headers on some compilers
0015 #include <boost/limits.hpp>
0016 #include <boost/config.hpp>
0017
0018 #include <algorithm>
0019 #include <iterator>
0020
0021 #include <boost/concept/detail/concept_def.hpp>
0022
0023 namespace boost_concepts
0024 {
0025   // Used a different namespace here (instead of "boost") so that the
0026   // concept descriptions do not take for granted the names in
0027   // namespace boost.
0028
0029   //===========================================================================
0030   // Iterator Access Concepts
0031
0032   BOOST_concept(ReadableIterator,(Iterator))
0033     : boost::Assignable<Iterator>
0034     , boost::CopyConstructible<Iterator>
0035
0036   {
0037       typedef BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::value_type value_type;
0038       typedef BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::reference reference;
0039
0040       BOOST_CONCEPT_USAGE(ReadableIterator)
0041       {
0042
0043           value_type v = *i;
0044           boost::ignore_unused_variable_warning(v);
0045       }
0046   private:
0047       Iterator i;
0048   };
0049
0050   template <
0051       typename Iterator
0052     , typename ValueType = BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::value_type
0053   >
0054   struct WritableIterator
0055     : boost::CopyConstructible<Iterator>
0056   {
0057       BOOST_CONCEPT_USAGE(WritableIterator)
0058       {
0059           *i = v;
0060       }
0061   private:
0062       ValueType v;
0063       Iterator i;
0064   };
0065
0066   template <
0067       typename Iterator
0068     , typename ValueType = BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::value_type
0069   >
0070   struct WritableIteratorConcept : WritableIterator<Iterator,ValueType> {};
0071
0072   BOOST_concept(SwappableIterator,(Iterator))
0073   {
0074       BOOST_CONCEPT_USAGE(SwappableIterator)
0075       {
0076           std::iter_swap(i1, i2);
0077       }
0078   private:
0079       Iterator i1;
0080       Iterator i2;
0081   };
0082
0083   BOOST_concept(LvalueIterator,(Iterator))
0084   {
0085       typedef typename std::iterator_traits<Iterator>::value_type value_type;
0086
0087       BOOST_CONCEPT_USAGE(LvalueIterator)
0088       {
0089         value_type& r = const_cast<value_type&>(*i);
0090         boost::ignore_unused_variable_warning(r);
0091       }
0092   private:
0093       Iterator i;
0094   };
0095
0096
0097   //===========================================================================
0098   // Iterator Traversal Concepts
0099
0100   BOOST_concept(IncrementableIterator,(Iterator))
0101     : boost::Assignable<Iterator>
0102     , boost::CopyConstructible<Iterator>
0103   {
0104       typedef typename boost::iterator_traversal<Iterator>::type traversal_category;
0105
0106       BOOST_CONCEPT_ASSERT((
0107         boost::Convertible<
0108             traversal_category
0109           , boost::incrementable_traversal_tag
0110         >));
0111
0112       BOOST_CONCEPT_USAGE(IncrementableIterator)
0113       {
0114           ++i;
0115           (void)i++;
0116       }
0117   private:
0118       Iterator i;
0119   };
0120
0121   BOOST_concept(SinglePassIterator,(Iterator))
0122     : IncrementableIterator<Iterator>
0123     , boost::EqualityComparable<Iterator>
0124
0125   {
0126       BOOST_CONCEPT_ASSERT((
0127           boost::Convertible<
0128              BOOST_DEDUCED_TYPENAME SinglePassIterator::traversal_category
0129            , boost::single_pass_traversal_tag
0130           > ));
0131   };
0132
0133   BOOST_concept(ForwardTraversal,(Iterator))
0134     : SinglePassIterator<Iterator>
0135     , boost::DefaultConstructible<Iterator>
0136   {
0137       typedef typename std::iterator_traits<Iterator>::difference_type difference_type;
0138
0139       static_assert(std::is_integral<difference_type>::value, "difference_type must be integral.");
0140       static_assert(std::numeric_limits<difference_type>::is_signed, "difference_type must be signed.");
0141
0142       BOOST_CONCEPT_ASSERT((
0143           boost::Convertible<
0144              BOOST_DEDUCED_TYPENAME ForwardTraversal::traversal_category
0145            , boost::forward_traversal_tag
0146           > ));
0147   };
0148
0149   BOOST_concept(BidirectionalTraversal,(Iterator))
0150     : ForwardTraversal<Iterator>
0151   {
0152       BOOST_CONCEPT_ASSERT((
0153           boost::Convertible<
0154              BOOST_DEDUCED_TYPENAME BidirectionalTraversal::traversal_category
0155            , boost::bidirectional_traversal_tag
0156           > ));
0157
0158       BOOST_CONCEPT_USAGE(BidirectionalTraversal)
0159       {
0160           --i;
0161           (void)i--;
0162       }
0163    private:
0164       Iterator i;
0165   };
0166
0167   BOOST_concept(RandomAccessTraversal,(Iterator))
0168     : BidirectionalTraversal<Iterator>
0169   {
0170       BOOST_CONCEPT_ASSERT((
0171           boost::Convertible<
0172              BOOST_DEDUCED_TYPENAME RandomAccessTraversal::traversal_category
0173            , boost::random_access_traversal_tag
0174           > ));
0175
0176       BOOST_CONCEPT_USAGE(RandomAccessTraversal)
0177       {
0178           i += n;
0179           i = i + n;
0180           i = n + i;
0181           i -= n;
0182           i = i - n;
0183           n = i - j;
0184       }
0185
0186    private:
0187       typename BidirectionalTraversal<Iterator>::difference_type n;
0188       Iterator i, j;
0189   };
0190
0191   //===========================================================================
0192   // Iterator Interoperability
0193
0194   namespace detail
0195   {
0196     template <typename Iterator1, typename Iterator2>
0197     void interop_single_pass_constraints(Iterator1 const& i1, Iterator2 const& i2)
0198     {
0199         bool b;
0200         b = i1 == i2;
0201         b = i1 != i2;
0202
0203         b = i2 == i1;
0204         b = i2 != i1;
0205         boost::ignore_unused_variable_warning(b);
0206     }
0207
0208     template <typename Iterator1, typename Iterator2>
0209     void interop_rand_access_constraints(
0210         Iterator1 const& i1, Iterator2 const& i2,
0211         boost::random_access_traversal_tag, boost::random_access_traversal_tag)
0212     {
0213         bool b;
0214         typename std::iterator_traits<Iterator2>::difference_type n;
0215         b = i1 <  i2;
0216         b = i1 <= i2;
0217         b = i1 >  i2;
0218         b = i1 >= i2;
0219         n = i1 -  i2;
0220
0221         b = i2 <  i1;
0222         b = i2 <= i1;
0223         b = i2 >  i1;
0224         b = i2 >= i1;
0225         n = i2 -  i1;
0226         boost::ignore_unused_variable_warning(b);
0227         boost::ignore_unused_variable_warning(n);
0228     }
0229
0230     template <typename Iterator1, typename Iterator2>
0231     void interop_rand_access_constraints(
0232         Iterator1 const&, Iterator2 const&,
0233         boost::single_pass_traversal_tag, boost::single_pass_traversal_tag)
0234     { }
0235
0236   } // namespace detail
0237
0238   BOOST_concept(InteroperableIterator,(Iterator)(ConstIterator))
0239   {
0240    private:
0241       typedef typename boost::iterators::pure_iterator_traversal<Iterator>::type traversal_category;
0242       typedef typename boost::iterators::pure_iterator_traversal<ConstIterator>::type const_traversal_category;
0243
0244    public:
0245       BOOST_CONCEPT_ASSERT((SinglePassIterator<Iterator>));
0246       BOOST_CONCEPT_ASSERT((SinglePassIterator<ConstIterator>));
0247
0248       BOOST_CONCEPT_USAGE(InteroperableIterator)
0249       {
0250           detail::interop_single_pass_constraints(i, ci);
0251           detail::interop_rand_access_constraints(i, ci, traversal_category(), const_traversal_category());
0252
0253           ci = i;
0254       }
0255
0256    private:
0257       Iterator      i;
0258       ConstIterator ci;
0259   };
0260
0261 } // namespace boost_concepts
0262
0263 #include <boost/concept/detail/concept_undef.hpp>
0264
0265 #endif // BOOST_ITERATOR_CONCEPTS_HPP