test/utils/algorithm.hpp

0001 //  (C) Copyright Gennadiy Rozental 2001.
0002 //  Distributed under the Boost Software License, Version 1.0.
0003 //  (See accompanying file LICENSE_1_0.txt or copy at
0004 //  http://www.boost.org/LICENSE_1_0.txt)
0005
0006 //  See http://www.boost.org/libs/test for the library home page.
0007 //
0008 /// @file
0009 /// Addition to STL algorithms
0010 // ***************************************************************************
0011
0012 #ifndef BOOST_TEST_UTILS_ALGORITHM_HPP
0013 #define BOOST_TEST_UTILS_ALGORITHM_HPP
0014
0015 #include <boost/test/detail/config.hpp>
0016
0017 // STL
0018 #include <utility>
0019 #include <algorithm> // std::find
0020 #include <functional> // std::bind1st or std::bind
0021
0022 #include <boost/test/detail/suppress_warnings.hpp>
0023
0024 #ifdef BOOST_NO_CXX98_BINDERS
0025 #define BOOST_TEST_BIND1ST(F,A) std::bind( (F), (A), std::placeholders::_1 )
0026 #else
0027 #define BOOST_TEST_BIND1ST(F,A) std::bind1st( (F), (A) )
0028 #endif
0029
0030 //____________________________________________________________________________//
0031
0032 namespace boost {
0033 namespace unit_test {
0034 namespace utils {
0035
0036 /// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
0037 /// of iterators, first pointing to the mismatch position in first collection, second iterator in second one
0038 ///
0039 /// @param first1 - first collection begin iterator
0040 /// @param last1 - first collection end iterator
0041 /// @param first2 - second collection begin iterator
0042 /// @param last2 - second collection end iterator
0043 template <class InputIter1, class InputIter2>
0044 inline std::pair<InputIter1, InputIter2>
0045 mismatch( InputIter1 first1, InputIter1 last1,
0046           InputIter2 first2, InputIter2 last2 )
0047 {
0048     while( first1 != last1 && first2 != last2 && *first1 == *first2 ) {
0049         ++first1;
0050         ++first2;
0051     }
0052
0053     return std::pair<InputIter1, InputIter2>(first1, first2);
0054 }
0055
0056 //____________________________________________________________________________//
0057
0058 /// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
0059 /// of iterators, first pointing to the mismatch position in first collection, second iterator in second one. This algorithms
0060 /// uses supplied predicate for collection elements comparison
0061 ///
0062 /// @param first1 - first collection begin iterator
0063 /// @param last1 - first collection end iterator
0064 /// @param first2 - second collection begin iterator
0065 /// @param last2 - second collection end iterator
0066 /// @param pred - predicate to be used for search
0067 template <class InputIter1, class InputIter2, class Predicate>
0068 inline std::pair<InputIter1, InputIter2>
0069 mismatch( InputIter1 first1, InputIter1 last1,
0070           InputIter2 first2, InputIter2 last2,
0071           Predicate pred )
0072 {
0073     while( first1 != last1 && first2 != last2 && pred( *first1, *first2 ) ) {
0074         ++first1;
0075         ++first2;
0076     }
0077
0078     return std::pair<InputIter1, InputIter2>(first1, first2);
0079 }
0080
0081 //____________________________________________________________________________//
0082
0083 /// @brief this algorithm search through first collection for first element that does not belong a second one
0084 ///
0085 /// @param first1 - first collection begin iterator
0086 /// @param last1 - first collection end iterator
0087 /// @param first2 - second collection begin iterator
0088 /// @param last2 - second collection end iterator
0089 template<class ForwardIterator1, class ForwardIterator2>
0090 inline ForwardIterator1
0091 find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
0092                    ForwardIterator2 first2, ForwardIterator2 last2 )
0093 {
0094     while( first1 != last1 ) {
0095         if( std::find( first2, last2, *first1 ) == last2 )
0096             break;
0097         ++first1;
0098     }
0099
0100     return first1;
0101 }
0102
0103 //____________________________________________________________________________//
0104
0105 /// @brief this algorithm search through first collection for first element that does not satisfy binary
0106 /// predicate in conjunction will any element in second collection
0107 ///
0108 /// @param first1 - first collection begin iterator
0109 /// @param last1 - first collection end iterator
0110 /// @param first2 - second collection begin iterator
0111 /// @param last2 - second collection end iterator
0112 /// @param pred - predicate to be used for search
0113 template<class ForwardIterator1, class ForwardIterator2, class Predicate>
0114 inline ForwardIterator1
0115 find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
0116                    ForwardIterator2 first2, ForwardIterator2 last2,
0117                    Predicate pred )
0118 {
0119     while( first1 != last1 ) {
0120         if( std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *first1 ) ) == last2 )
0121             break;
0122         ++first1;
0123     }
0124
0125     return first1;
0126 }
0127
0128 //____________________________________________________________________________//
0129
0130 /// @brief this algorithm search through first collection for last element that belongs to a second one
0131 ///
0132 /// @param first1 - first collection begin iterator
0133 /// @param last1 - first collection end iterator
0134 /// @param first2 - second collection begin iterator
0135 /// @param last2 - second collection end iterator
0136 template<class BidirectionalIterator1, class ForwardIterator2>
0137 inline BidirectionalIterator1
0138 find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
0139               ForwardIterator2 first2, ForwardIterator2 last2 )
0140 {
0141     if( first1 == last1 || first2 == last2 )
0142         return last1;
0143
0144     BidirectionalIterator1 it1 = last1;
0145     while( --it1 != first1 && std::find( first2, last2, *it1 ) == last2 ) {}
0146
0147     return it1 == first1 && std::find( first2, last2, *it1 ) == last2 ? last1 : it1;
0148 }
0149
0150 //____________________________________________________________________________//
0151
0152 /// @brief this algorithm search through first collection for last element that satisfy binary
0153 /// predicate in conjunction will at least one element in second collection
0154 ///
0155 /// @param first1 - first collection begin iterator
0156 /// @param last1 - first collection end iterator
0157 /// @param first2 - second collection begin iterator
0158 /// @param last2 - second collection end iterator
0159 /// @param pred - predicate to be used for search
0160 template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
0161 inline BidirectionalIterator1
0162 find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
0163               ForwardIterator2 first2, ForwardIterator2 last2,
0164               Predicate pred )
0165 {
0166     if( first1 == last1 || first2 == last2 )
0167         return last1;
0168
0169     BidirectionalIterator1 it1 = last1;
0170     while( --it1 != first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) == last2 ) {}
0171
0172     return it1 == first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) == last2 ? last1 : it1;
0173 }
0174
0175 //____________________________________________________________________________//
0176
0177 /// @brief this algorithm search through first collection for last element that does not belong to a second one
0178 ///
0179 /// @param first1 - first collection begin iterator
0180 /// @param last1 - first collection end iterator
0181 /// @param first2 - second collection begin iterator
0182 /// @param last2 - second collection end iterator
0183 template<class BidirectionalIterator1, class ForwardIterator2>
0184 inline BidirectionalIterator1
0185 find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
0186                   ForwardIterator2 first2, ForwardIterator2 last2 )
0187 {
0188     if( first1 == last1 || first2 == last2 )
0189         return last1;
0190
0191     BidirectionalIterator1 it1 = last1;
0192     while( --it1 != first1 && std::find( first2, last2, *it1 ) != last2 ) {}
0193
0194     return it1 == first1 && std::find( first2, last2, *it1 ) != last2 ? last1 : it1;
0195 }
0196
0197 //____________________________________________________________________________//
0198
0199 /// @brief this algorithm search through first collection for last element that does not satisfy binary
0200 /// predicate in conjunction will any element in second collection
0201 ///
0202 /// @param first1 - first collection begin iterator
0203 /// @param last1 - first collection end iterator
0204 /// @param first2 - second collection begin iterator
0205 /// @param last2 - second collection end iterator
0206 /// @param pred - predicate to be used for search
0207 template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
0208 inline BidirectionalIterator1
0209 find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
0210                   ForwardIterator2 first2, ForwardIterator2 last2,
0211                   Predicate pred )
0212 {
0213     if( first1 == last1 || first2 == last2 )
0214         return last1;
0215
0216     BidirectionalIterator1 it1 = last1;
0217     while( --it1 != first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) != last2 ) {}
0218
0219     return it1 == first1 && std::find_if( first2, last2, BOOST_TEST_BIND1ST( pred, *it1 ) ) == last2 ? last1 : it1;
0220 }
0221
0222 //____________________________________________________________________________//
0223
0224
0225 /// @brief This algorithm replaces all occurrences of a set of substrings by another substrings
0226 ///
0227 /// @param str - string of operation
0228 /// @param first1 - iterator to the beginning of the substrings to replace
0229 /// @param last1 - iterator to the end of the substrings to replace
0230 /// @param first2 - iterator to the beginning of the substrings to replace with
0231 /// @param last2 - iterator to the end of the substrings to replace with
0232 template<class StringClass, class ForwardIterator>
0233 inline StringClass
0234 replace_all_occurrences_of( StringClass str,
0235                             ForwardIterator first1, ForwardIterator last1,
0236                             ForwardIterator first2, ForwardIterator last2)
0237 {
0238     for(; first1 != last1 && first2 != last2; ++first1, ++first2) {
0239         std::size_t found = str.find( *first1 );
0240         while( found != StringClass::npos ) {
0241             str.replace(found, first1->size(), *first2 );
0242             found = str.find( *first1, found + first2->size() );
0243         }
0244     }
0245
0246     return str;
0247 }
0248
0249 /// @brief This algorithm replaces all occurrences of a string with basic wildcards
0250 /// with another (optionally containing wildcards as well).
0251 ///
0252 /// @param str - string to transform
0253 /// @param it_string_to_find - iterator to the beginning of the substrings to replace
0254 /// @param it_string_to_find_end - iterator to the end of the substrings to replace
0255 /// @param it_string_to_replace - iterator to the beginning of the substrings to replace with
0256 /// @param it_string_to_replace_end - iterator to the end of the substrings to replace with
0257 ///
0258 /// The wildcard is the symbol '*'. Only a unique wildcard per string is supported. The replacement
0259 /// string may also contain a wildcard, in which case it is considered as a placeholder to the content
0260 /// of the wildcard in the source string.
0261 /// Example:
0262 /// - In order to replace the occurrences of @c 'time=\"some-variable-value\"' to a constant string,
0263 ///   one may use @c 'time=\"*\"' as the string to search for, and 'time=\"0.0\"' as the replacement string.
0264 /// - In order to replace the occurrences of 'file.cpp(XX)' per 'file.cpp:XX', where XX is a variable to keep,
0265 ///   on may use @c 'file.cpp(*)' as the string to search for, and 'file.cpp:*' as the replacement string.
0266 template<class StringClass, class ForwardIterator>
0267 inline StringClass
0268 replace_all_occurrences_with_wildcards(
0269     StringClass str,
0270     ForwardIterator it_string_to_find, ForwardIterator it_string_to_find_end,
0271     ForwardIterator it_string_to_replace, ForwardIterator it_string_to_replace_end)
0272 {
0273     for(; it_string_to_find != it_string_to_find_end && it_string_to_replace != it_string_to_replace_end;
0274         ++it_string_to_find, ++ it_string_to_replace) {
0275
0276         std::size_t wildcard_pos = it_string_to_find->find("*");
0277         if(wildcard_pos == StringClass::npos) {
0278             ForwardIterator it_to_find_current_end(it_string_to_find);
0279             ForwardIterator it_to_replace_current_end(it_string_to_replace);
0280             str = replace_all_occurrences_of(
0281                 str,
0282                 it_string_to_find, ++it_to_find_current_end,
0283                 it_string_to_replace, ++it_to_replace_current_end);
0284             continue;
0285         }
0286
0287         std::size_t wildcard_pos_replace = it_string_to_replace->find("*");
0288
0289         std::size_t found_begin = str.find( it_string_to_find->substr(0, wildcard_pos) );
0290         while( found_begin != StringClass::npos ) {
0291             std::size_t found_end = str.find(it_string_to_find->substr(wildcard_pos+1), found_begin + wildcard_pos + 1); // to simplify
0292             if( found_end != StringClass::npos ) {
0293
0294                 if( wildcard_pos_replace == StringClass::npos ) {
0295                     StringClass replace_content = *it_string_to_replace;
0296                     str.replace(
0297                         found_begin,
0298                         found_end + (it_string_to_find->size() - wildcard_pos - 1 ) - found_begin,
0299                         replace_content);
0300                 } else {
0301                     StringClass replace_content =
0302                         it_string_to_replace->substr(0, wildcard_pos_replace)
0303                         + str.substr(found_begin + wildcard_pos,
0304                                      found_end - found_begin - wildcard_pos)
0305                         + it_string_to_replace->substr(wildcard_pos_replace+1) ;
0306                     str.replace(
0307                         found_begin,
0308                         found_end + (it_string_to_find->size() - wildcard_pos - 1 ) - found_begin,
0309                         replace_content);
0310
0311                 }
0312             }
0313
0314             // may adapt the restart to the replacement and be more efficient
0315             found_begin = str.find( it_string_to_find->substr(0, wildcard_pos), found_begin + 1 );
0316        }
0317     }
0318
0319     return str;
0320 }
0321
0322 } // namespace utils
0323 } // namespace unit_test
0324 } // namespace boost
0325
0326 #include <boost/test/detail/enable_warnings.hpp>
0327
0328 #endif // BOOST_TEST_UTILS_ALGORITHM_HPP