]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
20effc67 | 16 | #include <iterator> |
7c673cae FG |
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 | ||
20effc67 TL |
130 | typedef BOOST_STRING_TYPENAME |
131 | std::iterator_traits<ForwardIteratorT>::iterator_category category; | |
7c673cae FG |
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; | |
20effc67 TL |
347 | for( unsigned int Index=0; Index<N && It!=End; ++Index,++It ) |
348 | ; | |
7c673cae FG |
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 | { | |
20effc67 TL |
377 | typedef BOOST_STRING_TYPENAME |
378 | std::iterator_traits<ForwardIteratorT>::iterator_category category; | |
7c673cae FG |
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 | |
20effc67 TL |
399 | for( Index=0; Index<N && It2!=End; ++Index,++It2 ) |
400 | ; | |
7c673cae FG |
401 | |
402 | // Advance It, It2 to the end | |
20effc67 TL |
403 | for(; It2!=End; ++It,++It2 ) |
404 | ; | |
7c673cae FG |
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; | |
20effc67 TL |
421 | for( unsigned int Index=0; Index<N && It!=Begin; ++Index,--It ) |
422 | ; | |
7c673cae FG |
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 | { | |
20effc67 TL |
451 | typedef BOOST_STRING_TYPENAME |
452 | std::iterator_traits<ForwardIteratorT>::iterator_category category; | |
7c673cae FG |
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 |