boost/range/algorithm/equal.hpp

   1 // Boost.Range library
   2 //
   3 //  Copyright Neil Groves 2009.
   4 //  Use, modification and distribution is subject to the Boost Software
   5 //  License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6 //  http://www.boost.org/LICENSE_1_0.txt)
   7 //
   8 // For more information, see http://www.boost.org/libs/range/
   9 //
  10 #ifndef BOOST_RANGE_ALGORITHM_EQUAL_HPP_INCLUDED
  11 #define BOOST_RANGE_ALGORITHM_EQUAL_HPP_INCLUDED
  12
  13 #include <boost/config.hpp>
  14 #include <boost/range/concepts.hpp>
  15 #include <iterator>
  16
  17 namespace boost
  18 {
  19     namespace range_detail
  20     {
  21         // An implementation of equality comparison that is optimized for iterator
  22         // traversal categories less than RandomAccessTraversal.
  23         template< class SinglePassTraversalReadableIterator1,
  24                   class SinglePassTraversalReadableIterator2,
  25                   class IteratorCategoryTag1,
  26                   class IteratorCategoryTag2 >
  27         inline bool equal_impl( SinglePassTraversalReadableIterator1 first1,
  28                                 SinglePassTraversalReadableIterator1 last1,
  29                                 SinglePassTraversalReadableIterator2 first2,
  30                                 SinglePassTraversalReadableIterator2 last2,
  31                                 IteratorCategoryTag1,
  32                                 IteratorCategoryTag2 )
  33         {
  34             while (true)
  35             {
  36                 // If we have reached the end of the left range then this is
  37                 // the end of the loop. They are equal if and only if we have
  38                 // simultaneously reached the end of the right range.
  39                 if (first1 == last1)
  40                     return first2 == last2;
  41
  42                 // If we have reached the end of the right range at this line
  43                 // it indicates that the right range is shorter than the left
  44                 // and hence the result is false.
  45                 if (first2 == last2)
  46                     return false;
  47
  48                 // continue looping if and only if the values are equal
  49                 if (*first1 != *first2)
  50                     break;
  51
  52                 ++first1;
  53                 ++first2;
  54             }
  55
  56             // Reaching this line in the algorithm indicates that a value
  57             // inequality has been detected.
  58             return false;
  59         }
  60
  61         template< class SinglePassTraversalReadableIterator1,
  62                   class SinglePassTraversalReadableIterator2,
  63                   class IteratorCategoryTag1,
  64                   class IteratorCategoryTag2,
  65                   class BinaryPredicate >
  66         inline bool equal_impl( SinglePassTraversalReadableIterator1 first1,
  67                                 SinglePassTraversalReadableIterator1 last1,
  68                                 SinglePassTraversalReadableIterator2 first2,
  69                                 SinglePassTraversalReadableIterator2 last2,
  70                                 BinaryPredicate                      pred,
  71                                 IteratorCategoryTag1,
  72                                 IteratorCategoryTag2 )
  73         {
  74             while (true)
  75             {
  76                 // If we have reached the end of the left range then this is
  77                 // the end of the loop. They are equal if and only if we have
  78                 // simultaneously reached the end of the right range.
  79                 if (first1 == last1)
  80                     return first2 == last2;
  81
  82                 // If we have reached the end of the right range at this line
  83                 // it indicates that the right range is shorter than the left
  84                 // and hence the result is false.
  85                 if (first2 == last2)
  86                     return false;
  87
  88                 // continue looping if and only if the values are equal
  89                 if (!pred(*first1, *first2))
  90                     break;
  91
  92                 ++first1;
  93                 ++first2;
  94             }
  95
  96             // Reaching this line in the algorithm indicates that a value
  97             // inequality has been detected.
  98             return false;
  99         }
 100
 101         // An implementation of equality comparison that is optimized for
 102         // random access iterators.
 103         template< class RandomAccessTraversalReadableIterator1,
 104                   class RandomAccessTraversalReadableIterator2 >
 105         inline bool equal_impl( RandomAccessTraversalReadableIterator1 first1,
 106                                 RandomAccessTraversalReadableIterator1 last1,
 107                                 RandomAccessTraversalReadableIterator2 first2,
 108                                 RandomAccessTraversalReadableIterator2 last2,
 109                                 std::random_access_iterator_tag,
 110                                 std::random_access_iterator_tag )
 111         {
 112             return ((last1 - first1) == (last2 - first2))
 113                 && std::equal(first1, last1, first2);
 114         }
 115
 116         template< class RandomAccessTraversalReadableIterator1,
 117                   class RandomAccessTraversalReadableIterator2,
 118                   class BinaryPredicate >
 119         inline bool equal_impl( RandomAccessTraversalReadableIterator1 first1,
 120                                 RandomAccessTraversalReadableIterator1 last1,
 121                                 RandomAccessTraversalReadableIterator2 first2,
 122                                 RandomAccessTraversalReadableIterator2 last2,
 123                                 BinaryPredicate                        pred )
 124         {
 125             return ((last1 - first1) == (last2 - first2))
 126                 && std::equal(first1, last1, first2, pred);
 127         }
 128
 129         template< class SinglePassTraversalReadableIterator1,
 130                   class SinglePassTraversalReadableIterator2 >
 131         inline bool equal( SinglePassTraversalReadableIterator1 first1,
 132                            SinglePassTraversalReadableIterator1 last1,
 133                            SinglePassTraversalReadableIterator2 first2,
 134                            SinglePassTraversalReadableIterator2 last2 )
 135         {
 136             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1;
 137             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2;
 138
 139             return equal_impl(first1, last1, first2, last2, tag1, tag2);
 140         }
 141
 142         template< class SinglePassTraversalReadableIterator1,
 143                   class SinglePassTraversalReadableIterator2,
 144                   class BinaryPredicate >
 145         inline bool equal( SinglePassTraversalReadableIterator1 first1,
 146                            SinglePassTraversalReadableIterator1 last1,
 147                            SinglePassTraversalReadableIterator2 first2,
 148                            SinglePassTraversalReadableIterator2 last2,
 149                            BinaryPredicate                      pred )
 150         {
 151             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1;
 152             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2;
 153
 154             return equal_impl(first1, last1, first2, last2, pred, tag1, tag2);
 155         }
 156
 157     } // namespace range_detail
 158
 159     namespace range
 160     {
 161
 162         /// \brief template function equal
 163         ///
 164         /// range-based version of the equal std algorithm
 165         ///
 166         /// \pre SinglePassRange1 is a model of the SinglePassRangeConcept
 167         /// \pre SinglePassRange2 is a model of the SinglePassRangeConcept
 168         /// \pre BinaryPredicate is a model of the BinaryPredicateConcept
 169         template< class SinglePassRange1, class SinglePassRange2 >
 170         inline bool equal( const SinglePassRange1& rng1, const SinglePassRange2& rng2 )
 171         {
 172             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> ));
 173             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> ));
 174
 175             return ::boost::range_detail::equal(
 176                 ::boost::begin(rng1), ::boost::end(rng1),
 177                 ::boost::begin(rng2), ::boost::end(rng2) );
 178         }
 179
 180         /// \overload
 181         template< class SinglePassRange1, class SinglePassRange2, class BinaryPredicate >
 182         inline bool equal( const SinglePassRange1& rng1, const SinglePassRange2& rng2,
 183                            BinaryPredicate pred )
 184         {
 185             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> ));
 186             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> ));
 187
 188             return ::boost::range_detail::equal(
 189                 ::boost::begin(rng1), ::boost::end(rng1),
 190                 ::boost::begin(rng2), ::boost::end(rng2),
 191                 pred);
 192         }
 193
 194     } // namespace range
 195     using ::boost::range::equal;
 196 } // namespace boost
 197
 198 #endif // include guard