blob: 70910352af89f2ff0b0e0304899459a562b7729b [file] [log] [blame]
Jeff Thompsonef2d5a42013-08-22 19:09:24 -07001// 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//
Jeff Thompson3d613fd2013-10-15 15:39:04 -070010#ifndef NDNBOOST_RANGE_ALGORITHM_EQUAL_HPP_INCLUDED
11#define NDNBOOST_RANGE_ALGORITHM_EQUAL_HPP_INCLUDED
Jeff Thompsonef2d5a42013-08-22 19:09:24 -070012
13#include <ndnboost/config.hpp>
14#include <ndnboost/range/concepts.hpp>
15#include <iterator>
16
17namespace ndnboost
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 {
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700136 NDNBOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1;
137 NDNBOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2;
Jeff Thompsonef2d5a42013-08-22 19:09:24 -0700138
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 {
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700151 NDNBOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1;
152 NDNBOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2;
Jeff Thompsonef2d5a42013-08-22 19:09:24 -0700153
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 {
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700172 NDNBOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> ));
173 NDNBOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> ));
Jeff Thompsonef2d5a42013-08-22 19:09:24 -0700174
175 return ::ndnboost::range_detail::equal(
176 ::ndnboost::begin(rng1), ::ndnboost::end(rng1),
177 ::ndnboost::begin(rng2), ::ndnboost::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 {
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700185 NDNBOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> ));
186 NDNBOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> ));
Jeff Thompsonef2d5a42013-08-22 19:09:24 -0700187
188 return ::ndnboost::range_detail::equal(
189 ::ndnboost::begin(rng1), ::ndnboost::end(rng1),
190 ::ndnboost::begin(rng2), ::ndnboost::end(rng2),
191 pred);
192 }
193
194 } // namespace range
195 using ::ndnboost::range::equal;
196} // namespace ndnboost
197
198#endif // include guard