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
22using namespace boost::sort;
23
24void test1 ( );
25void test2 ( );
26void test3 ( );
27
28//---------------- stability test -----------------------------------
29struct xk
30{
31 unsigned tail : 4;
32 unsigned num : 28;
33 xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){};
34 bool operator< (xk A) const { return (num < A.num); };
35};
36
37void 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 (n: 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 (x: G);
54 };
55 };
56 //check sort 0 elements
57 flat_stable_sort< iter_t, compare_t > (first: V1.begin ( ), last: V1.begin ( ), cmp: compare_t ( ));
58 V2 = V1;
59 flat_stable_sort< iter_t, compare_t > (first: V1.begin ( ), last: V1.end ( ), cmp: compare_t ( ));
60 std::stable_sort (first: V2.begin ( ), last: V2.end ( ));
61
62 BOOST_CHECK (V1.size ( ) == V2.size ( ));
63 for (uint32_t i = 0; i < V1.size ( ); ++i) {
64 BOOST_CHECK (V1[ i ].num == V2[ i ].num and
65 V1[ i ].tail == V2[ i ].tail);
66 };
67};
68
69void test2 (void)
70{
71 typedef std::less< uint64_t > compare_t;
72
73 const uint32_t NElem = 100000;
74 std::vector< uint64_t > V1,V2;
75 std::mt19937_64 my_rand (0);
76 compare_t comp;
77
78 // ------------------------ random elements -------------------------------
79 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (x: my_rand ( ) % NElem);
80 V2 = V1;
81 flat_stable_sort (first: V1.begin ( ), last: V1.end ( ), cmp: comp);
82 std::stable_sort (first: V2.begin ( ), last: V2.end ( ), comp: comp);
83 for (unsigned i = 0; i < NElem; i++) {
84 BOOST_CHECK (V2[ i ] == V1[ i ]);
85 };
86
87 // --------------------------- sorted elements ----------------------------
88 V1.clear ( );
89 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (x: i);
90 flat_stable_sort (first: V1.begin ( ), last: V1.end ( ), cmp: comp);
91 for (unsigned i = 1; i < NElem; i++) {
92 BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
93 };
94
95 //-------------------------- reverse sorted elements ----------------------
96 V1.clear ( );
97 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (x: NElem - i);
98 flat_stable_sort (first: V1.begin ( ), last: V1.end ( ), cmp: comp);
99 for (unsigned i = 1; i < NElem; i++) {
100 BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
101 };
102
103 //---------------------------- equal elements ----------------------------
104 V1.clear ( );
105 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (x: 1000);
106 flat_stable_sort (first: V1.begin ( ), last: V1.end ( ), cmp: comp);
107 for (unsigned i = 1; i < NElem; i++) {
108 BOOST_CHECK (V1[ i - 1 ] == V1[ i ]);
109 };
110};
111
112
113void test3 (void)
114{
115 typedef typename std::vector<xk>::iterator iter_t;
116 typedef std::less<xk> compare_t;
117 std::mt19937 my_rand (0);
118 std::vector<xk> V ;
119 const uint32_t NELEM = 100000;
120 V.reserve(n: NELEM * 10);
121
122
123 for (uint32_t k =0 ; k < 10 ; ++k)
124 { for ( uint32_t i =0 ; i < NELEM ; ++i)
125 { V.emplace_back(args&: i , args&: k);
126 };
127 iter_t first = V.begin() + (k * NELEM);
128 iter_t last = first + NELEM ;
129 std::shuffle( first: first, last: last, g&: my_rand);
130 };
131 flat_stable_sort( first: V.begin() , last: V.end(), cmp: compare_t());
132 for ( uint32_t i =0 ; i < ( NELEM * 10); ++i)
133 { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) );
134 };
135}
136int test_main (int, char *[])
137{
138 test1 ( );
139 test2 ( );
140 test3 ( );
141 return 0;
142};
143

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