1// (C) Copyright Gennadiy Rozental 2001.
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#include <boost/test/detail/config.hpp>
16
17// STL
18#include <utility>
19#include <algorithm> // std::find
20#include <functional> // std::bind1st or std::bind
21
22#include <boost/test/detail/suppress_warnings.hpp>
23
24#ifdef BOOST_NO_CXX98_BINDERS
25#define BOOST_TEST_BIND1ST(F,A) std::bind( (F), (A), std::placeholders::_1 )
26#else
27#define BOOST_TEST_BIND1ST(F,A) std::bind1st( (F), (A) )
28#endif
29
30//____________________________________________________________________________//
31
32namespace boost {
33namespace unit_test {
34namespace utils {
35
36/// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
37/// of iterators, first pointing to the mismatch position in first collection, second iterator in second one
38///
39/// @param first1 - first collection begin iterator
40/// @param last1 - first collection end iterator
41/// @param first2 - second collection begin iterator
42/// @param last2 - second collection end iterator
43template <class InputIter1, class InputIter2>
44inline std::pair<InputIter1, InputIter2>
45mismatch( InputIter1 first1, InputIter1 last1,
46 InputIter2 first2, InputIter2 last2 )
47{
48 while( first1 != last1 && first2 != last2 && *first1 == *first2 ) {
49 ++first1;
50 ++first2;
51 }
52
53 return std::pair<InputIter1, InputIter2>(first1, first2);
54}
55
56//____________________________________________________________________________//
57
58/// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
59/// of iterators, first pointing to the mismatch position in first collection, second iterator in second one. This algorithms
60/// uses supplied predicate for collection elements comparison
61///
62/// @param first1 - first collection begin iterator
63/// @param last1 - first collection end iterator
64/// @param first2 - second collection begin iterator
65/// @param last2 - second collection end iterator
66/// @param pred - predicate to be used for search
67template <class InputIter1, class InputIter2, class Predicate>
68inline std::pair<InputIter1, InputIter2>
69mismatch( InputIter1 first1, InputIter1 last1,
70 InputIter2 first2, InputIter2 last2,
71 Predicate pred )
72{
73 while( first1 != last1 && first2 != last2 && pred( *first1, *first2 ) ) {
74 ++first1;
75 ++first2;
76 }
77
78 return std::pair<InputIter1, InputIter2>(first1, first2);
79}
80
81//____________________________________________________________________________//
82
83/// @brief this algorithm search through first collection for first element that does not belong a second one
84///
85/// @param first1 - first collection begin iterator
86/// @param last1 - first collection end iterator
87/// @param first2 - second collection begin iterator
88/// @param last2 - second collection end iterator
89template<class ForwardIterator1, class ForwardIterator2>
90inline ForwardIterator1
91find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
92 ForwardIterator2 first2, ForwardIterator2 last2 )
93{
94 while( first1 != last1 ) {
95 if( std::find( first2, last2, *first1 ) == last2 )
96 break;
97 ++first1;
98 }
99
100 return first1;
101}
102
103//____________________________________________________________________________//
104
105/// @brief this algorithm search through first collection for first element that does not satisfy binary
106/// predicate in conjunction will any element in second collection
107///
108/// @param first1 - first collection begin iterator
109/// @param last1 - first collection end iterator
110/// @param first2 - second collection begin iterator
111/// @param last2 - second collection end iterator
112/// @param pred - predicate to be used for search
113template<class ForwardIterator1, class ForwardIterator2, class Predicate>
114inline ForwardIterator1
115find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
116 ForwardIterator2 first2, ForwardIterator2 last2,
117 Predicate pred )
118{
119 while( first1 != last1 ) {
120 if( std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *first1 ) ) == last2 )
121 break;
122 ++first1;
123 }
124
125 return first1;
126}
127
128//____________________________________________________________________________//
129
130/// @brief this algorithm search through first collection for last element that belongs to a second one
131///
132/// @param first1 - first collection begin iterator
133/// @param last1 - first collection end iterator
134/// @param first2 - second collection begin iterator
135/// @param last2 - second collection end iterator
136template<class BidirectionalIterator1, class ForwardIterator2>
137inline BidirectionalIterator1
138find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
139 ForwardIterator2 first2, ForwardIterator2 last2 )
140{
141 if( first1 == last1 || first2 == last2 )
142 return last1;
143
144 BidirectionalIterator1 it1 = last1;
145 while( --it1 != first1 && std::find( first2, last2, *it1 ) == last2 ) {}
146
147 return it1 == first1 && std::find( first2, last2, *it1 ) == last2 ? last1 : it1;
148}
149
150//____________________________________________________________________________//
151
152/// @brief this algorithm search through first collection for last element that satisfy binary
153/// predicate in conjunction will at least one element in second collection
154///
155/// @param first1 - first collection begin iterator
156/// @param last1 - first collection end iterator
157/// @param first2 - second collection begin iterator
158/// @param last2 - second collection end iterator
159/// @param pred - predicate to be used for search
160template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
161inline BidirectionalIterator1
162find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
163 ForwardIterator2 first2, ForwardIterator2 last2,
164 Predicate pred )
165{
166 if( first1 == last1 || first2 == last2 )
167 return last1;
168
169 BidirectionalIterator1 it1 = last1;
170 while( --it1 != first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) == last2 ) {}
171
172 return it1 == first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) == last2 ? last1 : it1;
173}
174
175//____________________________________________________________________________//
176
177/// @brief this algorithm search through first collection for last element that does not belong to a second one
178///
179/// @param first1 - first collection begin iterator
180/// @param last1 - first collection end iterator
181/// @param first2 - second collection begin iterator
182/// @param last2 - second collection end iterator
183template<class BidirectionalIterator1, class ForwardIterator2>
184inline BidirectionalIterator1
185find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
186 ForwardIterator2 first2, ForwardIterator2 last2 )
187{
188 if( first1 == last1 || first2 == last2 )
189 return last1;
190
191 BidirectionalIterator1 it1 = last1;
192 while( --it1 != first1 && std::find( first2, last2, *it1 ) != last2 ) {}
193
194 return it1 == first1 && std::find( first2, last2, *it1 ) != last2 ? last1 : it1;
195}
196
197//____________________________________________________________________________//
198
199/// @brief this algorithm search through first collection for last element that does not satisfy binary
200/// predicate in conjunction will any element in second collection
201///
202/// @param first1 - first collection begin iterator
203/// @param last1 - first collection end iterator
204/// @param first2 - second collection begin iterator
205/// @param last2 - second collection end iterator
206/// @param pred - predicate to be used for search
207template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
208inline BidirectionalIterator1
209find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
210 ForwardIterator2 first2, ForwardIterator2 last2,
211 Predicate pred )
212{
213 if( first1 == last1 || first2 == last2 )
214 return last1;
215
216 BidirectionalIterator1 it1 = last1;
217 while( --it1 != first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) != last2 ) {}
218
219 return it1 == first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) == last2 ? last1 : it1;
220}
221
222//____________________________________________________________________________//
223
224
225/// @brief This algorithm replaces all occurrences of a set of substrings by another substrings
226///
227/// @param str - string of operation
228/// @param first1 - iterator to the beginning of the substrings to replace
229/// @param last1 - iterator to the end of the substrings to replace
230/// @param first2 - iterator to the beginning of the substrings to replace with
231/// @param last2 - iterator to the end of the substrings to replace with
232template<class StringClass, class ForwardIterator>
233inline StringClass
234replace_all_occurrences_of( StringClass str,
235 ForwardIterator first1, ForwardIterator last1,
236 ForwardIterator first2, ForwardIterator last2)
237{
238 for(; first1 != last1 && first2 != last2; ++first1, ++first2) {
239 std::size_t found = str.find( *first1 );
240 while( found != StringClass::npos ) {
241 str.replace(found, first1->size(), *first2 );
242 found = str.find( *first1, found + first2->size() );
243 }
244 }
245
246 return str;
247}
248
249/// @brief This algorithm replaces all occurrences of a string with basic wildcards
250/// with another (optionally containing wildcards as well).
251///
252/// @param str - string to transform
253/// @param it_string_to_find - iterator to the beginning of the substrings to replace
254/// @param it_string_to_find_end - iterator to the end of the substrings to replace
255/// @param it_string_to_replace - iterator to the beginning of the substrings to replace with
256/// @param it_string_to_replace_end - iterator to the end of the substrings to replace with
257///
258/// The wildcard is the symbol '*'. Only a unique wildcard per string is supported. The replacement
259/// string may also contain a wildcard, in which case it is considered as a placeholder to the content
260/// of the wildcard in the source string.
261/// Example:
262/// - In order to replace the occurrences of @c 'time=\"some-variable-value\"' to a constant string,
263/// one may use @c 'time=\"*\"' as the string to search for, and 'time=\"0.0\"' as the replacement string.
264/// - In order to replace the occurrences of 'file.cpp(XX)' per 'file.cpp:XX', where XX is a variable to keep,
265/// on may use @c 'file.cpp(*)' as the string to search for, and 'file.cpp:*' as the replacement string.
266template<class StringClass, class ForwardIterator>
267inline StringClass
268replace_all_occurrences_with_wildcards(
269 StringClass str,
270 ForwardIterator it_string_to_find, ForwardIterator it_string_to_find_end,
271 ForwardIterator it_string_to_replace, ForwardIterator it_string_to_replace_end)
272{
273 for(; it_string_to_find != it_string_to_find_end && it_string_to_replace != it_string_to_replace_end;
274 ++it_string_to_find, ++ it_string_to_replace) {
275
276 std::size_t wildcard_pos = it_string_to_find->find("*");
277 if(wildcard_pos == StringClass::npos) {
278 ForwardIterator it_to_find_current_end(it_string_to_find);
279 ForwardIterator it_to_replace_current_end(it_string_to_replace);
280 str = replace_all_occurrences_of(
281 str,
282 it_string_to_find, ++it_to_find_current_end,
283 it_string_to_replace, ++it_to_replace_current_end);
284 continue;
285 }
286
287 std::size_t wildcard_pos_replace = it_string_to_replace->find("*");
288
289 std::size_t found_begin = str.find( it_string_to_find->substr(0, wildcard_pos) );
290 while( found_begin != StringClass::npos ) {
291 std::size_t found_end = str.find(it_string_to_find->substr(wildcard_pos+1), found_begin + wildcard_pos + 1); // to simplify
292 if( found_end != StringClass::npos ) {
293
294 if( wildcard_pos_replace == StringClass::npos ) {
295 StringClass replace_content = *it_string_to_replace;
296 str.replace(
297 found_begin,
298 found_end + (it_string_to_find->size() - wildcard_pos - 1 ) - found_begin,
299 replace_content);
300 } else {
301 StringClass replace_content =
302 it_string_to_replace->substr(0, wildcard_pos_replace)
303 + str.substr(found_begin + wildcard_pos,
304 found_end - found_begin - wildcard_pos)
305 + it_string_to_replace->substr(wildcard_pos_replace+1) ;
306 str.replace(
307 found_begin,
308 found_end + (it_string_to_find->size() - wildcard_pos - 1 ) - found_begin,
309 replace_content);
310
311 }
312 }
313
314 // may adapt the restart to the replacement and be more efficient
315 found_begin = str.find( it_string_to_find->substr(0, wildcard_pos), found_begin + 1 );
316 }
317 }
318
319 return str;
320}
321
322} // namespace utils
323} // namespace unit_test
324} // namespace boost
325
326#include <boost/test/detail/enable_warnings.hpp>
327
328#endif // BOOST_TEST_UTILS_ALGORITHM_HPP
329

source code of include/boost/test/utils/algorithm.hpp