From 483eb2f56657e8e7f419ab1a4fab8dce9ade8609 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 27 Apr 2024 20:24:20 +0200 Subject: Adding upstream version 14.2.21. Signed-off-by: Daniel Baumann --- src/boost/libs/heap/test/mutable_heap_tests.hpp | 325 ++++++++++++++++++++++++ 1 file changed, 325 insertions(+) create mode 100644 src/boost/libs/heap/test/mutable_heap_tests.hpp (limited to 'src/boost/libs/heap/test/mutable_heap_tests.hpp') 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 +#else +#include +#endif + +#include "common_heap_tests.hpp" + + +#define PUSH_WITH_HANDLES(HANDLES, Q, DATA) \ + std::vector HANDLES; \ + \ + for (unsigned int k = 0; k != data.size(); ++k) \ + HANDLES.push_back(Q.push(DATA[k])); + + + +template +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 +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 +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 +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 +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 +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 +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 +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 +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 +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 +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 +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 +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 > 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 +void run_mutable_heap_update_tests(void) +{ + pri_queue_test_update_increase(); + pri_queue_test_update_decrease(); + + pri_queue_test_update_shuffled(); +} + +template +void run_mutable_heap_update_function_tests(void) +{ + pri_queue_test_update_increase_function(); + pri_queue_test_update_decrease_function(); + pri_queue_test_update_function_identity(); +} + + +template +void run_mutable_heap_decrease_tests(void) +{ + pri_queue_test_decrease(); + pri_queue_test_decrease_function(); + pri_queue_test_decrease_function_identity(); +} + +template +void run_mutable_heap_increase_tests(void) +{ + pri_queue_test_increase(); + pri_queue_test_increase_function(); + pri_queue_test_increase_function_identity(); +} + +template +void run_mutable_heap_erase_tests(void) +{ + pri_queue_test_erase(); +} + +template +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 +void run_mutable_heap_tests(void) +{ + run_mutable_heap_update_function_tests(); + run_mutable_heap_update_tests(); + run_mutable_heap_decrease_tests(); + run_mutable_heap_increase_tests(); + run_mutable_heap_erase_tests(); + run_mutable_heap_test_handle_from_iterator(); +} + +template +void run_ordered_iterator_tests() +{ + pri_queue_test_ordered_iterators(); +} -- cgit v1.2.3