1 /*=============================================================================
2 Copyright (c) 2010 Tim Blechmann
3
4 Use, modification and distribution is subject to the Boost Software
5 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
7 =============================================================================*/
8
9 #include <boost/foreach.hpp>
10 #include "common_heap_tests.hpp"
11
12 struct q_tester
13 {
q_testerq_tester14 q_tester(int i = 0, int j = 0):
15 value(i), id(j)
16 {}
17
operator <q_tester18 bool operator< (q_tester const & rhs) const
19 {
20 return value < rhs.value;
21 }
22
operator >q_tester23 bool operator> (q_tester const & rhs) const
24 {
25 return value > rhs.value;
26 }
27
operator ==q_tester28 bool operator== (q_tester const & rhs) const
29 {
30 return (value == rhs.value) && (id == rhs.id);
31 }
32
33 int value;
34 int id;
35 };
36
operator <<(std::ostream & out,q_tester const & t)37 std::ostream& operator<< (std::ostream& out, q_tester const & t)
38 {
39 out << "[" << t.value << " " << t.id << "]";
40 return out;
41 }
42
43 typedef std::vector<q_tester> stable_test_data;
44
make_stable_test_data(int size,int same_count=3,int offset=0,int strive=1)45 stable_test_data make_stable_test_data(int size, int same_count = 3,
46 int offset = 0, int strive = 1)
47 {
48 stable_test_data ret;
49
50 for (int i = 0; i != size; ++i)
51 for (int j = 0; j != same_count; ++j)
52 ret.push_back(q_tester(i * strive + offset, j));
53 return ret;
54 }
55
56 struct compare_by_id
57 {
operator ()compare_by_id58 bool operator()(q_tester const & lhs, q_tester const & rhs)
59 {
60 return lhs.id > rhs.id;
61 }
62 };
63
64 template <typename pri_queue>
pri_queue_stable_test_sequential_push(void)65 void pri_queue_stable_test_sequential_push(void)
66 {
67 stable_test_data data = make_stable_test_data(test_size);
68
69 pri_queue q;
70 fill_q(q, data);
71 std::stable_sort(data.begin(), data.end(), compare_by_id());
72 std::stable_sort(data.begin(), data.end(), std::less<q_tester>());
73 check_q(q, data);
74 }
75
76 template <typename pri_queue>
pri_queue_stable_test_sequential_reverse_push(void)77 void pri_queue_stable_test_sequential_reverse_push(void)
78 {
79 stable_test_data data = make_stable_test_data(test_size);
80 pri_queue q;
81 stable_test_data push_data(data);
82
83 std::stable_sort(push_data.begin(), push_data.end(), std::greater<q_tester>());
84
85 fill_q(q, push_data);
86
87 std::stable_sort(data.begin(), data.end(), compare_by_id());
88 std::stable_sort(data.begin(), data.end(), std::less<q_tester>());
89
90 check_q(q, data);
91 }
92
93
94 template <typename pri_queue>
run_stable_heap_tests(void)95 void run_stable_heap_tests(void)
96 {
97 pri_queue_stable_test_sequential_push<pri_queue>();
98 pri_queue_stable_test_sequential_reverse_push<pri_queue>();
99 }
100