source: NonGTP/Boost/boost/algorithm/string/detail/finder.hpp @ 857

Revision 857, 20.1 KB checked in by igarcia, 19 years ago (diff)
Line 
1//  Boost string_algo library finder.hpp header file  ---------------------------//
2
3//  Copyright Pavol Droba 2002-2003. 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 subsequnce 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 subsequnce 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
216                // Construction
217                template< typename SearchT >
218                nth_finderF(
219                        const SearchT& Search,
220                        unsigned int Nth,
221                        PredicateT Comp) :
222                    m_Search(begin(Search), end(Search)),
223                    m_Nth(Nth),
224                    m_Comp(Comp) {}
225                nth_finderF(
226                        search_iterator_type SearchBegin,
227                        search_iterator_type SearchEnd,
228                        unsigned int Nth,
229                        PredicateT Comp) :
230                    m_Search(SearchBegin, SearchEnd),
231                    m_Nth(Nth),
232                    m_Comp(Comp) {}
233
234                // Operation
235                template< typename ForwardIteratorT >
236                iterator_range<ForwardIteratorT>
237                operator()(
238                    ForwardIteratorT Begin,
239                    ForwardIteratorT End ) const
240                {
241                    typedef ForwardIteratorT input_iterator_type;
242                    typedef iterator_range<ForwardIteratorT> result_type;
243
244                    // Sanity check
245                    if( boost::empty(m_Search) )
246                        return result_type( End, End );
247
248                    // Instantiate find funtor
249                    first_finder_type first_finder(
250                        m_Search.begin(), m_Search.end(), m_Comp );
251
252                    result_type M( Begin, Begin );
253
254                    for( unsigned int n=0; n<=m_Nth; ++n )
255                    {
256                        // find next match
257                        M=first_finder( end(M), End );
258
259                        if ( !M )
260                        {
261                            // Subsequence not found, return
262                            return M;
263                        }
264                    }
265
266                    return M;
267                }
268
269            private:
270                iterator_range<search_iterator_type> m_Search;
271                unsigned int m_Nth;
272                PredicateT m_Comp;
273            };
274
275//  find head functor -----------------------------------------------//
276
277            // find a head in the sequence ( functor )
278            /*
279                This functor find a head of the specified range. For
280                a specified N, the head is a subsequence of N starting
281                elements of the range.
282            */
283            struct head_finderF
284            {
285                // Construction
286                head_finderF( unsigned int N ) : m_N(N) {}
287
288                // Operation
289                template< typename ForwardIteratorT >
290                iterator_range<ForwardIteratorT>
291                operator()(
292                    ForwardIteratorT Begin,
293                    ForwardIteratorT End ) const
294                {
295                    typedef BOOST_STRING_TYPENAME boost::detail::
296                        iterator_traits<ForwardIteratorT>::iterator_category category;
297
298                    return findit( Begin, End, category() );
299                }
300
301            private:
302                // Find operation implementation
303                template< typename ForwardIteratorT >
304                    iterator_range<ForwardIteratorT>
305                findit(
306                    ForwardIteratorT Begin,
307                    ForwardIteratorT End,
308                    std::forward_iterator_tag ) const
309                {
310                    typedef ForwardIteratorT input_iterator_type;
311                    typedef iterator_range<ForwardIteratorT> result_type;
312
313                    input_iterator_type It=Begin;
314                    for(
315                        unsigned int Index=0;
316                        Index<m_N && It!=End; ++Index,++It ) {};
317
318                    return result_type( Begin, It );
319                }
320
321                template< typename ForwardIteratorT >
322                    iterator_range<ForwardIteratorT>
323                findit(
324                    ForwardIteratorT Begin,
325                    ForwardIteratorT End,
326                    std::random_access_iterator_tag ) const
327                {
328                    typedef ForwardIteratorT input_iterator_type;
329                    typedef iterator_range<ForwardIteratorT> result_type;
330
331                    if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < m_N ) )
332                        return result_type( Begin, End );
333
334                    return result_type(Begin,Begin+m_N);
335                }
336
337            private:
338                unsigned int m_N;
339            };
340
341//  find tail functor -----------------------------------------------//
342
343            // find a tail in the sequence ( functor )
344            /*
345                This functor find a tail of the specified range. For
346                a specified N, the head is a subsequence of N starting
347                elements of the range.
348            */
349            struct tail_finderF
350            {
351                // Construction
352                tail_finderF( unsigned int N ) : m_N(N) {}
353
354                // Operation
355                template< typename ForwardIteratorT >
356                iterator_range<ForwardIteratorT>
357                operator()(
358                    ForwardIteratorT Begin,
359                    ForwardIteratorT End ) const
360                {
361                    typedef BOOST_STRING_TYPENAME boost::detail::
362                        iterator_traits<ForwardIteratorT>::iterator_category category;
363
364                    return findit( Begin, End, category() );
365                }
366
367            private:
368                // Find operation implementation
369                template< typename ForwardIteratorT >
370                    iterator_range<ForwardIteratorT>
371                findit(
372                    ForwardIteratorT Begin,
373                    ForwardIteratorT End,
374                    std::forward_iterator_tag ) const
375                {
376                    typedef ForwardIteratorT input_iterator_type;
377                    typedef iterator_range<ForwardIteratorT> result_type;
378
379                    unsigned int Index=0;
380                    input_iterator_type It=Begin;
381                    input_iterator_type It2=Begin;
382
383                    // Advance It2 by N incremets
384                    for( Index=0; Index<m_N && It2!=End; ++Index,++It2 ) {};
385
386                    // Advance It, It2 to the end
387                    for(; It2!=End; ++It,++It2 ) {};
388
389                    return result_type( It, It2 );
390                }
391
392                template< typename ForwardIteratorT >
393                    iterator_range<ForwardIteratorT>
394                findit(
395                    ForwardIteratorT Begin,
396                    ForwardIteratorT End,
397                    std::bidirectional_iterator_tag ) const
398                {
399                    typedef ForwardIteratorT input_iterator_type;
400                    typedef iterator_range<ForwardIteratorT> result_type;
401
402                    input_iterator_type It=End;
403                    for(
404                        unsigned int Index=0;
405                        Index<m_N && It!=Begin; ++Index,--It ) {};
406
407                    return result_type( It, End );
408                }
409
410                template< typename ForwardIteratorT >
411                    iterator_range<ForwardIteratorT>
412                findit(
413                    ForwardIteratorT Begin,
414                    ForwardIteratorT End,
415                    std::random_access_iterator_tag ) const
416                {
417                    typedef ForwardIteratorT input_iterator_type;
418                    typedef iterator_range<ForwardIteratorT> result_type;
419
420                    if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < m_N ) )
421                        return result_type( Begin, End );
422
423                    return result_type( End-m_N, End );
424                }
425
426
427            private:
428                unsigned int m_N;
429            };
430
431//  find token functor -----------------------------------------------//
432
433            // find a token in a sequence ( functor )
434            /*
435                This find functor finds a token specified be a predicate
436                in a sequence. It is equivalent of std::find algorithm,
437                with an exception that it return range instead of a single
438                iterator.
439
440                If bCompress is set to true, adjacent matching tokens are
441                concatenated into one match.
442            */
443            template< typename PredicateT >
444            struct token_finderF
445            {
446                // Construction
447                token_finderF(
448                    PredicateT Pred,
449                    token_compress_mode_type eCompress=token_compress_off ) :
450                        m_Pred(Pred), m_eCompress(eCompress) {}
451
452                // Operation
453                template< typename ForwardIteratorT >
454                iterator_range<ForwardIteratorT>
455                operator()(
456                    ForwardIteratorT Begin,
457                    ForwardIteratorT End ) const
458                {
459                    typedef iterator_range<ForwardIteratorT> result_type;
460
461                    ForwardIteratorT It=std::find_if( Begin, End, m_Pred );
462
463                    if( It==End )
464                    {
465                        return result_type( End, End );
466                    }
467                    else
468                    {
469                        ForwardIteratorT It2=It;
470
471                        if( m_eCompress==token_compress_on )
472                        {
473                            // Find first non-matching character
474                            while( It2!=End && m_Pred(*It2) ) ++It2;
475                        }
476                        else
477                        {
478                            // Advance by one possition
479                            ++It2;
480                        }
481
482                        return result_type( It, It2 );
483                    }
484                }
485
486            private:
487                PredicateT m_Pred;
488                token_compress_mode_type m_eCompress;
489            };
490
491//  find range functor -----------------------------------------------//
492
493            // find a range in the sequence ( functor )
494            /*
495                This functor actually does not perform any find operation.
496                It always returns given iterator range as a result.
497            */
498            template<typename ForwardIterator1T>
499            struct range_finderF
500            {
501                typedef ForwardIterator1T input_iterator_type;
502                typedef iterator_range<input_iterator_type> result_type;
503
504                // Construction
505                range_finderF(
506                    input_iterator_type Begin,
507                    input_iterator_type End ) : m_Range(Begin, End) {}
508
509                range_finderF(const iterator_range<input_iterator_type>& Range) :
510                    m_Range(Range) {}
511
512                // Operation
513                template< typename ForwardIterator2T >
514                iterator_range<ForwardIterator2T>
515                operator()(
516                    ForwardIterator2T,
517                    ForwardIterator2T ) const
518                {
519#if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 )
520                    return iterator_range<const ForwardIterator2T>(this->m_Range);
521#elif BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
522                    return iterator_range<ForwardIterator2T>(m_Range.begin(), m_Range.end());
523#else
524                    return m_Range;
525#endif
526                }
527
528            private:
529                iterator_range<input_iterator_type> m_Range;
530            };
531
532
533        } // namespace detail
534    } // namespace algorithm
535} // namespace boost
536
537#endif  // BOOST_STRING_FINDER_DETAIL_HPP
Note: See TracBrowser for help on using the repository browser.