1 //----------------------------------------------------------------------------
2 /// @file test_spinsort.cpp
3 /// @brief test program of the spinsort algorithm
4 ///
5 /// @author Copyright (c) 2016 Francisco José 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 <algorithm>
15 #include <iostream>
16 #include <cstdio>
17 #include <cstdlib>
18 #include <ctime>
19 #include <vector>
20 #include <random>
21 #include <boost/sort/spinsort/spinsort.hpp>
22 #include <boost/test/included/test_exec_monitor.hpp>
23 #include <boost/test/test_tools.hpp>
24
25
26 using namespace boost::sort;
27 using spin_detail::check_stable_sort;
28 using spin_detail::range_sort;
29 using common::range;
30
31 void test1 ( );
32 void test2 ( );
33 void test3 ( );
34 void test4 ( );
35
36 //---------------- stability test -----------------------------------
37 struct xk
38 {
39 unsigned tail : 4;
40 unsigned num : 28;
xkxk41 xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){};
operator <xk42 bool operator< (xk A) const { return (num < A.num); };
43 };
44
test1()45 void test1 ( )
46 {
47 typedef std::less< xk > compare_t;
48 std::mt19937_64 my_rand (0);
49
50 const uint32_t NMAX = 100000;
51
52 std::vector< xk > V1, V2;
53 V1.reserve (NMAX);
54 for (uint32_t i = 0; i < 8; ++i) {
55 for (uint32_t k = 0; k < NMAX; ++k) {
56 uint32_t NM = my_rand ( );
57 xk G;
58 G.num = NM >> 3;
59 G.tail = i;
60 V1.push_back (G);
61 };
62 };
63 V2 = V1;
64 spinsort (V1.begin ( ), V1.end ( ), compare_t ( ));
65 std::stable_sort (V2.begin ( ), V2.end ( ));
66
67 BOOST_CHECK (V1.size ( ) == V2.size ( ));
68 for (uint32_t i = 0; i < V1.size ( ); ++i) {
69 BOOST_CHECK (V1[ i ].num == V2[ i ].num and
70 V1[ i ].tail == V2[ i ].tail);
71 };
72 };
73
test2(void)74 void test2 (void)
75 {
76 typedef std::less< uint64_t > compare_t;
77
78 const uint32_t NElem = 100000;
79 std::vector< uint64_t > V1,V2;
80 std::mt19937_64 my_rand (0);
81 compare_t comp;
82
83 // ------------------------ random elements -------------------------------
84 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (my_rand ( ) % NElem);
85 V2 = V1;
86 spinsort (V1.begin ( ), V1.end ( ), comp);
87 std::stable_sort (V2.begin ( ), V2.end ( ), comp);
88 for (unsigned i = 0; i < NElem; i++) {
89 BOOST_CHECK (V2[ i ] == V1[ i ]);
90 };
91
92 // --------------------------- sorted elements ----------------------------
93 V1.clear ( );
94 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (i);
95 spinsort (V1.begin ( ), V1.end ( ), comp);
96 for (unsigned i = 1; i < NElem; i++) {
97 BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
98 };
99
100 //-------------------------- reverse sorted elements ----------------------
101 V1.clear ( );
102 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (NElem - i);
103 spinsort (V1.begin ( ), V1.end ( ), comp);
104 for (unsigned i = 1; i < NElem; i++) {
105 BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
106 };
107
108 //---------------------------- equal elements ----------------------------
109 V1.clear ( );
110 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (1000);
111 spinsort (V1.begin ( ), V1.end ( ), comp);
112 for (unsigned i = 1; i < NElem; i++) {
113 BOOST_CHECK (V1[ i - 1 ] == V1[ i ]);
114 };
115 };
116
117
test3(void)118 void test3 (void)
119 {
120 typedef typename std::vector<uint64_t>::iterator iter_t ;
121 typedef range<iter_t> range_it ;
122 std::less<uint64_t> comp ;
123
124 std::vector<uint64_t> V = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
125 21, 23, 25, 27, 29, 31, 33, 35, 37, 39,
126 41, 43, 45, 47, 49, 51, 53, 55, 57, 59,
127 14, 2, 4, 6, 8, 10, 12, 16, 18, 20};
128 range_it rdata (V.begin() , V.end());
129 std::vector<uint64_t> aux (40,0 );
130 range_it raux ( aux.begin() , aux.end());
131
132 check_stable_sort ( rdata, raux, comp );
133 for ( uint32_t i =0 ; i < V.size() ; ++i)
134 std::cout<<V[i]<<", ";
135 std::cout<<std::endl;
136
137 V = {59, 57, 55, 53, 51, 49, 47, 45, 43, 41,
138 39, 37, 35, 33, 31, 29, 27, 25, 23, 21,
139 19, 17, 15, 13, 11, 9, 7, 5, 3, 1,
140 14, 2, 6, 16, 18, 20, 12, 4, 8, 10};
141 rdata = range_it (V.begin() , V.end());
142 aux.assign (40,0);
143 raux = range_it ( aux.begin() , aux.end());
144 check_stable_sort ( rdata, raux, comp );
145 for ( uint32_t i =0 ; i < V.size() ; ++i)
146 std::cout<<V[i]<<", ";
147 std::cout<<std::endl;
148
149 }
test4(void)150 void test4 (void)
151 {
152 typedef typename std::vector<xk>::iterator iter_t;
153 typedef std::less<xk> compare_t;
154 std::mt19937 my_rand (0);
155 std::vector<xk> V ;
156 const uint32_t NELEM = 100000;
157 V.reserve(NELEM * 10);
158
159
160 for (uint32_t k =0 ; k < 10 ; ++k)
161 { for ( uint32_t i =0 ; i < NELEM ; ++i)
162 { V.emplace_back(i , k);
163 };
164 iter_t first = V.begin() + (k * NELEM);
165 iter_t last = first + NELEM ;
166 std::shuffle( first, last, my_rand);
167 };
168 spinsort( V.begin() , V.end(), compare_t());
169 for ( uint32_t i =0 ; i < ( NELEM * 10); ++i)
170 { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) );
171 };
172 }
test_main(int,char * [])173 int test_main (int, char *[])
174 {
175 test1 ( );
176 test2 ( );
177 test3 ( );
178 test4 ( );
179 return 0;
180 };
181