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
17namespace 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 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 >
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 >
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 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 >
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 >
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 >
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 >
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