1// Boost Sort library string_sort_test.cpp file ----------------------------//
2
3// Copyright Steven Ross 2009. 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/sort/spreadsort/detail/string_sort.hpp>
11#include <boost/sort/spreadsort/string_sort.hpp>
12#include <boost/sort/spreadsort/spreadsort.hpp>
13// Include unit test framework
14#include <boost/test/included/test_exec_monitor.hpp>
15#include <boost/test/test_tools.hpp>
16#include <vector>
17#include <string>
18
19
20using namespace std;
21using namespace boost::sort::spreadsort;
22using boost::sort::spreadsort::detail::offset_less_than;
23using boost::sort::spreadsort::detail::offset_greater_than;
24using boost::sort::spreadsort::detail::update_offset;
25
26struct bracket {
27 unsigned char operator()(const string &x, size_t offset) const {
28 return x[offset];
29 }
30};
31
32struct wbracket {
33 wchar_t operator()(const wstring &x, size_t offset) const {
34 return x[offset];
35 }
36};
37
38struct get_size {
39 size_t operator()(const string &x) const{ return x.size(); }
40};
41
42struct wget_size {
43 size_t operator()(const wstring &x) const{ return x.size(); }
44};
45
46static const unsigned input_count = 100000;
47
48// Test that update_offset finds the first character with a difference.
49void update_offset_test() {
50 vector<string> input;
51 input.push_back(x: "test1");
52 input.push_back(x: "test2");
53 size_t char_offset = 1;
54 update_offset<vector<string>::iterator, unsigned char>(first: input.begin(),
55 finish: input.end(),
56 char_offset);
57 BOOST_CHECK(char_offset == 4);
58
59 // Functor version
60 char_offset = 1;
61 update_offset(first: input.begin(), finish: input.end(), char_offset, get_character: bracket(), length: get_size());
62 BOOST_CHECK(char_offset == 4);
63}
64
65// Test that offset comparison operators only look after the offset.
66void offset_comparison_test() {
67 string input1 = "ab";
68 string input2 = "ba";
69 string input3 = "aba";
70 offset_less_than<string, unsigned char> less_than(0);
71 offset_greater_than<string, unsigned char> greater_than(0);
72 BOOST_CHECK(less_than(input1, input2));
73 BOOST_CHECK(less_than(input1, input3));
74 BOOST_CHECK(!less_than(input2, input1));
75 BOOST_CHECK(!less_than(input1, input1));
76 BOOST_CHECK(!greater_than(input1, input2));
77 BOOST_CHECK(!greater_than(input1, input3));
78 BOOST_CHECK(greater_than(input2, input1));
79 BOOST_CHECK(!greater_than(input1, input1));
80
81 // Offset comparisons only check after the specified offset.
82 offset_less_than<string, unsigned char> offset_less(1);
83 offset_greater_than<string, unsigned char> offset_greater(1);
84 BOOST_CHECK(!offset_less(input1, input2));
85 BOOST_CHECK(offset_less(input1, input3));
86 BOOST_CHECK(offset_less(input2, input1));
87 BOOST_CHECK(!offset_less(input1, input1));
88 BOOST_CHECK(offset_greater(input1, input2));
89 BOOST_CHECK(!offset_greater(input1, input3));
90 BOOST_CHECK(!offset_greater(input2, input1));
91 BOOST_CHECK(!offset_greater(input1, input1));
92}
93
94void string_test()
95{
96 // Prepare inputs
97 vector<string> base_vec;
98 const unsigned max_length = 32;
99 srand(seed: 1);
100 //Generating semirandom numbers
101 for (unsigned u = 0; u < input_count; ++u) {
102 unsigned length = rand() % max_length;
103 string result;
104 for (unsigned v = 0; v < length; ++v) {
105 result.push_back(c: rand() % 256);
106 }
107 base_vec.push_back(x: result);
108 }
109 vector<string> sorted_vec = base_vec;
110 vector<string> test_vec = base_vec;
111 std::sort(first: sorted_vec.begin(), last: sorted_vec.end());
112 //Testing basic call
113 string_sort(first: test_vec.begin(), last: test_vec.end());
114 BOOST_CHECK(test_vec == sorted_vec);
115 //Testing boost::sort::spreadsort wrapper
116 test_vec = base_vec;
117 boost::sort::spreadsort::spreadsort(first: test_vec.begin(), last: test_vec.end());
118 BOOST_CHECK(test_vec == sorted_vec);
119 //Character functors
120 test_vec = base_vec;
121 string_sort(first: test_vec.begin(), last: test_vec.end(), get_character: bracket(), length: get_size());
122 BOOST_CHECK(test_vec == sorted_vec);
123 //All functors
124 test_vec = base_vec;
125 string_sort(first: test_vec.begin(), last: test_vec.end(), get_character: bracket(), length: get_size(),
126 comp: less<string>());
127 BOOST_CHECK(test_vec == sorted_vec);
128 //reverse order
129 std::sort(first: sorted_vec.begin(), last: sorted_vec.end(), comp: greater<string>());
130 reverse_string_sort(first: test_vec.begin(), last: test_vec.end(), comp: greater<string>());
131 BOOST_CHECK(test_vec == sorted_vec);
132 //reverse order with functors
133 test_vec = base_vec;
134 reverse_string_sort(first: test_vec.begin(), last: test_vec.end(), get_character: bracket(), length: get_size(),
135 comp: greater<string>());
136 BOOST_CHECK(test_vec == sorted_vec);
137}
138
139// Verify that 0, 1, and input_count empty strings all sort correctly.
140void corner_test() {
141 vector<string> test_vec;
142 boost::sort::spreadsort::spreadsort(first: test_vec.begin(), last: test_vec.end());
143 test_vec.resize(new_size: 1);
144 boost::sort::spreadsort::spreadsort(first: test_vec.begin(), last: test_vec.end());
145 BOOST_CHECK(test_vec[0].empty());
146 test_vec.resize(new_size: input_count);
147 boost::sort::spreadsort::spreadsort(first: test_vec.begin(), last: test_vec.end());
148 BOOST_CHECK(test_vec.size() == input_count);
149 for (unsigned i = 0; i < test_vec.size(); ++i) {
150 BOOST_CHECK(test_vec[i].empty());
151 }
152}
153
154// test main
155int test_main( int, char*[] )
156{
157 update_offset_test();
158 offset_comparison_test();
159 string_test();
160 corner_test();
161 return 0;
162}
163

source code of boost/libs/sort/test/string_sort_test.cpp