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
20 using namespace std;
21 using namespace boost::sort::spreadsort;
22 using boost::sort::spreadsort::detail::offset_less_than;
23 using boost::sort::spreadsort::detail::offset_greater_than;
24 using boost::sort::spreadsort::detail::update_offset;
25
26 struct bracket {
operator ()bracket27 unsigned char operator()(const string &x, size_t offset) const {
28 return x[offset];
29 }
30 };
31
32 struct wbracket {
operator ()wbracket33 wchar_t operator()(const wstring &x, size_t offset) const {
34 return x[offset];
35 }
36 };
37
38 struct get_size {
operator ()get_size39 size_t operator()(const string &x) const{ return x.size(); }
40 };
41
42 struct wget_size {
operator ()wget_size43 size_t operator()(const wstring &x) const{ return x.size(); }
44 };
45
46 static const unsigned input_count = 100000;
47
48 // Test that update_offset finds the first character with a difference.
update_offset_test()49 void update_offset_test() {
50 vector<string> input;
51 input.push_back("test1");
52 input.push_back("test2");
53 size_t char_offset = 1;
54 update_offset<vector<string>::iterator, unsigned char>(input.begin(),
55 input.end(),
56 char_offset);
57 BOOST_CHECK(char_offset == 4);
58
59 // Functor version
60 char_offset = 1;
61 update_offset(input.begin(), input.end(), char_offset, bracket(), get_size());
62 BOOST_CHECK(char_offset == 4);
63 }
64
65 // Test that offset comparison operators only look after the offset.
offset_comparison_test()66 void 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
string_test()94 void string_test()
95 {
96 // Prepare inputs
97 vector<string> base_vec;
98 const unsigned max_length = 32;
99 srand(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(rand() % 256);
106 }
107 base_vec.push_back(result);
108 }
109 vector<string> sorted_vec = base_vec;
110 vector<string> test_vec = base_vec;
111 std::sort(sorted_vec.begin(), sorted_vec.end());
112 //Testing basic call
113 string_sort(test_vec.begin(), 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(test_vec.begin(), test_vec.end());
118 BOOST_CHECK(test_vec == sorted_vec);
119 //Character functors
120 test_vec = base_vec;
121 string_sort(test_vec.begin(), test_vec.end(), bracket(), get_size());
122 BOOST_CHECK(test_vec == sorted_vec);
123 //All functors
124 test_vec = base_vec;
125 string_sort(test_vec.begin(), test_vec.end(), bracket(), get_size(),
126 less<string>());
127 BOOST_CHECK(test_vec == sorted_vec);
128 //reverse order
129 std::sort(sorted_vec.begin(), sorted_vec.end(), greater<string>());
130 reverse_string_sort(test_vec.begin(), test_vec.end(), greater<string>());
131 BOOST_CHECK(test_vec == sorted_vec);
132 //reverse order with functors
133 test_vec = base_vec;
134 reverse_string_sort(test_vec.begin(), test_vec.end(), bracket(), get_size(),
135 greater<string>());
136 BOOST_CHECK(test_vec == sorted_vec);
137 }
138
139 // Verify that 0, 1, and input_count empty strings all sort correctly.
corner_test()140 void corner_test() {
141 vector<string> test_vec;
142 boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
143 test_vec.resize(1);
144 boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
145 BOOST_CHECK(test_vec[0].empty());
146 test_vec.resize(input_count);
147 boost::sort::spreadsort::spreadsort(test_vec.begin(), 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
test_main(int,char * [])155 int test_main( int, char*[] )
156 {
157 update_offset_test();
158 offset_comparison_test();
159 string_test();
160 corner_test();
161 return 0;
162 }
163