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 >
equal_impl(SinglePassTraversalReadableIterator1 first1,SinglePassTraversalReadableIterator1 last1,SinglePassTraversalReadableIterator2 first2,SinglePassTraversalReadableIterator2 last2,IteratorCategoryTag1,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 >
equal_impl(SinglePassTraversalReadableIterator1 first1,SinglePassTraversalReadableIterator1 last1,SinglePassTraversalReadableIterator2 first2,SinglePassTraversalReadableIterator2 last2,BinaryPredicate pred,IteratorCategoryTag1,IteratorCategoryTag2)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 >
equal_impl(RandomAccessTraversalReadableIterator1 first1,RandomAccessTraversalReadableIterator1 last1,RandomAccessTraversalReadableIterator2 first2,RandomAccessTraversalReadableIterator2 last2,std::random_access_iterator_tag,std::random_access_iterator_tag)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 >
equal_impl(RandomAccessTraversalReadableIterator1 first1,RandomAccessTraversalReadableIterator1 last1,RandomAccessTraversalReadableIterator2 first2,RandomAccessTraversalReadableIterator2 last2,BinaryPredicate pred,std::random_access_iterator_tag,std::random_access_iterator_tag)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 >
equal(SinglePassTraversalReadableIterator1 first1,SinglePassTraversalReadableIterator1 last1,SinglePassTraversalReadableIterator2 first2,SinglePassTraversalReadableIterator2 last2)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 >
equal(SinglePassTraversalReadableIterator1 first1,SinglePassTraversalReadableIterator1 last1,SinglePassTraversalReadableIterator2 first2,SinglePassTraversalReadableIterator2 last2,BinaryPredicate pred)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 >
equal(const SinglePassRange1 & rng1,const SinglePassRange2 & rng2)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 >
equal(const SinglePassRange1 & rng1,const SinglePassRange2 & rng2,BinaryPredicate pred)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