diff options
Diffstat (limited to 'contrib/src/boost/algorithm/string/detail/finder.hpp')
| -rw-r--r-- | contrib/src/boost/algorithm/string/detail/finder.hpp | 1278 |
1 files changed, 639 insertions, 639 deletions
diff --git a/contrib/src/boost/algorithm/string/detail/finder.hpp b/contrib/src/boost/algorithm/string/detail/finder.hpp index 5bf36a9..a2a9582 100644 --- a/contrib/src/boost/algorithm/string/detail/finder.hpp +++ b/contrib/src/boost/algorithm/string/detail/finder.hpp @@ -1,639 +1,639 @@ -// Boost string_algo library finder.hpp header file ---------------------------//
-
-// Copyright Pavol Droba 2002-2006.
-//
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org/ for updates, documentation, and revision history.
-
-#ifndef BOOST_STRING_FINDER_DETAIL_HPP
-#define BOOST_STRING_FINDER_DETAIL_HPP
-
-#include <boost/algorithm/string/config.hpp>
-#include <boost/algorithm/string/constants.hpp>
-#include <boost/detail/iterator.hpp>
-
-#include <boost/range/iterator_range_core.hpp>
-#include <boost/range/begin.hpp>
-#include <boost/range/end.hpp>
-#include <boost/range/empty.hpp>
-#include <boost/range/as_literal.hpp>
-
-namespace boost {
- namespace algorithm {
- namespace detail {
-
-
-// find first functor -----------------------------------------------//
-
- // find a subsequence in the sequence ( functor )
- /*
- Returns a pair <begin,end> marking the subsequence in the sequence.
- If the find fails, functor returns <End,End>
- */
- template<typename SearchIteratorT,typename PredicateT>
- struct first_finderF
- {
- typedef SearchIteratorT search_iterator_type;
-
- // Construction
- template< typename SearchT >
- first_finderF( const SearchT& Search, PredicateT Comp ) :
- m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
- first_finderF(
- search_iterator_type SearchBegin,
- search_iterator_type SearchEnd,
- PredicateT Comp ) :
- m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
- typedef ForwardIteratorT input_iterator_type;
-
- // Outer loop
- for(input_iterator_type OuterIt=Begin;
- OuterIt!=End;
- ++OuterIt)
- {
- // Sanity check
- if( boost::empty(m_Search) )
- return result_type( End, End );
-
- input_iterator_type InnerIt=OuterIt;
- search_iterator_type SubstrIt=m_Search.begin();
- for(;
- InnerIt!=End && SubstrIt!=m_Search.end();
- ++InnerIt,++SubstrIt)
- {
- if( !( m_Comp(*InnerIt,*SubstrIt) ) )
- break;
- }
-
- // Substring matching succeeded
- if ( SubstrIt==m_Search.end() )
- return result_type( OuterIt, InnerIt );
- }
-
- return result_type( End, End );
- }
-
- private:
- iterator_range<search_iterator_type> m_Search;
- PredicateT m_Comp;
- };
-
-// find last functor -----------------------------------------------//
-
- // find the last match a subsequence in the sequence ( functor )
- /*
- Returns a pair <begin,end> marking the subsequence in the sequence.
- If the find fails, returns <End,End>
- */
- template<typename SearchIteratorT, typename PredicateT>
- struct last_finderF
- {
- typedef SearchIteratorT search_iterator_type;
- typedef first_finderF<
- search_iterator_type,
- PredicateT> first_finder_type;
-
- // Construction
- template< typename SearchT >
- last_finderF( const SearchT& Search, PredicateT Comp ) :
- m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
- last_finderF(
- search_iterator_type SearchBegin,
- search_iterator_type SearchEnd,
- PredicateT Comp ) :
- m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
-
- if( boost::empty(m_Search) )
- return result_type( End, End );
-
- typedef BOOST_STRING_TYPENAME boost::detail::
- iterator_traits<ForwardIteratorT>::iterator_category category;
-
- return findit( Begin, End, category() );
- }
-
- private:
- // forward iterator
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- findit(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- std::forward_iterator_tag ) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
-
- first_finder_type first_finder(
- m_Search.begin(), m_Search.end(), m_Comp );
-
- result_type M=first_finder( Begin, End );
- result_type Last=M;
-
- while( M )
- {
- Last=M;
- M=first_finder( ::boost::end(M), End );
- }
-
- return Last;
- }
-
- // bidirectional iterator
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- findit(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- std::bidirectional_iterator_tag ) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
- typedef ForwardIteratorT input_iterator_type;
-
- // Outer loop
- for(input_iterator_type OuterIt=End;
- OuterIt!=Begin; )
- {
- input_iterator_type OuterIt2=--OuterIt;
-
- input_iterator_type InnerIt=OuterIt2;
- search_iterator_type SubstrIt=m_Search.begin();
- for(;
- InnerIt!=End && SubstrIt!=m_Search.end();
- ++InnerIt,++SubstrIt)
- {
- if( !( m_Comp(*InnerIt,*SubstrIt) ) )
- break;
- }
-
- // Substring matching succeeded
- if( SubstrIt==m_Search.end() )
- return result_type( OuterIt2, InnerIt );
- }
-
- return result_type( End, End );
- }
-
- private:
- iterator_range<search_iterator_type> m_Search;
- PredicateT m_Comp;
- };
-
-// find n-th functor -----------------------------------------------//
-
- // find the n-th match of a subsequence in the sequence ( functor )
- /*
- Returns a pair <begin,end> marking the subsequence in the sequence.
- If the find fails, returns <End,End>
- */
- template<typename SearchIteratorT, typename PredicateT>
- struct nth_finderF
- {
- typedef SearchIteratorT search_iterator_type;
- typedef first_finderF<
- search_iterator_type,
- PredicateT> first_finder_type;
- typedef last_finderF<
- search_iterator_type,
- PredicateT> last_finder_type;
-
- // Construction
- template< typename SearchT >
- nth_finderF(
- const SearchT& Search,
- int Nth,
- PredicateT Comp) :
- m_Search(::boost::begin(Search), ::boost::end(Search)),
- m_Nth(Nth),
- m_Comp(Comp) {}
- nth_finderF(
- search_iterator_type SearchBegin,
- search_iterator_type SearchEnd,
- int Nth,
- PredicateT Comp) :
- m_Search(SearchBegin, SearchEnd),
- m_Nth(Nth),
- m_Comp(Comp) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- if(m_Nth>=0)
- {
- return find_forward(Begin, End, m_Nth);
- }
- else
- {
- return find_backward(Begin, End, -m_Nth);
- }
-
- }
-
- private:
- // Implementation helpers
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_forward(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
-
- // Sanity check
- if( boost::empty(m_Search) )
- return result_type( End, End );
-
- // Instantiate find functor
- first_finder_type first_finder(
- m_Search.begin(), m_Search.end(), m_Comp );
-
- result_type M( Begin, Begin );
-
- for( unsigned int n=0; n<=N; ++n )
- {
- // find next match
- M=first_finder( ::boost::end(M), End );
-
- if ( !M )
- {
- // Subsequence not found, return
- return M;
- }
- }
-
- return M;
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_backward(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
-
- // Sanity check
- if( boost::empty(m_Search) )
- return result_type( End, End );
-
- // Instantiate find functor
- last_finder_type last_finder(
- m_Search.begin(), m_Search.end(), m_Comp );
-
- result_type M( End, End );
-
- for( unsigned int n=1; n<=N; ++n )
- {
- // find next match
- M=last_finder( Begin, ::boost::begin(M) );
-
- if ( !M )
- {
- // Subsequence not found, return
- return M;
- }
- }
-
- return M;
- }
-
-
- private:
- iterator_range<search_iterator_type> m_Search;
- int m_Nth;
- PredicateT m_Comp;
- };
-
-// find head/tail implementation helpers ---------------------------//
-
- template<typename ForwardIteratorT>
- iterator_range<ForwardIteratorT>
- find_head_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::forward_iterator_tag )
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- input_iterator_type It=Begin;
- for(
- unsigned int Index=0;
- Index<N && It!=End; ++Index,++It ) {};
-
- return result_type( Begin, It );
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_head_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::random_access_iterator_tag )
- {
- typedef iterator_range<ForwardIteratorT> result_type;
-
- if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
- return result_type( Begin, End );
-
- return result_type(Begin,Begin+N);
- }
-
- // Find head implementation
- template<typename ForwardIteratorT>
- iterator_range<ForwardIteratorT>
- find_head_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N )
- {
- typedef BOOST_STRING_TYPENAME boost::detail::
- iterator_traits<ForwardIteratorT>::iterator_category category;
-
- return ::boost::algorithm::detail::find_head_impl( Begin, End, N, category() );
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_tail_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::forward_iterator_tag )
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- unsigned int Index=0;
- input_iterator_type It=Begin;
- input_iterator_type It2=Begin;
-
- // Advance It2 by N increments
- for( Index=0; Index<N && It2!=End; ++Index,++It2 ) {};
-
- // Advance It, It2 to the end
- for(; It2!=End; ++It,++It2 ) {};
-
- return result_type( It, It2 );
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_tail_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::bidirectional_iterator_tag )
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- input_iterator_type It=End;
- for(
- unsigned int Index=0;
- Index<N && It!=Begin; ++Index,--It ) {};
-
- return result_type( It, End );
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_tail_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::random_access_iterator_tag )
- {
- typedef iterator_range<ForwardIteratorT> result_type;
-
- if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
- return result_type( Begin, End );
-
- return result_type( End-N, End );
- }
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_tail_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N )
- {
- typedef BOOST_STRING_TYPENAME boost::detail::
- iterator_traits<ForwardIteratorT>::iterator_category category;
-
- return ::boost::algorithm::detail::find_tail_impl( Begin, End, N, category() );
- }
-
-
-
-// find head functor -----------------------------------------------//
-
-
- // find a head in the sequence ( functor )
- /*
- This functor find a head of the specified range. For
- a specified N, the head is a subsequence of N starting
- elements of the range.
- */
- struct head_finderF
- {
- // Construction
- head_finderF( int N ) : m_N(N) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- if(m_N>=0)
- {
- return ::boost::algorithm::detail::find_head_impl( Begin, End, m_N );
- }
- else
- {
- iterator_range<ForwardIteratorT> Res=
- ::boost::algorithm::detail::find_tail_impl( Begin, End, -m_N );
-
- return ::boost::make_iterator_range(Begin, Res.begin());
- }
- }
-
- private:
- int m_N;
- };
-
-// find tail functor -----------------------------------------------//
-
-
- // find a tail in the sequence ( functor )
- /*
- This functor find a tail of the specified range. For
- a specified N, the head is a subsequence of N starting
- elements of the range.
- */
- struct tail_finderF
- {
- // Construction
- tail_finderF( int N ) : m_N(N) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- if(m_N>=0)
- {
- return ::boost::algorithm::detail::find_tail_impl( Begin, End, m_N );
- }
- else
- {
- iterator_range<ForwardIteratorT> Res=
- ::boost::algorithm::detail::find_head_impl( Begin, End, -m_N );
-
- return ::boost::make_iterator_range(Res.end(), End);
- }
- }
-
- private:
- int m_N;
- };
-
-// find token functor -----------------------------------------------//
-
- // find a token in a sequence ( functor )
- /*
- This find functor finds a token specified be a predicate
- in a sequence. It is equivalent of std::find algorithm,
- with an exception that it return range instead of a single
- iterator.
-
- If bCompress is set to true, adjacent matching tokens are
- concatenated into one match.
- */
- template< typename PredicateT >
- struct token_finderF
- {
- // Construction
- token_finderF(
- PredicateT Pred,
- token_compress_mode_type eCompress=token_compress_off ) :
- m_Pred(Pred), m_eCompress(eCompress) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
-
- ForwardIteratorT It=std::find_if( Begin, End, m_Pred );
-
- if( It==End )
- {
- return result_type( End, End );
- }
- else
- {
- ForwardIteratorT It2=It;
-
- if( m_eCompress==token_compress_on )
- {
- // Find first non-matching character
- while( It2!=End && m_Pred(*It2) ) ++It2;
- }
- else
- {
- // Advance by one position
- ++It2;
- }
-
- return result_type( It, It2 );
- }
- }
-
- private:
- PredicateT m_Pred;
- token_compress_mode_type m_eCompress;
- };
-
-// find range functor -----------------------------------------------//
-
- // find a range in the sequence ( functor )
- /*
- This functor actually does not perform any find operation.
- It always returns given iterator range as a result.
- */
- template<typename ForwardIterator1T>
- struct range_finderF
- {
- typedef ForwardIterator1T input_iterator_type;
- typedef iterator_range<input_iterator_type> result_type;
-
- // Construction
- range_finderF(
- input_iterator_type Begin,
- input_iterator_type End ) : m_Range(Begin, End) {}
-
- range_finderF(const iterator_range<input_iterator_type>& Range) :
- m_Range(Range) {}
-
- // Operation
- template< typename ForwardIterator2T >
- iterator_range<ForwardIterator2T>
- operator()(
- ForwardIterator2T,
- ForwardIterator2T ) const
- {
-#if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 )
- return iterator_range<const ForwardIterator2T>(this->m_Range);
-#else
- return m_Range;
-#endif
- }
-
- private:
- iterator_range<input_iterator_type> m_Range;
- };
-
-
- } // namespace detail
- } // namespace algorithm
-} // namespace boost
-
-#endif // BOOST_STRING_FINDER_DETAIL_HPP
+// Boost string_algo library finder.hpp header file ---------------------------// + +// Copyright Pavol Droba 2002-2006. +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// See http://www.boost.org/ for updates, documentation, and revision history. + +#ifndef BOOST_STRING_FINDER_DETAIL_HPP +#define BOOST_STRING_FINDER_DETAIL_HPP + +#include <boost/algorithm/string/config.hpp> +#include <boost/algorithm/string/constants.hpp> +#include <boost/detail/iterator.hpp> + +#include <boost/range/iterator_range_core.hpp> +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> +#include <boost/range/empty.hpp> +#include <boost/range/as_literal.hpp> + +namespace boost { + namespace algorithm { + namespace detail { + + +// find first functor -----------------------------------------------// + + // find a subsequence in the sequence ( functor ) + /* + Returns a pair <begin,end> marking the subsequence in the sequence. + If the find fails, functor returns <End,End> + */ + template<typename SearchIteratorT,typename PredicateT> + struct first_finderF + { + typedef SearchIteratorT search_iterator_type; + + // Construction + template< typename SearchT > + first_finderF( const SearchT& Search, PredicateT Comp ) : + m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {} + first_finderF( + search_iterator_type SearchBegin, + search_iterator_type SearchEnd, + PredicateT Comp ) : + m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {} + + // Operation + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + operator()( + ForwardIteratorT Begin, + ForwardIteratorT End ) const + { + typedef iterator_range<ForwardIteratorT> result_type; + typedef ForwardIteratorT input_iterator_type; + + // Outer loop + for(input_iterator_type OuterIt=Begin; + OuterIt!=End; + ++OuterIt) + { + // Sanity check + if( boost::empty(m_Search) ) + return result_type( End, End ); + + input_iterator_type InnerIt=OuterIt; + search_iterator_type SubstrIt=m_Search.begin(); + for(; + InnerIt!=End && SubstrIt!=m_Search.end(); + ++InnerIt,++SubstrIt) + { + if( !( m_Comp(*InnerIt,*SubstrIt) ) ) + break; + } + + // Substring matching succeeded + if ( SubstrIt==m_Search.end() ) + return result_type( OuterIt, InnerIt ); + } + + return result_type( End, End ); + } + + private: + iterator_range<search_iterator_type> m_Search; + PredicateT m_Comp; + }; + +// find last functor -----------------------------------------------// + + // find the last match a subsequence in the sequence ( functor ) + /* + Returns a pair <begin,end> marking the subsequence in the sequence. + If the find fails, returns <End,End> + */ + template<typename SearchIteratorT, typename PredicateT> + struct last_finderF + { + typedef SearchIteratorT search_iterator_type; + typedef first_finderF< + search_iterator_type, + PredicateT> first_finder_type; + + // Construction + template< typename SearchT > + last_finderF( const SearchT& Search, PredicateT Comp ) : + m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {} + last_finderF( + search_iterator_type SearchBegin, + search_iterator_type SearchEnd, + PredicateT Comp ) : + m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {} + + // Operation + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + operator()( + ForwardIteratorT Begin, + ForwardIteratorT End ) const + { + typedef iterator_range<ForwardIteratorT> result_type; + + if( boost::empty(m_Search) ) + return result_type( End, End ); + + typedef BOOST_STRING_TYPENAME boost::detail:: + iterator_traits<ForwardIteratorT>::iterator_category category; + + return findit( Begin, End, category() ); + } + + private: + // forward iterator + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + findit( + ForwardIteratorT Begin, + ForwardIteratorT End, + std::forward_iterator_tag ) const + { + typedef iterator_range<ForwardIteratorT> result_type; + + first_finder_type first_finder( + m_Search.begin(), m_Search.end(), m_Comp ); + + result_type M=first_finder( Begin, End ); + result_type Last=M; + + while( M ) + { + Last=M; + M=first_finder( ::boost::end(M), End ); + } + + return Last; + } + + // bidirectional iterator + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + findit( + ForwardIteratorT Begin, + ForwardIteratorT End, + std::bidirectional_iterator_tag ) const + { + typedef iterator_range<ForwardIteratorT> result_type; + typedef ForwardIteratorT input_iterator_type; + + // Outer loop + for(input_iterator_type OuterIt=End; + OuterIt!=Begin; ) + { + input_iterator_type OuterIt2=--OuterIt; + + input_iterator_type InnerIt=OuterIt2; + search_iterator_type SubstrIt=m_Search.begin(); + for(; + InnerIt!=End && SubstrIt!=m_Search.end(); + ++InnerIt,++SubstrIt) + { + if( !( m_Comp(*InnerIt,*SubstrIt) ) ) + break; + } + + // Substring matching succeeded + if( SubstrIt==m_Search.end() ) + return result_type( OuterIt2, InnerIt ); + } + + return result_type( End, End ); + } + + private: + iterator_range<search_iterator_type> m_Search; + PredicateT m_Comp; + }; + +// find n-th functor -----------------------------------------------// + + // find the n-th match of a subsequence in the sequence ( functor ) + /* + Returns a pair <begin,end> marking the subsequence in the sequence. + If the find fails, returns <End,End> + */ + template<typename SearchIteratorT, typename PredicateT> + struct nth_finderF + { + typedef SearchIteratorT search_iterator_type; + typedef first_finderF< + search_iterator_type, + PredicateT> first_finder_type; + typedef last_finderF< + search_iterator_type, + PredicateT> last_finder_type; + + // Construction + template< typename SearchT > + nth_finderF( + const SearchT& Search, + int Nth, + PredicateT Comp) : + m_Search(::boost::begin(Search), ::boost::end(Search)), + m_Nth(Nth), + m_Comp(Comp) {} + nth_finderF( + search_iterator_type SearchBegin, + search_iterator_type SearchEnd, + int Nth, + PredicateT Comp) : + m_Search(SearchBegin, SearchEnd), + m_Nth(Nth), + m_Comp(Comp) {} + + // Operation + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + operator()( + ForwardIteratorT Begin, + ForwardIteratorT End ) const + { + if(m_Nth>=0) + { + return find_forward(Begin, End, m_Nth); + } + else + { + return find_backward(Begin, End, -m_Nth); + } + + } + + private: + // Implementation helpers + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + find_forward( + ForwardIteratorT Begin, + ForwardIteratorT End, + unsigned int N) const + { + typedef iterator_range<ForwardIteratorT> result_type; + + // Sanity check + if( boost::empty(m_Search) ) + return result_type( End, End ); + + // Instantiate find functor + first_finder_type first_finder( + m_Search.begin(), m_Search.end(), m_Comp ); + + result_type M( Begin, Begin ); + + for( unsigned int n=0; n<=N; ++n ) + { + // find next match + M=first_finder( ::boost::end(M), End ); + + if ( !M ) + { + // Subsequence not found, return + return M; + } + } + + return M; + } + + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + find_backward( + ForwardIteratorT Begin, + ForwardIteratorT End, + unsigned int N) const + { + typedef iterator_range<ForwardIteratorT> result_type; + + // Sanity check + if( boost::empty(m_Search) ) + return result_type( End, End ); + + // Instantiate find functor + last_finder_type last_finder( + m_Search.begin(), m_Search.end(), m_Comp ); + + result_type M( End, End ); + + for( unsigned int n=1; n<=N; ++n ) + { + // find next match + M=last_finder( Begin, ::boost::begin(M) ); + + if ( !M ) + { + // Subsequence not found, return + return M; + } + } + + return M; + } + + + private: + iterator_range<search_iterator_type> m_Search; + int m_Nth; + PredicateT m_Comp; + }; + +// find head/tail implementation helpers ---------------------------// + + template<typename ForwardIteratorT> + iterator_range<ForwardIteratorT> + find_head_impl( + ForwardIteratorT Begin, + ForwardIteratorT End, + unsigned int N, + std::forward_iterator_tag ) + { + typedef ForwardIteratorT input_iterator_type; + typedef iterator_range<ForwardIteratorT> result_type; + + input_iterator_type It=Begin; + for( + unsigned int Index=0; + Index<N && It!=End; ++Index,++It ) {}; + + return result_type( Begin, It ); + } + + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + find_head_impl( + ForwardIteratorT Begin, + ForwardIteratorT End, + unsigned int N, + std::random_access_iterator_tag ) + { + typedef iterator_range<ForwardIteratorT> result_type; + + if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) ) + return result_type( Begin, End ); + + return result_type(Begin,Begin+N); + } + + // Find head implementation + template<typename ForwardIteratorT> + iterator_range<ForwardIteratorT> + find_head_impl( + ForwardIteratorT Begin, + ForwardIteratorT End, + unsigned int N ) + { + typedef BOOST_STRING_TYPENAME boost::detail:: + iterator_traits<ForwardIteratorT>::iterator_category category; + + return ::boost::algorithm::detail::find_head_impl( Begin, End, N, category() ); + } + + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + find_tail_impl( + ForwardIteratorT Begin, + ForwardIteratorT End, + unsigned int N, + std::forward_iterator_tag ) + { + typedef ForwardIteratorT input_iterator_type; + typedef iterator_range<ForwardIteratorT> result_type; + + unsigned int Index=0; + input_iterator_type It=Begin; + input_iterator_type It2=Begin; + + // Advance It2 by N increments + for( Index=0; Index<N && It2!=End; ++Index,++It2 ) {}; + + // Advance It, It2 to the end + for(; It2!=End; ++It,++It2 ) {}; + + return result_type( It, It2 ); + } + + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + find_tail_impl( + ForwardIteratorT Begin, + ForwardIteratorT End, + unsigned int N, + std::bidirectional_iterator_tag ) + { + typedef ForwardIteratorT input_iterator_type; + typedef iterator_range<ForwardIteratorT> result_type; + + input_iterator_type It=End; + for( + unsigned int Index=0; + Index<N && It!=Begin; ++Index,--It ) {}; + + return result_type( It, End ); + } + + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + find_tail_impl( + ForwardIteratorT Begin, + ForwardIteratorT End, + unsigned int N, + std::random_access_iterator_tag ) + { + typedef iterator_range<ForwardIteratorT> result_type; + + if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) ) + return result_type( Begin, End ); + + return result_type( End-N, End ); + } + + // Operation + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + find_tail_impl( + ForwardIteratorT Begin, + ForwardIteratorT End, + unsigned int N ) + { + typedef BOOST_STRING_TYPENAME boost::detail:: + iterator_traits<ForwardIteratorT>::iterator_category category; + + return ::boost::algorithm::detail::find_tail_impl( Begin, End, N, category() ); + } + + + +// find head functor -----------------------------------------------// + + + // find a head in the sequence ( functor ) + /* + This functor find a head of the specified range. For + a specified N, the head is a subsequence of N starting + elements of the range. + */ + struct head_finderF + { + // Construction + head_finderF( int N ) : m_N(N) {} + + // Operation + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + operator()( + ForwardIteratorT Begin, + ForwardIteratorT End ) const + { + if(m_N>=0) + { + return ::boost::algorithm::detail::find_head_impl( Begin, End, m_N ); + } + else + { + iterator_range<ForwardIteratorT> Res= + ::boost::algorithm::detail::find_tail_impl( Begin, End, -m_N ); + + return ::boost::make_iterator_range(Begin, Res.begin()); + } + } + + private: + int m_N; + }; + +// find tail functor -----------------------------------------------// + + + // find a tail in the sequence ( functor ) + /* + This functor find a tail of the specified range. For + a specified N, the head is a subsequence of N starting + elements of the range. + */ + struct tail_finderF + { + // Construction + tail_finderF( int N ) : m_N(N) {} + + // Operation + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + operator()( + ForwardIteratorT Begin, + ForwardIteratorT End ) const + { + if(m_N>=0) + { + return ::boost::algorithm::detail::find_tail_impl( Begin, End, m_N ); + } + else + { + iterator_range<ForwardIteratorT> Res= + ::boost::algorithm::detail::find_head_impl( Begin, End, -m_N ); + + return ::boost::make_iterator_range(Res.end(), End); + } + } + + private: + int m_N; + }; + +// find token functor -----------------------------------------------// + + // find a token in a sequence ( functor ) + /* + This find functor finds a token specified be a predicate + in a sequence. It is equivalent of std::find algorithm, + with an exception that it return range instead of a single + iterator. + + If bCompress is set to true, adjacent matching tokens are + concatenated into one match. + */ + template< typename PredicateT > + struct token_finderF + { + // Construction + token_finderF( + PredicateT Pred, + token_compress_mode_type eCompress=token_compress_off ) : + m_Pred(Pred), m_eCompress(eCompress) {} + + // Operation + template< typename ForwardIteratorT > + iterator_range<ForwardIteratorT> + operator()( + ForwardIteratorT Begin, + ForwardIteratorT End ) const + { + typedef iterator_range<ForwardIteratorT> result_type; + + ForwardIteratorT It=std::find_if( Begin, End, m_Pred ); + + if( It==End ) + { + return result_type( End, End ); + } + else + { + ForwardIteratorT It2=It; + + if( m_eCompress==token_compress_on ) + { + // Find first non-matching character + while( It2!=End && m_Pred(*It2) ) ++It2; + } + else + { + // Advance by one position + ++It2; + } + + return result_type( It, It2 ); + } + } + + private: + PredicateT m_Pred; + token_compress_mode_type m_eCompress; + }; + +// find range functor -----------------------------------------------// + + // find a range in the sequence ( functor ) + /* + This functor actually does not perform any find operation. + It always returns given iterator range as a result. + */ + template<typename ForwardIterator1T> + struct range_finderF + { + typedef ForwardIterator1T input_iterator_type; + typedef iterator_range<input_iterator_type> result_type; + + // Construction + range_finderF( + input_iterator_type Begin, + input_iterator_type End ) : m_Range(Begin, End) {} + + range_finderF(const iterator_range<input_iterator_type>& Range) : + m_Range(Range) {} + + // Operation + template< typename ForwardIterator2T > + iterator_range<ForwardIterator2T> + operator()( + ForwardIterator2T, + ForwardIterator2T ) const + { +#if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 ) + return iterator_range<const ForwardIterator2T>(this->m_Range); +#else + return m_Range; +#endif + } + + private: + iterator_range<input_iterator_type> m_Range; + }; + + + } // namespace detail + } // namespace algorithm +} // namespace boost + +#endif // BOOST_STRING_FINDER_DETAIL_HPP |