BVB Source Codes

mars Show finder.hpp Source code

Return Download mars: download finder.hpp Source code - Download mars Source code - Type:.hpp
  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 mars_boost {} namespace boost = mars_boost; namespace mars_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(::mars_boost::begin(Search), ::mars_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( mars_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(::mars_boost::begin(Search), ::mars_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( mars_boost::empty(m_Search) )
  128.                         return result_type( End, End );
  129.  
  130.                     typedef BOOST_STRING_TYPENAME mars_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( ::mars_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(::mars_boost::begin(Search), ::mars_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( mars_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( ::mars_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( mars_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, ::mars_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 mars_boost::detail::
  379.                     iterator_traits<ForwardIteratorT>::iterator_category category;
  380.  
  381.                 return ::mars_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 mars_boost::detail::
  452.                     iterator_traits<ForwardIteratorT>::iterator_category category;
  453.  
  454.                 return ::mars_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 ::mars_boost::algorithm::detail::find_head_impl( Begin, End, m_N );
  483.                     }
  484.                     else
  485.                     {
  486.                         iterator_range<ForwardIteratorT> Res=
  487.                             ::mars_boost::algorithm::detail::find_tail_impl( Begin, End, -m_N );
  488.  
  489.                         return ::mars_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 ::mars_boost::algorithm::detail::find_tail_impl( Begin, End, m_N );
  521.                     }
  522.                     else
  523.                     {
  524.                         iterator_range<ForwardIteratorT> Res=
  525.                             ::mars_boost::algorithm::detail::find_head_impl( Begin, End, -m_N );
  526.  
  527.                         return ::mars_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 mars_boost
  638.  
  639. #endif  // BOOST_STRING_FINDER_DETAIL_HPP
  640.  
downloadfinder.hpp Source code - Download mars Source code
Related Source Codes/Software:
Hero - Elegant transition library for iOS & tvOS 2017-06-09
deep-photo-styletransfer - Code and data for paper "Deep Photo Style Transfer... 2017-06-09
mastodon - A GNU Social-compatible microblogging server ... 2017-06-09
plyr - A simple HTML5, YouTube and Vimeo player ... 2017-06-08
prepack - Prepack is a partial evaluator for JavaScript. Pre... 2017-06-08
Public-APIs - 2017-06-09
lottie-ios - An iOS library to natively render After Effects ve... 2017-06-09
Awesome-Hacking - A collection of various awesome lists for hackers,... 2017-06-09
algorithms - Minimal examples of data structures and algorithms... 2017-06-10
lectures - Oxford Deep NLP 2017 course 2017-06-10
CRYENGINE - CRYENGINE is a powerful real-time game development... 2017-06-11
postal - 2017-06-11
reactide - Reactide is the first dedicated IDE for React web ... 2017-06-11
rkt - rkt is a pod-native container engine for Linux. It... 2017-06-11
uWebSockets - Tiny WebSockets https://for... 2017-06-11
realworld - TodoMVC for the RealWorld - Exemplary fullstack Me... 2017-06-11
goreplay - GoReplay is an open-source tool for capturing and ... 2017-06-10
pyenv - Simple Python version management 2017-06-10
redux-saga - An alternative side effect model for Redux apps ... 2017-06-10
angular-starter - 2017-06-10

 Back to top