1 //----------------------------------------------------------------------------
2 /// @file test_sample_sort.cpp
3 /// @brief test sample_sort algorithm
4 ///
5 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
6 /// Distributed under the Boost Software License, Version 1.0.\n
7 /// ( See accompanying file LICENSE_1_0.txt or copy at
8 /// http://www.boost.org/LICENSE_1_0.txt )
9 /// @version 0.1
10 ///
11 /// @remarks
12 //-----------------------------------------------------------------------------
13 #include <ciso646>
14 #include <cstdlib>
15 #include <ctime>
16 #include <algorithm>
17 #include <vector>
18 #include <random>
19 #include <boost/sort/sample_sort/sample_sort.hpp>
20 #include <boost/test/included/test_exec_monitor.hpp>
21 #include <boost/test/test_tools.hpp>
22
23 namespace bss = boost::sort;
24
25
26 struct xk
27 {
28 unsigned tail : 4;
29 unsigned num : 28;
xkxk30 xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){};
operator <xk31 bool operator< (xk A) const { return (num < A.num); };
32 };
test1()33 void test1()
34 {
35
36 std::mt19937_64 my_rand(0);
37
38 const uint32_t NMAX = 100000;
39
40 std::vector<xk> V1, V2, V3;
41 V1.reserve(NMAX);
42 for (uint32_t i = 0; i < 8; ++i)
43 {
44 for (uint32_t k = 0; k < NMAX; ++k)
45 { uint32_t NM = my_rand();
46 xk G;
47 G.num = NM >> 3;
48 G.tail = i;
49 V1.push_back(G);
50 };
51 };
52 V3 = V2 = V1;
53 bss::sample_sort(V1.begin(), V1.end());
54 std::stable_sort(V2.begin(), V2.end());
55 bss::sample_sort(V3.begin(), V3.end(), 0);
56
57 BOOST_CHECK(V1.size() == V2.size());
58 for (uint32_t i = 0; i < V1.size(); ++i)
59 { BOOST_CHECK(V1[i].num == V2[i].num and V1[i].tail == V2[i].tail);
60 };
61
62 BOOST_CHECK(V3.size() == V2.size());
63 for (uint32_t i = 0; i < V3.size(); ++i)
64 { BOOST_CHECK(V3[i].num == V2[i].num and V3[i].tail == V2[i].tail);
65 };
66 };
67
test2(void)68 void test2(void)
69 {
70 const uint32_t NElem = 2000000;
71 std::vector<uint64_t> V1;
72
73 // ----------------- sorted elements ------------------------------------
74 V1.clear();
75 for (uint32_t i = 0; i < NElem; ++i) V1.push_back(i);
76 bss::sample_sort(V1.begin(), V1.end());
77 for (unsigned i = 1; i < NElem; i++)
78 { BOOST_CHECK(V1[i - 1] <= V1[i]);
79 };
80
81 // ------------- reverse sorted elements --------------------------------
82 V1.clear();
83 for (uint32_t i = 0; i < NElem; ++i) V1.push_back(NElem - i);
84 bss::sample_sort(V1.begin(), V1.end());
85 for (unsigned i = 1; i < NElem; i++)
86 { BOOST_CHECK(V1[i - 1] <= V1[i]);
87 };
88
89 // -------------------- equals elements -----------------------------------
90 V1.clear();
91 for (uint32_t i = 0; i < NElem; ++i) V1.push_back(1000);
92 bss::sample_sort(V1.begin(), V1.end());
93 for (unsigned i = 1; i < NElem; i++)
94 { BOOST_CHECK(V1[i - 1] == V1[i]);
95 };
96 };
test3(void)97 void test3(void)
98 {
99 typedef std::less<uint64_t> compare;
100 const uint32_t NElem = 2000000;
101 std::vector<uint64_t> V1,V2,V3;
102 std::mt19937_64 my_rand(0);
103
104 for (uint32_t i = 0; i < NElem; ++i) V1.push_back(my_rand() % NElem);
105 V3 = V2 = V1;
106 std::stable_sort (V2.begin(), V2.end());
107
108
109 // --------------- unsorted elements 0 threads ----------------------------
110 V3 = V1;
111 bss::sample_sort(V3.begin(), V3.end(), compare(), 0);
112 for (unsigned i = 0; i < NElem; i++)
113 { BOOST_CHECK(V3[i] == V2[i]);
114 };
115
116 // --------------- unsorted elements -------------------------------------
117 V3 = V1;
118 bss::sample_sort(V3.begin(), V3.end(), compare());
119 for (unsigned i = 0; i < NElem; i++)
120 { BOOST_CHECK(V3[i] == V2[i]);
121 };
122
123 // --------------- unsorted elements 100 threads ----------------------------
124 V3 = V1;
125 bss::sample_sort(V3.begin(), V3.end(), compare(), 100);
126 for (unsigned i = 0; i < NElem; i++)
127 { BOOST_CHECK(V3[i] == V2[i]);
128 };
129 };
130
test4(void)131 void test4(void)
132 {
133 const uint32_t KMax = 66000;
134
135 std::vector<uint64_t> K, M;
136 std::mt19937_64 my_rand(0);
137
138 for (uint32_t i = 0; i < KMax; ++i)
139 K.push_back(my_rand());
140 M = K;
141
142 bss::sample_sort(K.begin(), K.end(), 300);
143
144 std::stable_sort(M.begin(), M.end());
145 for (unsigned i = 0; i < KMax; i++)
146 BOOST_CHECK(M[i] == K[i]);
147 };
148
test5(void)149 void test5 (void)
150 {
151 typedef typename std::vector<xk>::iterator iter_t;
152 std::mt19937 my_rand (0);
153 std::vector<xk> V ;
154 const uint32_t NELEM = 100000;
155 V.reserve(NELEM * 10);
156
157
158 for (uint32_t k =0 ; k < 10 ; ++k)
159 { for ( uint32_t i =0 ; i < NELEM ; ++i)
160 { V.emplace_back(i , k);
161 };
162 iter_t first = V.begin() + (k * NELEM);
163 iter_t last = first + NELEM ;
164 std::shuffle( first, last, my_rand);
165 };
166 bss::sample_sort( V.begin() , V.end());
167 for ( uint32_t i =0 ; i < ( NELEM * 10); ++i)
168 { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) );
169 };
170 }
171
172
test_main(int,char * [])173 int test_main(int, char *[])
174 {
175 test1();
176 test2();
177 test3();
178 test4();
179 test5();
180 return 0;
181 };
182