summaryrefslogtreecommitdiffstats
path: root/src/boost/libs/heap/test
diff options
context:
space:
mode:
Diffstat (limited to 'src/boost/libs/heap/test')
-rw-r--r--src/boost/libs/heap/test/Jamfile.v239
-rw-r--r--src/boost/libs/heap/test/binomial_heap_test.cpp72
-rw-r--r--src/boost/libs/heap/test/common_heap_tests.hpp520
-rw-r--r--src/boost/libs/heap/test/d_ary_heap_test.cpp135
-rw-r--r--src/boost/libs/heap/test/fibonacci_heap_test.cpp76
-rw-r--r--src/boost/libs/heap/test/merge_heap_tests.hpp75
-rw-r--r--src/boost/libs/heap/test/mutable_heap_test.cpp142
-rw-r--r--src/boost/libs/heap/test/mutable_heap_tests.hpp325
-rw-r--r--src/boost/libs/heap/test/pairing_heap_tests.cpp74
-rw-r--r--src/boost/libs/heap/test/priority_queue_test.cpp49
-rw-r--r--src/boost/libs/heap/test/self_contained_header.cpp22
-rw-r--r--src/boost/libs/heap/test/skew_heap_test.cpp120
-rw-r--r--src/boost/libs/heap/test/stable_heap_tests.hpp99
13 files changed, 1748 insertions, 0 deletions
diff --git a/src/boost/libs/heap/test/Jamfile.v2 b/src/boost/libs/heap/test/Jamfile.v2
new file mode 100644
index 00000000..9f591b99
--- /dev/null
+++ b/src/boost/libs/heap/test/Jamfile.v2
@@ -0,0 +1,39 @@
+# (C) Copyright 2010: Tim Blechmann
+# Distributed under 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)
+
+import testing ;
+import path ;
+import regex ;
+
+rule test_all
+{
+ local all_rules ;
+ local file ;
+ local headers_path = [ path.make $(BOOST_ROOT)/libs/heap/include/boost/heap ] ;
+ for file in [ path.glob-tree $(headers_path) : *.hpp : detail ]
+ {
+ local rel_file = [ path.relative-to $(headers_path) $(file) ] ;
+ # Note: The test name starts with '~' in order to group these tests in the test report table, preferably at the end.
+ # All '/' are replaced with '-' because apparently test scripts have a problem with test names containing slashes.
+ local test_name = [ regex.replace ~hdr/$(rel_file) "/" "-" ] ;
+ #ECHO $(rel_file) ;
+ all_rules += [ compile self_contained_header.cpp : <define>"BOOST_HEAP_TEST_HEADER=$(rel_file)" <dependency>$(file) : $(test_name) ] ;
+ }
+
+ for file in [ glob *.cpp ]
+ {
+ if [ path.basename $(file) ] != "self_contained_header.cpp"
+ {
+ all_rules += [ run $(file)
+ : # additional args
+ : # test-files
+ : <library>/boost/test//boost_unit_test_framework # requirements
+ ] ;
+ }
+ }
+
+ return $(all_rules) ;
+}
+
+test-suite heap : [ test_all ] : <threading>multi ;
diff --git a/src/boost/libs/heap/test/binomial_heap_test.cpp b/src/boost/libs/heap/test/binomial_heap_test.cpp
new file mode 100644
index 00000000..05434e99
--- /dev/null
+++ b/src/boost/libs/heap/test/binomial_heap_test.cpp
@@ -0,0 +1,72 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/binomial_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable, bool constant_time_size>
+void run_binomial_heap_test(void)
+{
+ typedef boost::heap::binomial_heap<int, boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size> > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_mutable_heap_tests<pri_queue >();
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::binomial_heap<q_tester, boost::heap::stable<stable>,
+ boost::heap::constant_time_size<constant_time_size> > stable_pri_queue;
+
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( binomial_heap_test )
+{
+ run_binomial_heap_test<false, false>();
+ run_binomial_heap_test<false, true>();
+ run_binomial_heap_test<true, false>();
+ run_binomial_heap_test<true, true>();
+
+ RUN_EMPLACE_TEST(binomial_heap);
+}
+
+BOOST_AUTO_TEST_CASE( binomial_heap_compare_lookup_test )
+{
+ typedef boost::heap::binomial_heap<int,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
+
+BOOST_AUTO_TEST_CASE( binomial_heap_leak_test )
+{
+ typedef boost::heap::binomial_heap<boost::shared_ptr<int> > pri_queue;
+ run_leak_check_test<pri_queue>();
+}
diff --git a/src/boost/libs/heap/test/common_heap_tests.hpp b/src/boost/libs/heap/test/common_heap_tests.hpp
new file mode 100644
index 00000000..4454c2a8
--- /dev/null
+++ b/src/boost/libs/heap/test/common_heap_tests.hpp
@@ -0,0 +1,520 @@
+/*=============================================================================
+ 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
diff --git a/src/boost/libs/heap/test/d_ary_heap_test.cpp b/src/boost/libs/heap/test/d_ary_heap_test.cpp
new file mode 100644
index 00000000..c459f3f9
--- /dev/null
+++ b/src/boost/libs/heap/test/d_ary_heap_test.cpp
@@ -0,0 +1,135 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_HEAP_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include <algorithm>
+
+#include <boost/heap/d_ary_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+
+template <int D, bool stable>
+void run_d_ary_heap_test(void)
+{
+ typedef boost::heap::d_ary_heap<int, boost::heap::arity<D>,
+ boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+
+ run_concept_check<pri_queue>();
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+ run_reserve_heap_tests<pri_queue>();
+ run_merge_tests<pri_queue>();
+
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::d_ary_heap<q_tester, boost::heap::arity<D>,
+ boost::heap::stable<stable>
+ > stable_pri_queue;
+
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+
+#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+ cmpthings ord;
+ boost::heap::d_ary_heap<thing, boost::heap::arity<D>, boost::heap::compare<cmpthings>, boost::heap::stable<stable> > vpq(ord);
+ vpq.emplace(5, 6, 7);
+#endif
+}
+
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_test )
+{
+ run_d_ary_heap_test<2, false>();
+ run_d_ary_heap_test<3, false>();
+ run_d_ary_heap_test<4, false>();
+ run_d_ary_heap_test<5, false>();
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_stable_test )
+{
+ run_d_ary_heap_test<2, true>();
+ run_d_ary_heap_test<3, true>();
+ run_d_ary_heap_test<4, true>();
+ run_d_ary_heap_test<5, true>();
+}
+
+template <int D, bool stable>
+void run_d_ary_heap_mutable_test(void)
+{
+ typedef boost::heap::d_ary_heap<int, boost::heap::mutable_<true>,
+ boost::heap::arity<D>,
+ boost::heap::stable<stable>
+ > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+ run_reserve_heap_tests<pri_queue>();
+ run_mutable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::d_ary_heap<q_tester, boost::heap::mutable_<true>,
+ boost::heap::arity<D>,
+ boost::heap::stable<stable>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_mutable_test )
+{
+ run_d_ary_heap_mutable_test<2, false>();
+ run_d_ary_heap_mutable_test<3, false>();
+ run_d_ary_heap_mutable_test<4, false>();
+ run_d_ary_heap_mutable_test<5, false>();
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_mutable_stable_test )
+{
+ run_d_ary_heap_mutable_test<2, true>();
+ run_d_ary_heap_mutable_test<3, true>();
+ run_d_ary_heap_mutable_test<4, true>();
+ run_d_ary_heap_mutable_test<5, true>();
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_compare_lookup_test )
+{
+ typedef boost::heap::d_ary_heap<int, boost::heap::arity<2>,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
+
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_leak_test )
+{
+ typedef boost::heap::d_ary_heap<boost::shared_ptr<int>, boost::heap::arity<2> > pri_queue;
+ run_leak_check_test<pri_queue>();
+}
diff --git a/src/boost/libs/heap/test/fibonacci_heap_test.cpp b/src/boost/libs/heap/test/fibonacci_heap_test.cpp
new file mode 100644
index 00000000..4fbf0779
--- /dev/null
+++ b/src/boost/libs/heap/test/fibonacci_heap_test.cpp
@@ -0,0 +1,76 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/fibonacci_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+
+template <bool stable, bool constant_time_size>
+void run_fibonacci_heap_test(void)
+{
+ typedef boost::heap::fibonacci_heap<int, boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size>
+ > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_mutable_heap_tests<pri_queue>();
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::fibonacci_heap<q_tester, boost::heap::stable<stable>,
+ boost::heap::constant_time_size<constant_time_size>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( fibonacci_heap_test )
+{
+ run_fibonacci_heap_test<true, false>();
+ run_fibonacci_heap_test<true, true>();
+
+ run_fibonacci_heap_test<false, false>();
+ run_fibonacci_heap_test<false, true>();
+
+ RUN_EMPLACE_TEST(fibonacci_heap);
+}
+
+BOOST_AUTO_TEST_CASE( fibonacci_heap_compare_lookup_test )
+{
+ typedef boost::heap::fibonacci_heap<int,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
+
+
+BOOST_AUTO_TEST_CASE( fibonacci_heap_leak_test )
+{
+ typedef boost::heap::fibonacci_heap<boost::shared_ptr<int> > pri_queue;
+ run_leak_check_test<pri_queue>();
+}
diff --git a/src/boost/libs/heap/test/merge_heap_tests.hpp b/src/boost/libs/heap/test/merge_heap_tests.hpp
new file mode 100644
index 00000000..6d2a01ba
--- /dev/null
+++ b/src/boost/libs/heap/test/merge_heap_tests.hpp
@@ -0,0 +1,75 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
+#include "common_heap_tests.hpp"
+#include <boost/heap/heap_merge.hpp>
+
+#define GENERATE_TEST_DATA(INDEX) \
+ test_data data = make_test_data(test_size, 0, 1); \
+ random_shuffle(data.begin(), data.end()); \
+ \
+ test_data data_q (data.begin(), data.begin() + INDEX); \
+ test_data data_r (data.begin() + INDEX, data.end()); \
+ \
+ std::stable_sort(data.begin(), data.end());
+
+
+template <typename pri_queue>
+struct pri_queue_test_merge
+{
+ static void run(void)
+ {
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue q, r;
+ GENERATE_TEST_DATA(i);
+
+ fill_q(q, data_q);
+ fill_q(r, data_r);
+
+ q.merge(r);
+
+ BOOST_REQUIRE(r.empty());
+ check_q(q, data);
+ }
+ }
+};
+
+
+template <typename pri_queue1, typename pri_queue2>
+struct pri_queue_test_heap_merge
+{
+ static void run (void)
+ {
+ for (int i = 0; i != test_size; ++i) {
+ pri_queue1 q;
+ pri_queue2 r;
+ GENERATE_TEST_DATA(i);
+
+ fill_q(q, data_q);
+ fill_q(r, data_r);
+
+ boost::heap::heap_merge(q, r);
+
+ BOOST_REQUIRE(r.empty());
+ check_q(q, data);
+ }
+ }
+};
+
+
+
+template <typename pri_queue>
+void run_merge_tests(void)
+{
+ boost::conditional<pri_queue::is_mergable,
+ pri_queue_test_merge<pri_queue>,
+ dummy_run
+ >::type::run();
+
+ pri_queue_test_heap_merge<pri_queue, pri_queue>::run();
+}
diff --git a/src/boost/libs/heap/test/mutable_heap_test.cpp b/src/boost/libs/heap/test/mutable_heap_test.cpp
new file mode 100644
index 00000000..d1a4844f
--- /dev/null
+++ b/src/boost/libs/heap/test/mutable_heap_test.cpp
@@ -0,0 +1,142 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <boost/heap/d_ary_heap.hpp>
+#include <boost/heap/fibonacci_heap.hpp>
+#include <boost/heap/pairing_heap.hpp>
+#include <boost/heap/binomial_heap.hpp>
+#include <boost/heap/skew_heap.hpp>
+
+using namespace boost::heap;
+
+
+typedef fibonacci_heap<struct fwd_declared_struct_1>::handle_type handle_type_1;
+typedef d_ary_heap<struct fwd_declared_struct_2, arity<4>, mutable_<true> >::handle_type handle_type_2;
+typedef pairing_heap<struct fwd_declared_struct_3>::handle_type handle_type_3;
+typedef binomial_heap<struct fwd_declared_struct_4>::handle_type handle_type_4;
+typedef skew_heap<struct fwd_declared_struct_5, mutable_<true> >::handle_type handle_type_5;
+
+template <typename HeapType>
+void run_handle_as_member_test(void)
+{
+ typedef typename HeapType::value_type value_type;
+ HeapType heap;
+ value_type f(2);
+ typename value_type::handle_type handle = heap.push(f);
+ value_type & fInHeap = *handle;
+ fInHeap.handle = handle;
+}
+
+
+struct fibonacci_heap_data
+{
+ typedef fibonacci_heap<fibonacci_heap_data>::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ fibonacci_heap_data(int i):i(i) {}
+
+ bool operator<(fibonacci_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+BOOST_AUTO_TEST_CASE( fibonacci_heap_handle_as_member )
+{
+ run_handle_as_member_test<fibonacci_heap<fibonacci_heap_data> >();
+}
+
+struct d_heap_data
+{
+ typedef d_ary_heap<d_heap_data, arity<4>, mutable_<true> >::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ d_heap_data(int i):i(i) {}
+
+ bool operator<(d_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+
+BOOST_AUTO_TEST_CASE( d_heap_handle_as_member )
+{
+ run_handle_as_member_test<d_ary_heap<d_heap_data, arity<4>, mutable_<true> > >();
+}
+
+struct pairing_heap_data
+{
+ typedef pairing_heap<pairing_heap_data>::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ pairing_heap_data(int i):i(i) {}
+
+ bool operator<(pairing_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+
+BOOST_AUTO_TEST_CASE( pairing_heap_handle_as_member )
+{
+ run_handle_as_member_test<pairing_heap<pairing_heap_data> >();
+}
+
+
+struct binomial_heap_data
+{
+ typedef binomial_heap<binomial_heap_data>::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ binomial_heap_data(int i):i(i) {}
+
+ bool operator<(binomial_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+
+BOOST_AUTO_TEST_CASE( binomial_heap_handle_as_member )
+{
+ run_handle_as_member_test<binomial_heap<binomial_heap_data> >();
+}
+
+struct skew_heap_data
+{
+ typedef skew_heap<skew_heap_data, mutable_<true> >::handle_type handle_type;
+
+ handle_type handle;
+ int i;
+
+ skew_heap_data(int i):i(i) {}
+
+ bool operator<(skew_heap_data const & rhs) const
+ {
+ return i < rhs.i;
+ }
+};
+
+
+BOOST_AUTO_TEST_CASE( skew_heap_handle_as_member )
+{
+ run_handle_as_member_test<skew_heap<skew_heap_data, mutable_<true> > >();
+}
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>();
+}
diff --git a/src/boost/libs/heap/test/pairing_heap_tests.cpp b/src/boost/libs/heap/test/pairing_heap_tests.cpp
new file mode 100644
index 00000000..250339dc
--- /dev/null
+++ b/src/boost/libs/heap/test/pairing_heap_tests.cpp
@@ -0,0 +1,74 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/pairing_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable, bool constant_time_size>
+void run_pairing_heap_test(void)
+{
+ typedef boost::heap::pairing_heap<int, boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size> > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_mutable_heap_tests<pri_queue >();
+
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::pairing_heap<q_tester, boost::heap::stable<stable>,
+ boost::heap::constant_time_size<constant_time_size>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( pairing_heap_test )
+{
+ run_pairing_heap_test<false, false>();
+ run_pairing_heap_test<false, true>();
+ run_pairing_heap_test<true, false>();
+ run_pairing_heap_test<true, true>();
+
+ RUN_EMPLACE_TEST(pairing_heap);
+}
+
+BOOST_AUTO_TEST_CASE( pairing_heap_compare_lookup_test )
+{
+ typedef boost::heap::pairing_heap<int,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
+
+
+BOOST_AUTO_TEST_CASE( pairing_heap_leak_test )
+{
+ typedef boost::heap::pairing_heap<boost::shared_ptr<int> > pri_queue;
+ run_leak_check_test<pri_queue>();
+}
diff --git a/src/boost/libs/heap/test/priority_queue_test.cpp b/src/boost/libs/heap/test/priority_queue_test.cpp
new file mode 100644
index 00000000..95876b93
--- /dev/null
+++ b/src/boost/libs/heap/test/priority_queue_test.cpp
@@ -0,0 +1,49 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/priority_queue.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable>
+void run_common_priority_queue_tests(void)
+{
+ typedef boost::heap::priority_queue<int, boost::heap::stable<stable> > pri_queue;
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+
+ run_concept_check<pri_queue>();
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+ run_merge_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::priority_queue<q_tester, boost::heap::stable<stable> > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+BOOST_AUTO_TEST_CASE( std_pri_queue_test )
+{
+ run_common_priority_queue_tests<false>();
+ run_common_priority_queue_tests<true>();
+}
+
+BOOST_AUTO_TEST_CASE( std_pri_queue_leak_test )
+{
+ typedef boost::heap::priority_queue<boost::shared_ptr<int> > pri_queue;
+ run_leak_check_test<pri_queue>();
+}
diff --git a/src/boost/libs/heap/test/self_contained_header.cpp b/src/boost/libs/heap/test/self_contained_header.cpp
new file mode 100644
index 00000000..bc8a5d7b
--- /dev/null
+++ b/src/boost/libs/heap/test/self_contained_header.cpp
@@ -0,0 +1,22 @@
+/*
+ * Copyright Andrey Semashev 2018.
+ * Distributed under 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)
+ */
+/*!
+ * \file self_contained_header.cpp
+ * \author Andrey Semashev
+ * \date 28.10.2018
+ *
+ * \brief This file contains a test boilerplate for checking that every public header is self-contained and does not have any missing #includes.
+ */
+
+#define BOOST_HEAP_TEST_INCLUDE_HEADER() <boost/heap/BOOST_HEAP_TEST_HEADER>
+
+#include BOOST_HEAP_TEST_INCLUDE_HEADER()
+
+int main(int, char*[])
+{
+ return 0;
+}
diff --git a/src/boost/libs/heap/test/skew_heap_test.cpp b/src/boost/libs/heap/test/skew_heap_test.cpp
new file mode 100644
index 00000000..8d25dd4a
--- /dev/null
+++ b/src/boost/libs/heap/test/skew_heap_test.cpp
@@ -0,0 +1,120 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/skew_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable, bool constant_time_size, bool store_parent_pointer>
+void run_skew_heap_test(void)
+{
+ typedef boost::heap::skew_heap<int, boost::heap::stable<stable>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size>,
+ boost::heap::store_parent_pointer<store_parent_pointer>
+ > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ pri_queue_test_ordered_iterators<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::skew_heap<q_tester, boost::heap::stable<stable>,
+ boost::heap::constant_time_size<constant_time_size>,
+ boost::heap::store_parent_pointer<store_parent_pointer>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+template <bool stable, bool constant_time_size>
+void run_skew_heap_mutable_test(void)
+{
+ typedef boost::heap::skew_heap<int, boost::heap::stable<stable>, boost::heap::mutable_<true>,
+ boost::heap::compare<std::less<int> >,
+ boost::heap::allocator<std::allocator<int> >,
+ boost::heap::constant_time_size<constant_time_size>
+ > pri_queue;
+
+ BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+ BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+ run_common_heap_tests<pri_queue>();
+ run_iterator_heap_tests<pri_queue>();
+ run_copyable_heap_tests<pri_queue>();
+ run_moveable_heap_tests<pri_queue>();
+
+ run_merge_tests<pri_queue>();
+
+ run_mutable_heap_tests<pri_queue >();
+
+ run_ordered_iterator_tests<pri_queue>();
+
+ if (stable) {
+ typedef boost::heap::skew_heap<q_tester, boost::heap::stable<stable>, boost::heap::mutable_<true>,
+ boost::heap::constant_time_size<constant_time_size>
+ > stable_pri_queue;
+ run_stable_heap_tests<stable_pri_queue>();
+ }
+}
+
+
+BOOST_AUTO_TEST_CASE( skew_heap_test )
+{
+ run_skew_heap_test<false, false, true>();
+ run_skew_heap_test<false, true, true>();
+ run_skew_heap_test<true, false, true>();
+ run_skew_heap_test<true, true, true>();
+
+ run_skew_heap_test<false, false, false>();
+ run_skew_heap_test<false, true, false>();
+ run_skew_heap_test<true, false, false>();
+ run_skew_heap_test<true, true, false>();
+
+ RUN_EMPLACE_TEST(skew_heap);
+}
+
+BOOST_AUTO_TEST_CASE( skew_heap_mutable_test )
+{
+ run_skew_heap_mutable_test<false, false>();
+ run_skew_heap_mutable_test<false, true>();
+ run_skew_heap_mutable_test<true, false>();
+ run_skew_heap_mutable_test<true, true>();
+}
+
+BOOST_AUTO_TEST_CASE( skew_heap_compare_lookup_test )
+{
+ typedef boost::heap::skew_heap<int,
+ boost::heap::compare<less_with_T>,
+ boost::heap::allocator<std::allocator<int> > > pri_queue;
+ run_common_heap_tests<pri_queue>();
+}
+
+
+BOOST_AUTO_TEST_CASE( skew_heap_leak_test )
+{
+ typedef boost::heap::skew_heap<boost::shared_ptr<int> > pri_queue;
+ run_leak_check_test<pri_queue>();
+}
diff --git a/src/boost/libs/heap/test/stable_heap_tests.hpp b/src/boost/libs/heap/test/stable_heap_tests.hpp
new file mode 100644
index 00000000..0b4e7995
--- /dev/null
+++ b/src/boost/libs/heap/test/stable_heap_tests.hpp
@@ -0,0 +1,99 @@
+/*=============================================================================
+ 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)
+=============================================================================*/
+
+#include <boost/foreach.hpp>
+#include "common_heap_tests.hpp"
+
+struct q_tester
+{
+ q_tester(int i = 0, int j = 0):
+ value(i), id(j)
+ {}
+
+ bool operator< (q_tester const & rhs) const
+ {
+ return value < rhs.value;
+ }
+
+ bool operator> (q_tester const & rhs) const
+ {
+ return value > rhs.value;
+ }
+
+ bool operator== (q_tester const & rhs) const
+ {
+ return (value == rhs.value) && (id == rhs.id);
+ }
+
+ int value;
+ int id;
+};
+
+std::ostream& operator<< (std::ostream& out, q_tester const & t)
+{
+ out << "[" << t.value << " " << t.id << "]";
+ return out;
+}
+
+typedef std::vector<q_tester> stable_test_data;
+
+stable_test_data make_stable_test_data(int size, int same_count = 3,
+ int offset = 0, int strive = 1)
+{
+ stable_test_data ret;
+
+ for (int i = 0; i != size; ++i)
+ for (int j = 0; j != same_count; ++j)
+ ret.push_back(q_tester(i * strive + offset, j));
+ return ret;
+}
+
+struct compare_by_id
+{
+ bool operator()(q_tester const & lhs, q_tester const & rhs)
+ {
+ return lhs.id > rhs.id;
+ }
+};
+
+template <typename pri_queue>
+void pri_queue_stable_test_sequential_push(void)
+{
+ stable_test_data data = make_stable_test_data(test_size);
+
+ pri_queue q;
+ fill_q(q, data);
+ std::stable_sort(data.begin(), data.end(), compare_by_id());
+ std::stable_sort(data.begin(), data.end(), std::less<q_tester>());
+ check_q(q, data);
+}
+
+template <typename pri_queue>
+void pri_queue_stable_test_sequential_reverse_push(void)
+{
+ stable_test_data data = make_stable_test_data(test_size);
+ pri_queue q;
+ stable_test_data push_data(data);
+
+ std::stable_sort(push_data.begin(), push_data.end(), std::greater<q_tester>());
+
+ fill_q(q, push_data);
+
+ std::stable_sort(data.begin(), data.end(), compare_by_id());
+ std::stable_sort(data.begin(), data.end(), std::less<q_tester>());
+
+ check_q(q, data);
+}
+
+
+template <typename pri_queue>
+void run_stable_heap_tests(void)
+{
+ pri_queue_stable_test_sequential_push<pri_queue>();
+ pri_queue_stable_test_sequential_reverse_push<pri_queue>();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-20 10:31:41 +0000