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