blob: 330c7a534655e8ebf74c1c84f6a206d17c63ebe3 [file] [log] [blame]
Jeff Thompsonef2d5a42013-08-22 19:09:24 -07001// 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 <ndnboost/algorithm/string/config.hpp>
15#include <ndnboost/algorithm/string/constants.hpp>
16#include <ndnboost/detail/iterator.hpp>
17
18#include <ndnboost/range/iterator_range.hpp>
19#include <ndnboost/range/begin.hpp>
20#include <ndnboost/range/end.hpp>
21#include <ndnboost/range/empty.hpp>
22#include <ndnboost/range/as_literal.hpp>
23
24namespace ndnboost {
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(::ndnboost::begin(Search), ::ndnboost::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( ndnboost::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(::ndnboost::begin(Search), ::ndnboost::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( ndnboost::empty(m_Search) )
128 return result_type( End, End );
129
130 typedef BOOST_STRING_TYPENAME ndnboost::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 ForwardIteratorT input_iterator_type;
146 typedef iterator_range<ForwardIteratorT> result_type;
147
148 first_finder_type first_finder(
149 m_Search.begin(), m_Search.end(), m_Comp );
150
151 result_type M=first_finder( Begin, End );
152 result_type Last=M;
153
154 while( M )
155 {
156 Last=M;
157 M=first_finder( ::ndnboost::end(M), End );
158 }
159
160 return Last;
161 }
162
163 // bidirectional iterator
164 template< typename ForwardIteratorT >
165 iterator_range<ForwardIteratorT>
166 findit(
167 ForwardIteratorT Begin,
168 ForwardIteratorT End,
169 std::bidirectional_iterator_tag ) const
170 {
171 typedef iterator_range<ForwardIteratorT> result_type;
172 typedef ForwardIteratorT input_iterator_type;
173
174 // Outer loop
175 for(input_iterator_type OuterIt=End;
176 OuterIt!=Begin; )
177 {
178 input_iterator_type OuterIt2=--OuterIt;
179
180 input_iterator_type InnerIt=OuterIt2;
181 search_iterator_type SubstrIt=m_Search.begin();
182 for(;
183 InnerIt!=End && SubstrIt!=m_Search.end();
184 ++InnerIt,++SubstrIt)
185 {
186 if( !( m_Comp(*InnerIt,*SubstrIt) ) )
187 break;
188 }
189
190 // Substring matching succeeded
191 if( SubstrIt==m_Search.end() )
192 return result_type( OuterIt2, InnerIt );
193 }
194
195 return result_type( End, End );
196 }
197
198 private:
199 iterator_range<search_iterator_type> m_Search;
200 PredicateT m_Comp;
201 };
202
203// find n-th functor -----------------------------------------------//
204
205 // find the n-th match of a subsequence in the sequence ( functor )
206 /*
207 Returns a pair <begin,end> marking the subsequence in the sequence.
208 If the find fails, returns <End,End>
209 */
210 template<typename SearchIteratorT, typename PredicateT>
211 struct nth_finderF
212 {
213 typedef SearchIteratorT search_iterator_type;
214 typedef first_finderF<
215 search_iterator_type,
216 PredicateT> first_finder_type;
217 typedef last_finderF<
218 search_iterator_type,
219 PredicateT> last_finder_type;
220
221 // Construction
222 template< typename SearchT >
223 nth_finderF(
224 const SearchT& Search,
225 int Nth,
226 PredicateT Comp) :
227 m_Search(::ndnboost::begin(Search), ::ndnboost::end(Search)),
228 m_Nth(Nth),
229 m_Comp(Comp) {}
230 nth_finderF(
231 search_iterator_type SearchBegin,
232 search_iterator_type SearchEnd,
233 int Nth,
234 PredicateT Comp) :
235 m_Search(SearchBegin, SearchEnd),
236 m_Nth(Nth),
237 m_Comp(Comp) {}
238
239 // Operation
240 template< typename ForwardIteratorT >
241 iterator_range<ForwardIteratorT>
242 operator()(
243 ForwardIteratorT Begin,
244 ForwardIteratorT End ) const
245 {
246 if(m_Nth>=0)
247 {
248 return find_forward(Begin, End, m_Nth);
249 }
250 else
251 {
252 return find_backward(Begin, End, -m_Nth);
253 }
254
255 }
256
257 private:
258 // Implementation helpers
259 template< typename ForwardIteratorT >
260 iterator_range<ForwardIteratorT>
261 find_forward(
262 ForwardIteratorT Begin,
263 ForwardIteratorT End,
264 unsigned int N) const
265 {
266 typedef ForwardIteratorT input_iterator_type;
267 typedef iterator_range<ForwardIteratorT> result_type;
268
269 // Sanity check
270 if( ndnboost::empty(m_Search) )
271 return result_type( End, End );
272
273 // Instantiate find functor
274 first_finder_type first_finder(
275 m_Search.begin(), m_Search.end(), m_Comp );
276
277 result_type M( Begin, Begin );
278
279 for( unsigned int n=0; n<=N; ++n )
280 {
281 // find next match
282 M=first_finder( ::ndnboost::end(M), End );
283
284 if ( !M )
285 {
286 // Subsequence not found, return
287 return M;
288 }
289 }
290
291 return M;
292 }
293
294 template< typename ForwardIteratorT >
295 iterator_range<ForwardIteratorT>
296 find_backward(
297 ForwardIteratorT Begin,
298 ForwardIteratorT End,
299 unsigned int N) const
300 {
301 typedef ForwardIteratorT input_iterator_type;
302 typedef iterator_range<ForwardIteratorT> result_type;
303
304 // Sanity check
305 if( ndnboost::empty(m_Search) )
306 return result_type( End, End );
307
308 // Instantiate find functor
309 last_finder_type last_finder(
310 m_Search.begin(), m_Search.end(), m_Comp );
311
312 result_type M( End, End );
313
314 for( unsigned int n=1; n<=N; ++n )
315 {
316 // find next match
317 M=last_finder( Begin, ::ndnboost::begin(M) );
318
319 if ( !M )
320 {
321 // Subsequence not found, return
322 return M;
323 }
324 }
325
326 return M;
327 }
328
329
330 private:
331 iterator_range<search_iterator_type> m_Search;
332 int m_Nth;
333 PredicateT m_Comp;
334 };
335
336// find head/tail implementation helpers ---------------------------//
337
338 template<typename ForwardIteratorT>
339 iterator_range<ForwardIteratorT>
340 find_head_impl(
341 ForwardIteratorT Begin,
342 ForwardIteratorT End,
343 unsigned int N,
344 std::forward_iterator_tag )
345 {
346 typedef ForwardIteratorT input_iterator_type;
347 typedef iterator_range<ForwardIteratorT> result_type;
348
349 input_iterator_type It=Begin;
350 for(
351 unsigned int Index=0;
352 Index<N && It!=End; ++Index,++It ) {};
353
354 return result_type( Begin, It );
355 }
356
357 template< typename ForwardIteratorT >
358 iterator_range<ForwardIteratorT>
359 find_head_impl(
360 ForwardIteratorT Begin,
361 ForwardIteratorT End,
362 unsigned int N,
363 std::random_access_iterator_tag )
364 {
365 typedef ForwardIteratorT input_iterator_type;
366 typedef iterator_range<ForwardIteratorT> result_type;
367
368 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
369 return result_type( Begin, End );
370
371 return result_type(Begin,Begin+N);
372 }
373
374 // Find head implementation
375 template<typename ForwardIteratorT>
376 iterator_range<ForwardIteratorT>
377 find_head_impl(
378 ForwardIteratorT Begin,
379 ForwardIteratorT End,
380 unsigned int N )
381 {
382 typedef BOOST_STRING_TYPENAME ndnboost::detail::
383 iterator_traits<ForwardIteratorT>::iterator_category category;
384
385 return ::ndnboost::algorithm::detail::find_head_impl( Begin, End, N, category() );
386 }
387
388 template< typename ForwardIteratorT >
389 iterator_range<ForwardIteratorT>
390 find_tail_impl(
391 ForwardIteratorT Begin,
392 ForwardIteratorT End,
393 unsigned int N,
394 std::forward_iterator_tag )
395 {
396 typedef ForwardIteratorT input_iterator_type;
397 typedef iterator_range<ForwardIteratorT> result_type;
398
399 unsigned int Index=0;
400 input_iterator_type It=Begin;
401 input_iterator_type It2=Begin;
402
403 // Advance It2 by N increments
404 for( Index=0; Index<N && It2!=End; ++Index,++It2 ) {};
405
406 // Advance It, It2 to the end
407 for(; It2!=End; ++It,++It2 ) {};
408
409 return result_type( It, It2 );
410 }
411
412 template< typename ForwardIteratorT >
413 iterator_range<ForwardIteratorT>
414 find_tail_impl(
415 ForwardIteratorT Begin,
416 ForwardIteratorT End,
417 unsigned int N,
418 std::bidirectional_iterator_tag )
419 {
420 typedef ForwardIteratorT input_iterator_type;
421 typedef iterator_range<ForwardIteratorT> result_type;
422
423 input_iterator_type It=End;
424 for(
425 unsigned int Index=0;
426 Index<N && It!=Begin; ++Index,--It ) {};
427
428 return result_type( It, End );
429 }
430
431 template< typename ForwardIteratorT >
432 iterator_range<ForwardIteratorT>
433 find_tail_impl(
434 ForwardIteratorT Begin,
435 ForwardIteratorT End,
436 unsigned int N,
437 std::random_access_iterator_tag )
438 {
439 typedef ForwardIteratorT input_iterator_type;
440 typedef iterator_range<ForwardIteratorT> result_type;
441
442 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
443 return result_type( Begin, End );
444
445 return result_type( End-N, End );
446 }
447
448 // Operation
449 template< typename ForwardIteratorT >
450 iterator_range<ForwardIteratorT>
451 find_tail_impl(
452 ForwardIteratorT Begin,
453 ForwardIteratorT End,
454 unsigned int N )
455 {
456 typedef BOOST_STRING_TYPENAME ndnboost::detail::
457 iterator_traits<ForwardIteratorT>::iterator_category category;
458
459 return ::ndnboost::algorithm::detail::find_tail_impl( Begin, End, N, category() );
460 }
461
462
463
464// find head functor -----------------------------------------------//
465
466
467 // find a head in the sequence ( functor )
468 /*
469 This functor find a head of the specified range. For
470 a specified N, the head is a subsequence of N starting
471 elements of the range.
472 */
473 struct head_finderF
474 {
475 // Construction
476 head_finderF( int N ) : m_N(N) {}
477
478 // Operation
479 template< typename ForwardIteratorT >
480 iterator_range<ForwardIteratorT>
481 operator()(
482 ForwardIteratorT Begin,
483 ForwardIteratorT End ) const
484 {
485 if(m_N>=0)
486 {
487 return ::ndnboost::algorithm::detail::find_head_impl( Begin, End, m_N );
488 }
489 else
490 {
491 iterator_range<ForwardIteratorT> Res=
492 ::ndnboost::algorithm::detail::find_tail_impl( Begin, End, -m_N );
493
494 return ::ndnboost::make_iterator_range(Begin, Res.begin());
495 }
496 }
497
498 private:
499 int m_N;
500 };
501
502// find tail functor -----------------------------------------------//
503
504
505 // find a tail in the sequence ( functor )
506 /*
507 This functor find a tail of the specified range. For
508 a specified N, the head is a subsequence of N starting
509 elements of the range.
510 */
511 struct tail_finderF
512 {
513 // Construction
514 tail_finderF( int N ) : m_N(N) {}
515
516 // Operation
517 template< typename ForwardIteratorT >
518 iterator_range<ForwardIteratorT>
519 operator()(
520 ForwardIteratorT Begin,
521 ForwardIteratorT End ) const
522 {
523 if(m_N>=0)
524 {
525 return ::ndnboost::algorithm::detail::find_tail_impl( Begin, End, m_N );
526 }
527 else
528 {
529 iterator_range<ForwardIteratorT> Res=
530 ::ndnboost::algorithm::detail::find_head_impl( Begin, End, -m_N );
531
532 return ::ndnboost::make_iterator_range(Res.end(), End);
533 }
534 }
535
536 private:
537 int m_N;
538 };
539
540// find token functor -----------------------------------------------//
541
542 // find a token in a sequence ( functor )
543 /*
544 This find functor finds a token specified be a predicate
545 in a sequence. It is equivalent of std::find algorithm,
546 with an exception that it return range instead of a single
547 iterator.
548
549 If bCompress is set to true, adjacent matching tokens are
550 concatenated into one match.
551 */
552 template< typename PredicateT >
553 struct token_finderF
554 {
555 // Construction
556 token_finderF(
557 PredicateT Pred,
558 token_compress_mode_type eCompress=token_compress_off ) :
559 m_Pred(Pred), m_eCompress(eCompress) {}
560
561 // Operation
562 template< typename ForwardIteratorT >
563 iterator_range<ForwardIteratorT>
564 operator()(
565 ForwardIteratorT Begin,
566 ForwardIteratorT End ) const
567 {
568 typedef iterator_range<ForwardIteratorT> result_type;
569
570 ForwardIteratorT It=std::find_if( Begin, End, m_Pred );
571
572 if( It==End )
573 {
574 return result_type( End, End );
575 }
576 else
577 {
578 ForwardIteratorT It2=It;
579
580 if( m_eCompress==token_compress_on )
581 {
582 // Find first non-matching character
583 while( It2!=End && m_Pred(*It2) ) ++It2;
584 }
585 else
586 {
587 // Advance by one position
588 ++It2;
589 }
590
591 return result_type( It, It2 );
592 }
593 }
594
595 private:
596 PredicateT m_Pred;
597 token_compress_mode_type m_eCompress;
598 };
599
600// find range functor -----------------------------------------------//
601
602 // find a range in the sequence ( functor )
603 /*
604 This functor actually does not perform any find operation.
605 It always returns given iterator range as a result.
606 */
607 template<typename ForwardIterator1T>
608 struct range_finderF
609 {
610 typedef ForwardIterator1T input_iterator_type;
611 typedef iterator_range<input_iterator_type> result_type;
612
613 // Construction
614 range_finderF(
615 input_iterator_type Begin,
616 input_iterator_type End ) : m_Range(Begin, End) {}
617
618 range_finderF(const iterator_range<input_iterator_type>& Range) :
619 m_Range(Range) {}
620
621 // Operation
622 template< typename ForwardIterator2T >
623 iterator_range<ForwardIterator2T>
624 operator()(
625 ForwardIterator2T,
626 ForwardIterator2T ) const
627 {
628#if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 )
629 return iterator_range<const ForwardIterator2T>(this->m_Range);
630#elif BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
631 return iterator_range<ForwardIterator2T>(m_Range.begin(), m_Range.end());
632#else
633 return m_Range;
634#endif
635 }
636
637 private:
638 iterator_range<input_iterator_type> m_Range;
639 };
640
641
642 } // namespace detail
643 } // namespace algorithm
644} // namespace ndnboost
645
646#endif // BOOST_STRING_FINDER_DETAIL_HPP