summaryrefslogtreecommitdiff
path: root/boost/test/utils/algorithm.hpp
blob: 7f16816c3a91ba062ec90e6e100d14ee0da6ead7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
//  (C) Copyright Gennadiy Rozental 2001.
//  Distributed under the Boost Software License, Version 1.0.
//  (See accompanying file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)

//  See http://www.boost.org/libs/test for the library home page.
//
/// @file
/// Addition to STL algorithms
// ***************************************************************************

#ifndef BOOST_TEST_UTILS_ALGORITHM_HPP
#define BOOST_TEST_UTILS_ALGORITHM_HPP

// STL
#include <utility>
#include <algorithm> // std::find
#include <functional> // std::bind1st or std::bind

#include <boost/test/detail/suppress_warnings.hpp>

#ifdef BOOST_NO_CXX98_BINDERS
#define BOOST_TEST_BIND1ST(F,A) std::bind( (F), (A), std::placeholders::_1 )
#else
#define BOOST_TEST_BIND1ST(F,A) std::bind1st( (F), (A) )
#endif

//____________________________________________________________________________//

namespace boost {
namespace unit_test {
namespace utils {

/// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
/// of iterators, first pointing to the mismatch position in first collection, second iterator in second one
///
/// @param first1 - first collection begin iterator
/// @param last1 - first collection end iterator
/// @param first2 - second collection begin iterator
/// @param last2 - second collection end iterator
template <class InputIter1, class InputIter2>
inline std::pair<InputIter1, InputIter2>
mismatch( InputIter1 first1, InputIter1 last1,
          InputIter2 first2, InputIter2 last2 )
{
    while( first1 != last1 && first2 != last2 && *first1 == *first2 ) {
        ++first1;
        ++first2;
    }

    return std::pair<InputIter1, InputIter2>(first1, first2);
}

//____________________________________________________________________________//

/// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
/// of iterators, first pointing to the mismatch position in first collection, second iterator in second one. This algorithms
/// uses supplied predicate for collection elements comparison
///
/// @param first1 - first collection begin iterator
/// @param last1 - first collection end iterator
/// @param first2 - second collection begin iterator
/// @param last2 - second collection end iterator
/// @param pred - predicate to be used for search
template <class InputIter1, class InputIter2, class Predicate>
inline std::pair<InputIter1, InputIter2>
mismatch( InputIter1 first1, InputIter1 last1,
          InputIter2 first2, InputIter2 last2,
          Predicate pred )
{
    while( first1 != last1 && first2 != last2 && pred( *first1, *first2 ) ) {
        ++first1;
        ++first2;
    }

    return std::pair<InputIter1, InputIter2>(first1, first2);
}

//____________________________________________________________________________//

/// @brief this algorithm search through first collection for first element that does not belong a second one
///
/// @param first1 - first collection begin iterator
/// @param last1 - first collection end iterator
/// @param first2 - second collection begin iterator
/// @param last2 - second collection end iterator
template<class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator1
find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
                   ForwardIterator2 first2, ForwardIterator2 last2 )
{
    while( first1 != last1 ) {
        if( std::find( first2, last2, *first1 ) == last2 )
            break;
        ++first1;
    }

    return first1;
}

//____________________________________________________________________________//

/// @brief this algorithm search through first collection for first element that does not satisfy binary
/// predicate in conjunction will any element in second collection
///
/// @param first1 - first collection begin iterator
/// @param last1 - first collection end iterator
/// @param first2 - second collection begin iterator
/// @param last2 - second collection end iterator
/// @param pred - predicate to be used for search
template<class ForwardIterator1, class ForwardIterator2, class Predicate>
inline ForwardIterator1
find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
                   ForwardIterator2 first2, ForwardIterator2 last2,
                   Predicate pred )
{
    while( first1 != last1 ) {
        if( std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *first1 ) ) == last2 )
            break;
        ++first1;
    }

    return first1;
}

//____________________________________________________________________________//

/// @brief this algorithm search through first collection for last element that belongs to a second one
///
/// @param first1 - first collection begin iterator
/// @param last1 - first collection end iterator
/// @param first2 - second collection begin iterator
/// @param last2 - second collection end iterator
template<class BidirectionalIterator1, class ForwardIterator2>
inline BidirectionalIterator1
find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
              ForwardIterator2 first2, ForwardIterator2 last2 )
{
    if( first1 == last1 || first2 == last2 )
        return last1;

    BidirectionalIterator1 it1 = last1;
    while( --it1 != first1 && std::find( first2, last2, *it1 ) == last2 ) {}

    return it1 == first1 && std::find( first2, last2, *it1 ) == last2 ? last1 : it1;
}

//____________________________________________________________________________//

/// @brief this algorithm search through first collection for last element that satisfy binary
/// predicate in conjunction will at least one element in second collection
///
/// @param first1 - first collection begin iterator
/// @param last1 - first collection end iterator
/// @param first2 - second collection begin iterator
/// @param last2 - second collection end iterator
/// @param pred - predicate to be used for search
template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
inline BidirectionalIterator1
find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
              ForwardIterator2 first2, ForwardIterator2 last2,
              Predicate pred )
{
    if( first1 == last1 || first2 == last2 )
        return last1;

    BidirectionalIterator1 it1 = last1;
    while( --it1 != first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) == last2 ) {}

    return it1 == first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) == last2 ? last1 : it1;
}

//____________________________________________________________________________//

