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