ceph/src/boost/libs/algorithm/test/partition_subrange_test.cpp

   1 #include <boost/config.hpp>
   2 #include <boost/algorithm/sort_subrange.hpp>
   3 #include <boost/algorithm/cxx11/is_sorted.hpp>
   4
   5 #define BOOST_TEST_MAIN
   6 #include <boost/test/unit_test.hpp>
   7
   8 #include <vector>
   9 #include <iostream>
  10
  11 #if __cplusplus >= 201103L
  12 #include <random>
  13
  14 std::default_random_engine gen;
  15 template<typename RandomIt>
  16 void do_shuffle(RandomIt first, RandomIt last)
  17 { std::shuffle(first, last, gen); }
  18 #else
  19 template<typename RandomIt>
  20 void do_shuffle(RandomIt first, RandomIt last)
  21 { std::random_shuffle(first, last); }
  22 #endif
  23
  24 namespace ba = boost::algorithm;
  25
  26 template <typename Iter>
  27 void check_sequence ( Iter first, Iter last, Iter sf, Iter sl )
  28 {
  29 //      for (Iter i = first; i < last; ++i) {
  30 //              if (i != first) std::cout << ' ';
  31 //              if (i == sf) std::cout << ">";
  32 //              std::cout << *i;
  33 //              if (i == sl) std::cout << "<";
  34 //              }
  35 //      if (sl == last) std::cout << "<";
  36 //      std::cout << '\n';
  37
  38         if (sf == sl) return;
  39         for (Iter i = first; i < sf; ++i)
  40                 BOOST_CHECK(*i < *sf);
  41         for (Iter i = sf; i < sl; ++i) {
  42                 if (first != sf) // if there is an element before the subrange
  43                         BOOST_CHECK(*i > *(sf-1));
  44                 if (last != sl) // if there is an element after the subrange
  45                         BOOST_CHECK(*i < *sl);
  46                 }
  47         for (Iter i = sl; i < last; ++i)
  48                 BOOST_CHECK(*(sl-1) < *i);
  49 }
  50
  51 template <typename Iter, typename Pred>
  52 void check_sequence ( Iter first, Iter last, Iter sf, Iter sl, Pred p )
  53 {
  54         if (sf == sl) return;
  55         for (Iter i = first; i < sf; ++i)
  56                 BOOST_CHECK(p(*i, *sf));
  57         for (Iter i = sf; i < sl; ++i) {
  58                 if (first != sf) // if there is an element before the subrange
  59                         BOOST_CHECK(p(*(sf-1), *i));
  60                 if (last != sl) // if there is an element after the subrange
  61                         BOOST_CHECK(p(*i, *sl));
  62                 }
  63         for (Iter i = sl; i < last; ++i)
  64                 BOOST_CHECK(p(*(sl-1), *i));
  65
  66 }
  67
  68 //      for ( int i = 0; i < v.size(); ++i )
  69 //              std::cout << v[i] << ' ';
  70 //      std::cout << std::endl;
  71
  72
  73 BOOST_AUTO_TEST_CASE( test_main )
  74 {
  75         {
  76         std::vector<int> v;
  77         for ( int i = 0; i < 10; ++i )
  78                 v.push_back(i);
  79
  80         const std::vector<int>::iterator b = v.begin();
  81         ba::partition_subrange(b, v.end(), b + 3, b + 6);
  82         check_sequence        (b, v.end(), b + 3, b + 6);
  83
  84 //      BOOST_CHECK_EQUAL(v[3], 3);
  85 //      BOOST_CHECK_EQUAL(v[4], 4);
  86 //      BOOST_CHECK_EQUAL(v[5], 5);
  87
  88 //      Mix them up and try again - single element
  89         do_shuffle(v.begin(), v.end());
  90         ba::partition_subrange(b, v.end(), b + 7, b + 8);
  91         check_sequence        (b, v.end(), b + 7, b + 8);
  92
  93 //      BOOST_CHECK_EQUAL(v[7], 7);
  94
  95 //      Mix them up and try again - at the end
  96         do_shuffle(v.begin(), v.end());
  97         ba::partition_subrange(b, v.end(), b + 7, v.end());
  98         check_sequence        (b, v.end(), b + 7, v.end());
  99
 100 //      BOOST_CHECK_EQUAL(v[7], 7);
 101 //      BOOST_CHECK_EQUAL(v[8], 8);
 102 //      BOOST_CHECK_EQUAL(v[9], 9);
 103
 104 //      Mix them up and try again - at the beginning
 105         do_shuffle(v.begin(), v.end());
 106         ba::partition_subrange(b, v.end(), b, b + 2);
 107         check_sequence        (b, v.end(), b, b + 2);
 108
 109 //      BOOST_CHECK_EQUAL(v[0], 0);
 110 //      BOOST_CHECK_EQUAL(v[1], 1);
 111
 112 //      Mix them up and try again - empty subrange
 113         do_shuffle(v.begin(), v.end());
 114         ba::partition_subrange(b, v.end(), b, b);
 115         check_sequence        (b, v.end(), b, b);
 116
 117 //      Mix them up and try again - entire subrange
 118         do_shuffle(v.begin(), v.end());
 119         ba::partition_subrange(b, v.end(), b, v.end());
 120         check_sequence        (b, v.end(), b, v.end());
 121         }
 122
 123         {
 124         std::vector<int> v;
 125         for ( int i = 0; i < 10; ++i )
 126                 v.push_back(i);
 127
 128         const std::vector<int>::iterator b = v.begin();
 129         ba::partition_subrange(b, v.end(), b + 3, b + 6, std::greater<int>());
 130         check_sequence        (b, v.end(), b + 3, b + 6, std::greater<int>());
 131
 132 //      BOOST_CHECK_EQUAL(v[3], 6);
 133 //      BOOST_CHECK_EQUAL(v[4], 5);
 134 //      BOOST_CHECK_EQUAL(v[5], 4);
 135
 136 //      Mix them up and try again - single element
 137         do_shuffle(v.begin(), v.end());
 138         ba::partition_subrange(b, v.end(), b + 7, b + 8, std::greater<int>());
 139         check_sequence        (b, v.end(), b + 7, b + 8, std::greater<int>());
 140
 141 //      BOOST_CHECK_EQUAL(v[7], 2);
 142
 143 //      Mix them up and try again - at the end
 144         do_shuffle(v.begin(), v.end());
 145         ba::partition_subrange(b, v.end(), b + 7, v.end(), std::greater<int>());
 146         check_sequence        (b, v.end(), b + 7, v.end(), std::greater<int>());
 147
 148 //      BOOST_CHECK_EQUAL(v[7], 2);
 149 //      BOOST_CHECK_EQUAL(v[8], 1);
 150 //      BOOST_CHECK_EQUAL(v[9], 0);
 151
 152 //      Mix them up and try again - at the beginning
 153         do_shuffle(v.begin(), v.end());
 154         ba::partition_subrange(b, v.end(), b, b + 2, std::greater<int>());
 155         check_sequence        (b, v.end(), b, b + 2, std::greater<int>());
 156
 157 //      BOOST_CHECK_EQUAL(v[0], 9);
 158 //      BOOST_CHECK_EQUAL(v[1], 8);
 159
 160 //      Mix them up and try again - empty subrange
 161         do_shuffle(v.begin(), v.end());
 162         ba::partition_subrange(b, v.end(), b, b, std::greater<int>());
 163         check_sequence        (b, v.end(), b, b, std::greater<int>());
 164
 165 //      Mix them up and try again - entire subrange
 166         do_shuffle(v.begin(), v.end());
 167         ba::partition_subrange(b, v.end(), b, v.end(), std::greater<int>());
 168         check_sequence        (b, v.end(), b, v.end(), std::greater<int>());
 169         }
 170 }