sort/test/sort_detail_test.cpp

//  Boost Sort library tests for integer_sort and float_sort details.

//  Copyright Steven Ross 2014. Use, modification and
//  distribution is subject to the Boost Software License, Version
//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)

//  See http://www.boost.org/libs/sort for library home page.

#include <boost/cstdint.hpp>
#include <boost/sort/spreadsort/detail/spreadsort_common.hpp>
#include <boost/sort/spreadsort/detail/integer_sort.hpp>
#include <boost/sort/spreadsort/detail/float_sort.hpp>
#include <boost/sort/spreadsort/detail/string_sort.hpp>
#include <boost/sort/spreadsort/float_sort.hpp>
// Include unit test framework
#include <boost/test/included/test_exec_monitor.hpp>
#include <boost/test/test_tools.hpp>
#include <vector>

#include <iostream>


using namespace std;
using namespace boost::sort::spreadsort;
using namespace boost::sort::spreadsort::detail;

namespace {

struct int_right_shift {
  int operator()(const int x, const unsigned offset) const { 
    return x >> offset; 
  }
};

struct float_right_shift {
  int operator()(const float x, const unsigned offset) const { 
    return float_mem_cast<float, int>(x) >> offset; 
  }
};

const int max_int_bits = sizeof(boost::uintmax_t) * 8;
const int max_size_bits = sizeof(size_t) * 8;
const boost::uintmax_t one = 1;

// spreadsort won't recurse for inputs smaller than min_count.
const int int_min_log_count = 
  (std::min)((int)int_log_finishing_count, 
             (int)int_log_mean_bin_size + int_log_min_split_count);
const int float_min_log_count = 
  (std::min)((int)float_log_finishing_count,
             (int)float_log_mean_bin_size + float_log_min_split_count);
const unsigned absolute_min_count = (std::min)(1 << int_min_log_count, 
                                               1 << float_min_log_count);

// Verify that roughlog2 is floor(log base 2) + 1.
void roughlog2_test()
{
  for (boost::uintmax_t i = 0; i < max_int_bits; ++i) {
    BOOST_CHECK(detail::rough_log_2_size(one << i) == i + 1);
    BOOST_CHECK(detail::rough_log_2_size((one << i) - 1) == i);
  }
}

// Test the worst-case performance handling, and assure that is using the
// correct formula for the worst-case number of radix iterations.
template<unsigned log_mean_bin_size, unsigned log_min_split_count,
         unsigned log_finishing_count>
void get_min_count_test()
{
  const unsigned min_log_size = log_mean_bin_size + log_min_split_count;
  size_t prev_min_count = absolute_min_count;
  for (int log_range = 0; log_range <= max_int_bits; ++log_range) {
    size_t min_count = get_min_count<log_mean_bin_size, log_min_split_count, 
                                     log_finishing_count>(log_range);
    BOOST_CHECK(min_count >= prev_min_count);
    prev_min_count = min_count;
    // When the range is really small, the radix sort will complete in one
    // iteration and worst-case handling doesn't apply.  The code below 
    // guarantees the worst-case number of radix sorting iteration.
    if (log_range > min_log_size) {
      BOOST_CHECK(min_count >= (1 << min_log_size));
      int iterations = rough_log_2_size(min_count) - min_log_size;
      BOOST_CHECK(iterations >= 1);
      int base_iterations = max_splits - log_min_split_count;
      int covered_log_range = 0;
      if (iterations > base_iterations) {
        covered_log_range += max_splits * (iterations - base_iterations);
      } else {
        base_iterations = iterations;
      }
      // sum of n to n + x = ((x + 1) * (n + (n + x)))/2 + log_mean_bin_size
      covered_log_range +=
        (base_iterations * (log_min_split_count * 2 + base_iterations - 1))/2 +
        log_mean_bin_size;
      BOOST_CHECK(covered_log_range >= log_range);
      BOOST_CHECK(covered_log_range - max_splits < log_range);
    }
  }
}

// Test the decision of how many pieces to split up the radix sort into
// (roughly 2^(log_range - log_divisor)) to make sure the results are logical.
void get_log_divisor_test()
{
  for (int log_range = 0; log_range <= max_int_bits; ++log_range) {
    int prev_log_divisor = max_int_bits +
      (std::max)((int)int_log_mean_bin_size, (int)float_log_mean_bin_size);
    for (int log_count = 0; log_count < max_size_bits; ++log_count) {
      size_t count = (one << log_count) - 1;
      BOOST_CHECK(rough_log_2_size(count) == (unsigned)log_count);
      int log_divisor =
        get_log_divisor<int_log_mean_bin_size>(count, log_range);
      // Only process counts >= int_log_finishing_count in this function.
      if (count >= absolute_min_count)
        BOOST_CHECK(log_divisor <= log_range);
      // More pieces should be used the larger count is.
      BOOST_CHECK(log_divisor <= prev_log_divisor);
      prev_log_divisor = log_divisor;
      BOOST_CHECK(log_divisor >= 0);
      if (log_range > log_count) {
        BOOST_CHECK(log_range - log_divisor <= max_splits);
      } else if (log_range <= max_finishing_splits) {
        BOOST_CHECK(log_divisor == 0);
      }
    }
  }
}

// Verify that is_sorted_or_find_extremes returns true if the data is sorted,
// and otherwise returns the actual min and max.
void is_sorted_or_find_extremes_test()
{
  vector<int> input;
  input.push_back(3);
  input.push_back(5);
  input.push_back(1);
  // Test a sorted input.
  vector<int> sorted_input(input);
  std::sort(sorted_input.begin(), sorted_input.end());
  vector<int>::iterator max, min;
  BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_input.begin(), 
                                                 sorted_input.end(), max, min));
  // Test an unsorted input.
  BOOST_CHECK(!detail::is_sorted_or_find_extremes(input.begin(), input.end(), 
                                                  max, min));
  BOOST_CHECK(*min == 1);
  BOOST_CHECK(*max == 5);
  // Test the comparison function version.
  BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_input.begin(), 
                                                 sorted_input.end(), max, min, 
                                                 std::less<int>()));
  BOOST_CHECK(!detail::is_sorted_or_find_extremes(sorted_input.begin(), 
                                                  sorted_input.end(), 
                                                  max, min, 
                                                  std::greater<int>()));
  BOOST_CHECK(*min == 5);
  BOOST_CHECK(*max == 1);

  // Test with floats
  vector<float> float_input;
  float_input.push_back(.3f);
  float_input.push_back(4.0f);
  float_input.push_back(.1f);
  vector<float> sorted_float_input(float_input);
  std::sort(sorted_float_input.begin(), sorted_float_input.end());
  // Test cast_float_iter
  int cast_min = detail::cast_float_iter<int, vector<float>::iterator>(
                     sorted_float_input.begin());
  int cast_max = detail::cast_float_iter<int, vector<float>::iterator>(
                     sorted_float_input.end() - 1);
  BOOST_CHECK(cast_min == float_right_shift()(.1f, 0));
  BOOST_CHECK(cast_max == float_right_shift()(4.0f, 0));
  // Test a sorted input
  int div_max, div_min;
  BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_float_input.begin(), 
                                                 sorted_float_input.end(), 
                                                 div_max, div_min));
  // Test an unsorted input.
  BOOST_CHECK(!detail::is_sorted_or_find_extremes(float_input.begin(), 
                                                  float_input.end(), 
                                                  div_max, div_min));
  BOOST_CHECK(div_min == cast_min);
  BOOST_CHECK(div_max == cast_max);

  // Test with a right_shift functor.
  BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_float_input.begin(), 
                                                 sorted_float_input.end(), 
                                                 div_max, div_min, 
                                                 float_right_shift()));
  // Test an unsorted input.
  BOOST_CHECK(!detail::is_sorted_or_find_extremes(float_input.begin(), 
                                                  float_input.end(), div_max, 
                                                  div_min, 
                                                  float_right_shift()));
  BOOST_CHECK(div_min == float_right_shift()(.1f, 0));
  BOOST_CHECK(div_max == float_right_shift()(4.0f, 0));
}

