Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / algorithm / string / detail / finder.hpp
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
22 namespace 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