/// @brief this algorithm search through first collection for last element that does not belong to a second one
///
/// @param first1 - first collection begin iterator
/// @param last1 - first collection end iterator
/// @param first2 - second collection begin iterator
/// @param last2 - second collection end iterator
template<class BidirectionalIterator1, class ForwardIterator2>
inline BidirectionalIterator1
find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
                  ForwardIterator2 first2, ForwardIterator2 last2 )
{
    if( first1 == last1 || first2 == last2 )
        return last1;

    BidirectionalIterator1 it1 = last1;
    while( --it1 != first1 && std::find( first2, last2, *it1 ) != last2 ) {}

    return it1 == first1 && std::find( first2, last2, *it1 ) != last2 ? last1 : it1;
}

//____________________________________________________________________________//

/// @brief this algorithm search through first collection for last element that does not satisfy binary
/// predicate in conjunction will any element in second collection
///
/// @param first1 - first collection begin iterator
/// @param last1 - first collection end iterator
/// @param first2 - second collection begin iterator
/// @param last2 - second collection end iterator
/// @param pred - predicate to be used for search
template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
inline BidirectionalIterator1
find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
                  ForwardIterator2 first2, ForwardIterator2 last2,
                  Predicate pred )
{
    if( first1 == last1 || first2 == last2 )
        return last1;

    BidirectionalIterator1 it1 = last1;
    while( --it1 != first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) != last2 ) {}

    return it1 == first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) == last2 ? last1 : it1;
}

//____________________________________________________________________________//


/// @brief This algorithm replaces all occurrences of a set of substrings by another substrings
///
/// @param str - string of operation
/// @param first1 - iterator to the beginning of the substrings to replace
/// @param last1 - iterator to the end of the substrings to replace
/// @param first2 - iterator to the beginning of the substrings to replace with
/// @param last2 - iterator to the end of the substrings to replace with
template<class StringClass, class ForwardIterator>
inline StringClass
replace_all_occurrences_of( StringClass str,
                            ForwardIterator first1, ForwardIterator last1,
                            ForwardIterator first2, ForwardIterator last2)
{
    for(; first1 != last1 && first2 != last2; ++first1, ++first2) {
        std::size_t found = str.find( *first1 );
        while( found != StringClass::npos ) {
            str.replace(found, first1->size(), *first2 );
            found = str.find( *first1, found + first2->size() );
        }
    }

    return str;
}

/// @brief This algorithm replaces all occurrences of a string with basic wildcards
/// with another (optionally containing wildcards as well).
///
/// @param str - string to transform
/// @param it_string_to_find - iterator to the beginning of the substrings to replace
/// @param it_string_to_find_end - iterator to the end of the substrings to replace
/// @param it_string_to_replace - iterator to the beginning of the substrings to replace with
/// @param it_string_to_replace_end - iterator to the end of the substrings to replace with
///
/// The wildcard is the symbol '*'. Only a unique wildcard per string is supported. The replacement
/// string may also contain a wildcard, in which case it is considered as a placeholder to the content
/// of the wildcard in the source string.
/// Example:
/// - In order to replace the occurrences of @c 'time=\"some-variable-value\"' to a constant string,
///   one may use @c 'time=\"*\"' as the string to search for, and 'time=\"0.0\"' as the replacement string.
/// - In order to replace the occurrences of 'file.cpp(XX)' per 'file.cpp:XX', where XX is a variable to keep,
///   on may use @c 'file.cpp(*)' as the string to search for, and 'file.cpp:*' as the replacement string.
template<class StringClass, class ForwardIterator>
inline StringClass
replace_all_occurrences_with_wildcards(
    StringClass str,
    ForwardIterator it_string_to_find, ForwardIterator it_string_to_find_end,
    ForwardIterator it_string_to_replace, ForwardIterator it_string_to_replace_end)
{
    for(; it_string_to_find != it_string_to_find_end && it_string_to_replace != it_string_to_replace_end;
        ++it_string_to_find, ++ it_string_to_replace) {

        std::size_t wildcard_pos = it_string_to_find->find("*");
        if(wildcard_pos == StringClass::npos) {
            ForwardIterator it_to_find_current_end(it_string_to_find);
            ForwardIterator it_to_replace_current_end(it_string_to_replace);
            str = replace_all_occurrences_of(
                str,
                it_string_to_find, ++it_to_find_current_end,
                it_string_to_replace, ++it_to_replace_current_end);
            continue;
        }

        std::size_t wildcard_pos_replace = it_string_to_replace->find("*");

        std::size_t found_begin = str.find( it_string_to_find->substr(0, wildcard_pos) );
        while( found_begin != StringClass::npos ) {
            std::size_t found_end = str.find(it_string_to_find->substr(wildcard_pos+1), found_begin + wildcard_pos + 1); // to simplify
            if( found_end != StringClass::npos ) {

                if( wildcard_pos_replace == StringClass::npos ) {
                    StringClass replace_content = *it_string_to_replace;
                    str.replace(
                        found_begin,
                        found_end + (it_string_to_find->size() - wildcard_pos - 1 ) - found_begin,
                        replace_content);
                } else {
                    StringClass replace_content =
                        it_string_to_replace->substr(0, wildcard_pos_replace)
                        + str.substr(found_begin + wildcard_pos,
                                     found_end - found_begin - wildcard_pos)
                        + it_string_to_replace->substr(wildcard_pos_replace+1) ;
                    str.replace(
                        found_begin,
                        found_end + (it_string_to_find->size() - wildcard_pos - 1 ) - found_begin,
                        replace_content);

                }
            }

            // may adapt the restart to the replacement and be more efficient
            found_begin = str.find( it_string_to_find->substr(0, wildcard_pos), found_begin + 1 );
       }
    }

    return str;
}

} // namespace utils
} // namespace unit_test
} // namespace boost

#include <boost/test/detail/enable_warnings.hpp>

#endif // BOOST_TEST_UTILS_ALGORITHM_HPP