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

source code of include/boost/algorithm/string/detail/finder.hpp