l4/pkg/boost-lite/include/boost/algorithm/string/detail/finder.hpp

   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.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 boost {
  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 >
  43                 first_finderF( const SearchT& Search, PredicateT Comp ) :
  44                     m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
  45                 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>
  54                 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( boost::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 subseqeunce 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 >
 110                 last_finderF( const SearchT& Search, PredicateT Comp ) :
 111                     m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
 112                 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>
 121                 operator()(
 122                     ForwardIteratorT Begin,
 123                     ForwardIteratorT End ) const
 124                 {
 125                     typedef iterator_range<ForwardIteratorT> result_type;
 126
 127                     if( boost::empty(m_Search) )
 128                         return result_type( End, End );
 129
 130                     typedef BOOST_STRING_TYPENAME boost::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>
 140                 findit(
 141                     ForwardIteratorT Begin,
 142                     ForwardIteratorT End,
 143                     std::forward_iterator_tag ) const
 144                 {
 145                     typedef ForwardIteratorT input_iterator_type;
 146                     typedef iterator_range<ForwardIteratorT> result_type;
 147
 148                     first_finder_type first_finder(
 149                         m_Search.begin(), m_Search.end(), m_Comp );
 150
 151                     result_type M=first_finder( Begin, End );
 152                     result_type Last=M;
 153
 154                     while( M )
 155                     {
 156                         Last=M;
 157                         M=first_finder( ::boost::end(M), End );
 158                     }
 159
 160                     return Last;
 161                 }
 162
 163                 // bidirectional iterator
 164                 template< typename ForwardIteratorT >
 165                 iterator_range<ForwardIteratorT>
 166                 findit(
 167                     ForwardIteratorT Begin,
 168                     ForwardIteratorT End,
 169                     std::bidirectional_iterator_tag ) const
 170                 {
 171                     typedef iterator_range<ForwardIteratorT> result_type;
 172                     typedef ForwardIteratorT input_iterator_type;
 173
 174                     // Outer loop
 175                     for(input_iterator_type OuterIt=End;
 176                         OuterIt!=Begin; )
 177                     {
 178                         input_iterator_type OuterIt2=--OuterIt;
 179
 180                         input_iterator_type InnerIt=OuterIt2;
 181                         search_iterator_type SubstrIt=m_Search.begin();
 182                         for(;
 183                             InnerIt!=End && SubstrIt!=m_Search.end();
 184                             ++InnerIt,++SubstrIt)
 185                         {
 186                             if( !( m_Comp(*InnerIt,*SubstrIt) ) )
 187                                 break;
 188                         }
 189
 190                         // Substring matching succeeded
 191                         if( SubstrIt==m_Search.end() )
 192                             return result_type( OuterIt2, InnerIt );
 193                     }
 194
 195                     return result_type( End, End );
 196                 }
 197
 198             private:
 199                 iterator_range<search_iterator_type> m_Search;
 200                 PredicateT m_Comp;
 201             };
 202
 203 //  find n-th functor -----------------------------------------------//
 204
 205             // find the n-th match of a subsequence in the sequence ( functor )
 206             /*
 207                 Returns a pair <begin,end> marking the subsequence in the sequence.
 208                 If the find fails, returns <End,End>
 209             */
 210             template<typename SearchIteratorT, typename PredicateT>
 211             struct nth_finderF
 212             {
 213                 typedef SearchIteratorT search_iterator_type;
 214                 typedef first_finderF<
 215                     search_iterator_type,
 216                     PredicateT> first_finder_type;
 217                 typedef last_finderF<
 218                     search_iterator_type,
 219                     PredicateT> last_finder_type;
 220
 221                 // Construction
 222                 template< typename SearchT >
 223                 nth_finderF(
 224                         const SearchT& Search,
 225                         int Nth,
 226                         PredicateT Comp) :
 227                     m_Search(::boost::begin(Search), ::boost::end(Search)),
 228                     m_Nth(Nth),
 229                     m_Comp(Comp) {}
 230                 nth_finderF(
 231                         search_iterator_type SearchBegin,
 232                         search_iterator_type SearchEnd,
 233                         int Nth,
 234                         PredicateT Comp) :
 235                     m_Search(SearchBegin, SearchEnd),
 236                     m_Nth(Nth),
 237                     m_Comp(Comp) {}
 238
 239                 // Operation
 240                 template< typename ForwardIteratorT >
 241                 iterator_range<ForwardIteratorT>
 242                 operator()(
 243                     ForwardIteratorT Begin,
 244                     ForwardIteratorT End ) const
 245                 {
 246                     if(m_Nth>=0)
 247                     {
 248                         return find_forward(Begin, End, m_Nth);
 249                     }
 250                     else
 251                     {
 252                         return find_backward(Begin, End, -m_Nth);
 253                     }
 254
 255                 }
 256
 257             private:
 258                 // Implementation helpers
 259                 template< typename ForwardIteratorT >
 260                 iterator_range<ForwardIteratorT>
 261                 find_forward(
 262                     ForwardIteratorT Begin,
 263                     ForwardIteratorT End,
 264                     unsigned int N) const
 265                 {
 266                     typedef ForwardIteratorT input_iterator_type;
 267                     typedef iterator_range<ForwardIteratorT> result_type;
 268
 269                     // Sanity check
 270                     if( boost::empty(m_Search) )
 271                         return result_type( End, End );
 272
 273                     // Instantiate find functor
 274                     first_finder_type first_finder(
 275                         m_Search.begin(), m_Search.end(), m_Comp );
 276
 277                     result_type M( Begin, Begin );
 278
 279                     for( unsigned int n=0; n<=N; ++n )
 280                     {
 281                         // find next match
 282                         M=first_finder( ::boost::end(M), End );
 283
 284                         if ( !M )
 285                         {
 286                             // Subsequence not found, return
 287                             return M;
 288                         }
 289                     }
 290
 291                     return M;
 292                 }
 293
 294                 template< typename ForwardIteratorT >
 295                 iterator_range<ForwardIteratorT>
 296                 find_backward(
 297                     ForwardIteratorT Begin,
 298                     ForwardIteratorT End,
 299                     unsigned int N) const
 300                 {
 301                     typedef ForwardIteratorT input_iterator_type;
 302                     typedef iterator_range<ForwardIteratorT> result_type;
 303
 304                     // Sanity check
 305                     if( boost::empty(m_Search) )
 306                         return result_type( End, End );
 307
 308                     // Instantiate find functor
 309                     last_finder_type last_finder(
 310                         m_Search.begin(), m_Search.end(), m_Comp );
 311
 312                     result_type M( End, End );
 313
 314                     for( unsigned int n=1; n<=N; ++n )
 315                     {
 316                         // find next match
 317                         M=last_finder( Begin, ::boost::begin(M) );
 318
 319                         if ( !M )
 320                         {
 321                             // Subsequence not found, return
 322                             return M;
 323                         }
 324                     }
 325
 326                     return M;
 327                 }
 328
 329
 330             private:
 331                 iterator_range<search_iterator_type> m_Search;
 332                 int m_Nth;
 333                 PredicateT m_Comp;
 334             };
 335
 336 //  find head/tail implementation helpers ---------------------------//
 337
 338             template<typename ForwardIteratorT>
 339                 iterator_range<ForwardIteratorT>
 340             find_head_impl(
 341                 ForwardIteratorT Begin,
 342                 ForwardIteratorT End,
 343                 unsigned int N,
 344                 std::forward_iterator_tag )
 345             {
 346                 typedef ForwardIteratorT input_iterator_type;
 347                 typedef iterator_range<ForwardIteratorT> result_type;
 348
 349                 input_iterator_type It=Begin;
 350                 for(
 351                     unsigned int Index=0;
 352                     Index<N && It!=End; ++Index,++It ) {};
 353
 354                 return result_type( Begin, It );
 355             }
 356
 357             template< typename ForwardIteratorT >
 358                 iterator_range<ForwardIteratorT>
 359             find_head_impl(
 360                 ForwardIteratorT Begin,
 361                 ForwardIteratorT End,
 362                 unsigned int N,
 363                 std::random_access_iterator_tag )
 364             {
 365                 typedef ForwardIteratorT input_iterator_type;
 366                 typedef iterator_range<ForwardIteratorT> result_type;
 367
 368                 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
 369                     return result_type( Begin, End );
 370
 371                 return result_type(Begin,Begin+N);
 372             }
 373
 374             // Find head implementation
 375             template<typename ForwardIteratorT>
 376                 iterator_range<ForwardIteratorT>
 377             find_head_impl(
 378                 ForwardIteratorT Begin,
 379                 ForwardIteratorT End,
 380                 unsigned int N )
 381             {
 382                 typedef BOOST_STRING_TYPENAME boost::detail::
 383                     iterator_traits<ForwardIteratorT>::iterator_category category;
 384
 385                 return find_head_impl( Begin, End, N, category() );
 386             }
 387
 388             template< typename ForwardIteratorT >
 389                 iterator_range<ForwardIteratorT>
 390             find_tail_impl(
 391                 ForwardIteratorT Begin,
 392                 ForwardIteratorT End,
 393                 unsigned int N,
 394                 std::forward_iterator_tag )
 395             {
 396                 typedef ForwardIteratorT input_iterator_type;
 397                 typedef iterator_range<ForwardIteratorT> result_type;
 398
 399                 unsigned int Index=0;
 400                 input_iterator_type It=Begin;
 401                 input_iterator_type It2=Begin;
 402
 403                 // Advance It2 by N increments
 404                 for( Index=0; Index<N && It2!=End; ++Index,++It2 ) {};
 405
 406                 // Advance It, It2 to the end
 407                 for(; It2!=End; ++It,++It2 ) {};
 408
 409                 return result_type( It, It2 );
 410             }
 411
 412             template< typename ForwardIteratorT >
 413                 iterator_range<ForwardIteratorT>
 414             find_tail_impl(
 415                 ForwardIteratorT Begin,
 416                 ForwardIteratorT End,
 417                 unsigned int N,
 418                 std::bidirectional_iterator_tag )
 419             {
 420                 typedef ForwardIteratorT input_iterator_type;
 421                 typedef iterator_range<ForwardIteratorT> result_type;
 422
 423                 input_iterator_type It=End;
 424                 for(
 425                     unsigned int Index=0;
 426                     Index<N && It!=Begin; ++Index,--It ) {};
 427
 428                 return result_type( It, End );
 429             }
 430
 431             template< typename ForwardIteratorT >
 432                 iterator_range<ForwardIteratorT>
 433             find_tail_impl(
 434                 ForwardIteratorT Begin,
 435                 ForwardIteratorT End,
 436                 unsigned int N,
 437                 std::random_access_iterator_tag )
 438             {
 439                 typedef ForwardIteratorT input_iterator_type;
 440                 typedef iterator_range<ForwardIteratorT> result_type;
 441
 442                 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
 443                     return result_type( Begin, End );
 444
 445                 return result_type( End-N, End );
 446             }
 447
 448                         // Operation
 449             template< typename ForwardIteratorT >
 450             iterator_range<ForwardIteratorT>
 451             find_tail_impl(
 452                 ForwardIteratorT Begin,
 453                 ForwardIteratorT End,
 454                 unsigned int N )
 455             {
 456                 typedef BOOST_STRING_TYPENAME boost::detail::
 457                     iterator_traits<ForwardIteratorT>::iterator_category category;
 458
 459                 return find_tail_impl( Begin, End, N, category() );
 460             }
 461
 462
 463
 464 //  find head functor -----------------------------------------------//
 465
 466
 467             // find a head in the sequence ( functor )
 468             /*
 469                 This functor find a head of the specified range. For
 470                 a specified N, the head is a subsequence of N starting
 471                 elements of the range.
 472             */
 473             struct head_finderF
 474             {
 475                 // Construction
 476                 head_finderF( int N ) : m_N(N) {}
 477
 478                 // Operation
 479                 template< typename ForwardIteratorT >
 480                 iterator_range<ForwardIteratorT>
 481                 operator()(
 482                     ForwardIteratorT Begin,
 483                     ForwardIteratorT End ) const
 484                 {
 485                     if(m_N>=0)
 486                     {
 487                         return find_head_impl( Begin, End, m_N );
 488                     }
 489                     else
 490                     {
 491                         iterator_range<ForwardIteratorT> Res=
 492                             find_tail_impl( Begin, End, -m_N );
 493
 494                         return make_iterator_range(Begin, Res.begin());
 495                     }
 496                 }
 497
 498             private:
 499                 int m_N;
 500             };
 501
 502 //  find tail functor -----------------------------------------------//
 503
 504
 505             // find a tail in the sequence ( functor )
 506             /*
 507                 This functor find a tail of the specified range. For
 508                 a specified N, the head is a subsequence of N starting
 509                 elements of the range.
 510             */
 511             struct tail_finderF
 512             {
 513                 // Construction
 514                 tail_finderF( int N ) : m_N(N) {}
 515
 516                 // Operation
 517                 template< typename ForwardIteratorT >
 518                 iterator_range<ForwardIteratorT>
 519                 operator()(
 520                     ForwardIteratorT Begin,
 521                     ForwardIteratorT End ) const
 522                 {
 523                     if(m_N>=0)
 524                     {
 525                         return find_tail_impl( Begin, End, m_N );
 526                     }
 527                     else
 528                     {
 529                         iterator_range<ForwardIteratorT> Res=
 530                             find_head_impl( Begin, End, -m_N );
 531
 532                         return make_iterator_range(Res.end(), End);
 533                     }
 534                 }
 535
 536             private:
 537                 int m_N;
 538             };
 539
 540 //  find token functor -----------------------------------------------//
 541
 542             // find a token in a sequence ( functor )
 543             /*
 544                 This find functor finds a token specified be a predicate
 545                 in a sequence. It is equivalent of std::find algorithm,
 546                 with an exception that it return range instead of a single
 547                 iterator.
 548
 549                 If bCompress is set to true, adjacent matching tokens are
 550                 concatenated into one match.
 551             */
 552             template< typename PredicateT >
 553             struct token_finderF
 554             {
 555                 // Construction
 556                 token_finderF(
 557                     PredicateT Pred,
 558                     token_compress_mode_type eCompress=token_compress_off ) :
 559                         m_Pred(Pred), m_eCompress(eCompress) {}
 560
 561                 // Operation
 562                 template< typename ForwardIteratorT >
 563                 iterator_range<ForwardIteratorT>
 564                 operator()(
 565                     ForwardIteratorT Begin,
 566                     ForwardIteratorT End ) const
 567                 {
 568                     typedef iterator_range<ForwardIteratorT> result_type;
 569
 570                     ForwardIteratorT It=std::find_if( Begin, End, m_Pred );
 571
 572                     if( It==End )
 573                     {
 574                         return result_type( End, End );
 575                     }
 576                     else
 577                     {
 578                         ForwardIteratorT It2=It;
 579
 580                         if( m_eCompress==token_compress_on )
 581                         {
 582                             // Find first non-matching character
 583                             while( It2!=End && m_Pred(*It2) ) ++It2;
 584                         }
 585                         else
 586                         {
 587                             // Advance by one position
 588                             ++It2;
 589                         }
 590
 591                         return result_type( It, It2 );
 592                     }
 593                 }
 594
 595             private:
 596                 PredicateT m_Pred;
 597                 token_compress_mode_type m_eCompress;
 598             };
 599
 600 //  find range functor -----------------------------------------------//
 601
 602             // find a range in the sequence ( functor )
 603             /*
 604                 This functor actually does not perform any find operation.
 605                 It always returns given iterator range as a result.
 606             */
 607             template<typename ForwardIterator1T>
 608             struct range_finderF
 609             {
 610                 typedef ForwardIterator1T input_iterator_type;
 611                 typedef iterator_range<input_iterator_type> result_type;
 612
 613                 // Construction
 614                 range_finderF(
 615                     input_iterator_type Begin,
 616                     input_iterator_type End ) : m_Range(Begin, End) {}
 617
 618                 range_finderF(const iterator_range<input_iterator_type>& Range) :
 619                     m_Range(Range) {}
 620
 621                 // Operation
 622                 template< typename ForwardIterator2T >
 623                 iterator_range<ForwardIterator2T>
 624                 operator()(
 625                     ForwardIterator2T,
 626                     ForwardIterator2T ) const
 627                 {
 628 #if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 )
 629                     return iterator_range<const ForwardIterator2T>(this->m_Range);
 630 #elif BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
 631                     return iterator_range<ForwardIterator2T>(m_Range.begin(), m_Range.end());
 632 #else
 633                     return m_Range;
 634 #endif
 635                 }
 636
 637             private:
 638                 iterator_range<input_iterator_type> m_Range;
 639             };
 640
 641
 642         } // namespace detail
 643     } // namespace algorithm
 644 } // namespace boost
 645
 646 #endif  // BOOST_STRING_FINDER_DETAIL_HPP