update sources to v12.2.4

[ceph.git] / ceph / src / boost / libs / sort / test / string_sort_test.cpp

//  Boost Sort library string_sort_test.cpp file  ----------------------------//\r
\r
//  Copyright Steven Ross 2009. Use, modification and\r
//  distribution is subject to the Boost Software License, Version\r
//  1.0. (See accompanying file LICENSE_1_0.txt or copy at\r
//  http://www.boost.org/LICENSE_1_0.txt)\r
\r
//  See http://www.boost.org/libs/sort for library home page.\r
\r
#include <boost/sort/spreadsort/detail/string_sort.hpp>\r
#include <boost/sort/spreadsort/string_sort.hpp>\r
#include <boost/sort/spreadsort/spreadsort.hpp>\r
// Include unit test framework\r
#include <boost/test/included/test_exec_monitor.hpp>\r
#include <boost/test/test_tools.hpp>\r
#include <vector>\r
#include <string>\r
\r
\r
using namespace std;\r
using namespace boost::sort::spreadsort;\r
using boost::sort::spreadsort::detail::offset_less_than;\r
using boost::sort::spreadsort::detail::offset_greater_than;\r
using boost::sort::spreadsort::detail::update_offset;\r
\r
struct bracket {\r
  unsigned char operator()(const string &x, size_t offset) const {\r
    return x[offset];\r
  }\r
};\r
\r
struct wbracket {\r
  wchar_t operator()(const wstring &x, size_t offset) const {\r
    return x[offset];\r
  }\r
};\r
\r
struct get_size {\r
  size_t operator()(const string &x) const{ return x.size(); }\r
};\r
\r
struct wget_size {\r
  size_t operator()(const wstring &x) const{ return x.size(); }\r
};\r
\r
static const unsigned input_count = 100000;\r
\r
// Test that update_offset finds the first character with a difference.\r
void update_offset_test() {\r
  vector<string> input;\r
  input.push_back("test1");\r
  input.push_back("test2");\r
  size_t char_offset = 1;\r
  update_offset<vector<string>::iterator, unsigned char>(input.begin(),\r
                                                         input.end(),\r
                                                         char_offset);\r
  BOOST_CHECK(char_offset == 4);\r
\r
  // Functor version\r
  char_offset = 1;\r
  update_offset(input.begin(), input.end(), char_offset, bracket(), get_size());\r
  BOOST_CHECK(char_offset == 4);\r
}\r
\r
// Test that offset comparison operators only look after the offset.\r
void offset_comparison_test() {\r
  string input1 = "ab";\r
  string input2 = "ba";\r
  string input3 = "aba";\r
  offset_less_than<string, unsigned char> less_than(0);\r
  offset_greater_than<string, unsigned char> greater_than(0);\r
  BOOST_CHECK(less_than(input1, input2));\r
  BOOST_CHECK(less_than(input1, input3));\r
  BOOST_CHECK(!less_than(input2, input1));\r
  BOOST_CHECK(!less_than(input1, input1));\r
  BOOST_CHECK(!greater_than(input1, input2));\r
  BOOST_CHECK(!greater_than(input1, input3));\r
  BOOST_CHECK(greater_than(input2, input1));\r
  BOOST_CHECK(!greater_than(input1, input1));\r
\r
  // Offset comparisons only check after the specified offset.\r
  offset_less_than<string, unsigned char> offset_less(1);\r
  offset_greater_than<string, unsigned char> offset_greater(1);\r
  BOOST_CHECK(!offset_less(input1, input2));\r
  BOOST_CHECK(offset_less(input1, input3));\r
  BOOST_CHECK(offset_less(input2, input1));\r
  BOOST_CHECK(!offset_less(input1, input1));\r
  BOOST_CHECK(offset_greater(input1, input2));\r
  BOOST_CHECK(!offset_greater(input1, input3));\r
  BOOST_CHECK(!offset_greater(input2, input1));\r
  BOOST_CHECK(!offset_greater(input1, input1));\r
}\r
\r
void string_test()\r
{\r
  // Prepare inputs\r
  vector<string> base_vec;\r
  const unsigned max_length = 32;\r
  srand(1);\r
  //Generating semirandom numbers\r
  for (unsigned u = 0; u < input_count; ++u) {\r
    unsigned length = rand() % max_length;\r
    string result;\r
    for (unsigned v = 0; v < length; ++v) {\r
      result.push_back(rand() % 256);\r
    }\r
    base_vec.push_back(result);\r
  }\r
  vector<string> sorted_vec = base_vec;\r
  vector<string> test_vec = base_vec;\r
  std::sort(sorted_vec.begin(), sorted_vec.end());\r
  //Testing basic call\r
  string_sort(test_vec.begin(), test_vec.end());\r
  BOOST_CHECK(test_vec == sorted_vec);\r
  //Testing boost::sort::spreadsort wrapper\r
  test_vec = base_vec;\r
  boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());\r
  BOOST_CHECK(test_vec == sorted_vec);\r
  //Character functors\r
  test_vec = base_vec;\r
  string_sort(test_vec.begin(), test_vec.end(), bracket(), get_size());\r
  BOOST_CHECK(test_vec == sorted_vec);\r
  //All functors\r
  test_vec = base_vec;\r
  string_sort(test_vec.begin(), test_vec.end(), bracket(), get_size(),\r
              less<string>());\r
  BOOST_CHECK(test_vec == sorted_vec);\r
  //reverse order\r
  std::sort(sorted_vec.begin(), sorted_vec.end(), greater<string>());\r
  reverse_string_sort(test_vec.begin(), test_vec.end(), greater<string>());\r
  BOOST_CHECK(test_vec == sorted_vec);\r
  //reverse order with functors\r
  test_vec = base_vec;\r
  reverse_string_sort(test_vec.begin(), test_vec.end(), bracket(), get_size(),\r
                      greater<string>());\r
  BOOST_CHECK(test_vec == sorted_vec);  \r
}\r
\r
// Verify that 0, 1, and input_count empty strings all sort correctly.\r
void corner_test() {\r
  vector<string> test_vec;\r
  boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());\r
  test_vec.resize(1);\r
  boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());\r
  BOOST_CHECK(test_vec[0].empty());\r
  test_vec.resize(input_count);\r
  boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());\r
  BOOST_CHECK(test_vec.size() == input_count);\r
  for (unsigned i = 0; i < test_vec.size(); ++i) {\r
    BOOST_CHECK(test_vec[i].empty());\r
  }\r
}\r
\r
// test main \r
int test_main( int, char*[] )\r
{\r
  update_offset_test();\r
  offset_comparison_test();\r
  string_test();\r
  corner_test();\r
  return 0;\r
}\r