123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325 |
- /*=============================================================================
- 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>();
- }
|