1 // Boost string_algo library finder.hpp header file ---------------------------// 2 3 // Copyright Pavol Droba 2002-2006. 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 9 // See http://www.boost.org/ for updates, documentation, and revision history. 10 11 #ifndef BOOST_STRING_FINDER_DETAIL_HPP 12 #define BOOST_STRING_FINDER_DETAIL_HPP 13 14 #include <boost/algorithm/string/config.hpp> 15 #include <boost/algorithm/string/constants.hpp> 16 #include <boost/detail/iterator.hpp> 17 18 #include <boost/range/iterator_range_core.hpp> 19 #include <boost/range/begin.hpp> 20 #include <boost/range/end.hpp> 21 #include <boost/range/empty.hpp> 22 #include <boost/range/as_literal.hpp> 23 24 namespace pdalboost { 25 namespace algorithm { 26 namespace detail { 27 28 29 // find first functor -----------------------------------------------// 30 31 // find a subsequence in the sequence ( functor ) 32 /* 33 Returns a pair <begin,end> marking the subsequence in the sequence. 34 If the find fails, functor returns <End,End> 35 */ 36 template<typename SearchIteratorT,typename PredicateT> 37 struct first_finderF 38 { 39 typedef SearchIteratorT search_iterator_type; 40 41 // Construction 42 template< typename SearchT > first_finderFpdalboost::algorithm::detail::first_finderF43 first_finderF( const SearchT& Search, PredicateT Comp ) : 44 m_Search(::pdalboost::begin(Search), ::pdalboost::end(Search)), m_Comp(Comp) {} first_finderFpdalboost::algorithm::detail::first_finderF45 first_finderF( 46 search_iterator_type SearchBegin, 47 search_iterator_type SearchEnd, 48 PredicateT Comp ) : 49 m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {} 50 51 // Operation 52 template< typename ForwardIteratorT > 53 iterator_range<ForwardIteratorT> operator ()pdalboost::algorithm::detail::first_finderF54 operator()( 55 ForwardIteratorT Begin, 56 ForwardIteratorT End ) const 57 { 58 typedef iterator_range<ForwardIteratorT> result_type; 59 typedef ForwardIteratorT input_iterator_type; 60 61 // Outer loop 62 for(input_iterator_type OuterIt=Begin; 63 OuterIt!=End; 64 ++OuterIt) 65 { 66 // Sanity check 67 if( pdalboost::empty(m_Search) ) 68 return result_type( End, End ); 69 70 input_iterator_type InnerIt=OuterIt; 71 search_iterator_type SubstrIt=m_Search.begin(); 72 for(; 73 InnerIt!=End && SubstrIt!=m_Search.end(); 74 ++InnerIt,++SubstrIt) 75 { 76 if( !( m_Comp(*InnerIt,*SubstrIt) ) ) 77 break; 78 } 79 80 // Substring matching succeeded 81 if ( SubstrIt==m_Search.end() ) 82 return result_type( OuterIt, InnerIt ); 83 } 84 85 return result_type( End, End ); 86 } 87 88 private: 89 iterator_range<search_iterator_type> m_Search; 90 PredicateT m_Comp; 91 }; 92 93 // find last functor -----------------------------------------------// 94 95 // find the last match a subsequence in the sequence ( functor ) 96 /* 97 Returns a pair <begin,end> marking the subsequence in the sequence. 98 If the find fails, returns <End,End> 99 */ 100 template<typename SearchIteratorT, typename PredicateT> 101 struct last_finderF 102 { 103 typedef SearchIteratorT search_iterator_type; 104 typedef first_finderF< 105 search_iterator_type, 106 PredicateT> first_finder_type; 107 108 // Construction 109 template< typename SearchT > last_finderFpdalboost::algorithm::detail::last_finderF110 last_finderF( const SearchT& Search, PredicateT Comp ) : 111 m_Search(::pdalboost::begin(Search), ::pdalboost::end(Search)), m_Comp(Comp) {} last_finderFpdalboost::algorithm::detail::last_finderF112 last_finderF( 113 search_iterator_type SearchBegin, 114 search_iterator_type SearchEnd, 115 PredicateT Comp ) : 116 m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {} 117 118 // Operation 119 template< typename ForwardIteratorT > 120 iterator_range<ForwardIteratorT> operator ()pdalboost::algorithm::detail::last_finderF121 operator()( 122 ForwardIteratorT Begin, 123 ForwardIteratorT End ) const 124 { 125 typedef iterator_range<ForwardIteratorT> result_type; 126 127 if( pdalboost::empty(m_Search) ) 128 return result_type( End, End ); 129 130 typedef BOOST_STRING_TYPENAME pdalboost::detail:: 131 iterator_traits<ForwardIteratorT>::iterator_category category; 132 133 return findit( Begin, End, category() ); 134 } 135 136 private: 137 // forward iterator 138 template< typename ForwardIteratorT > 139 iterator_range<ForwardIteratorT> finditpdalboost::algorithm::detail::last_finderF140 findit( 141 ForwardIteratorT Begin, 142 ForwardIteratorT End, 143 std::forward_iterator_tag ) const 144 { 145 typedef iterator_range<ForwardIteratorT> result_type; 146 147 first_finder_type first_finder( 148 m_Search.begin(), m_Search.end(), m_Comp ); 149 150 result_type M=first_finder( Begin, End ); 151 result_type Last=M; 152 153 while( M ) 154 { 155 Last=M; 156 M=first_finder( ::pdalboost::end(M), End ); 157 } 158 159 return Last; 160 } 161 162 // bidirectional iterator 163 template< typename ForwardIteratorT > 164 iterator_range<ForwardIteratorT> finditpdalboost::algorithm::detail::last_finderF165 findit( 166 ForwardIteratorT Begin, 167 ForwardIteratorT End, 168 std::bidirectional_iterator_tag ) const 169 { 170 typedef iterator_range<ForwardIteratorT> result_type; 171 typedef ForwardIteratorT input_iterator_type; 172 173 // Outer loop 174 for(input_iterator_type OuterIt=End; 175 OuterIt!=Begin; ) 176 { 177 input_iterator_type OuterIt2=--OuterIt; 178 179 input_iterator_type InnerIt=OuterIt2; 180 search_iterator_type SubstrIt=m_Search.begin(); 181 for(; 182 InnerIt!=End && SubstrIt!=m_Search.end(); 183 ++InnerIt,++SubstrIt) 184 { 185 if( !( m_Comp(*InnerIt,*SubstrIt) ) ) 186 break; 187 } 188 189 // Substring matching succeeded 190 if( SubstrIt==m_Search.end() ) 191 return result_type( OuterIt2, InnerIt ); 192 } 193 194 return result_type( End, End ); 195 } 196 197 private: 198 iterator_range<search_iterator_type> m_Search; 199 PredicateT m_Comp; 200 }; 201 202 // find n-th functor -----------------------------------------------// 203 204 // find the n-th match of a subsequence in the sequence ( functor ) 205 /* 206 Returns a pair <begin,end> marking the subsequence in the sequence. 207 If the find fails, returns <End,End> 208 */ 209 template<typename SearchIteratorT, typename PredicateT> 210 struct nth_finderF 211 { 212 typedef SearchIteratorT search_iterator_type; 213 typedef first_finderF< 214 search_iterator_type, 215 PredicateT> first_finder_type; 216 typedef last_finderF< 217 search_iterator_type, 218 PredicateT> last_finder_type; 219 220 // Construction 221 template< typename SearchT > nth_finderFpdalboost::algorithm::detail::nth_finderF222 nth_finderF( 223 const SearchT& Search, 224 int Nth, 225 PredicateT Comp) : 226 m_Search(::pdalboost::begin(Search), ::pdalboost::end(Search)), 227 m_Nth(Nth), 228 m_Comp(Comp) {} nth_finderFpdalboost::algorithm::detail::nth_finderF229 nth_finderF( 230 search_iterator_type SearchBegin, 231 search_iterator_type SearchEnd, 232 int Nth, 233 PredicateT Comp) : 234 m_Search(SearchBegin, SearchEnd), 235 m_Nth(Nth), 236 m_Comp(Comp) {} 237 238 // Operation 239 template< typename ForwardIteratorT > 240 iterator_range<ForwardIteratorT> operator ()pdalboost::algorithm::detail::nth_finderF241 operator()( 242 ForwardIteratorT Begin, 243 ForwardIteratorT End ) const 244 { 245 if(m_Nth>=0) 246 { 247 return find_forward(Begin, End, m_Nth); 248 } 249 else 250 { 251 return find_backward(Begin, End, -m_Nth); 252 } 253 254 } 255 256 private: 257 // Implementation helpers 258 template< typename ForwardIteratorT > 259 iterator_range<ForwardIteratorT> find_forwardpdalboost::algorithm::detail::nth_finderF260 find_forward( 261 ForwardIteratorT Begin, 262 ForwardIteratorT End, 263 unsigned int N) const 264 { 265 typedef iterator_range<ForwardIteratorT> result_type; 266 267 // Sanity check 268 if( pdalboost::empty(m_Search) ) 269 return result_type( End, End ); 270 271 // Instantiate find functor 272 first_finder_type first_finder( 273 m_Search.begin(), m_Search.end(), m_Comp ); 274 275 result_type M( Begin, Begin ); 276 277 for( unsigned int n=0; n<=N; ++n ) 278 { 279 // find next match 280 M=first_finder( ::pdalboost::end(M), End ); 281 282 if ( !M ) 283 { 284 // Subsequence not found, return 285 return M; 286 } 287 } 288 289 return M; 290 } 291 292 template< typename ForwardIteratorT > 293 iterator_range<ForwardIteratorT> find_backwardpdalboost::algorithm::detail::nth_finderF294 find_backward( 295 ForwardIteratorT Begin, 296 ForwardIteratorT End, 297 unsigned int N) const 298 { 299 typedef iterator_range<ForwardIteratorT> result_type; 300 301 // Sanity check 302 if( pdalboost::empty(m_Search) ) 303 return result_type( End, End ); 304 305 // Instantiate find functor 306 last_finder_type last_finder( 307 m_Search.begin(), m_Search.end(), m_Comp ); 308 309 result_type M( End, End ); 310 311 for( unsigned int n=1; n<=N; ++n ) 312 { 313 // find next match 314 M=last_finder( Begin, ::pdalboost::begin(M) ); 315 316 if ( !M ) 317 { 318 // Subsequence not found, return 319 return M; 320 } 321 } 322 323 return M; 324 } 325 326 327 private: 328 iterator_range<search_iterator_type> m_Search; 329 int m_Nth; 330 PredicateT m_Comp; 331 }; 332 333 // find head/tail implementation helpers ---------------------------// 334 335 template<typename ForwardIteratorT> 336 iterator_range<ForwardIteratorT> find_head_impl(ForwardIteratorT Begin,ForwardIteratorT End,unsigned int N,std::forward_iterator_tag)337 find_head_impl( 338 ForwardIteratorT Begin, 339 ForwardIteratorT End, 340 unsigned int N, 341 std::forward_iterator_tag ) 342 { 343 typedef ForwardIteratorT input_iterator_type; 344 typedef iterator_range<ForwardIteratorT> result_type; 345 346 input_iterator_type It=Begin; 347 for( 348 unsigned int Index=0; 349 Index<N && It!=End; ++Index,++It ) {}; 350 351 return result_type( Begin, It ); 352 } 353 354 template< typename ForwardIteratorT > 355 iterator_range<ForwardIteratorT> find_head_impl(ForwardIteratorT Begin,ForwardIteratorT End,unsigned int N,std::random_access_iterator_tag)356 find_head_impl( 357 ForwardIteratorT Begin, 358 ForwardIteratorT End, 359 unsigned int N, 360 std::random_access_iterator_tag ) 361 { 362 typedef iterator_range<ForwardIteratorT> result_type; 363 364 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) ) 365 return result_type( Begin, End ); 366 367 return result_type(Begin,Begin+N); 368 } 369 370 // Find head implementation 371 template<typename ForwardIteratorT> 372 iterator_range<ForwardIteratorT> find_head_impl(ForwardIteratorT Begin,ForwardIteratorT End,unsigned int N)373 find_head_impl( 374 ForwardIteratorT Begin, 375 ForwardIteratorT End, 376 unsigned int N ) 377 { 378 typedef BOOST_STRING_TYPENAME pdalboost::detail:: 379 iterator_traits<ForwardIteratorT>::iterator_category category; 380 381 return ::pdalboost::algorithm::detail::find_head_impl( Begin, End, N, category() ); 382 } 383 384 template< typename ForwardIteratorT > 385 iterator_range<ForwardIteratorT> find_tail_impl(ForwardIteratorT Begin,ForwardIteratorT End,unsigned int N,std::forward_iterator_tag)386 find_tail_impl( 387 ForwardIteratorT Begin, 388 ForwardIteratorT End, 389 unsigned int N, 390 std::forward_iterator_tag ) 391 { 392 typedef ForwardIteratorT input_iterator_type; 393 typedef iterator_range<ForwardIteratorT> result_type; 394 395 unsigned int Index=0; 396 input_iterator_type It=Begin; 397 input_iterator_type It2=Begin; 398 399 // Advance It2 by N increments 400 for( Index=0; Index<N && It2!=End; ++Index,++It2 ) {}; 401 402 // Advance It, It2 to the end 403 for(; It2!=End; ++It,++It2 ) {}; 404 405 return result_type( It, It2 ); 406 } 407 408 template< typename ForwardIteratorT > 409 iterator_range<ForwardIteratorT> find_tail_impl(ForwardIteratorT Begin,ForwardIteratorT End,unsigned int N,std::bidirectional_iterator_tag)410 find_tail_impl( 411 ForwardIteratorT Begin, 412 ForwardIteratorT End, 413 unsigned int N, 414 std::bidirectional_iterator_tag ) 415 { 416 typedef ForwardIteratorT input_iterator_type; 417 typedef iterator_range<ForwardIteratorT> result_type; 418 419 input_iterator_type It=End; 420 for( 421 unsigned int Index=0; 422 Index<N && It!=Begin; ++Index,--It ) {}; 423 424 return result_type( It, End ); 425 } 426 427 template< typename ForwardIteratorT > 428 iterator_range<ForwardIteratorT> find_tail_impl(ForwardIteratorT Begin,ForwardIteratorT End,unsigned int N,std::random_access_iterator_tag)429 find_tail_impl( 430 ForwardIteratorT Begin, 431 ForwardIteratorT End, 432 unsigned int N, 433 std::random_access_iterator_tag ) 434 { 435 typedef iterator_range<ForwardIteratorT> result_type; 436 437 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) ) 438 return result_type( Begin, End ); 439 440 return result_type( End-N, End ); 441 } 442 443 // Operation 444 template< typename ForwardIteratorT > 445 iterator_range<ForwardIteratorT> find_tail_impl(ForwardIteratorT Begin,ForwardIteratorT End,unsigned int N)446 find_tail_impl( 447 ForwardIteratorT Begin, 448 ForwardIteratorT End, 449 unsigned int N ) 450 { 451 typedef BOOST_STRING_TYPENAME pdalboost::detail:: 452 iterator_traits<ForwardIteratorT>::iterator_category category; 453 454 return ::pdalboost::algorithm::detail::find_tail_impl( Begin, End, N, category() ); 455 } 456 457 458 459 // find head functor -----------------------------------------------// 460 461 462 // find a head in the sequence ( functor ) 463 /* 464 This functor find a head of the specified range. For 465 a specified N, the head is a subsequence of N starting 466 elements of the range. 467 */ 468 struct head_finderF 469 { 470 // Construction head_finderFpdalboost::algorithm::detail::head_finderF471 head_finderF( int N ) : m_N(N) {} 472 473 // Operation 474 template< typename ForwardIteratorT > 475 iterator_range<ForwardIteratorT> operator ()pdalboost::algorithm::detail::head_finderF476 operator()( 477 ForwardIteratorT Begin, 478 ForwardIteratorT End ) const 479 { 480 if(m_N>=0) 481 { 482 return ::pdalboost::algorithm::detail::find_head_impl( Begin, End, m_N ); 483 } 484 else 485 { 486 iterator_range<ForwardIteratorT> Res= 487 ::pdalboost::algorithm::detail::find_tail_impl( Begin, End, -m_N ); 488 489 return ::pdalboost::make_iterator_range(Begin, Res.begin()); 490 } 491 } 492 493 private: 494 int m_N; 495 }; 496 497 // find tail functor -----------------------------------------------// 498 499 500 // find a tail in the sequence ( functor ) 501 /* 502 This functor find a tail of the specified range. For 503 a specified N, the head is a subsequence of N starting 504 elements of the range. 505 */ 506 struct tail_finderF 507 { 508 // Construction tail_finderFpdalboost::algorithm::detail::tail_finderF509 tail_finderF( int N ) : m_N(N) {} 510 511 // Operation 512 template< typename ForwardIteratorT > 513 iterator_range<ForwardIteratorT> operator ()pdalboost::algorithm::detail::tail_finderF514 operator()( 515 ForwardIteratorT Begin, 516 ForwardIteratorT End ) const 517 { 518 if(m_N>=0) 519 { 520 return ::pdalboost::algorithm::detail::find_tail_impl( Begin, End, m_N ); 521 } 522 else 523 { 524 iterator_range<ForwardIteratorT> Res= 525 ::pdalboost::algorithm::detail::find_head_impl( Begin, End, -m_N ); 526 527 return ::pdalboost::make_iterator_range(Res.end(), End); 528 } 529 } 530 531 private: 532 int m_N; 533 }; 534 535 // find token functor -----------------------------------------------// 536 537 // find a token in a sequence ( functor ) 538 /* 539 This find functor finds a token specified be a predicate 540 in a sequence. It is equivalent of std::find algorithm, 541 with an exception that it return range instead of a single 542 iterator. 543 544 If bCompress is set to true, adjacent matching tokens are 545 concatenated into one match. 546 */ 547 template< typename PredicateT > 548 struct token_finderF 549 { 550 // Construction token_finderFpdalboost::algorithm::detail::token_finderF551 token_finderF( 552 PredicateT Pred, 553 token_compress_mode_type eCompress=token_compress_off ) : 554 m_Pred(Pred), m_eCompress(eCompress) {} 555 556 // Operation 557 template< typename ForwardIteratorT > 558 iterator_range<ForwardIteratorT> operator ()pdalboost::algorithm::detail::token_finderF559 operator()( 560 ForwardIteratorT Begin, 561 ForwardIteratorT End ) const 562 { 563 typedef iterator_range<ForwardIteratorT> result_type; 564 565 ForwardIteratorT It=std::find_if( Begin, End, m_Pred ); 566 567 if( It==End ) 568 { 569 return result_type( End, End ); 570 } 571 else 572 { 573 ForwardIteratorT It2=It; 574 575 if( m_eCompress==token_compress_on ) 576 { 577 // Find first non-matching character 578 while( It2!=End && m_Pred(*It2) ) ++It2; 579 } 580 else 581 { 582 // Advance by one position 583 ++It2; 584 } 585 586 return result_type( It, It2 ); 587 } 588 } 589 590 private: 591 PredicateT m_Pred; 592 token_compress_mode_type m_eCompress; 593 }; 594 595 // find range functor -----------------------------------------------// 596 597 // find a range in the sequence ( functor ) 598 /* 599 This functor actually does not perform any find operation. 600 It always returns given iterator range as a result. 601 */ 602 template<typename ForwardIterator1T> 603 struct range_finderF 604 { 605 typedef ForwardIterator1T input_iterator_type; 606 typedef iterator_range<input_iterator_type> result_type; 607 608 // Construction range_finderFpdalboost::algorithm::detail::range_finderF609 range_finderF( 610 input_iterator_type Begin, 611 input_iterator_type End ) : m_Range(Begin, End) {} 612 range_finderFpdalboost::algorithm::detail::range_finderF613 range_finderF(const iterator_range<input_iterator_type>& Range) : 614 m_Range(Range) {} 615 616 // Operation 617 template< typename ForwardIterator2T > 618 iterator_range<ForwardIterator2T> operator ()pdalboost::algorithm::detail::range_finderF619 operator()( 620 ForwardIterator2T, 621 ForwardIterator2T ) const 622 { 623 #if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 ) 624 return iterator_range<const ForwardIterator2T>(this->m_Range); 625 #else 626 return m_Range; 627 #endif 628 } 629 630 private: 631 iterator_range<input_iterator_type> m_Range; 632 }; 633 634 635 } // namespace detail 636 } // namespace algorithm 637 } // namespace pdalboost 638 639 #endif // BOOST_STRING_FINDER_DETAIL_HPP 640