Line data Source code
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 0 : 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 0 : 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 0 : 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 0 : return ::boost::range_detail::equal(
178 : ::boost::begin(rng1), ::boost::end(rng1),
179 0 : ::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
|