ceph/src/boost/libs/sort/test/integer_sort_test.cpp

   1 //  Boost Sort library int_test.cpp file  ------------------------------------//
   2
   3 //  Copyright Steven Ross 2009-2014. 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 //  See http://www.boost.org/libs/sort for library home page.
   9
  10 #include <boost/cstdint.hpp>
  11 #include <boost/sort/spreadsort/spreadsort.hpp>
  12 // Include unit test framework
  13 #include <boost/test/included/test_exec_monitor.hpp>
  14 #include <boost/test/test_tools.hpp>
  15 #include <vector>
  16
  17 #include <iostream>
  18
  19
  20 using namespace std;
  21 using namespace boost::sort::spreadsort;
  22
  23 struct rightshift {
  24   int operator()(int x, unsigned offset) { return x >> offset; }
  25 };
  26
  27 struct rightshift_max {
  28   boost::intmax_t operator()(const boost::intmax_t &x, unsigned offset) {
  29     return x >> offset;
  30   }
  31 };
  32
  33 struct negrightshift {
  34   int operator()(const int &x, const unsigned offset) { return -(x >> offset); }
  35 };
  36
  37 struct negrightshift_max {
  38   boost::intmax_t operator()(const boost::intmax_t &x, const unsigned offset) {
  39     return -(x >> offset);
  40   }
  41 };
  42
  43 boost::int32_t
  44 rand_32(bool sign = true) {
  45    boost::int32_t result = rand() | (rand()<< 16);
  46    if (rand() % 2)
  47      result |= 1 << 15;
  48    //Adding the sign bit
  49    if (sign && (rand() % 2))
  50      result *= -1;
  51    return result;
  52 }
  53
  54 void int_test()
  55 {
  56   // Prepare inputs
  57   vector<int> base_vec;
  58   unsigned count = 100000;
  59   srand(1);
  60   //Generating semirandom numbers
  61   for (unsigned u = 0; u < count; ++u)
  62     base_vec.push_back(rand_32());
  63   vector<int> sorted_vec = base_vec;
  64   vector<int> test_vec = base_vec;
  65   std::sort(sorted_vec.begin(), sorted_vec.end());
  66   //Testing basic call
  67   integer_sort(test_vec.begin(), test_vec.end());
  68   BOOST_CHECK(test_vec == sorted_vec);
  69   //boost::sort::spreadsort variant
  70   test_vec = base_vec;
  71   boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
  72   BOOST_CHECK(test_vec == sorted_vec);
  73   //One functor
  74   test_vec = base_vec;
  75   integer_sort(test_vec.begin(), test_vec.end(), rightshift());
  76   BOOST_CHECK(test_vec == sorted_vec);
  77   //Both functors
  78   test_vec = base_vec;
  79   integer_sort(test_vec.begin(), test_vec.end(), rightshift(), less<int>());
  80   BOOST_CHECK(test_vec == sorted_vec);
  81   //reverse order
  82   std::sort(sorted_vec.begin(), sorted_vec.end(), greater<int>());
  83   integer_sort(test_vec.begin(), test_vec.end(), negrightshift(),
  84                greater<int>());
  85   BOOST_CHECK(test_vec == sorted_vec);
  86
  87   //Making sure we're correctly sorting boost::intmax_ts; should use std::sort
  88   vector<boost::intmax_t> long_base_vec;
  89   for (unsigned u = 0; u < base_vec.size(); ++u)
  90     long_base_vec.push_back((((boost::intmax_t)rand_32()) <<
  91                              ((8 * sizeof(int)) -1)) + rand_32(false));
  92   vector<boost::intmax_t> long_sorted_vec = long_base_vec;
  93   vector<boost::intmax_t> long_test_vec = long_base_vec;
  94   integer_sort(long_test_vec.begin(), long_test_vec.end());
  95   std::sort(long_sorted_vec.begin(), long_sorted_vec.end());
  96   BOOST_CHECK(long_test_vec == long_sorted_vec);
  97   //One functor
  98   long_test_vec = long_base_vec;
  99   integer_sort(long_test_vec.begin(), long_test_vec.end(), rightshift_max());
 100   BOOST_CHECK(long_test_vec == long_sorted_vec);
 101   //Both functors
 102   long_test_vec = long_base_vec;
 103   integer_sort(long_test_vec.begin(), long_test_vec.end(), rightshift_max(),
 104                less<boost::intmax_t>());
 105   BOOST_CHECK(long_test_vec == long_sorted_vec);
 106   //reverse order
 107   std::sort(long_sorted_vec.begin(), long_sorted_vec.end(),
 108             greater<boost::intmax_t>());
 109   integer_sort(long_test_vec.begin(), long_test_vec.end(), negrightshift_max(),
 110                greater<boost::intmax_t>());
 111   BOOST_CHECK(long_test_vec == long_sorted_vec);
 112 }
 113
 114 // Verify that 0 and 1 elements work correctly.
 115 void corner_test() {
 116   vector<int> test_vec;
 117   boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
 118   const int test_value = 42;
 119   test_vec.push_back(test_value);
 120   boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
 121   BOOST_CHECK(test_vec.size() == 1);
 122   BOOST_CHECK(test_vec[0] == test_value);
 123 }
 124
 125 // test main
 126 int test_main( int, char*[] )
 127 {
 128   int_test();
 129   corner_test();
 130   return 0;
 131 }