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 | 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 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 | 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 | if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) ) |
365 | return result_type( Begin, End ); |
366 | |
367 | return result_type(Begin,Begin+N); |
368 | } |
369 | |
370 | // Find head implementation |
371 | template<typename ForwardIteratorT> |
372 | iterator_range<ForwardIteratorT> |
373 | 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 | 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 | 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 boost::detail:: |
452 | 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 | |