libs/range/test/algorithm_test/search_n.cpp

   1 // Boost.Range library
   2 //
   3 //  Copyright Neil Groves 2009. Use, modification and
   4 //  distribution is subject to the Boost Software License, Version
   5 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6 //  http://www.boost.org/LICENSE_1_0.txt)
   7 //
   8 //
   9 // For more information, see http://www.boost.org/libs/range/
  10 //
  11 #include <boost/range/algorithm/search_n.hpp>
  12
  13 #include <boost/test/test_tools.hpp>
  14 #include <boost/test/unit_test.hpp>
  15
  16 #include <boost/assign.hpp>
  17 #include <algorithm>
  18 #include <list>
  19 #include <set>
  20 #include <vector>
  21
  22 namespace
  23 {
  24     template<typename ForwardIterator, typename Integer, typename Value>
  25     inline ForwardIterator
  26     reference_search_n(ForwardIterator first, ForwardIterator last,
  27                        Integer count, const Value& value)
  28     {
  29         if (count <= 0)
  30             return first;
  31         else if (count == 1)
  32             return std::find(first, last, value);
  33         else
  34         {
  35             first = std::find(first, last, value);
  36             while (first != last)
  37             {
  38                 typename std::iterator_traits<ForwardIterator>::difference_type n = count;
  39                 ForwardIterator i = first;
  40                 ++i;
  41                 while (i != last && n != 1 && *i==value)
  42                 {
  43                     ++i;
  44                     --n;
  45                 }
  46                 if (n == 1)
  47                     return first;
  48                 if (i == last)
  49                     return last;
  50                 first = std::find(++i, last, value);
  51             }
  52         }
  53         return last;
  54     }
  55
  56     template<typename ForwardIterator, typename Integer, typename Value,
  57              typename BinaryPredicate>
  58     inline ForwardIterator
  59     reference_search_n(ForwardIterator first, ForwardIterator last,
  60                        Integer count, const Value& value,
  61                        BinaryPredicate pred)
  62     {
  63         typedef typename std::iterator_traits<
  64             ForwardIterator
  65         >::iterator_category cat_t BOOST_RANGE_UNUSED;
  66
  67         if (count <= 0)
  68             return first;
  69         if (count == 1)
  70         {
  71             while (first != last && !static_cast<bool>(pred(*first, value)))
  72                 ++first;
  73             return first;
  74         }
  75         else
  76         {
  77             typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_t;
  78
  79             while (first != last && !static_cast<bool>(pred(*first, value)))
  80                 ++first;
  81
  82             while (first != last)
  83             {
  84                 difference_t n = count;
  85                 ForwardIterator i = first;
  86                 ++i;
  87                 while (i != last && n != 1 && static_cast<bool>(pred(*i, value)))
  88                 {
  89                     ++i;
  90                     --n;
  91                 }
  92                 if (n == 1)
  93                     return first;
  94                 if (i == last)
  95                     return last;
  96                 first = ++i;
  97                 while (first != last && !static_cast<bool>(pred(*first, value)))
  98                     ++first;
  99             }
 100         }
 101         return last;
 102     }
 103
 104     template< class Container1, class Value, class Pred >
 105     void test_search_n_pred_impl(Container1& cont1, Value value, Pred pred)
 106     {
 107         typedef BOOST_DEDUCED_TYPENAME Container1::const_iterator const_iterator1_t;
 108         typedef BOOST_DEDUCED_TYPENAME Container1::iterator iterator1_t;
 109
 110         const Container1& ccont1 = cont1;
 111
 112         for (std::size_t n = 0; n < cont1.size(); ++n)
 113         {
 114             iterator1_t it = boost::search_n(cont1, n, value, pred);
 115             BOOST_CHECK( it == boost::search_n(boost::make_iterator_range(cont1), n, value, pred) );
 116             BOOST_CHECK( it == reference_search_n(cont1.begin(), cont1.end(), n, value, pred) );
 117
 118             const_iterator1_t cit = boost::search_n(ccont1, n, value, pred);
 119             BOOST_CHECK( cit == boost::search_n(boost::make_iterator_range(ccont1), n, value, pred) );
 120             BOOST_CHECK( cit == reference_search_n(ccont1.begin(), ccont1.end(), n, value, pred) );
 121         }
 122     }
 123
 124     template< class Container1, class Value >
 125     void test_search_n_impl(Container1& cont1, Value value)
 126     {
 127         typedef BOOST_DEDUCED_TYPENAME Container1::const_iterator const_iterator1_t;
 128         typedef BOOST_DEDUCED_TYPENAME Container1::iterator iterator1_t;
 129
 130         const Container1& ccont1 = cont1;
 131
 132         for (std::size_t n = 0; n < cont1.size(); ++n)
 133         {
 134             iterator1_t it = boost::search_n(cont1, n, value);
 135             BOOST_CHECK( it == boost::search_n(boost::make_iterator_range(cont1), n, value) );
 136             BOOST_CHECK( it == reference_search_n(cont1.begin(), cont1.end(), n, value) );
 137
 138             const_iterator1_t cit = boost::search_n(ccont1, n, value);
 139             BOOST_CHECK( cit == boost::search_n(boost::make_iterator_range(ccont1), n, value) );
 140             BOOST_CHECK( cit == reference_search_n(ccont1.begin(), ccont1.end(), n, value) );
 141         }
 142
 143         test_search_n_pred_impl(cont1, value, std::less<int>());
 144         test_search_n_pred_impl(cont1, value, std::greater<int>());
 145         test_search_n_pred_impl(cont1, value, std::equal_to<int>());
 146         test_search_n_pred_impl(cont1, value, std::not_equal_to<int>());
 147     }
 148
 149     template< class Container1, class Container2 >
 150     void test_search_n_impl()
 151     {
 152         using namespace boost::assign;
 153
 154         Container1 cont1;
 155
 156         test_search_n_impl(cont1, 1);
 157
 158         cont1 += 1;
 159         test_search_n_impl(cont1, 1);
 160         test_search_n_impl(cont1, 0);
 161
 162         cont1.clear();
 163         cont1 += 1,1;
 164         test_search_n_impl(cont1, 1);
 165         test_search_n_impl(cont1, 0);
 166
 167         cont1 += 1,1,1;
 168         test_search_n_impl(cont1, 1);
 169         test_search_n_impl(cont1, 0);
 170
 171         cont1.clear();
 172         cont1 += 1,2,3,4,5,6,7,8,9;
 173         test_search_n_impl(cont1, 1);
 174         test_search_n_impl(cont1, 2);
 175         test_search_n_impl(cont1, 5);
 176         test_search_n_impl(cont1, 9);
 177     }
 178
 179     void test_search_n()
 180     {
 181         test_search_n_impl< std::list<int>, std::list<int> >();
 182         test_search_n_impl< std::vector<int>, std::vector<int> >();
 183         test_search_n_impl< std::set<int>, std::set<int> >();
 184         test_search_n_impl< std::list<int>, std::vector<int> >();
 185         test_search_n_impl< std::vector<int>, std::list<int> >();
 186     }
 187 }
 188
 189 boost::unit_test::test_suite*
 190 init_unit_test_suite(int argc, char* argv[])
 191 {
 192     boost::unit_test::test_suite* test
 193         = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.search_n" );
 194
 195     test->add( BOOST_TEST_CASE( &test_search_n ) );
 196
 197     return test;
 198 }