// Make sure bins are created correctly.
void size_bins_test() {
  size_t bin_sizes[1 << detail::max_finishing_splits];
  bin_sizes[0] = 1;
  bin_sizes[2] = 7;
  const int old_bin_value = 7;
  std::vector<int> old_bins;
  old_bins.push_back(old_bin_value);
  std::vector<vector<int>::iterator> bin_cache;
  bin_cache.push_back(old_bins.begin());
  unsigned cache_offset = 1;
  unsigned cache_end;
  const unsigned bin_count = 2;
  std::vector<int>::iterator *new_cache_start = 
    size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
  BOOST_CHECK((new_cache_start - &bin_cache[0]) == cache_offset);
  BOOST_CHECK(bin_sizes[0] == 0);
  BOOST_CHECK(bin_sizes[1] == 0);
  BOOST_CHECK(bin_sizes[2] == 7);  // shouldn't modify past bin_count
  BOOST_CHECK(cache_end == 3);
  BOOST_CHECK(bin_cache.size() == cache_end);
  BOOST_CHECK(old_bins[0] == old_bin_value);
}

// Test the specialized 3-way swap loops.
void swap_loop_test() {
  size_t bin_sizes[1 << detail::max_finishing_splits];
  bin_sizes[0] = bin_sizes[1] = 2;
  bin_sizes[2] = 1;

  // test integer swap loop
  vector<int> ints;
  const int int_div_min = 3;
  const int int_log_divisor = 1;
  const unsigned int_offset = int_div_min << int_log_divisor;
  ints.push_back(2 + int_offset);
  ints.push_back(1 + int_offset); // stays in place
  ints.push_back(4 + int_offset);
  ints.push_back(3 + int_offset);
  ints.push_back(0 + int_offset);
  vector<vector<int>::iterator> int_bin_vector;
  int_bin_vector.push_back(ints.begin());
  int_bin_vector.push_back(int_bin_vector[0] + bin_sizes[0]);
  int_bin_vector.push_back(int_bin_vector[1] + bin_sizes[1]);
  vector<int>::iterator next_int_bin_start = int_bin_vector[0];
  vector<int>::iterator *int_bins = &int_bin_vector[0];
  int_right_shift integer_right_shift;
  swap_loop(int_bins, next_int_bin_start, 0, integer_right_shift, bin_sizes, 
            int_log_divisor, int_div_min);
  for (unsigned i = 0; i < ints.size(); ++i) {
    BOOST_CHECK(ints[i] == int(int_offset + i));
  }
  BOOST_CHECK(next_int_bin_start == ints.begin() + bin_sizes[0]);

  // test float swap loop
  vector<float> floats;
  const int float_four_as_int = float_mem_cast<float, int>(4.0f);
  const int float_log_divisor = 
    rough_log_2_size(float_mem_cast<float, int>(5.0f) - float_four_as_int);
  const int float_div_min = float_four_as_int >> float_log_divisor;
  floats.push_back(6.0f);
  floats.push_back(5.0f); // stays in place
  floats.push_back(8.0f);
  floats.push_back(7.0f);
  floats.push_back(4.0f);
  vector<vector<float>::iterator> float_bin_vector;
  float_bin_vector.push_back(floats.begin());
  float_bin_vector.push_back(float_bin_vector[0] + bin_sizes[0]);
  float_bin_vector.push_back(float_bin_vector[1] + bin_sizes[1]);
  vector<float>::iterator next_float_bin_start = float_bin_vector[0];
  vector<float>::iterator *float_bins = &float_bin_vector[0];
  float_swap_loop(float_bins, next_float_bin_start, 0, bin_sizes,
                  float_log_divisor, float_div_min);
  for (unsigned i = 0; i < floats.size(); ++i) {
    BOOST_CHECK(floats[i] == 4.0f + i);
  }
  BOOST_CHECK(next_float_bin_start == floats.begin() + bin_sizes[0]);
}

} // end anonymous namespace

// test main 
int test_main( int, char*[] )
{
  roughlog2_test();
  get_min_count_test<int_log_mean_bin_size, int_log_min_split_count,
                    int_log_finishing_count>();
  get_min_count_test<float_log_mean_bin_size, float_log_min_split_count,
                    float_log_finishing_count>();
  get_log_divisor_test();
  is_sorted_or_find_extremes_test();
  size_bins_test();
  swap_loop_test();
  return 0;
}