1 | ////////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Ion Gaztanaga 2015-2016. |
4 | // Distributed under the Boost Software License, Version 1.0. |
5 | // (See accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | // |
8 | // See http://www.boost.org/libs/move for documentation. |
9 | // |
10 | ////////////////////////////////////////////////////////////////////////////// |
11 | |
12 | #ifdef NDEBUG |
13 | #undef NDEBUG |
14 | #endif |
15 | |
16 | #define BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS |
17 | |
18 | #include <cstdlib> //std::srand |
19 | #include <iostream> //std::cout |
20 | |
21 | #include <boost/config.hpp> |
22 | |
23 | #include <boost/move/unique_ptr.hpp> |
24 | #include <boost/container/vector.hpp> |
25 | |
26 | #include "order_type.hpp" |
27 | #include "random_shuffle.hpp" |
28 | |
29 | #include <boost/move/algo/adaptive_sort.hpp> |
30 | #include <boost/move/core.hpp> |
31 | #include <cstdlib> |
32 | |
33 | template<class T> |
34 | bool test_random_shuffled(std::size_t const element_count, std::size_t const num_keys, std::size_t const num_iter) |
35 | { |
36 | boost::movelib::unique_ptr<T[]> elements(new T[element_count]); |
37 | boost::movelib::unique_ptr<std::size_t[]> key_reps(new std::size_t[num_keys ? num_keys : element_count]); |
38 | std::cout << "- - N: " << element_count << ", Keys: " << num_keys << ", It: " << num_iter << " \n" ; |
39 | |
40 | //Initialize keys |
41 | for(std::size_t i=0; i < element_count; ++i){ |
42 | std::size_t key = num_keys ? (i % num_keys) : i; |
43 | elements[i].key=key; |
44 | } |
45 | |
46 | std::srand(seed: 0); |
47 | |
48 | for (std::size_t it = 0; it != num_iter; ++it) |
49 | { |
50 | ::random_shuffle(elements.get(), elements.get() + element_count); |
51 | for(std::size_t i = 0; i < (num_keys ? num_keys : element_count); ++i){ |
52 | key_reps[i]=0; |
53 | } |
54 | for(std::size_t i = 0; i < element_count; ++i){ |
55 | elements[i].val = key_reps[elements[i].key]++; |
56 | } |
57 | |
58 | boost::movelib::adaptive_sort(elements.get(), elements.get()+element_count, order_type_less()); |
59 | |
60 | if (!is_order_type_ordered(elements.get(), element_count)) |
61 | { |
62 | std::cout << "\n ERROR\n" ; |
63 | std::abort(); |
64 | } |
65 | } |
66 | return true; |
67 | } |
68 | |
69 | void instantiate_smalldiff_iterators() |
70 | { |
71 | typedef randit<int, short> short_rand_it_t; |
72 | boost::movelib::adaptive_sort(first: short_rand_it_t(), last: short_rand_it_t(), comp: less_int()); |
73 | |
74 | typedef randit<int, signed char> schar_rand_it_t; |
75 | boost::movelib::adaptive_sort(first: schar_rand_it_t(), last: schar_rand_it_t(), comp: less_int()); |
76 | } |
77 | |
78 | int main() |
79 | { |
80 | instantiate_smalldiff_iterators(); |
81 | |
82 | const std::size_t NIter = 100; |
83 | |
84 | test_random_shuffled<order_move_type>(element_count: 1001, num_keys: 3, num_iter: NIter); |
85 | test_random_shuffled<order_move_type>(element_count: 1001, num_keys: 65, num_iter: NIter); |
86 | test_random_shuffled<order_move_type>(element_count: 1001, num_keys: 101, num_iter: NIter); |
87 | test_random_shuffled<order_move_type>(element_count: 1001, num_keys: 200, num_iter: NIter); |
88 | |
89 | |
90 | //Below absolute minimal unique values |
91 | test_random_shuffled<order_move_type>(element_count: 10001, num_keys: 3, num_iter: NIter); |
92 | //Above absolute minimal unique values, below internal buffer |
93 | test_random_shuffled<order_move_type>(element_count: 10001, num_keys: 65, num_iter: NIter); |
94 | //Enough keys for internal buffer but below minimal keys |
95 | test_random_shuffled<order_move_type>(element_count: 10001, num_keys: 101, num_iter: NIter); |
96 | //Enough keys for internal buffer and above minimal keys |
97 | test_random_shuffled<order_move_type>(element_count: 10001, num_keys: 200, num_iter: NIter); |
98 | //Enough keys for internal buffer, and full keys |
99 | test_random_shuffled<order_move_type>(element_count: 10001, num_keys: 1023, num_iter: NIter); |
100 | test_random_shuffled<order_move_type>(element_count: 10001, num_keys: 4095, num_iter: NIter); |
101 | test_random_shuffled<order_move_type>(element_count: 10001, num_keys: 0, num_iter: NIter); |
102 | |
103 | return 0; |
104 | } |
105 | |