ceph/src/boost/libs/test/include/boost/test/utils/algorithm.hpp

   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 // 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 namespace unit_test {
  26 namespace utils {
  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>
  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>
  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
  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
 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
 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
 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
 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
 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
 217 /// @brief This algorithm replaces all occurrences of a set of substrings by another substrings
 218 ///
 219 /// @param str - string of operation
 220 /// @param first1 - iterator to the beginning of the substrings to replace
 221 /// @param last1 - iterator to the end of the substrings to replace
 222 /// @param first2 - iterator to the beginning of the substrings to replace with
 223 /// @param last2 - iterator to the end of the substrings to replace with
 224 template<class StringClass, class ForwardIterator>
 225 inline StringClass
 226 replace_all_occurrences_of( StringClass str,
 227                             ForwardIterator first1, ForwardIterator last1,
 228                             ForwardIterator first2, ForwardIterator last2)
 229 {
 230     for(; first1 != last1 && first2 != last2; ++first1, ++first2) {
 231         std::size_t found = str.find( *first1 );
 232         while( found != StringClass::npos ) {
 233             str.replace(found, first1->size(), *first2 );
 234             found = str.find( *first1, found + first2->size() );
 235         }
 236     }
 237
 238     return str;
 239 }
 240
 241 /// @brief This algorithm replaces all occurrences of a string with basic wildcards
 242 /// with another (optionally containing wildcards as well).
 243 ///
 244 /// @param str - string to transform
 245 /// @param it_string_to_find - iterator to the beginning of the substrings to replace
 246 /// @param it_string_to_find_end - iterator to the end of the substrings to replace
 247 /// @param it_string_to_replace - iterator to the beginning of the substrings to replace with
 248 /// @param it_string_to_replace_end - iterator to the end of the substrings to replace with
 249 ///
 250 /// The wildcard is the symbol '*'. Only a unique wildcard per string is supported. The replacement
 251 /// string may also contain a wildcard, in which case it is considered as a placeholder to the content
 252 /// of the wildcard in the source string.
 253 /// Example:
 254 /// - In order to replace the occurrences of @c 'time=\"some-variable-value\"' to a constant string,
 255 ///   one may use @c 'time=\"*\"' as the string to search for, and 'time=\"0.0\"' as the replacement string.
 256 /// - In order to replace the occurrences of 'file.cpp(XX)' per 'file.cpp:XX', where XX is a variable to keep,
 257 ///   on may use @c 'file.cpp(*)' as the string to search for, and 'file.cpp:*' as the replacement string.
 258 template<class StringClass, class ForwardIterator>
 259 inline StringClass
 260 replace_all_occurrences_with_wildcards(
 261     StringClass str,
 262     ForwardIterator it_string_to_find, ForwardIterator it_string_to_find_end,
 263     ForwardIterator it_string_to_replace, ForwardIterator it_string_to_replace_end)
 264 {
 265     for(; it_string_to_find != it_string_to_find_end && it_string_to_replace != it_string_to_replace_end;
 266         ++it_string_to_find, ++ it_string_to_replace) {
 267
 268         std::size_t wildcard_pos = it_string_to_find->find("*");
 269         if(wildcard_pos == StringClass::npos) {
 270             ForwardIterator it_to_find_current_end(it_string_to_find);
 271             ForwardIterator it_to_replace_current_end(it_string_to_replace);
 272             str = replace_all_occurrences_of(
 273                 str,
 274                 it_string_to_find, ++it_to_find_current_end,
 275                 it_string_to_replace, ++it_to_replace_current_end);
 276             continue;
 277         }
 278
 279         std::size_t wildcard_pos_replace = it_string_to_replace->find("*");
 280
 281         std::size_t found_begin = str.find( it_string_to_find->substr(0, wildcard_pos) );
 282         while( found_begin != StringClass::npos ) {
 283             std::size_t found_end = str.find(it_string_to_find->substr(wildcard_pos+1), found_begin + wildcard_pos + 1); // to simplify
 284             if( found_end != StringClass::npos ) {
 285
 286                 if( wildcard_pos_replace == StringClass::npos ) {
 287                     StringClass replace_content = *it_string_to_replace;
 288                     str.replace(
 289                         found_begin,
 290                         found_end + (it_string_to_find->size() - wildcard_pos - 1 ) - found_begin,
 291                         replace_content);
 292                 } else {
 293                     StringClass replace_content =
 294                         it_string_to_replace->substr(0, wildcard_pos_replace)
 295                         + str.substr(found_begin + wildcard_pos,
 296                                      found_end - found_begin - wildcard_pos)
 297                         + it_string_to_replace->substr(wildcard_pos_replace+1) ;
 298                     str.replace(
 299                         found_begin,
 300                         found_end + (it_string_to_find->size() - wildcard_pos - 1 ) - found_begin,
 301                         replace_content);
 302
 303                 }
 304             }
 305
 306             // may adapt the restart to the replacement and be more efficient
 307             found_begin = str.find( it_string_to_find->substr(0, wildcard_pos), found_begin + 1 );
 308        }
 309     }
 310
 311     return str;
 312 }
 313
 314 } // namespace utils
 315 } // namespace unit_test
 316 } // namespace boost
 317
 318 #include <boost/test/detail/enable_warnings.hpp>
 319
 320 #endif // BOOST_TEST_UTILS_ALGORITHM_HPP