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

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