1 // Boost string_algo library finder.hpp header file ---------------------------//
3 // Copyright Pavol Droba 2002-2006.
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)
9 // See http://www.boost.org/ for updates, documentation, and revision history.
11 #ifndef BOOST_STRING_FINDER_DETAIL_HPP
12 #define BOOST_STRING_FINDER_DETAIL_HPP
14 #include <boost/algorithm/string/config.hpp>
15 #include <boost/algorithm/string/constants.hpp>
16 #include <boost/detail/iterator.hpp>
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>
29 // find first functor -----------------------------------------------//
31 // find a subsequence in the sequence ( functor )
33 Returns a pair <begin,end> marking the subsequence in the sequence.
34 If the find fails, functor returns <End,End>
36 template<typename SearchIteratorT,typename PredicateT>
39 typedef SearchIteratorT search_iterator_type;
42 template< typename SearchT >
43 first_finderF( const SearchT& Search, PredicateT Comp ) :
44 m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
46 search_iterator_type SearchBegin,
47 search_iterator_type SearchEnd,
49 m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}
52 template< typename ForwardIteratorT >
53 iterator_range<ForwardIteratorT>
55 ForwardIteratorT Begin,
56 ForwardIteratorT End ) const
58 typedef iterator_range<ForwardIteratorT> result_type;
59 typedef ForwardIteratorT input_iterator_type;
62 for(input_iterator_type OuterIt=Begin;
67 if( boost::empty(m_Search) )
68 return result_type( End, End );
70 input_iterator_type InnerIt=OuterIt;
71 search_iterator_type SubstrIt=m_Search.begin();
73 InnerIt!=End && SubstrIt!=m_Search.end();
76 if( !( m_Comp(*InnerIt,*SubstrIt) ) )
80 // Substring matching succeeded
81 if ( SubstrIt==m_Search.end() )
82 return result_type( OuterIt, InnerIt );
85 return result_type( End, End );
89 iterator_range<search_iterator_type> m_Search;
93 // find last functor -----------------------------------------------//
95 // find the last match a subsequence in the sequence ( functor )
97 Returns a pair <begin,end> marking the subsequence in the sequence.
98 If the find fails, returns <End,End>
100 template<typename SearchIteratorT, typename PredicateT>
103 typedef SearchIteratorT search_iterator_type;
104 typedef first_finderF<
105 search_iterator_type,
106 PredicateT> first_finder_type;
109 template< typename SearchT >
110 last_finderF( const SearchT& Search, PredicateT Comp ) :
111 m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
113 search_iterator_type SearchBegin,
114 search_iterator_type SearchEnd,
116 m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}
119 template< typename ForwardIteratorT >
120 iterator_range<ForwardIteratorT>
122 ForwardIteratorT Begin,
123 ForwardIteratorT End ) const
125 typedef iterator_range<ForwardIteratorT> result_type;
127 if( boost::empty(m_Search) )
128 return result_type( End, End );
130 typedef BOOST_STRING_TYPENAME boost::detail::
131 iterator_traits<ForwardIteratorT>::iterator_category category;
133 return findit( Begin, End, category() );
138 template< typename ForwardIteratorT >
139 iterator_range<ForwardIteratorT>
141 ForwardIteratorT Begin,
142 ForwardIteratorT End,
143 std::forward_iterator_tag ) const
145 typedef iterator_range<ForwardIteratorT> result_type;
147 first_finder_type first_finder(
148 m_Search.begin(), m_Search.end(), m_Comp );
150 result_type M=first_finder( Begin, End );
156 M=first_finder( ::boost::end(M), End );
162 // bidirectional iterator
163 template< typename ForwardIteratorT >
164 iterator_range<ForwardIteratorT>
166 ForwardIteratorT Begin,
167 ForwardIteratorT End,
168 std::bidirectional_iterator_tag ) const
170 typedef iterator_range<ForwardIteratorT> result_type;
171 typedef ForwardIteratorT input_iterator_type;
174 for(input_iterator_type OuterIt=End;
177 input_iterator_type OuterIt2=--OuterIt;
179 input_iterator_type InnerIt=OuterIt2;
180 search_iterator_type SubstrIt=m_Search.begin();
182 InnerIt!=End && SubstrIt!=m_Search.end();
183 ++InnerIt,++SubstrIt)
185 if( !( m_Comp(*InnerIt,*SubstrIt) ) )
189 // Substring matching succeeded
190 if( SubstrIt==m_Search.end() )
191 return result_type( OuterIt2, InnerIt );
194 return result_type( End, End );
198 iterator_range<search_iterator_type> m_Search;
202 // find n-th functor -----------------------------------------------//
204 // find the n-th match of a subsequence in the sequence ( functor )
206 Returns a pair <begin,end> marking the subsequence in the sequence.
207 If the find fails, returns <End,End>
209 template<typename SearchIteratorT, typename PredicateT>
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;
221 template< typename SearchT >
223 const SearchT& Search,
226 m_Search(::boost::begin(Search), ::boost::end(Search)),
230 search_iterator_type SearchBegin,
231 search_iterator_type SearchEnd,
234 m_Search(SearchBegin, SearchEnd),
239 template< typename ForwardIteratorT >
240 iterator_range<ForwardIteratorT>
242 ForwardIteratorT Begin,
243 ForwardIteratorT End ) const
247 return find_forward(Begin, End, m_Nth);
251 return find_backward(Begin, End, -m_Nth);
257 // Implementation helpers
258 template< typename ForwardIteratorT >
259 iterator_range<ForwardIteratorT>
261 ForwardIteratorT Begin,
262 ForwardIteratorT End,
263 unsigned int N) const
265 typedef iterator_range<ForwardIteratorT> result_type;
268 if( boost::empty(m_Search) )
269 return result_type( End, End );
271 // Instantiate find functor
272 first_finder_type first_finder(
273 m_Search.begin(), m_Search.end(), m_Comp );
275 result_type M( Begin, Begin );
277 for( unsigned int n=0; n<=N; ++n )
280 M=first_finder( ::boost::end(M), End );
284 // Subsequence not found, return
292 template< typename ForwardIteratorT >
293 iterator_range<ForwardIteratorT>
295 ForwardIteratorT Begin,
296 ForwardIteratorT End,
297 unsigned int N) const
299 typedef iterator_range<ForwardIteratorT> result_type;
302 if( boost::empty(m_Search) )
303 return result_type( End, End );
305 // Instantiate find functor
306 last_finder_type last_finder(
307 m_Search.begin(), m_Search.end(), m_Comp );
309 result_type M( End, End );
311 for( unsigned int n=1; n<=N; ++n )
314 M=last_finder( Begin, ::boost::begin(M) );
318 // Subsequence not found, return
328 iterator_range<search_iterator_type> m_Search;
333 // find head/tail implementation helpers ---------------------------//
335 template<typename ForwardIteratorT>
336 iterator_range<ForwardIteratorT>
338 ForwardIteratorT Begin,
339 ForwardIteratorT End,
341 std::forward_iterator_tag )
343 typedef ForwardIteratorT input_iterator_type;
344 typedef iterator_range<ForwardIteratorT> result_type;
346 input_iterator_type It=Begin;
348 unsigned int Index=0;
349 Index<N && It!=End; ++Index,++It ) {};
351 return result_type( Begin, It );
354 template< typename ForwardIteratorT >
355 iterator_range<ForwardIteratorT>
357 ForwardIteratorT Begin,
358 ForwardIteratorT End,
360 std::random_access_iterator_tag )
362 typedef iterator_range<ForwardIteratorT> result_type;
364 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
365 return result_type( Begin, End );
367 return result_type(Begin,Begin+N);
370 // Find head implementation
371 template<typename ForwardIteratorT>
372 iterator_range<ForwardIteratorT>
374 ForwardIteratorT Begin,
375 ForwardIteratorT End,
378 typedef BOOST_STRING_TYPENAME boost::detail::
379 iterator_traits<ForwardIteratorT>::iterator_category category;
381 return ::boost::algorithm::detail::find_head_impl( Begin, End, N, category() );
384 template< typename ForwardIteratorT >
385 iterator_range<ForwardIteratorT>
387 ForwardIteratorT Begin,
388 ForwardIteratorT End,
390 std::forward_iterator_tag )
392 typedef ForwardIteratorT input_iterator_type;
393 typedef iterator_range<ForwardIteratorT> result_type;
395 unsigned int Index=0;
396 input_iterator_type It=Begin;
397 input_iterator_type It2=Begin;
399 // Advance It2 by N increments
400 for( Index=0; Index<N && It2!=End; ++Index,++It2 ) {};
402 // Advance It, It2 to the end
403 for(; It2!=End; ++It,++It2 ) {};
405 return result_type( It, It2 );
408 template< typename ForwardIteratorT >
409 iterator_range<ForwardIteratorT>
411 ForwardIteratorT Begin,
412 ForwardIteratorT End,
414 std::bidirectional_iterator_tag )
416 typedef ForwardIteratorT input_iterator_type;
417 typedef iterator_range<ForwardIteratorT> result_type;
419 input_iterator_type It=End;
421 unsigned int Index=0;
422 Index<N && It!=Begin; ++Index,--It ) {};
424 return result_type( It, End );
427 template< typename ForwardIteratorT >
428 iterator_range<ForwardIteratorT>
430 ForwardIteratorT Begin,
431 ForwardIteratorT End,
433 std::random_access_iterator_tag )
435 typedef iterator_range<ForwardIteratorT> result_type;
437 if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
438 return result_type( Begin, End );
440 return result_type( End-N, End );
444 template< typename ForwardIteratorT >
445 iterator_range<ForwardIteratorT>
447 ForwardIteratorT Begin,
448 ForwardIteratorT End,
451 typedef BOOST_STRING_TYPENAME boost::detail::
452 iterator_traits<ForwardIteratorT>::iterator_category category;
454 return ::boost::algorithm::detail::find_tail_impl( Begin, End, N, category() );
459 // find head functor -----------------------------------------------//
462 // find a head in the sequence ( functor )
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.
471 head_finderF( int N ) : m_N(N) {}
474 template< typename ForwardIteratorT >
475 iterator_range<ForwardIteratorT>
477 ForwardIteratorT Begin,
478 ForwardIteratorT End ) const
482 return ::boost::algorithm::detail::find_head_impl( Begin, End, m_N );
486 iterator_range<ForwardIteratorT> Res=
487 ::boost::algorithm::detail::find_tail_impl( Begin, End, -m_N );
489 return ::boost::make_iterator_range(Begin, Res.begin());
497 // find tail functor -----------------------------------------------//
500 // find a tail in the sequence ( functor )
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.
509 tail_finderF( int N ) : m_N(N) {}
512 template< typename ForwardIteratorT >
513 iterator_range<ForwardIteratorT>
515 ForwardIteratorT Begin,
516 ForwardIteratorT End ) const
520 return ::boost::algorithm::detail::find_tail_impl( Begin, End, m_N );
524 iterator_range<ForwardIteratorT> Res=
525 ::boost::algorithm::detail::find_head_impl( Begin, End, -m_N );
527 return ::boost::make_iterator_range(Res.end(), End);
535 // find token functor -----------------------------------------------//
537 // find a token in a sequence ( functor )
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
544 If bCompress is set to true, adjacent matching tokens are
545 concatenated into one match.
547 template< typename PredicateT >
553 token_compress_mode_type eCompress=token_compress_off ) :
554 m_Pred(Pred), m_eCompress(eCompress) {}
557 template< typename ForwardIteratorT >
558 iterator_range<ForwardIteratorT>
560 ForwardIteratorT Begin,
561 ForwardIteratorT End ) const
563 typedef iterator_range<ForwardIteratorT> result_type;
565 ForwardIteratorT It=std::find_if( Begin, End, m_Pred );
569 return result_type( End, End );
573 ForwardIteratorT It2=It;
575 if( m_eCompress==token_compress_on )
577 // Find first non-matching character
578 while( It2!=End && m_Pred(*It2) ) ++It2;
582 // Advance by one position
586 return result_type( It, It2 );
592 token_compress_mode_type m_eCompress;
595 // find range functor -----------------------------------------------//
597 // find a range in the sequence ( functor )
599 This functor actually does not perform any find operation.
600 It always returns given iterator range as a result.
602 template<typename ForwardIterator1T>
605 typedef ForwardIterator1T input_iterator_type;
606 typedef iterator_range<input_iterator_type> result_type;
610 input_iterator_type Begin,
611 input_iterator_type End ) : m_Range(Begin, End) {}
613 range_finderF(const iterator_range<input_iterator_type>& Range) :
617 template< typename ForwardIterator2T >
618 iterator_range<ForwardIterator2T>
621 ForwardIterator2T ) const
623 #if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 )
624 return iterator_range<const ForwardIterator2T>(this->m_Range);
631 iterator_range<input_iterator_type> m_Range;
635 } // namespace detail
636 } // namespace algorithm
639 #endif // BOOST_STRING_FINDER_DETAIL_HPP