Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

19 files changed, 2769 insertions, 0 deletions

diff --git a/src/boost/libs/heap/examples/interface.cpp b/src/boost/libs/heap/examples/interface.cpp
new file mode 100644
index 000000000..a3a24c7c9
--- /dev/null
+++ b/src/boost/libs/heap/examples/interface.cpp
@@ -0,0 +1,261 @@
+/*=============================================================================
+    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 <iostream>
+#include <iomanip>
+
+#include "../../../boost/heap/fibonacci_heap.hpp"
+
+using std::cout;
+using std::endl;
+using namespace boost::heap;
+
+//[ basic_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void basic_interface(void)
+{
+    PriorityQueue pq;
+
+    pq.push(2);
+    pq.push(3);
+    pq.push(1);
+
+    cout << "Priority Queue: popped elements" << endl;
+    cout << pq.top() << " "; // 3
+    pq.pop();
+    cout << pq.top() << " "; // 2
+    pq.pop();
+    cout << pq.top() << " "; // 1
+    pq.pop();
+    cout << endl;
+}
+//]
+
+//[ iterator_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void iterator_interface(void)
+{
+    PriorityQueue pq;
+
+    pq.push(2);
+    pq.push(3);
+    pq.push(1);
+
+    typename PriorityQueue::iterator begin = pq.begin();
+    typename PriorityQueue::iterator end = pq.end();
+
+    cout << "Priority Queue: iteration" << endl;
+    for (typename PriorityQueue::iterator it = begin; it != end; ++it)
+        cout << *it << " "; // 1, 2, 3 in unspecified order
+    cout << endl;
+}
+//]
+
+//[ ordered_iterator_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void ordered_iterator_interface(void)
+{
+    PriorityQueue pq;
+
+    pq.push(2);
+    pq.push(3);
+    pq.push(1);
+
+    typename PriorityQueue::ordered_iterator begin = pq.ordered_begin();
+    typename PriorityQueue::ordered_iterator end = pq.ordered_end();
+
+    cout << "Priority Queue: ordered iteration" << endl;
+    for (typename PriorityQueue::ordered_iterator it = begin; it != end; ++it)
+        cout << *it << " "; // 3, 2, 1 (i.e. 1, 2, 3 in heap order)
+    cout << endl;
+}
+//]
+
+
+//[ merge_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void merge_interface(void)
+{
+    PriorityQueue pq;
+
+    pq.push(3);
+    pq.push(5);
+    pq.push(1);
+
+    PriorityQueue pq2;
+
+    pq2.push(2);
+    pq2.push(4);
+    pq2.push(0);
+
+    pq.merge(pq2);
+
+    cout << "Priority Queue: merge" << endl;
+    cout << "first queue: ";
+    while (!pq.empty()) {
+        cout << pq.top() << " "; // 5 4 3 2 1 0
+        pq.pop();
+    }
+    cout << endl;
+
+    cout << "second queue: ";
+    while (!pq2.empty()) {
+        cout << pq2.top() << " "; // 4 2 0
+        pq2.pop();
+    }
+    cout << endl;
+}
+//]
+
+//[ heap_merge_algorithm
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void heap_merge_algorithm(void)
+{
+    PriorityQueue pq;
+
+    pq.push(3);
+    pq.push(5);
+    pq.push(1);
+
+    PriorityQueue pq2;
+
+    pq2.push(2);
+    pq2.push(4);
+    pq2.push(0);
+
+    boost::heap::heap_merge(pq, pq2);
+
+    cout << "Priority Queue: merge" << endl;
+    cout << "first queue: ";
+    while (!pq.empty()) {
+        cout << pq.top() << " "; // 5 4 3 2 1 0
+        pq.pop();
+    }
+    cout << endl;
+
+    cout << "second queue: ";
+    while (!pq2.empty()) {
+        cout << pq2.top() << " "; // 4 2 0
+        pq2.pop();
+    }
+    cout << endl;
+}
+//]
+
+//[ mutable_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void mutable_interface(void)
+{
+    PriorityQueue pq;
+    typedef typename PriorityQueue::handle_type handle_t;
+
+    handle_t t3 = pq.push(3);
+    handle_t t5 = pq.push(5);
+    handle_t t1 = pq.push(1);
+
+    pq.update(t3, 4);
+    pq.increase(t5, 7);
+    pq.decrease(t1, 0);
+
+    cout << "Priority Queue: update" << endl;
+    while (!pq.empty()) {
+        cout << pq.top() << " "; // 7, 4, 0
+        pq.pop();
+    }
+    cout << endl;
+}
+//]
+
+//[ mutable_fixup_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void mutable_fixup_interface(void)
+{
+    PriorityQueue pq;
+    typedef typename PriorityQueue::handle_type handle_t;
+
+    handle_t t3 = pq.push(3);
+    handle_t t5 = pq.push(5);
+    handle_t t1 = pq.push(1);
+
+    *t3 = 4;
+    pq.update(t3);
+
+    *t5 = 7;
+    pq.increase(t5);
+
+    *t1 = 0;
+    pq.decrease(t1);
+
+    cout << "Priority Queue: update with fixup" << endl;
+    while (!pq.empty()) {
+        cout << pq.top() << " "; // 7, 4, 0
+        pq.pop();
+    }
+    cout << endl;
+}
+//]
+
+//[ mutable_interface_handle_in_value
+struct heap_data
+{
+    fibonacci_heap<heap_data>::handle_type handle;
+    int payload;
+
+    heap_data(int i):
+        payload(i)
+    {}
+
+    bool operator<(heap_data const & rhs) const
+    {
+        return payload < rhs.payload;
+    }
+};
+
+void mutable_interface_handle_in_value(void)
+{
+    fibonacci_heap<heap_data> heap;
+    heap_data f(2);
+
+    fibonacci_heap<heap_data>::handle_type handle = heap.push(f);
+    (*handle).handle = handle; // store handle in node
+}
+//]
+
+
+int main(void)
+{
+    using boost::heap::fibonacci_heap;
+
+    cout << std::setw(2);
+
+    basic_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    iterator_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    ordered_iterator_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    merge_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    mutable_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    mutable_fixup_interface<fibonacci_heap<int> >();
+
+    mutable_interface_handle_in_value();
+}
diff --git a/src/boost/libs/heap/index.html b/src/boost/libs/heap/index.html
new file mode 100644
index 000000000..2717f9711
--- /dev/null
+++ b/src/boost/libs/heap/index.html
@@ -0,0 +1,13 @@
+<html>
+<head>
+<meta http-equiv="refresh" content="0; URL=../../doc/html/heap.html">
+</head>
+<body>
+Automatic redirection failed, please go to
+<a href="../../doc/html/heap.html">../../doc/html/heap.html</a> &nbsp;<hr>
+<p>&copy; Copyright Beman Dawes, 2001</p>
+<p>Distributed under the Boost Software License, Version 1.0. (See accompanying 
+file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or copy 
+at <a href="http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</p>
+</body>
+</html>
diff --git a/src/boost/libs/heap/meta/libraries.json b/src/boost/libs/heap/meta/libraries.json
new file mode 100644
index 000000000..dddbf838f
--- /dev/null
+++ b/src/boost/libs/heap/meta/libraries.json
@@ -0,0 +1,14 @@
+{
+    "key": "heap",
+    "name": "Heap",
+    "authors": [
+        "Tim Blechmann"
+    ],
+    "description": "Priority queue data structures.",
+    "category": [
+        "Data"
+    ],
+    "maintainers": [
+        "Tim Blechmann <tim -at- klingt.org>"
+    ]
+}
diff --git a/src/boost/libs/heap/test/Jamfile.v2 b/src/boost/libs/heap/test/Jamfile.v2
new file mode 100644
index 000000000..9f591b990
--- /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 000000000..05434e99e
--- /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 000000000..4454c2a88
--- /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 000000000..c459f3f99
--- /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 000000000..4fbf0779e
--- /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 000000000..6d2a01bab
--- /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 000000000..d1a4844f0
--- /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 000000000..3df1d30fb
--- /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 000000000..250339dc3
--- /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 000000000..95876b931
--- /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 000000000..bc8a5d7b7
--- /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 000000000..8d25dd4a4
--- /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 000000000..0b4e7995f
--- /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>();
+}
diff --git a/src/boost/libs/heap/tools/heap_benchmarks.hpp b/src/boost/libs/heap/tools/heap_benchmarks.hpp
new file mode 100644
index 000000000..08bc65791
--- /dev/null
+++ b/src/boost/libs/heap/tools/heap_benchmarks.hpp
@@ -0,0 +1,277 @@
+/*=============================================================================
+    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 <algorithm>
+#include <vector>
+
+#include <boost/foreach.hpp>
+#include "high_resolution_timer.hpp"
+
+#include <boost/heap/heap_merge.hpp>
+
+#if defined(__GNUC__) && (!defined __INTEL_COMPILER)
+#define no_inline __attribute__ ((noinline))
+#else
+#define no_inline
+#endif
+
+typedef std::vector<int> test_data;
+
+const int num_benchmarks = 1;
+
+inline test_data make_sequential_test_data(int size)
+{
+    test_data v(size);
+    for (int i = 0; i != size; ++i)
+        v[i] = i;
+    return v;
+}
+
+inline test_data make_test_data(int size)
+{
+    test_data v = make_sequential_test_data(size);
+    std::random_shuffle(v.begin(), v.end());
+    return v;
+}
+
+const int max_data = 20;
+
+test_data const & get_data(int index)
+{
+    static std::vector <test_data> data;
+    if (data.empty())
+        for (int i = 0; i != num_benchmarks; ++i)
+            data.push_back(make_test_data((1<<(max_data+1))+1024));
+
+    return data[index];
+}
+
+
+#define DEFINE_BENCHMARKS_SELECTOR(SUFFIX)  \
+struct make_##SUFFIX                        \
+{                                           \
+    template <typename heap>                \
+    struct rebind {                         \
+        typedef run_##SUFFIX<heap> type;    \
+    };                                      \
+};
+
+
+template <typename pri_queue>
+void fill_heap(pri_queue & q, int index, int size, int offset = 0)
+{
+    test_data const & data = get_data(index);
+
+    for (int i = 0; i != size + 1; ++i) {
+        q.push(data[i]);
+        int top = q.top();
+        q.pop();
+        q.push(top);
+    }
+}
+
+template <typename pri_queue,
+          typename handle_container
+         >
+void fill_heap_with_handles(pri_queue & q, handle_container & handles, int index, int size, int offset = 0)
+{
+    test_data const & data = get_data(index);
+
+    for (int i = 0; i != size + 1; ++i) {
+        handles[i] = q.push(data[i]);
+
+        if (i > 0) {
+            typename pri_queue::handle_type last = handles[i-1];
+            int val = *last;
+            q.erase(last);
+            handles[i-1] = q.push(val);
+        }
+    }
+}
+
+
+template <typename pri_queue>
+struct run_sequential_push
+{
+    run_sequential_push(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap(q, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        test_data const & data = get_data(index);
+
+        for (int i = 0; i != 16; ++i)
+            q.push(data[(1<<max_data) + i]);
+    }
+
+    pri_queue q;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_push)
+
+template <typename pri_queue>
+struct run_sequential_pop
+{
+    run_sequential_pop(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap(q, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        for (int i = 0; i != 16; ++i)
+            q.pop();
+    }
+
+    pri_queue q;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_pop)
+
+template <typename pri_queue>
+struct run_sequential_increase
+{
+    run_sequential_increase(int size):
+        size(size), handles(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap_with_handles(q, handles, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        test_data const & data = get_data(index);
+        for (int i = 0; i != 16; ++i)
+            q.increase(handles[i], data[i] + (1<<max_data));
+    }
+
+    pri_queue q;
+    int size;
+    std::vector<typename pri_queue::handle_type> handles;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_increase)
+
+template <typename pri_queue>
+struct run_sequential_decrease
+{
+    run_sequential_decrease(int size):
+        size(size), handles(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap_with_handles(q, handles, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        test_data const & data = get_data(index);
+        for (int i = 0; i != 16; ++i)
+            q.decrease(handles[i], data[i] + (1<<max_data));
+    }
+
+    pri_queue q;
+    int size;
+    std::vector<typename pri_queue::handle_type> handles;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_decrease)
+
+template <typename pri_queue>
+struct run_merge_and_clear
+{
+    run_merge_and_clear(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        r.clear();
+
+        fill_heap(q, index, size);
+        fill_heap(r, index, size, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        boost::heap::heap_merge(q, r);
+    }
+
+    pri_queue q, r;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(merge_and_clear)
+
+template <typename pri_queue>
+struct run_equivalence
+{
+    run_equivalence(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        r.clear();
+        s.clear();
+
+        fill_heap(q, index, size);
+        fill_heap(r, index, size, size);
+        fill_heap(s, index, size);
+    }
+
+    no_inline bool operator()(int index)
+    {
+        return (q == r) ^ (q == s);
+    }
+
+    pri_queue q, r, s;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(equivalence)
+
+
+template <typename benchmark>
+inline double run_benchmark(benchmark & b)
+{
+    boost::high_resolution_timer timer;
+    std::vector<double> results;
+
+    for (int i = 0; i != num_benchmarks; ++i)
+    {
+        b.prepare(i);
+        timer.restart();
+        b(i);
+        double t = timer.elapsed();
+        results.push_back(t);
+    }
+
+    return results.at(results.size()/2); // median
+}
diff --git a/src/boost/libs/heap/tools/high_resolution_timer.hpp b/src/boost/libs/heap/tools/high_resolution_timer.hpp
new file mode 100644
index 000000000..9893b2441
--- /dev/null
+++ b/src/boost/libs/heap/tools/high_resolution_timer.hpp
@@ -0,0 +1,208 @@
+/*=============================================================================
+    Copyright (c) 2005-2007 Hartmut Kaiser
+                  2007, 2009 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)
+=============================================================================*/
+#if !defined(BOOST_HIGH_RESOLUTION_TIMER_HPP)
+#define BOOST_HIGH_RESOLUTION_TIMER_HPP
+
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+
+#if _POSIX_C_SOURCE >= 199309L
+
+#include "time.h"
+
+#include <stdexcept>
+#include <limits>
+
+namespace boost {
+
+class high_resolution_timer
+{
+public:
+    high_resolution_timer()
+    {
+        restart();
+    }
+
+    void restart()
+    {
+        int status = clock_gettime(CLOCK_REALTIME, &start_time);
+
+        if (status == -1)
+            boost::throw_exception(std::runtime_error("Couldn't initialize start_time"));
+    }
+
+    double elapsed() const                  // return elapsed time in seconds
+    {
+        struct timespec now;
+
+        int status = clock_gettime(CLOCK_REALTIME, &now);
+
+        if (status == -1)
+            boost::throw_exception(std::runtime_error("Couldn't get current time"));
+
+        struct timespec diff;
+
+        double ret_sec = double(now.tv_sec - start_time.tv_sec);
+        double ret_nsec = double(now.tv_nsec - start_time.tv_nsec);
+
+        while (ret_nsec < 0)
+        {
+            ret_sec -= 1.0;
+            ret_nsec += 1e9;
+        }
+
+        double ret = ret_sec + ret_nsec / 1e9;
+
+        return ret;
+    }
+
+    double elapsed_max() const   // return estimated maximum value for elapsed()
+    {
+        return double((std::numeric_limits<double>::max)());
+    }
+
+    double elapsed_min() const            // return minimum value for elapsed()
+    {
+        return 0.0;
+    }
+
+private:
+    struct timespec start_time;
+};
+
+} // namespace boost
+
+#elif defined(__APPLE__)
+
+#import <mach/mach_time.h>
+
+
+namespace boost {
+
+class high_resolution_timer
+{
+public:
+    high_resolution_timer(void)
+    {
+        mach_timebase_info_data_t info;
+
+        kern_return_t err = mach_timebase_info(&info);
+        if (err)
+            throw std::runtime_error("cannot create mach timebase info");
+
+        conversion_factor = (double)info.numer/(double)info.denom;
+        restart();
+    }
+
+    void restart()
+    {
+        start = mach_absolute_time();
+    }
+
+    double elapsed() const                  // return elapsed time in seconds
+    {
+        uint64_t now = mach_absolute_time();
+        double duration = double(now - start) * conversion_factor;
+
+        return duration
+    }
+
+    double elapsed_max() const   // return estimated maximum value for elapsed()
+    {
+        return double((std::numeric_limits<double>::max)());
+    }
+
+    double elapsed_min() const            // return minimum value for elapsed()
+    {
+        return 0.0;
+    }
+
+private:
+    uint64_t start;
+    double conversion_factor;
+};
+
+} // namespace boost
+
+#elif defined(BOOST_WINDOWS)
+
+#include <stdexcept>
+#include <limits>
+#include <windows.h>
+
+namespace boost {
+
+///////////////////////////////////////////////////////////////////////////////
+//
+//  high_resolution_timer
+//      A timer object measures elapsed time.
+//      CAUTION: Windows only!
+//
+///////////////////////////////////////////////////////////////////////////////
+class high_resolution_timer
+{
+public:
+    high_resolution_timer()
+    {
+        start_time.QuadPart = 0;
+        frequency.QuadPart = 0;
+
+        if (!QueryPerformanceFrequency(&frequency))
+            boost::throw_exception(std::runtime_error("Couldn't acquire frequency"));
+
+        restart();
+    }
+
+    void restart()
+    {
+        if (!QueryPerformanceCounter(&start_time))
+            boost::throw_exception(std::runtime_error("Couldn't initialize start_time"));
+    }
+
+    double elapsed() const                  // return elapsed time in seconds
+    {
+        LARGE_INTEGER now;
+        if (!QueryPerformanceCounter(&now))
+            boost::throw_exception(std::runtime_error("Couldn't get current time"));
+
+        return double(now.QuadPart - start_time.QuadPart) / frequency.QuadPart;
+    }
+
+    double elapsed_max() const   // return estimated maximum value for elapsed()
+    {
+        return (double((std::numeric_limits<LONGLONG>::max)())
+            - double(start_time.QuadPart)) / double(frequency.QuadPart);
+    }
+
+    double elapsed_min() const            // return minimum value for elapsed()
+    {
+        return 1.0 / frequency.QuadPart;
+    }
+
+private:
+    LARGE_INTEGER start_time;
+    LARGE_INTEGER frequency;
+};
+
+} // namespace boost
+
+#else
+
+//  For other platforms, simply fall back to boost::timer
+#include <boost/timer.hpp>
+#include <boost/throw_exception.hpp>
+
+namespace boost {
+    typedef boost::timer high_resolution_timer;
+}
+
+#endif
+
+#endif  // !defined(BOOST_HIGH_RESOLUTION_TIMER_HPP)
+
diff --git a/src/boost/libs/heap/tools/throughput_benchmarks.cpp b/src/boost/libs/heap/tools/throughput_benchmarks.cpp
new file mode 100644
index 000000000..ea3f5b0d6
--- /dev/null
+++ b/src/boost/libs/heap/tools/throughput_benchmarks.cpp
@@ -0,0 +1,248 @@
+/*=============================================================================
+    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 <iostream>
+#include <iomanip>
+
+
+#include "../../../boost/heap/d_ary_heap.hpp"
+#include "../../../boost/heap/pairing_heap.hpp"
+#include "../../../boost/heap/fibonacci_heap.hpp"
+#include "../../../boost/heap/binomial_heap.hpp"
+#include "../../../boost/heap/skew_heap.hpp"
+
+#include "heap_benchmarks.hpp"
+
+using namespace std;
+
+template <typename benchmark_selector>
+void run_benchmarks_immutable(void)
+{
+    for (int i = 4; i != max_data; ++i) {
+        for (int j = 0; j != 8; ++j) {
+            int size = 1<<i;
+            if (j%4 == 1)
+                size += 1<<(i-3);
+            if (j%4 == 2)
+                size += 1<<(i-2);
+            if (j%4 == 3)
+                size += (1<<(i-3)) + (1<<(i-2));
+            if (j >= 4)
+                size += (1<<(i-1));
+
+            cout << size << "\t";
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::binomial_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::fibonacci_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::pairing_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::skew_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::skew_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+            cout << endl;
+        }
+    }
+}
+
+template <typename benchmark_selector>
+void run_benchmarks_mutable(void)
+{
+    for (int i = 4; i != max_data; ++i)
+    {
+        for (int j = 0; j != 8; ++j)
+        {
+            int size = 1<<i;
+            if (j%4 == 1)
+                size += 1<<(i-3);
+            if (j%4 == 2)
+                size += 1<<(i-2);
+            if (j%4 == 3)
+                size += (1<<(i-3)) + (1<<(i-2));
+            if (j >= 4)
+                size += (1<<(i-1));
+
+            cout << size << "\t";
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::binomial_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::fibonacci_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::pairing_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::skew_heap<long, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+            cout << endl;
+        }
+    }
+}
+
+int main()
+{
+    cout << fixed << setprecision(12);
+
+    cout << "sequential push" << endl;
+    run_benchmarks_immutable<make_sequential_push>();
+
+    cout << endl << "sequential pop" << endl;
+    run_benchmarks_immutable<make_sequential_pop>();
+
+    cout << endl << "sequential increase" << endl;
+    run_benchmarks_mutable<make_sequential_increase>();
+
+    cout << endl << "sequential decrease" << endl;
+    run_benchmarks_mutable<make_sequential_decrease>();
+
+    cout << endl << "merge_and_clear" << endl;
+    run_benchmarks_immutable<make_merge_and_clear>();
+
+    cout << endl << "equivalence" << endl;
+    run_benchmarks_immutable<make_equivalence>();
+}