summaryrefslogtreecommitdiffstats
path: root/src/boost/libs/heap/test/mutable_heap_tests.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/boost/libs/heap/test/mutable_heap_tests.hpp')
-rw-r--r--src/boost/libs/heap/test/mutable_heap_tests.hpp325
1 files changed, 325 insertions, 0 deletions
diff --git a/src/boost/libs/heap/test/mutable_heap_tests.hpp b/src/boost/libs/heap/test/mutable_heap_tests.hpp
new file mode 100644
index 00000000..3df1d30f
--- /dev/null
+++ b/src/boost/libs/heap/test/mutable_heap_tests.hpp
@@ -0,0 +1,325 @@
+/*=============================================================================
+ Copyright (c) 2010 Tim Blechmann
+
+ Use, modification and distribution is subject to the Boost Software
+ License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+=============================================================================*/
+
+// random uses boost.fusion, which clashes with boost.test
+//#define USE_BOOST_RANDOM
+
+#ifdef USE_BOOST_RANDOM
+#include <boost/random.hpp>
+#else
+#include <cstdlib>
+#endif
+
+#include "common_heap_tests.hpp"
+
+
+#define PUSH_WITH_HANDLES(HANDLES, Q, DATA) \
+ std::vector<typename pri_queue::handle_type> HANDLES; \
+ \
+ for (unsigned int k = 0; k != data.size(); ++k) \
+ HANDLES.push_back(Q.push(DATA[k]));
+
+
+
+template <typename pri_queue>
+void pri_queue_test_update_decrease(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ *handles[i] = -1;
+ data[i] = -1;
+ q.update(handles[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_decrease_function(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = -1;
+ q.update(handles[i], -1);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_function_identity(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ q.update(handles[i], data[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_shuffled(void)
+{
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ test_data shuffled (data);
+ random_shuffle(shuffled.begin(), shuffled.end());
+
+ for (int i = 0; i != test_size; ++i)
+ q.update(handles[i], shuffled[i]);
+
+ check_q(q, data);
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_update_increase(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = data.back()+1;
+ *handles[i] = data[i];
+ q.update(handles[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_increase_function(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = data.back()+1;
+ q.update(handles[i], data[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_decrease(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ *handles[i] = -1;
+ data[i] = -1;
+ q.decrease(handles[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_decrease_function(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = -1;
+ q.decrease(handles[i], -1);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_decrease_function_identity(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ q.decrease(handles[i], data[i]);
+
+ check_q(q, data);
+ }
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_increase(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = data.back()+1;
+ *handles[i] = data[i];
+ q.increase(handles[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_increase_function(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ data[i] = data.back()+1;
+ q.increase(handles[i], data[i]);
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_increase_function_identity(void)
+{
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ q.increase(handles[i], data[i]);
+
+ check_q(q, data);
+ }
+}
+
+template <typename pri_queue>
+void pri_queue_test_erase(void)
+{
+#ifdef USE_BOOST_RANDOM
+ boost::mt19937 rng;
+#endif
+
+ for (int i = 0; i != test_size; ++i)
+ {
+ pri_queue q;
+ test_data data = make_test_data(test_size);
+ PUSH_WITH_HANDLES(handles, q, data);
+
+ for (int j = 0; j != i; ++j)
+ {
+#ifdef USE_BOOST_RANDOM
+ boost::uniform_int<> range(0, data.size() - 1);
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<> > gen(rng, range);
+
+ int index = gen();
+#else
+ int index = std::rand() % (data.size() - 1);
+#endif
+ q.erase(handles[index]);
+ handles.erase(handles.begin() + index);
+ data.erase(data.begin() + index);
+ }
+
+ std::sort(data.begin(), data.end());
+ check_q(q, data);
+ }
+}
+
+
+template <typename pri_queue>
+void run_mutable_heap_update_tests(void)
+{
+ pri_queue_test_update_increase<pri_queue>();
+ pri_queue_test_update_decrease<pri_queue>();
+
+ pri_queue_test_update_shuffled<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_update_function_tests(void)
+{
+ pri_queue_test_update_increase_function<pri_queue>();
+ pri_queue_test_update_decrease_function<pri_queue>();
+ pri_queue_test_update_function_identity<pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_mutable_heap_decrease_tests(void)
+{
+ pri_queue_test_decrease<pri_queue>();
+ pri_queue_test_decrease_function<pri_queue>();
+ pri_queue_test_decrease_function_identity<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_increase_tests(void)
+{
+ pri_queue_test_increase<pri_queue>();
+ pri_queue_test_increase_function<pri_queue>();
+ pri_queue_test_increase_function_identity<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_erase_tests(void)
+{
+ pri_queue_test_erase<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_test_handle_from_iterator(void)
+{
+ pri_queue que;
+
+ que.push(3);
+ que.push(1);
+ que.push(4);
+
+ que.update(pri_queue::s_handle_from_iterator(que.begin()),
+ 6);
+}
+
+
+template <typename pri_queue>
+void run_mutable_heap_tests(void)
+{
+ run_mutable_heap_update_function_tests<pri_queue>();
+ run_mutable_heap_update_tests<pri_queue>();
+ run_mutable_heap_decrease_tests<pri_queue>();
+ run_mutable_heap_increase_tests<pri_queue>();
+ run_mutable_heap_erase_tests<pri_queue>();
+ run_mutable_heap_test_handle_from_iterator<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_ordered_iterator_tests()
+{
+ pri_queue_test_ordered_iterators<pri_queue>();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-06 16:13:50 +0000