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 199
