1 //----------------------------------------------------------------------------
2 /// @file test_flat_stable_sort.cpp
3 /// @brief test program of the flat_stable_sort algorithm
4 ///
5 /// @author Copyright (c) 2017 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 <algorithm>
14 #include <iostream>
15 #include <random>
16 #include <vector>
17 #include <ciso646>
18 #include <boost/sort/flat_stable_sort/flat_stable_sort.hpp>
19 #include <boost/test/included/test_exec_monitor.hpp>
20 #include <boost/test/test_tools.hpp>
21
22 using namespace boost::sort;
23
24 void test1 ( );
25 void test2 ( );
26 void test3 ( );
27
28 //---------------- stability test -----------------------------------
29 struct xk
30 {
31 unsigned tail : 4;
32 unsigned num : 28;
xkxk33 xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){};
operator <xk34 bool operator< (xk A) const { return (num < A.num); };
35 };
36
test1()37 void test1 ( )
38 {
39 typedef typename std::vector< xk >::iterator iter_t;
40 typedef std::less< xk > compare_t;
41 std::mt19937_64 my_rand (0);
42
43 const uint32_t NMAX = 100000;
44
45 std::vector< xk > V1, V2;
46 V1.reserve (NMAX);
47 for (uint32_t i = 0; i < 8; ++i) {
48 for (uint32_t k = 0; k < NMAX; ++k) {
49 uint32_t NM = my_rand ( );
50 xk G;
51 G.num = NM >> 3;
52 G.tail = i;
53 V1.push_back (G);
54 };
55 };
56 V2 = V1;
57 flat_stable_sort< iter_t, compare_t > (V1.begin ( ), V1.end ( ), compare_t ( ));
58 std::stable_sort (V2.begin ( ), V2.end ( ));
59
60 BOOST_CHECK (V1.size ( ) == V2.size ( ));
61 for (uint32_t i = 0; i < V1.size ( ); ++i) {
62 BOOST_CHECK (V1[ i ].num == V2[ i ].num and
63 V1[ i ].tail == V2[ i ].tail);
64 };
65 };
66
test2(void)67 void test2 (void)
68 {
69 typedef std::less< uint64_t > compare_t;
70
71 const uint32_t NElem = 100000;
72 std::vector< uint64_t > V1,V2;
73 std::mt19937_64 my_rand (0);
74 compare_t comp;
75
76 // ------------------------ random elements -------------------------------
77 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (my_rand ( ) % NElem);
78 V2 = V1;
79 flat_stable_sort (V1.begin ( ), V1.end ( ), comp);
80 std::stable_sort (V2.begin ( ), V2.end ( ), comp);
81 for (unsigned i = 0; i < NElem; i++) {
82 BOOST_CHECK (V2[ i ] == V1[ i ]);
83 };
84
85 // --------------------------- sorted elements ----------------------------
86 V1.clear ( );
87 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (i);
88 flat_stable_sort (V1.begin ( ), V1.end ( ), comp);
89 for (unsigned i = 1; i < NElem; i++) {
90 BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
91 };
92
93 //-------------------------- reverse sorted elements ----------------------
94 V1.clear ( );
95 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (NElem - i);
96 flat_stable_sort (V1.begin ( ), V1.end ( ), comp);
97 for (unsigned i = 1; i < NElem; i++) {
98 BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
99 };
100
101 //---------------------------- equal elements ----------------------------
102 V1.clear ( );
103 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (1000);
104 flat_stable_sort (V1.begin ( ), V1.end ( ), comp);
105 for (unsigned i = 1; i < NElem; i++) {
106 BOOST_CHECK (V1[ i - 1 ] == V1[ i ]);
107 };
108 };
109
110
test3(void)111 void test3 (void)
112 {
113 typedef typename std::vector<xk>::iterator iter_t;
114 typedef std::less<xk> compare_t;
115 std::mt19937 my_rand (0);
116 std::vector<xk> V ;
117 const uint32_t NELEM = 100000;
118 V.reserve(NELEM * 10);
119
120
121 for (uint32_t k =0 ; k < 10 ; ++k)
122 { for ( uint32_t i =0 ; i < NELEM ; ++i)
123 { V.emplace_back(i , k);
124 };
125 iter_t first = V.begin() + (k * NELEM);
126 iter_t last = first + NELEM ;
127 std::shuffle( first, last, my_rand);
128 };
129 flat_stable_sort( V.begin() , V.end(), compare_t());
130 for ( uint32_t i =0 ; i < ( NELEM * 10); ++i)
131 { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) );
132 };
133 }
test_main(int,char * [])134 int test_main (int, char *[])
135 {
136 test1 ( );
137 test2 ( );
138 test3 ( );
139 return 0;
140 };
141