123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520 |
- /*=============================================================================
- 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)
- =============================================================================*/
- #ifndef COMMON_HEAP_TESTS_HPP_INCLUDED
- #define COMMON_HEAP_TESTS_HPP_INCLUDED
- #include <algorithm>
- #include <vector>
- #include <boost/concept/assert.hpp>
- #include <boost/concept_archetype.hpp>
- #include <boost/shared_ptr.hpp>
- #include <boost/heap/heap_concepts.hpp>
- #ifdef BOOST_NO_CXX98_RANDOM_SHUFFLE
- #include <cstdlib>
- #include <iterator>
- template<class RandomIt>
- void random_shuffle(RandomIt first, RandomIt last)
- {
- typedef typename std::iterator_traits<RandomIt>::difference_type difference_type;
- difference_type n = last - first;
- for (difference_type i = n-1; i > 0; --i) {
- difference_type j = std::rand() % (i + 1);
- if (j != i) {
- using std::swap;
- swap(first[i], first[j]);
- }
- }
- }
- #else
-
- using std::random_shuffle;
- #endif
- typedef boost::default_constructible_archetype<
- boost::less_than_comparable_archetype<
- boost::copy_constructible_archetype<
- boost::assignable_archetype<
- > > > > test_value_type;
- typedef std::vector<int> test_data;
- const int test_size = 32;
- struct dummy_run
- {
- static void run(void)
- {}
- };
- test_data make_test_data(int size, int offset = 0, int strive = 1)
- {
- test_data ret;
- for (int i = 0; i != size; ++i)
- ret.push_back(i * strive + offset);
- return ret;
- }
- template <typename pri_queue, typename data_container>
- void check_q(pri_queue & q, data_container const & expected)
- {
- BOOST_REQUIRE_EQUAL(q.size(), expected.size());
- for (unsigned int i = 0; i != expected.size(); ++i)
- {
- BOOST_REQUIRE_EQUAL(q.size(), expected.size() - i);
- BOOST_REQUIRE_EQUAL(q.top(), expected[expected.size()-1-i]);
- q.pop();
- }
- BOOST_REQUIRE(q.empty());
- }
- template <typename pri_queue, typename data_container>
- void fill_q(pri_queue & q, data_container const & data)
- {
- for (unsigned int i = 0; i != data.size(); ++i)
- q.push(data[i]);
- }
- #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
- template <typename pri_queue, typename data_container>
- void fill_emplace_q(pri_queue & q, data_container const & data)
- {
- for (unsigned int i = 0; i != data.size(); ++i) {
- typename pri_queue::value_type value = data[i];
- q.emplace(std::move(value));
- }
- }
- #endif
- template <typename pri_queue>
- void pri_queue_test_sequential_push(void)
- {
- for (int i = 0; i != test_size; ++i)
- {
- pri_queue q;
- test_data data = make_test_data(i);
- fill_q(q, data);
- check_q(q, data);
- }
- }
- template <typename pri_queue>
- void pri_queue_test_sequential_reverse_push(void)
- {
- for (int i = 0; i != test_size; ++i)
- {
- pri_queue q;
- test_data data = make_test_data(i);
- std::reverse(data.begin(), data.end());
- fill_q(q, data);
- std::reverse(data.begin(), data.end());
- check_q(q, data);
- }
- }
- template <typename pri_queue>
- void pri_queue_test_emplace(void)
- {
- #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
- for (int i = 0; i != test_size; ++i)
- {
- pri_queue q;
- test_data data = make_test_data(i);
- std::reverse(data.begin(), data.end());
- fill_emplace_q(q, data);
- std::reverse(data.begin(), data.end());
- check_q(q, data);
- }
- #endif
- }
- template <typename pri_queue>
- void pri_queue_test_random_push(void)
- {
- for (int i = 0; i != test_size; ++i)
- {
- pri_queue q;
- test_data data = make_test_data(i);
- test_data shuffled (data);
- random_shuffle(shuffled.begin(), shuffled.end());
- fill_q(q, shuffled);
- check_q(q, data);
- }
- }
- template <typename pri_queue>
- void pri_queue_test_copyconstructor(void)
- {
- for (int i = 0; i != test_size; ++i)
- {
- pri_queue q;
- test_data data = make_test_data(i);
- fill_q(q, data);
- pri_queue r(q);
- check_q(r, data);
- }
- }
- template <typename pri_queue>
- void pri_queue_test_assignment(void)
- {
- for (int i = 0; i != test_size; ++i)
- {
- pri_queue q;
- test_data data = make_test_data(i);
- fill_q(q, data);
- pri_queue r;
- r = q;
- check_q(r, data);
- }
- }
- template <typename pri_queue>
- void pri_queue_test_moveconstructor(void)
- {
- #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
- pri_queue q;
- test_data data = make_test_data(test_size);
- fill_q(q, data);
- pri_queue r(std::move(q));
- check_q(r, data);
- BOOST_REQUIRE(q.empty());
- #endif
- }
- template <typename pri_queue>
- void pri_queue_test_move_assignment(void)
- {
- #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
- pri_queue q;
- test_data data = make_test_data(test_size);
- fill_q(q, data);
- pri_queue r;
- r = std::move(q);
- check_q(r, data);
- BOOST_REQUIRE(q.empty());
- #endif
- }
- template <typename pri_queue>
- void pri_queue_test_swap(void)
- {
- for (int i = 0; i != test_size; ++i)
- {
- pri_queue q;
- test_data data = make_test_data(i);
- test_data shuffled (data);
- random_shuffle(shuffled.begin(), shuffled.end());
- fill_q(q, shuffled);
- pri_queue r;
- q.swap(r);
- check_q(r, data);
- BOOST_REQUIRE(q.empty());
- }
- }
- template <typename pri_queue>
- void pri_queue_test_iterators(void)
- {
- for (int i = 0; i != test_size; ++i) {
- test_data data = make_test_data(test_size);
- test_data shuffled (data);
- random_shuffle(shuffled.begin(), shuffled.end());
- pri_queue q;
- BOOST_REQUIRE(q.begin() == q.end());
- fill_q(q, shuffled);
- for (unsigned long j = 0; j != data.size(); ++j)
- BOOST_REQUIRE(std::find(q.begin(), q.end(), data[j]) != q.end());
- for (unsigned long j = 0; j != data.size(); ++j)
- BOOST_REQUIRE(std::find(q.begin(), q.end(), data[j] + data.size()) == q.end());
- test_data data_from_queue(q.begin(), q.end());
- std::sort(data_from_queue.begin(), data_from_queue.end());
- BOOST_REQUIRE(data == data_from_queue);
- for (unsigned long j = 0; j != data.size(); ++j) {
- BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - j));
- q.pop();
- }
- }
- }
- template <typename pri_queue>
- void pri_queue_test_ordered_iterators(void)
- {
- for (int i = 0; i != test_size; ++i) {
- test_data data = make_test_data(i);
- test_data shuffled (data);
- random_shuffle(shuffled.begin(), shuffled.end());
- pri_queue q;
- BOOST_REQUIRE(q.ordered_begin() == q.ordered_end());
- fill_q(q, shuffled);
- test_data data_from_queue(q.ordered_begin(), q.ordered_end());
- std::reverse(data_from_queue.begin(), data_from_queue.end());
- BOOST_REQUIRE(data == data_from_queue);
- for (unsigned long j = 0; j != data.size(); ++j)
- BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[j]) != q.ordered_end());
- for (unsigned long j = 0; j != data.size(); ++j)
- BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[j] + data.size()) == q.ordered_end());
- for (unsigned long j = 0; j != data.size(); ++j) {
- BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - j));
- q.pop();
- }
- }
- }
- template <typename pri_queue>
- void pri_queue_test_equality(void)
- {
- for (int i = 0; i != test_size; ++i)
- {
- pri_queue q, r;
- test_data data = make_test_data(i);
- fill_q(q, data);
- std::reverse(data.begin(), data.end());
- fill_q(r, data);
- BOOST_REQUIRE(r == q);
- }
- }
- template <typename pri_queue>
- void pri_queue_test_inequality(void)
- {
- for (int i = 1; i != test_size; ++i)
- {
- pri_queue q, r;
- test_data data = make_test_data(i);
- fill_q(q, data);
- data[0] = data.back() + 1;
- fill_q(r, data);
- BOOST_REQUIRE(r != q);
- }
- }
- template <typename pri_queue>
- void pri_queue_test_less(void)
- {
- for (int i = 1; i != test_size; ++i)
- {
- pri_queue q, r;
- test_data data = make_test_data(i);
- test_data r_data(data);
- r_data.pop_back();
- fill_q(q, data);
- fill_q(r, r_data);
- BOOST_REQUIRE(r < q);
- }
- for (int i = 1; i != test_size; ++i)
- {
- pri_queue q, r;
- test_data data = make_test_data(i);
- test_data r_data(data);
- data.push_back(data.back() + 1);
- fill_q(q, data);
- fill_q(r, r_data);
- BOOST_REQUIRE(r < q);
- }
- for (int i = 1; i != test_size; ++i)
- {
- pri_queue q, r;
- test_data data = make_test_data(i);
- test_data r_data(data);
- data.back() += 1;
- fill_q(q, data);
- fill_q(r, r_data);
- BOOST_REQUIRE(r < q);
- }
- for (int i = 1; i != test_size; ++i)
- {
- pri_queue q, r;
- test_data data = make_test_data(i);
- test_data r_data(data);
- r_data.front() -= 1;
- fill_q(q, data);
- fill_q(r, r_data);
- BOOST_REQUIRE(r < q);
- }
- }
- template <typename pri_queue>
- void pri_queue_test_clear(void)
- {
- for (int i = 0; i != test_size; ++i)
- {
- pri_queue q;
- test_data data = make_test_data(i);
- fill_q(q, data);
- q.clear();
- BOOST_REQUIRE(q.size() == 0);
- BOOST_REQUIRE(q.empty());
- }
- }
- template <typename pri_queue>
- void run_concept_check(void)
- {
- BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
- }
- template <typename pri_queue>
- void run_common_heap_tests(void)
- {
- pri_queue_test_sequential_push<pri_queue>();
- pri_queue_test_sequential_reverse_push<pri_queue>();
- pri_queue_test_random_push<pri_queue>();
- pri_queue_test_equality<pri_queue>();
- pri_queue_test_inequality<pri_queue>();
- pri_queue_test_less<pri_queue>();
- pri_queue_test_clear<pri_queue>();
- pri_queue_test_emplace<pri_queue>();
- }
- template <typename pri_queue>
- void run_iterator_heap_tests(void)
- {
- pri_queue_test_iterators<pri_queue>();
- }
- template <typename pri_queue>
- void run_copyable_heap_tests(void)
- {
- pri_queue_test_copyconstructor <pri_queue>();
- pri_queue_test_assignment<pri_queue>();
- pri_queue_test_swap<pri_queue>();
- }
- template <typename pri_queue>
- void run_moveable_heap_tests(void)
- {
- pri_queue_test_moveconstructor <pri_queue>();
- pri_queue_test_move_assignment <pri_queue>();
- }
- template <typename pri_queue>
- void run_reserve_heap_tests(void)
- {
- test_data data = make_test_data(test_size);
- pri_queue q;
- q.reserve(6);
- fill_q(q, data);
- check_q(q, data);
- }
- template <typename pri_queue>
- void run_leak_check_test(void)
- {
- pri_queue q;
- q.push(boost::shared_ptr<int>(new int(0)));
- }
- struct less_with_T
- {
- typedef int T;
- bool operator()(const int& a, const int& b) const
- {
- return a < b;
- }
- };
- #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
- class thing {
- public:
- thing( int a_, int b_, int c_ ) : a(a_), b(b_), c(c_) {}
- public:
- int a;
- int b;
- int c;
- };
- class cmpthings {
- public:
- bool operator() ( const thing& lhs, const thing& rhs ) const {
- return lhs.a > rhs.a;
- }
- bool operator() ( const thing& lhs, const thing& rhs ) {
- return lhs.a > rhs.a;
- }
- };
- #define RUN_EMPLACE_TEST(HEAP_TYPE) \
- do { \
- cmpthings ord; \
- boost::heap::HEAP_TYPE<thing, boost::heap::compare<cmpthings> > vpq(ord); \
- vpq.emplace(5, 6, 7); \
- boost::heap::HEAP_TYPE<thing, boost::heap::compare<cmpthings>, boost::heap::stable<true> > vpq2(ord); \
- vpq2.emplace(5, 6, 7); \
- } while(0);
- #else
- #define RUN_EMPLACE_TEST(HEAP_TYPE)
- #endif
- #endif // COMMON_HEAP_TESTS_HPP_INCLUDED
|