1 // (C) Copyright Gennadiy Rozental 2004-2014.
2 // Distributed under the Boost Software License, Version 1.0.
3 // (See accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5
6 // See http://www.boost.org/libs/test for the library home page.
7 //
8 /// @file
9 /// Addition to STL algorithms
10 // ***************************************************************************
11
12 #ifndef BOOST_TEST_UTILS_ALGORITHM_HPP
13 #define BOOST_TEST_UTILS_ALGORITHM_HPP
14
15 // STL
16 #include <utility>
17 #include <algorithm> // std::find
18 #include <functional> // std::bind1st
19
20 #include <boost/test/detail/suppress_warnings.hpp>
21
22 //____________________________________________________________________________//
23
24 namespace boost {
25
26 namespace unit_test {
27
28 /// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
29 /// of iterators, first pointing to the mismatch position in first collection, second iterator in second one
30 ///
31 /// @param first1 - first collection begin iterator
32 /// @param last1 - first collection end iterator
33 /// @param first2 - second collection begin iterator
34 /// @param last2 - second collection end iterator
35 template <class InputIter1, class InputIter2>
36 inline std::pair<InputIter1, InputIter2>
mismatch(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2)37 mismatch( InputIter1 first1, InputIter1 last1,
38 InputIter2 first2, InputIter2 last2 )
39 {
40 while( first1 != last1 && first2 != last2 && *first1 == *first2 ) {
41 ++first1;
42 ++first2;
43 }
44
45 return std::pair<InputIter1, InputIter2>(first1, first2);
46 }
47
48 //____________________________________________________________________________//
49
50 /// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
51 /// of iterators, first pointing to the mismatch position in first collection, second iterator in second one. This algorithms
52 /// uses supplied predicate for collection elements comparison
53 ///
54 /// @param first1 - first collection begin iterator
55 /// @param last1 - first collection end iterator
56 /// @param first2 - second collection begin iterator
57 /// @param last2 - second collection end iterator
58 /// @param pred - predicate to be used for search
59 template <class InputIter1, class InputIter2, class Predicate>
60 inline std::pair<InputIter1, InputIter2>
mismatch(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2,Predicate pred)61 mismatch( InputIter1 first1, InputIter1 last1,
62 InputIter2 first2, InputIter2 last2,
63 Predicate pred )
64 {
65 while( first1 != last1 && first2 != last2 && pred( *first1, *first2 ) ) {
66 ++first1;
67 ++first2;
68 }
69
70 return std::pair<InputIter1, InputIter2>(first1, first2);
71 }
72
73 //____________________________________________________________________________//
74
75 /// @brief this algorithm search through first collection for first element that does not belong a second one
76 ///
77 /// @param first1 - first collection begin iterator
78 /// @param last1 - first collection end iterator
79 /// @param first2 - second collection begin iterator
80 /// @param last2 - second collection end iterator
81 template<class ForwardIterator1, class ForwardIterator2>
82 inline ForwardIterator1
find_first_not_of(ForwardIterator1 first1,ForwardIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2)83 find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
84 ForwardIterator2 first2, ForwardIterator2 last2 )
85 {
86 while( first1 != last1 ) {
87 if( std::find( first2, last2, *first1 ) == last2 )
88 break;
89 ++first1;
90 }
91
92 return first1;
93 }
94
95 //____________________________________________________________________________//
96
97 /// @brief this algorithm search through first collection for first element that does not satisfy binary
98 /// predicate in conjunction will any element in second collection
99 ///
100 /// @param first1 - first collection begin iterator
101 /// @param last1 - first collection end iterator
102 /// @param first2 - second collection begin iterator
103 /// @param last2 - second collection end iterator
104 /// @param pred - predicate to be used for search
105 template<class ForwardIterator1, class ForwardIterator2, class Predicate>
106 inline ForwardIterator1
find_first_not_of(ForwardIterator1 first1,ForwardIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2,Predicate pred)107 find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
108 ForwardIterator2 first2, ForwardIterator2 last2,
109 Predicate pred )
110 {
111 while( first1 != last1 ) {
112 if( std::find_if( first2, last2, std::bind1st( pred, *first1 ) ) == last2 )
113 break;
114 ++first1;
115 }
116
117 return first1;
118 }
119
120 //____________________________________________________________________________//
121
122 /// @brief this algorithm search through first collection for last element that belongs to a second one
123 ///
124 /// @param first1 - first collection begin iterator
125 /// @param last1 - first collection end iterator
126 /// @param first2 - second collection begin iterator
127 /// @param last2 - second collection end iterator
128 template<class BidirectionalIterator1, class ForwardIterator2>
129 inline BidirectionalIterator1
find_last_of(BidirectionalIterator1 first1,BidirectionalIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2)130 find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
131 ForwardIterator2 first2, ForwardIterator2 last2 )
132 {
133 if( first1 == last1 || first2 == last2 )
134 return last1;
135
136 BidirectionalIterator1 it1 = last1;
137 while( --it1 != first1 && std::find( first2, last2, *it1 ) == last2 ) {}
138
139 return it1 == first1 && std::find( first2, last2, *it1 ) == last2 ? last1 : it1;
140 }
141
142 //____________________________________________________________________________//
143
144 /// @brief this algorithm search through first collection for last element that satisfy binary
145 /// predicate in conjunction will at least one element in second collection
146 ///
147 /// @param first1 - first collection begin iterator
148 /// @param last1 - first collection end iterator
149 /// @param first2 - second collection begin iterator
150 /// @param last2 - second collection end iterator
151 /// @param pred - predicate to be used for search
152 template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
153 inline BidirectionalIterator1
find_last_of(BidirectionalIterator1 first1,BidirectionalIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2,Predicate pred)154 find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
155 ForwardIterator2 first2, ForwardIterator2 last2,
156 Predicate pred )
157 {
158 if( first1 == last1 || first2 == last2 )
159 return last1;
160
161 BidirectionalIterator1 it1 = last1;
162 while( --it1 != first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) == last2 ) {}
163
164 return it1 == first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) == last2 ? last1 : it1;
165 }
166
167 //____________________________________________________________________________//
168
169 /// @brief this algorithm search through first collection for last element that does not belong to a second one
170 ///
171 /// @param first1 - first collection begin iterator
172 /// @param last1 - first collection end iterator
173 /// @param first2 - second collection begin iterator
174 /// @param last2 - second collection end iterator
175 template<class BidirectionalIterator1, class ForwardIterator2>
176 inline BidirectionalIterator1
find_last_not_of(BidirectionalIterator1 first1,BidirectionalIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2)177 find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
178 ForwardIterator2 first2, ForwardIterator2 last2 )
179 {
180 if( first1 == last1 || first2 == last2 )
181 return last1;
182
183 BidirectionalIterator1 it1 = last1;
184 while( --it1 != first1 && std::find( first2, last2, *it1 ) != last2 ) {}
185
186 return it1 == first1 && std::find( first2, last2, *it1 ) != last2 ? last1 : it1;
187 }
188
189 //____________________________________________________________________________//
190
191 /// @brief this algorithm search through first collection for last element that does not satisfy binary
192 /// predicate in conjunction will any element in second collection
193 ///
194 /// @param first1 - first collection begin iterator
195 /// @param last1 - first collection end iterator
196 /// @param first2 - second collection begin iterator
197 /// @param last2 - second collection end iterator
198 /// @param pred - predicate to be used for search
199 template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
200 inline BidirectionalIterator1
find_last_not_of(BidirectionalIterator1 first1,BidirectionalIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2,Predicate pred)201 find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
202 ForwardIterator2 first2, ForwardIterator2 last2,
203 Predicate pred )
204 {
205 if( first1 == last1 || first2 == last2 )
206 return last1;
207
208 BidirectionalIterator1 it1 = last1;
209 while( --it1 != first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) != last2 ) {}
210
211 return it1 == first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) == last2 ? last1 : it1;
212 }
213
214 //____________________________________________________________________________//
215
216 } // namespace unit_test
217 } // namespace boost
218
219 #include <boost/test/detail/enable_warnings.hpp>
220
221 #endif // BOOST_TEST_UTILS_ALGORITHM_HPP
222
223
224