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 > equal_impl(SinglePassTraversalReadableIterator1 first1,SinglePassTraversalReadableIterator1 last1,SinglePassTraversalReadableIterator2 first2,SinglePassTraversalReadableIterator2 last2,IteratorCategoryTag1,IteratorCategoryTag2)27 inline bool equal_impl( SinglePassTraversalReadableIterator1 first1, 28 SinglePassTraversalReadableIterator1 last1, 29 SinglePassTraversalReadableIterator2 first2, 30 SinglePassTraversalReadableIterator2 last2, 31 IteratorCategoryTag1, 32 IteratorCategoryTag2 ) 33 { 34 for (;;) 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 > equal_impl(SinglePassTraversalReadableIterator1 first1,SinglePassTraversalReadableIterator1 last1,SinglePassTraversalReadableIterator2 first2,SinglePassTraversalReadableIterator2 last2,BinaryPredicate pred,IteratorCategoryTag1,IteratorCategoryTag2)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 for (;;) 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 > equal_impl(RandomAccessTraversalReadableIterator1 first1,RandomAccessTraversalReadableIterator1 last1,RandomAccessTraversalReadableIterator2 first2,RandomAccessTraversalReadableIterator2 last2,std::random_access_iterator_tag,std::random_access_iterator_tag)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 > equal_impl(RandomAccessTraversalReadableIterator1 first1,RandomAccessTraversalReadableIterator1 last1,RandomAccessTraversalReadableIterator2 first2,RandomAccessTraversalReadableIterator2 last2,BinaryPredicate pred,std::random_access_iterator_tag,std::random_access_iterator_tag)119 inline bool equal_impl( RandomAccessTraversalReadableIterator1 first1, 120 RandomAccessTraversalReadableIterator1 last1, 121 RandomAccessTraversalReadableIterator2 first2, 122 RandomAccessTraversalReadableIterator2 last2, 123 BinaryPredicate pred, 124 std::random_access_iterator_tag, 125 std::random_access_iterator_tag ) 126 { 127 return ((last1 - first1) == (last2 - first2)) 128 && std::equal(first1, last1, first2, pred); 129 } 130 131 template< class SinglePassTraversalReadableIterator1, 132 class SinglePassTraversalReadableIterator2 > equal(SinglePassTraversalReadableIterator1 first1,SinglePassTraversalReadableIterator1 last1,SinglePassTraversalReadableIterator2 first2,SinglePassTraversalReadableIterator2 last2)133 inline bool equal( SinglePassTraversalReadableIterator1 first1, 134 SinglePassTraversalReadableIterator1 last1, 135 SinglePassTraversalReadableIterator2 first2, 136 SinglePassTraversalReadableIterator2 last2 ) 137 { 138 BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1; 139 BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2; 140 141 return equal_impl(first1, last1, first2, last2, tag1, tag2); 142 } 143 144 template< class SinglePassTraversalReadableIterator1, 145 class SinglePassTraversalReadableIterator2, 146 class BinaryPredicate > equal(SinglePassTraversalReadableIterator1 first1,SinglePassTraversalReadableIterator1 last1,SinglePassTraversalReadableIterator2 first2,SinglePassTraversalReadableIterator2 last2,BinaryPredicate pred)147 inline bool equal( SinglePassTraversalReadableIterator1 first1, 148 SinglePassTraversalReadableIterator1 last1, 149 SinglePassTraversalReadableIterator2 first2, 150 SinglePassTraversalReadableIterator2 last2, 151 BinaryPredicate pred ) 152 { 153 BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1; 154 BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2; 155 156 return equal_impl(first1, last1, first2, last2, pred, tag1, tag2); 157 } 158 159 } // namespace range_detail 160 161 namespace range 162 { 163 164 /// \brief template function equal 165 /// 166 /// range-based version of the equal std algorithm 167 /// 168 /// \pre SinglePassRange1 is a model of the SinglePassRangeConcept 169 /// \pre SinglePassRange2 is a model of the SinglePassRangeConcept 170 /// \pre BinaryPredicate is a model of the BinaryPredicateConcept 171 template< class SinglePassRange1, class SinglePassRange2 > equal(const SinglePassRange1 & rng1,const SinglePassRange2 & rng2)172 inline bool equal( const SinglePassRange1& rng1, const SinglePassRange2& rng2 ) 173 { 174 BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> )); 175 BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> )); 176 177 return ::boost::range_detail::equal( 178 ::boost::begin(rng1), ::boost::end(rng1), 179 ::boost::begin(rng2), ::boost::end(rng2) ); 180 } 181 182 /// \overload 183 template< class SinglePassRange1, class SinglePassRange2, class BinaryPredicate > equal(const SinglePassRange1 & rng1,const SinglePassRange2 & rng2,BinaryPredicate pred)184 inline bool equal( const SinglePassRange1& rng1, const SinglePassRange2& rng2, 185 BinaryPredicate pred ) 186 { 187 BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> )); 188 BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> )); 189 190 return ::boost::range_detail::equal( 191 ::boost::begin(rng1), ::boost::end(rng1), 192 ::boost::begin(rng2), ::boost::end(rng2), 193 pred); 194 } 195 196 } // namespace range 197 using ::boost::range::equal; 198 } // namespace boost 199 200 #endif // include guard 201