text: //  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;
  }
  