Line data Source code
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 <boost/detail/iterator.hpp>
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 :
24 : namespace 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 562 : first_finderF( const SearchT& Search, PredicateT Comp ) :
44 562 : 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 562 : 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 29476 : for(input_iterator_type OuterIt=Begin;
63 29476 : OuterIt!=End;
64 29476 : ++OuterIt)
65 : {
66 : // Sanity check
67 28914 : if( boost::empty(m_Search) )
68 0 : return result_type( End, End );
69 :
70 : input_iterator_type InnerIt=OuterIt;
71 : search_iterator_type SubstrIt=m_Search.begin();
72 0 : for(;
73 28914 : InnerIt!=End && SubstrIt!=m_Search.end();
74 0 : ++InnerIt,++SubstrIt)
75 : {
76 28914 : if( !( m_Comp(*InnerIt,*SubstrIt) ) )
77 : break;
78 : }
79 :
80 : // Substring matching succeeded
81 28914 : if ( SubstrIt==m_Search.end() )
82 0 : return result_type( OuterIt, InnerIt );
83 : }
84 :
85 562 : 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 boost::detail::
131 : 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(
348 : unsigned int Index=0;
349 : Index<N && It!=End; ++Index,++It ) {};
350 :
351 : return result_type( Begin, It );
352 : }
353 :
354 : template< typename ForwardIteratorT >
355 : iterator_range<ForwardIteratorT>
356 0 : find_head_impl(
357 : ForwardIteratorT Begin,
358 : ForwardIteratorT End,
359 : unsigned int N,
360 : std::random_access_iterator_tag )
361 : {
362 : typedef iterator_range<ForwardIteratorT> result_type;
363 :
364 0 : if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
365 0 : return result_type( Begin, End );
366 :
367 0 : return result_type(Begin,Begin+N);
368 : }
369 :
370 : // Find head implementation
371 : template<typename ForwardIteratorT>
372 : iterator_range<ForwardIteratorT>
373 0 : find_head_impl(
374 : ForwardIteratorT Begin,
375 : ForwardIteratorT End,
376 : unsigned int N )
377 : {
378 : typedef BOOST_STRING_TYPENAME boost::detail::
379 : iterator_traits<ForwardIteratorT>::iterator_category category;
380 :
381 0 : return ::boost::algorithm::detail::find_head_impl( Begin, End, N, category() );
382 : }
383 :
384 : template< typename ForwardIteratorT >
385 : iterator_range<ForwardIteratorT>
386 : find_tail_impl(
387 : ForwardIteratorT Begin,
388 : ForwardIteratorT End,
389 : unsigned int N,
390 : std::forward_iterator_tag )
391 : {
392 : typedef ForwardIteratorT input_iterator_type;
393 : typedef iterator_range<ForwardIteratorT> result_type;
394 :
395 : unsigned int Index=0;
396 : input_iterator_type It=Begin;
397 : input_iterator_type It2=Begin;
398 :
399 : // Advance It2 by N increments
400 : for( Index=0; Index<N && It2!=End; ++Index,++It2 ) {};
401 :
402 : // Advance It, It2 to the end
403 : for(; It2!=End; ++It,++It2 ) {};
404 :
405 : return result_type( It, It2 );
406 : }
407 :
408 : template< typename ForwardIteratorT >
409 : iterator_range<ForwardIteratorT>
410 : find_tail_impl(
411 : ForwardIteratorT Begin,
412 : ForwardIteratorT End,
413 : unsigned int N,
414 : std::bidirectional_iterator_tag )
415 : {
416 : typedef ForwardIteratorT input_iterator_type;
417 : typedef iterator_range<ForwardIteratorT> result_type;
418 :
419 : input_iterator_type It=End;
420 : for(
421 : unsigned int Index=0;
422 : Index<N && It!=Begin; ++Index,--It ) {};
423 :
424 : return result_type( It, End );
425 : }
426 :
427 : template< typename ForwardIteratorT >
428 : iterator_range<ForwardIteratorT>
429 0 : 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 0 : if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
438 0 : return result_type( Begin, End );
439 :
440 0 : return result_type( End-N, End );
441 : }
442 :
443 : // Operation
444 : template< typename ForwardIteratorT >
445 : iterator_range<ForwardIteratorT>
446 0 : find_tail_impl(
447 : ForwardIteratorT Begin,
448 : ForwardIteratorT End,
449 : unsigned int N )
450 : {
451 : typedef BOOST_STRING_TYPENAME boost::detail::
452 : iterator_traits<ForwardIteratorT>::iterator_category category;
453 :
454 0 : 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 0 : tail_finderF( int N ) : m_N(N) {}
510 :
511 : // Operation
512 : template< typename ForwardIteratorT >
513 : iterator_range<ForwardIteratorT>
514 0 : operator()(
515 : ForwardIteratorT Begin,
516 : ForwardIteratorT End ) const
517 : {
518 0 : if(m_N>=0)
519 : {
520 0 : return ::boost::algorithm::detail::find_tail_impl( Begin, End, m_N );
521 : }
522 : else
523 : {
524 : iterator_range<ForwardIteratorT> Res=
525 0 : ::boost::algorithm::detail::find_head_impl( Begin, End, -m_N );
526 :
527 0 : 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 0 : struct token_finderF
549 : {
550 : // Construction
551 0 : token_finderF(
552 : PredicateT Pred,
553 : token_compress_mode_type eCompress=token_compress_off ) :
554 0 : m_Pred(Pred), m_eCompress(eCompress) {}
555 :
556 : // Operation
557 : template< typename ForwardIteratorT >
558 : iterator_range<ForwardIteratorT>
559 0 : operator()(
560 : ForwardIteratorT Begin,
561 : ForwardIteratorT End ) const
562 : {
563 : typedef iterator_range<ForwardIteratorT> result_type;
564 :
565 0 : ForwardIteratorT It=std::find_if( Begin, End, m_Pred );
566 :
567 0 : if( It==End )
568 : {
569 0 : return result_type( End, End );
570 : }
571 : else
572 : {
573 0 : ForwardIteratorT It2=It;
574 :
575 0 : if( m_eCompress==token_compress_on )
576 : {
577 : // Find first non-matching character
578 0 : while( It2!=End && m_Pred(*It2) ) ++It2;
579 : }
580 : else
581 : {
582 : // Advance by one position
583 0 : ++It2;
584 : }
585 :
586 0 : 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
|
