Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/boost/algorithm/string/detail/finder.hpp @ 56

Last change on this file since 56 was 29, checked in by landauf, 17 years ago

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