string/detail/finder.hpp

0001 //  Boost string_algo library finder.hpp header file  ---------------------------//
0002
0003 //  Copyright Pavol Droba 2002-2006.
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008
0009 //  See http://www.boost.org/ for updates, documentation, and revision history.
0010
0011 #ifndef BOOST_STRING_FINDER_DETAIL_HPP
0012 #define BOOST_STRING_FINDER_DETAIL_HPP
0013
0014 #include <boost/algorithm/string/config.hpp>
0015 #include <boost/algorithm/string/constants.hpp>
0016 #include <iterator>
0017
0018 #include <boost/range/iterator_range_core.hpp>
0019 #include <boost/range/begin.hpp>
0020 #include <boost/range/end.hpp>
0021 #include <boost/range/empty.hpp>
0022 #include <boost/range/as_literal.hpp>
0023
0024 namespace boost {
0025     namespace algorithm {
0026         namespace detail {
0027
0028
0029 //  find first functor -----------------------------------------------//
0030
0031             // find a subsequence in the sequence ( functor )
0032             /*
0033                 Returns a pair <begin,end> marking the subsequence in the sequence.
0034                 If the find fails, functor returns <End,End>
0035             */
0036             template<typename SearchIteratorT,typename PredicateT>
0037             struct first_finderF
0038             {
0039                 typedef SearchIteratorT search_iterator_type;
0040
0041                 // Construction
0042                 template< typename SearchT >
0043                 first_finderF( const SearchT& Search, PredicateT Comp ) :
0044                     m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
0045                 first_finderF(
0046                         search_iterator_type SearchBegin,
0047                         search_iterator_type SearchEnd,
0048                         PredicateT Comp ) :
0049                     m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}
0050
0051                 // Operation
0052                 template< typename ForwardIteratorT >
0053                 iterator_range<ForwardIteratorT>
0054                 operator()(
0055                     ForwardIteratorT Begin,
0056                     ForwardIteratorT End ) const
0057                 {
0058                     typedef iterator_range<ForwardIteratorT> result_type;
0059                     typedef ForwardIteratorT input_iterator_type;
0060
0061                     // Outer loop
0062                     for(input_iterator_type OuterIt=Begin;
0063                         OuterIt!=End;
0064                         ++OuterIt)
0065                     {
0066                         // Sanity check
0067                         if( boost::empty(m_Search) )
0068                             return result_type( End, End );
0069
0070                         input_iterator_type InnerIt=OuterIt;
0071                         search_iterator_type SubstrIt=m_Search.begin();
0072                         for(;
0073                             InnerIt!=End && SubstrIt!=m_Search.end();
0074                             ++InnerIt,++SubstrIt)
0075                         {
0076                             if( !( m_Comp(*InnerIt,*SubstrIt) ) )
0077                                 break;
0078                         }
0079
0080                         // Substring matching succeeded
0081                         if ( SubstrIt==m_Search.end() )
0082                             return result_type( OuterIt, InnerIt );
0083                     }
0084
0085                     return result_type( End, End );
0086                 }
0087
0088             private:
0089                 iterator_range<search_iterator_type> m_Search;
0090                 PredicateT m_Comp;
0091             };
0092
0093 //  find last functor -----------------------------------------------//
0094
0095             // find the last match a subsequence in the sequence ( functor )
0096             /*
0097                 Returns a pair <begin,end> marking the subsequence in the sequence.
0098                 If the find fails, returns <End,End>
0099             */
0100             template<typename SearchIteratorT, typename PredicateT>
0101             struct last_finderF
0102             {
0103                 typedef SearchIteratorT search_iterator_type;
0104                 typedef first_finderF<
0105                     search_iterator_type,
0106                     PredicateT> first_finder_type;
0107
0108                 // Construction
0109                 template< typename SearchT >
0110                 last_finderF( const SearchT& Search, PredicateT Comp ) :
0111                     m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
0112                 last_finderF(
0113                         search_iterator_type SearchBegin,
0114                         search_iterator_type SearchEnd,
0115                         PredicateT Comp ) :
0116                     m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}
0117
0118                 // Operation
0119                 template< typename ForwardIteratorT >
0120                 iterator_range<ForwardIteratorT>
0121                 operator()(
0122                     ForwardIteratorT Begin,
0123                     ForwardIteratorT End ) const
0124                 {
0125                     typedef iterator_range<ForwardIteratorT> result_type;
0126
0127                     if( boost::empty(m_Search) )
0128                         return result_type( End, End );
0129
0130                     typedef BOOST_STRING_TYPENAME
0131                         std::iterator_traits<ForwardIteratorT>::iterator_category category;
0132
0133                     return findit( Begin, End, category() );
0134                 }
0135
0136             private:
0137                 // forward iterator
0138                 template< typename ForwardIteratorT >
0139                 iterator_range<ForwardIteratorT>
0140                 findit(
0141                     ForwardIteratorT Begin,
0142                     ForwardIteratorT End,
0143                     std::forward_iterator_tag ) const
0144                 {
0145                     typedef iterator_range<ForwardIteratorT> result_type;
0146
0147                     first_finder_type first_finder(
0148                         m_Search.begin(), m_Search.end(), m_Comp );
0149
0150                     result_type M=first_finder( Begin, End );
0151                     result_type Last=M;
0152
0153                     while( M )
0154                     {
0155                         Last=M;
0156                         M=first_finder( ::boost::end(M), End );
0157                     }
0158
0159                     return Last;
0160                 }
0161
0162                 // bidirectional iterator
0163                 template< typename ForwardIteratorT >
0164                 iterator_range<ForwardIteratorT>
0165                 findit(
0166                     ForwardIteratorT Begin,
0167                     ForwardIteratorT End,
0168                     std::bidirectional_iterator_tag ) const
0169                 {
0170                     typedef iterator_range<ForwardIteratorT> result_type;
0171                     typedef ForwardIteratorT input_iterator_type;
0172
0173                     // Outer loop
0174                     for(input_iterator_type OuterIt=End;
0175                         OuterIt!=Begin; )
0176                     {
0177                         input_iterator_type OuterIt2=--OuterIt;
0178
0179                         input_iterator_type InnerIt=OuterIt2;
0180                         search_iterator_type SubstrIt=m_Search.begin();
0181                         for(;
0182                             InnerIt!=End && SubstrIt!=m_Search.end();
0183                             ++InnerIt,++SubstrIt)
0184                         {
0185                             if( !( m_Comp(*InnerIt,*SubstrIt) ) )
0186                                 break;
0187                         }
0188
0189                         // Substring matching succeeded
0190                         if( SubstrIt==m_Search.end() )
0191                             return result_type( OuterIt2, InnerIt );
0192                     }
0193
0194                     return result_type( End, End );
0195                 }
0196
0197             private:
0198                 iterator_range<search_iterator_type> m_Search;
0199                 PredicateT m_Comp;
0200             };
0201
0202 //  find n-th functor -----------------------------------------------//
0203
0204             // find the n-th match of a subsequence in the sequence ( functor )
0205             /*
0206                 Returns a pair <begin,end> marking the subsequence in the sequence.
0207                 If the find fails, returns <End,End>
0208             */
0209             template<typename SearchIteratorT, typename PredicateT>
0210             struct nth_finderF
0211             {
0212                 typedef SearchIteratorT search_iterator_type;
0213                 typedef first_finderF<
0214                     search_iterator_type,
0215                     PredicateT> first_finder_type;
0216                 typedef last_finderF<
0217                     search_iterator_type,
0218                     PredicateT> last_finder_type;
0219
0220                 // Construction
0221                 template< typename SearchT >
0222                 nth_finderF(
0223                         const SearchT& Search,
0224                         int Nth,
0225                         PredicateT Comp) :
0226                     m_Search(::boost::begin(Search), ::boost::end(Search)),
0227                     m_Nth(Nth),
0228                     m_Comp(Comp) {}
0229                 nth_finderF(
0230                         search_iterator_type SearchBegin,
0231                         search_iterator_type SearchEnd,
0232                         int Nth,
0233                         PredicateT Comp) :
0234                     m_Search(SearchBegin, SearchEnd),
0235                     m_Nth(Nth),
0236                     m_Comp(Comp) {}
0237
0238                 // Operation
0239                 template< typename ForwardIteratorT >
0240                 iterator_range<ForwardIteratorT>
0241                 operator()(
0242                     ForwardIteratorT Begin,
0243                     ForwardIteratorT End ) const
0244                 {
0245                     if(m_Nth>=0)
0246                     {
0247                         return find_forward(Begin, End, m_Nth);
0248                     }
0249                     else
0250                     {
0251                         return find_backward(Begin, End, -m_Nth);
0252                     }
0253
0254                 }
0255
0256             private:
0257                 // Implementation helpers
0258                 template< typename ForwardIteratorT >
0259                 iterator_range<ForwardIteratorT>
0260                 find_forward(
0261                     ForwardIteratorT Begin,
0262                     ForwardIteratorT End,
0263                     unsigned int N) const
0264                 {
0265                     typedef iterator_range<ForwardIteratorT> result_type;
0266
0267                     // Sanity check
0268                     if( boost::empty(m_Search) )
0269                         return result_type( End, End );
0270
0271                     // Instantiate find functor
0272                     first_finder_type first_finder(
0273                         m_Search.begin(), m_Search.end(), m_Comp );
0274
0275                     result_type M( Begin, Begin );
0276
0277                     for( unsigned int n=0; n<=N; ++n )
0278                     {
0279                         // find next match
0280                         M=first_finder( ::boost::end(M), End );
0281
0282                         if ( !M )
0283                         {
0284                             // Subsequence not found, return
0285                             return M;
0286                         }
0287                     }
0288
0289                     return M;
0290                 }
0291
0292                 template< typename ForwardIteratorT >
0293                 iterator_range<ForwardIteratorT>
0294                 find_backward(
0295                     ForwardIteratorT Begin,
0296                     ForwardIteratorT End,
0297                     unsigned int N) const
0298                 {
0299                     typedef iterator_range<ForwardIteratorT> result_type;
0300
0301                     // Sanity check
0302                     if( boost::empty(m_Search) )
0303                         return result_type( End, End );
0304
0305                     // Instantiate find functor
0306                     last_finder_type last_finder(
0307                         m_Search.begin(), m_Search.end(), m_Comp );
0308
0309                     result_type M( End, End );
0310
0311                     for( unsigned int n=1; n<=N; ++n )
0312                     {
0313                         // find next match
0314                         M=last_finder( Begin, ::boost::begin(M) );
0315
0316                         if ( !M )
0317                         {
0318                             // Subsequence not found, return
0319                             return M;
0320                         }
0321                     }
0322
0323                     return M;
0324                 }
0325
0326
0327             private:
0328                 iterator_range<search_iterator_type> m_Search;
0329                 int m_Nth;
0330                 PredicateT m_Comp;
0331             };
0332
0333 //  find head/tail implementation helpers ---------------------------//
0334
0335             template<typename ForwardIteratorT>
0336                 iterator_range<ForwardIteratorT>
0337             find_head_impl(
0338                 ForwardIteratorT Begin,
0339                 ForwardIteratorT End,
0340                 unsigned int N,
0341                 std::forward_iterator_tag )
0342             {
0343                 typedef ForwardIteratorT input_iterator_type;
0344                 typedef iterator_range<ForwardIteratorT> result_type;
0345
0346                 input_iterator_type It=Begin;
0347                 for( unsigned int Index=0; Index<N && It!=End; ++Index,++It )
0348                     ;
0349
0350                 return result_type( Begin, It );
0351             }
0352
0353             template< typename ForwardIteratorT >
0354                 iterator_range<ForwardIteratorT>
0355             find_head_impl(
0356                 ForwardIteratorT Begin,
0357                 ForwardIteratorT End,
0358                 unsigned int N,
0359                 std::random_access_iterator_tag )
0360             {
0361                 typedef iterator_range<ForwardIteratorT> result_type;
0362
0363                 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
0364                     return result_type( Begin, End );
0365
0366                 return result_type(Begin,Begin+N);
0367             }
0368
0369             // Find head implementation
0370             template<typename ForwardIteratorT>
0371                 iterator_range<ForwardIteratorT>
0372             find_head_impl(
0373                 ForwardIteratorT Begin,
0374                 ForwardIteratorT End,
0375                 unsigned int N )
0376             {
0377                 typedef BOOST_STRING_TYPENAME
0378                     std::iterator_traits<ForwardIteratorT>::iterator_category category;
0379
0380                 return ::boost::algorithm::detail::find_head_impl( Begin, End, N, category() );
0381             }
0382
0383             template< typename ForwardIteratorT >
0384                 iterator_range<ForwardIteratorT>
0385             find_tail_impl(
0386                 ForwardIteratorT Begin,
0387                 ForwardIteratorT End,
0388                 unsigned int N,
0389                 std::forward_iterator_tag )
0390             {
0391                 typedef ForwardIteratorT input_iterator_type;
0392                 typedef iterator_range<ForwardIteratorT> result_type;
0393
0394                 unsigned int Index=0;
0395                 input_iterator_type It=Begin;
0396                 input_iterator_type It2=Begin;
0397
0398                 // Advance It2 by N increments
0399                 for( Index=0; Index<N && It2!=End; ++Index,++It2 )
0400                     ;
0401
0402                 // Advance It, It2 to the end
0403                 for(; It2!=End; ++It,++It2 )
0404                     ;
0405
0406                 return result_type( It, It2 );
0407             }
0408
0409             template< typename ForwardIteratorT >
0410                 iterator_range<ForwardIteratorT>
0411             find_tail_impl(
0412                 ForwardIteratorT Begin,
0413                 ForwardIteratorT End,
0414                 unsigned int N,
0415                 std::bidirectional_iterator_tag )
0416             {
0417                 typedef ForwardIteratorT input_iterator_type;
0418                 typedef iterator_range<ForwardIteratorT> result_type;
0419
0420                 input_iterator_type It=End;
0421                 for( unsigned int Index=0; Index<N && It!=Begin; ++Index,--It )
0422                     ;
0423
0424                 return result_type( It, End );
0425             }
0426
0427             template< typename ForwardIteratorT >
0428                 iterator_range<ForwardIteratorT>
0429             find_tail_impl(
0430                 ForwardIteratorT Begin,
0431                 ForwardIteratorT End,
0432                 unsigned int N,
0433                 std::random_access_iterator_tag )
0434             {
0435                 typedef iterator_range<ForwardIteratorT> result_type;
0436
0437                 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
0438                     return result_type( Begin, End );
0439
0440                 return result_type( End-N, End );
0441             }
0442
0443                         // Operation
0444             template< typename ForwardIteratorT >
0445             iterator_range<ForwardIteratorT>
0446             find_tail_impl(
0447                 ForwardIteratorT Begin,
0448                 ForwardIteratorT End,
0449                 unsigned int N )
0450             {
0451                 typedef BOOST_STRING_TYPENAME
0452                     std::iterator_traits<ForwardIteratorT>::iterator_category category;
0453
0454                 return ::boost::algorithm::detail::find_tail_impl( Begin, End, N, category() );
0455             }
0456
0457
0458
0459 //  find head functor -----------------------------------------------//
0460
0461
0462             // find a head in the sequence ( functor )
0463             /*
0464                 This functor find a head of the specified range. For
0465                 a specified N, the head is a subsequence of N starting
0466                 elements of the range.
0467             */
0468             struct head_finderF
0469             {
0470                 // Construction
0471                 head_finderF( int N ) : m_N(N) {}
0472
0473                 // Operation
0474                 template< typename ForwardIteratorT >
0475                 iterator_range<ForwardIteratorT>
0476                 operator()(
0477                     ForwardIteratorT Begin,
0478                     ForwardIteratorT End ) const
0479                 {
0480                     if(m_N>=0)
0481                     {
0482                         return ::boost::algorithm::detail::find_head_impl( Begin, End, m_N );
0483                     }
0484                     else
0485                     {
0486                         iterator_range<ForwardIteratorT> Res=
0487                             ::boost::algorithm::detail::find_tail_impl( Begin, End, -m_N );
0488
0489                         return ::boost::make_iterator_range(Begin, Res.begin());
0490                     }
0491                 }
0492
0493             private:
0494                 int m_N;
0495             };
0496
0497 //  find tail functor -----------------------------------------------//
0498
0499
0500             // find a tail in the sequence ( functor )
0501             /*
0502                 This functor find a tail of the specified range. For
0503                 a specified N, the head is a subsequence of N starting
0504                 elements of the range.
0505             */
0506             struct tail_finderF
0507             {
0508                 // Construction
0509                 tail_finderF( int N ) : m_N(N) {}
0510
0511                 // Operation
0512                 template< typename ForwardIteratorT >
0513                 iterator_range<ForwardIteratorT>
0514                 operator()(
0515                     ForwardIteratorT Begin,
0516                     ForwardIteratorT End ) const
0517                 {
0518                     if(m_N>=0)
0519                     {
0520                         return ::boost::algorithm::detail::find_tail_impl( Begin, End, m_N );
0521                     }
0522                     else
0523                     {
0524                         iterator_range<ForwardIteratorT> Res=
0525                             ::boost::algorithm::detail::find_head_impl( Begin, End, -m_N );
0526
0527                         return ::boost::make_iterator_range(Res.end(), End);
0528                     }
0529                 }
0530
0531             private:
0532                 int m_N;
0533             };
0534
0535 //  find token functor -----------------------------------------------//
0536
0537             // find a token in a sequence ( functor )
0538             /*
0539                 This find functor finds a token specified be a predicate
0540                 in a sequence. It is equivalent of std::find algorithm,
0541                 with an exception that it return range instead of a single
0542                 iterator.
0543
0544                 If bCompress is set to true, adjacent matching tokens are
0545                 concatenated into one match.
0546             */
0547             template< typename PredicateT >
0548             struct token_finderF
0549             {
0550                 // Construction
0551                 token_finderF(
0552                     PredicateT Pred,
0553                     token_compress_mode_type eCompress=token_compress_off ) :
0554                         m_Pred(Pred), m_eCompress(eCompress) {}
0555
0556                 // Operation
0557                 template< typename ForwardIteratorT >
0558                 iterator_range<ForwardIteratorT>
0559                 operator()(
0560                     ForwardIteratorT Begin,
0561                     ForwardIteratorT End ) const
0562                 {
0563                     typedef iterator_range<ForwardIteratorT> result_type;
0564
0565                     ForwardIteratorT It=std::find_if( Begin, End, m_Pred );
0566
0567                     if( It==End )
0568                     {
0569                         return result_type( End, End );
0570                     }
0571                     else
0572                     {
0573                         ForwardIteratorT It2=It;
0574
0575                         if( m_eCompress==token_compress_on )
0576                         {
0577                             // Find first non-matching character
0578                             while( It2!=End && m_Pred(*It2) ) ++It2;
0579                         }
0580                         else
0581                         {
0582                             // Advance by one position
0583                             ++It2;
0584                         }
0585
0586                         return result_type( It, It2 );
0587                     }
0588                 }
0589
0590             private:
0591                 PredicateT m_Pred;
0592                 token_compress_mode_type m_eCompress;
0593             };
0594
0595 //  find range functor -----------------------------------------------//
0596
0597             // find a range in the sequence ( functor )
0598             /*
0599                 This functor actually does not perform any find operation.
0600                 It always returns given iterator range as a result.
0601             */
0602             template<typename ForwardIterator1T>
0603             struct range_finderF
0604             {
0605                 typedef ForwardIterator1T input_iterator_type;
0606                 typedef iterator_range<input_iterator_type> result_type;
0607
0608                 // Construction
0609                 range_finderF(
0610                     input_iterator_type Begin,
0611                     input_iterator_type End ) : m_Range(Begin, End) {}
0612
0613                 range_finderF(const iterator_range<input_iterator_type>& Range) :
0614                     m_Range(Range) {}
0615
0616                 // Operation
0617                 template< typename ForwardIterator2T >
0618                 iterator_range<ForwardIterator2T>
0619                 operator()(
0620                     ForwardIterator2T,
0621                     ForwardIterator2T ) const
0622                 {
0623 #if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 )
0624                     return iterator_range<const ForwardIterator2T>(this->m_Range);
0625 #else
0626                     return m_Range;
0627 #endif
0628                 }
0629
0630             private:
0631                 iterator_range<input_iterator_type> m_Range;
0632             };
0633
0634
0635         } // namespace detail
0636     } // namespace algorithm
0637 } // namespace boost
0638
0639 #endif  // BOOST_STRING_FINDER_DETAIL_HPP