From 1a78a62555be32868418fe52f8e330c9d0f95d5a Mon Sep 17 00:00:00 2001 From: Anas Nashif Date: Tue, 30 Oct 2012 12:57:26 -0700 Subject: Imported Upstream version 1.49.0 --- libs/heap/doc/Jamfile.v2 | 52 ++++ libs/heap/doc/heap.qbk | 422 +++++++++++++++++++++++++++++ libs/heap/examples/interface.cpp | 261 ++++++++++++++++++ libs/heap/index.html | 13 + libs/heap/test/Jamfile.v2 | 23 ++ libs/heap/test/binomial_heap_test.cpp | 48 ++++ libs/heap/test/common_heap_tests.hpp | 435 ++++++++++++++++++++++++++++++ libs/heap/test/d_ary_heap_test.cpp | 102 +++++++ libs/heap/test/fibonacci_heap_test.cpp | 51 ++++ libs/heap/test/merge_heap_tests.hpp | 67 +++++ libs/heap/test/mutable_heap_test.cpp | 134 +++++++++ libs/heap/test/mutable_heap_tests.hpp | 303 +++++++++++++++++++++ libs/heap/test/pairing_heap_tests.cpp | 49 ++++ libs/heap/test/priority_queue_test.cpp | 35 +++ libs/heap/test/skew_heap_test.cpp | 95 +++++++ libs/heap/test/stable_heap_tests.hpp | 91 +++++++ libs/heap/tools/heap_benchmarks.hpp | 269 ++++++++++++++++++ libs/heap/tools/high_resolution_timer.hpp | 208 ++++++++++++++ libs/heap/tools/throughput_benchmarks.cpp | 240 +++++++++++++++++ 19 files changed, 2898 insertions(+) create mode 100644 libs/heap/doc/Jamfile.v2 create mode 100644 libs/heap/doc/heap.qbk create mode 100644 libs/heap/examples/interface.cpp create mode 100644 libs/heap/index.html create mode 100644 libs/heap/test/Jamfile.v2 create mode 100644 libs/heap/test/binomial_heap_test.cpp create mode 100644 libs/heap/test/common_heap_tests.hpp create mode 100644 libs/heap/test/d_ary_heap_test.cpp create mode 100644 libs/heap/test/fibonacci_heap_test.cpp create mode 100644 libs/heap/test/merge_heap_tests.hpp create mode 100644 libs/heap/test/mutable_heap_test.cpp create mode 100644 libs/heap/test/mutable_heap_tests.hpp create mode 100644 libs/heap/test/pairing_heap_tests.cpp create mode 100644 libs/heap/test/priority_queue_test.cpp create mode 100644 libs/heap/test/skew_heap_test.cpp create mode 100644 libs/heap/test/stable_heap_tests.hpp create mode 100644 libs/heap/tools/heap_benchmarks.hpp create mode 100644 libs/heap/tools/high_resolution_timer.hpp create mode 100644 libs/heap/tools/throughput_benchmarks.cpp (limited to 'libs/heap') diff --git a/libs/heap/doc/Jamfile.v2 b/libs/heap/doc/Jamfile.v2 new file mode 100644 index 0000000000..c4b46465c8 --- /dev/null +++ b/libs/heap/doc/Jamfile.v2 @@ -0,0 +1,52 @@ +# 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 doxygen ; +import quickbook ; + +doxygen autodoc + : + [ glob ../../../boost/heap/*.hpp ] ../../../boost/heap/detail/mutable_heap.hpp + : + #EXTRACT_ALL=YES + "PREDEFINED=\"BOOST_DOXYGEN_INVOKED\" \\ + \"BOOST_DEDUCED_TYPENAME=typename\" \\ + \"BOOST_HAS_RVALUE_REFS\" \\ + " + HIDE_UNDOC_MEMBERS=YES + HIDE_UNDOC_CLASSES=YES + INLINE_INHERITED_MEMB=YES + EXTRACT_PRIVATE=NO + ENABLE_PREPROCESSING=YES + MACRO_EXPANSION=YES + EXPAND_ONLY_PREDEF=YES + SEARCH_INCLUDES=YES + INCLUDE_PATH=$(BOOST_ROOT) + EXAMPLE_PATH=$(BOOST_ROOT)/libs/heap/examples + BRIEF_MEMBER_DESC=YES + REPEAT_BRIEF=YES + ALWAYS_DETAILED_SEC=YES + MULTILINE_CPP_IS_BRIEF=YES + ; + +xml heap : heap.qbk : ; + +boostbook standalone + : heap + : html.stylesheet=boostbook.css + boost.root=../../../.. + boost.libraries=../../../libraries.htm + toc.max.depth=3 + toc.section.depth=1 + chunk.section.depth=1 + autodoc + pdf:boost.url.prefix=http://www.boost.org/doc/libs/release/libs/heap/doc/html + ; + +install css : [ glob $(BOOST_ROOT)/doc/src/*.css ] + : html ; +install images : [ glob $(BOOST_ROOT)/doc/src/images/*.png ] + : html/images ; +explicit css ; +explicit images ; diff --git a/libs/heap/doc/heap.qbk b/libs/heap/doc/heap.qbk new file mode 100644 index 0000000000..494f228300 --- /dev/null +++ b/libs/heap/doc/heap.qbk @@ -0,0 +1,422 @@ +[library Boost.Heap + [quickbook 1.4] + [authors [Blechmann, Tim]] + [copyright 2010-2011 Tim Blechmann] + [category algorithms] + [purpose + heap data structures + ] + [id heap] + [dirname heap] + [license + 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]) + ] +] + +[c++] + + +[/ Links ] + +[def _heap_ [^boost.heap]] + +[/ unspecified stuff ] +[def __unspecified_int__ /unspecified-int-type/] +[def __unspecified__ /unspecified/] +[def __unspecified_bool__ /unspecified-bool-type/] + +[section Introduction & Motivation] + +_heap_ is an implementation of priority queues. Priority queues are queue data structures, that order their elements by +a priority. The STL provides a single template class =std::priority_queue=, which only provides a limited functionality. +To overcome these limitations, _heap_ implements [link heap.data_structures data structures] with more functionality and +different performance characteristics. Especially, it deals with additional aspects: + +* *Mutability*: The priority of heap elements can be modified. +* *Iterators*: Heaps provide iterators to iterate all elements. +* *Mergable*: While all heaps can be merged, some can be merged efficiently. +* *Stability*: Heaps can be configured to be stable sorted. +* *Comparison*: Heaps can be compared for equivalence. + +[endsect] + +[section:concepts Concepts & Interface] + +[section:basic Basic Priority Queue Interface] + +Priority queues are queues of objects, that are ordered by their priority. They support the operations of adding nodes to +the data structure, accessing the top element (the element with the highest priority), and removing the top element. + +[note _heap_ implements priority queues as max-heaps to be consistent with the STL heap functions. This is in contrast to +the typical textbook design, which uses min-heaps.] + +[h5 Synopsis] + + template + class priority_queue + { + // types + typedef T value_type; + typedef ``/unspecified/`` size_type; + typedef ``/unspecified/`` difference_type; + + typedef ``/unspecified/`` allocator_type; + typedef ``/unspecified/`` value_compare; + + typedef ``/unspecified/`` reference; + typedef ``/unspecified/`` const_reference; + typedef ``/unspecified/`` pointer; + typedef ``/unspecified/`` const_pointer; + + // construct/copy/destruct + explicit priority_queue(value_compare const & = value_compare()); + priority_queue(priority_queue const &); + priority_queue& operator=(priority_queue const &); + priority_queue(priority_queue &&); // move semantics (C++11 only) + priority_queue& operator=(priority_queue &&); // move semantics (C++11 only) + + // public member functions + ``/unspecified/`` push(const_reference); // push new element to heap + template void emplace(Args &&...); // push new element to heap, C++11 only + const_reference top() const; // return top element + void pop(); // remove top element + void clear(); // clear heap + size_type size() const; // number of elements + bool empty() const; // priority queue is empty + allocator_type get_allocator(void) const; // return allocator + size_type max_size(void) const; // maximal possible size + void reserve(size_type); // reserve space, only available if (has_reserve == true) + + // heap equivalence + template bool operator==(HeapType const &) const; + template bool operator!=(HeapType const &) const; + + // heap comparison + template bool operator<(HeapType const &) const; + template bool operator>(HeapType const &) const; + template bool operator>=(HeapType const &) const; + template bool operator<=(HeapType const &) const; + + // public data members + static const bool constant_time_size; // size() has constant complexity + static const bool has_ordered_iterators; // priority queue has ``[link heap.concepts.iterators ordered iterators]`` + static const bool is_mergable; // priority queue is efficiently ``[link heap.concepts.merge mergable]`` + static const bool is_stable; // priority queue has a ``[link heap.concepts.stability stable heap order]`` + static const bool has_reserve; // priority queue has a reserve() member + }; + +[h5 Example] + +[import ../examples/interface.cpp] +[basic_interface] + +[endsect] + + +[section:iterators Priority Queue Iterators] + +[h5 Synopsis] + class iteratable_heap_interface + { + public: + // types + typedef ``/unspecified/`` iterator; + typedef ``/unspecified/`` const_iterator; + typedef ``/unspecified/`` ordered_iterator; + + // public member functions + iterator begin(void) const; + iterator end(void) const; + ordered_iterator ordered_begin(void) const; + ordered_iterator ordered_end(void) const; + }; + +Priority queues provide iterators, that can be used to traverse their elements. All heap iterators are const_iterators, that means +they cannot be used to modify the values, because changing the value of a heap node may corrupt the heap order. Details about +modifying heap nodes are described in the section about the [link heap.concepts.mutability mutability interface]. + +Iterators do not visit heap elements in any specific order. Unless otherwise noted, all non-const heap member functions invalidate +iterators, while all const member functions preserve the iterator validity. + +[note Some implementations require iterators, that contain a set of elements, that are *discovered*, but not *visited*. Therefore +copying iterators can be inefficient and should be avoided.] + +[h5 Example] +[iterator_interface] + +[section:ordered_iterators Ordered Iterators] + +Except for [classref boost::heap::priority_queue] all _heap_ data structures support ordered iterators, which visit all elements +of the heap in heap-order. The implementation of these [^ordered_iterator]s requires some internal bookkeeping, so iterating the a +heap in heap order has an amortized complexity of O(N*log(N)). + +[h5 Example] +[ordered_iterator_interface] + +[endsect] + +[endsect] + +[section:comparing Comparing Priority Queues & Equivalence] + +The data structures of _heap_ can be compared with standard comparison operators. The comparison is performed by comparing two +heaps element by element using =value_compare=. + +[note Depending on the heap type, this operation can be rather expensive, because both data structures need to be traversed in +heap order. On heaps without ordered iterators, the heap needs to be copied internally. The typical complexity is O(n log(n)).] + +[endsect] + + +[section:merge Merging Priority Queues] + + +[h3 Mergable Priority Queues] + +[h5 Synopsis] + class mergable_heap_interface + { + public: + // public member functions + void merge(mergable_heap_interface &); + }; + +_heap_ has a concept of a Mergable Priority Queue. A mergable priority queue can efficiently be merged with a different instance +of the same type. + +[h5 Example] +[merge_interface] + + +[h3 Heap Merge Algorithms] + +_heap_ provides a =heap_merge()= algorithm that is can be used to merge different kinds of heaps. Using this algorithm, all _heap_ +data structures can be merged, although some cannot be merged efficiently. + +[h5 Example] +[heap_merge_algorithm] + +[endsect] + +[section:mutability Mutability] + +Some priority queues of _heap_ are mutable, that means the priority of their elements can be changed. To achieve mutability, +_heap_ introduces the concept of *handles*, which can be used to access the internal nodes of the priority queue in order to +change its value and to restore the heap order. + +[h5 Synopsis] + class mutable_heap_interface + { + public: + typedef ``/unspecified/`` iterator; + struct handle_type + { + value_type & operator*() const; + }; + + static handle_type s_iterator_to_handle(iterator const &); + + // priority queue interface + handle_type push(T const & v); + + // update element via assignment and fix heap + void update(handle_type const & handle, value_type const & v); + void increase(handle_type const & handle, value_type const & v); + void decrease(handle_type const & handle, value_type const & v); + + // fix heap after element has been changed via the handle + void update(handle_type const & handle); + void increase(handle_type const & handle); + void decrease(handle_type const & handle); + }; + +[warning Incorrect use of =increase= or =decrease= may corrupt the priority queue data structure. If unsure use =update= can be +used at the cost of efficiency.] + +[h5 Example] +[mutable_interface] + +Note that handles can be stored inside the =value_type=: + +[mutable_interface_handle_in_value] + +[h3 The Fixup Interface] + +There are two different APIs to support mutability. The first family of functions provides update functionality by changing +the current element by assigning a new value. The second family of functions can be used to fix the heap data structure after +an element has been changed directly via a handle. While this provides the user with a means to modify the priority of queue +elements without the need to change their non-priority part, this needs to be handled with care. The heap needs to be fixed up +immediately after the priority of the element has been changed. + + +Beside an =update= function, two additional functions =increase= and =decrease= are provided, that are generally more efficient +than the generic =update= function. However the user has do ensure, that the priority of an element is changed to the right +direction. + +[h5 Example] + +[mutable_fixup_interface] + +Iterators can be coverted to handles using the static member function =s_handle_from_iterator=. However most implementations of +=update= invalidate all iterators. The most notable exception is the [classref boost::heap::fibonacci_heap fibonacci heap], +providing a lazy update function, that just invalidates the iterators, that are related to this handle. + +[warning After changing the priority via a handle, the heap needs to be fixed by calling one of the update functions. Otherwise the +priority queue structure may be corrupted!] + +[endsect] + +[section:stability Stability] + +A priority queue is `stable', if elements with the same priority are popped from the heap, in the same order as +they are inserted. The data structures provided by _heap_, can be configured to be stable at compile time using the +[classref boost::heap::stable] policy. Two notions of stability are supported. If a heap is configured with *no stability*, +the order of nodes of the same priority is undefined, if it is configured as *stable*, nodes of the same priority are ordered by +their insertion time. + +Stability is achieved by associating an integer version count with each value in order to distinguish values with the same node. +The type of this version count defaults to =boost::uintmax_t=, which is at least 64bit on most systems. However it can be +configured to use a different type using the [classref boost::heap::stability_counter_type] template argument. + +[warning The stability counter is prone to integer overflows. If an overflow occurs during a =push()= call, the operation + will fail and an exception is thrown. Later =push()= call will succeed, but the stable heap order will be compromised. However an + integer overflow at 64bit is very unlikely: if an application would issue one =push()= operation per microsecond, the value will + overflow in more than 500000 years.] + +[endsect] + + +[endsect] + +[section:data_structures Data Structures] +_heap_ provides the following data structures: + +[variablelist + [[[classref boost::heap::priority_queue]] + [ + The [classref boost::heap::priority_queue priority_queue] class is a wrapper to the stl heap functions. It implements + a heap as container adaptor ontop of a =std::vector= and is immutable. + ] + ] + + [[[classref boost::heap::d_ary_heap]] + [ + [@http://en.wikipedia.org/wiki/D-ary_heap D-ary heaps] are a generalization of binary heap with each non-leaf node + having N children. For a low arity, the height of the heap is larger, but the number of comparisons to find the largest + child node is bigger. D-ary heaps are implemented as container adaptors based on a =std::vector=. + + The data structure can be configured as mutable. This is achieved by storing the values inside a std::list. + ] + ] + + [[[classref boost::heap::binomial_heap]] + [ + [@http://en.wikipedia.org/wiki/Binomial_heap Binomial heaps] are node-base heaps, that are implemented as a set of + binomial trees of piecewise different order. The most important heap operations have a worst-case complexity of O(log n). + In contrast to d-ary heaps, binomial heaps can also be merged in O(log n). + ] + ] + + [[[classref boost::heap::fibonacci_heap]] + [ + [@http://en.wikipedia.org/wiki/Fibonacci_heap Fibonacci heaps] are node-base heaps, that are implemented as a forest of + heap-ordered trees. They provide better amortized performance than binomial heaps. Except =pop()= and =erase()=, the most + important heap operations have constant amortized complexity. + ] + ] + + [[[classref boost::heap::pairing_heap]] + [ + [@http://en.wikipedia.org/wiki/Pairing_heap Pairing heaps] are self-adjusting node-based heaps. Although design and + implementation are rather simple, the complexity analysis is yet unsolved. For details, consult: + + Pettie, Seth (2005), "Towards a final analysis of pairing heaps", Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174–183 + ] + ] + + [[[classref boost::heap::skew_heap]] + [ + [@http://en.wikipedia.org/wiki/Skew_heap Skew heaps] are self-adjusting node-based heaps. Although there are no + constraints for the tree structure, all heap operations can be performed in O(log n). + ] + ] +] + +[table Comparison of amortized complexity + [[] [[^top()]] [[^push()]] [[^pop()]] [[^update()]] [[^increase()]] [[^decrease()]] [[^erase()]] [[^merge_and_clear()]]] + [[[classref boost::heap::priority_queue]] [[^O(1)]] [O(log(N))] [O(log(N))] [n/a] [n/a] [n/a] [n/a] [O((N+M)*log(N+M))]] + [[[classref boost::heap::d_ary_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O((N+M)*log(N+M))]] + [[[classref boost::heap::binomial_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N+M))]] + [[[classref boost::heap::fibonacci_heap]] [[^O(1)]] [O(1)] [O(log(N))] [O(log(N)) + [footnote The fibonacci a [^update_lazy()] method, which has O(log(N)) amortized complexity as well, but does not try to consolidate the internal forest] + ] [O(1)] [O(log(N))] [O(log(N))] [O(1)]] + + [[[classref boost::heap::pairing_heap]] [[^O(1)]] [O(2**2*log(log(N)))] [O(log(N))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))]] + [[[classref boost::heap::skew_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N+M))]] +] + + + +[section Data Structure Configuration] + +The data structures can be configured with [@boost:/libs/parameter/doc/html/index.html Boost.Parameter]-style templates. + +[variablelist + [[[classref boost::heap::compare]] + [Predicate for defining the heap order, optional + (defaults to =boost::heap::compare >=)] + ] + [[[classref boost::heap::allocator]] + [Allocator for internal memory management, optional + (defaults to =boost::heap::allocator >=)] + ] + [[[classref boost::heap::stable]] + [Configures the heap to use a [link heap.concepts.stability stable heap order], optional (defaults to =boost::heap::stable=). + ] + ] + [[[classref boost::heap::mutable_]] + [Configures the heap to be mutable. [classref boost::heap::d_ary_heap] and [classref boost::heap::skew_heap] have to be configured + with this policy to enable the [link heap.concepts.mutability mutability interface]. + ] + ] + [[[classref boost::heap::stability_counter_type]] + [Configures the integer type used for the stability counter, optional (defaults to =boost::heap::stability_counter_type=). + For more details, consult the [link heap.concepts.stability Stability] section. + ] + ] + [[[classref boost::heap::constant_time_size]] + [Specifies, whether =size()= should have linear or constant complexity. This argument is only available for node-based + heap data structures and if available, it is optional (defaults to =boost::heap::constant_time_size=)] + ] + + [[[classref boost::heap::arity]] + [Specifies the arity of a d-ary heap. For details, please consult the class reference of [classref boost::heap::d_ary_heap]] + ] + + [[[classref boost::heap::store_parent_pointer]] + [Store the parent pointer in the heap nodes. This policy is only available in the [classref boost::heap::skew_heap]. + ] + ] +] + +[endsect] + +[endsect] + + +[xinclude autodoc.xml] + + +[section Acknowledgements] + +[variablelist + [[Google Inc.] + [For sponsoring the development of this library during the Summer of Code 2010] + ] + [[Hartmut Kaiser] + [For mentoring the Summer of Code project] + ] +] +[endsect] \ No newline at end of file diff --git a/libs/heap/examples/interface.cpp b/libs/heap/examples/interface.cpp new file mode 100644 index 0000000000..f46a20d498 --- /dev/null +++ b/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 +#include + +#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 +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 +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 +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 +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 +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 +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 +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::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; + heap_data f(2); + + fibonacci_heap::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 >(); + cout << endl; + + iterator_interface >(); + cout << endl; + + ordered_iterator_interface >(); + cout << endl; + + merge_interface >(); + cout << endl; + + mutable_interface >(); + cout << endl; + + mutable_fixup_interface >(); + + mutable_interface_handle_in_value(); +} \ No newline at end of file diff --git a/libs/heap/index.html b/libs/heap/index.html new file mode 100644 index 0000000000..2717f97112 --- /dev/null +++ b/libs/heap/index.html @@ -0,0 +1,13 @@ + + + + + +Automatic redirection failed, please go to +../../doc/html/heap.html  
+

© Copyright Beman Dawes, 2001

+

Distributed under the Boost Software License, Version 1.0. (See accompanying +file LICENSE_1_0.txt or copy +at www.boost.org/LICENSE_1_0.txt)

+ + diff --git a/libs/heap/test/Jamfile.v2 b/libs/heap/test/Jamfile.v2 new file mode 100644 index 0000000000..856ad5c919 --- /dev/null +++ b/libs/heap/test/Jamfile.v2 @@ -0,0 +1,23 @@ +# (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 ; + +rule test_all +{ + local all_rules = ; + + for local fileb in [ glob *.cpp ] + { + all_rules += [ run $(fileb) ../../test/build//boost_unit_test_framework/static + : # additional args + : # test-files + : /boost/test//boost_unit_test_framework # requirements + ] ; + } + + return $(all_rules) ; +} + +test-suite heap : [ test_all r ] : multi ; diff --git a/libs/heap/test/binomial_heap_test.cpp b/libs/heap/test/binomial_heap_test.cpp new file mode 100644 index 0000000000..50c0e17009 --- /dev/null +++ b/libs/heap/test/binomial_heap_test.cpp @@ -0,0 +1,48 @@ +#define BOOST_TEST_MAIN +#include + +#include + +#include + +#include "common_heap_tests.hpp" +#include "stable_heap_tests.hpp" +#include "mutable_heap_tests.hpp" +#include "merge_heap_tests.hpp" + +template +void run_binomial_heap_test(void) +{ + typedef boost::heap::binomial_heap, + boost::heap::compare >, + boost::heap::allocator >, + boost::heap::constant_time_size > pri_queue; + + BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue)); + BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue)); + + run_common_heap_tests(); + run_iterator_heap_tests(); + run_copyable_heap_tests(); + run_moveable_heap_tests(); + + run_merge_tests(); + + run_mutable_heap_tests(); + run_ordered_iterator_tests(); + + if (stable) { + typedef boost::heap::binomial_heap, + boost::heap::constant_time_size > stable_pri_queue; + + run_stable_heap_tests(); + } +} + +BOOST_AUTO_TEST_CASE( binomial_heap_test ) +{ + run_binomial_heap_test(); + run_binomial_heap_test(); + run_binomial_heap_test(); + run_binomial_heap_test(); +} diff --git a/libs/heap/test/common_heap_tests.hpp b/libs/heap/test/common_heap_tests.hpp new file mode 100644 index 0000000000..191ab7f343 --- /dev/null +++ b/libs/heap/test/common_heap_tests.hpp @@ -0,0 +1,435 @@ +#ifndef COMMON_HEAP_TESTS_HPP_INCLUDED +#define COMMON_HEAP_TESTS_HPP_INCLUDED + +#include +#include + +#include +#include + +#include + + +typedef boost::default_constructible_archetype< + boost::less_than_comparable_archetype< + boost::copy_constructible_archetype< + boost::assignable_archetype< + > > > > test_value_type; + + +typedef std::vector test_data; +const int test_size = 64;//128; + +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 +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 +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_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES) +template +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 +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 +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 +void pri_queue_test_emplace(void) +{ +#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_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 +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); + std::random_shuffle(shuffled.begin(), shuffled.end()); + + fill_q(q, shuffled); + + check_q(q, data); + } +} + +template +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 +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 +void pri_queue_test_moveconstructor(void) +{ +#ifdef BOOST_HAS_RVALUE_REFS + 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 +void pri_queue_test_move_assignment(void) +{ +#ifdef BOOST_HAS_RVALUE_REFS + 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 +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); + std::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 +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); + std::random_shuffle(shuffled.begin(), shuffled.end()); + pri_queue q; + BOOST_REQUIRE(q.begin() == q.end()); + fill_q(q, shuffled); + + for (unsigned long i = 0; i != data.size(); ++i) + BOOST_REQUIRE(std::find(q.begin(), q.end(), data[i]) != q.end()); + + for (unsigned long i = 0; i != data.size(); ++i) + BOOST_REQUIRE(std::find(q.begin(), q.end(), data[i] + 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 i = 0; i != data.size(); ++i) { + BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - i)); + q.pop(); + } + } +} + +template +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); + std::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 i = 0; i != data.size(); ++i) + BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[i]) != q.ordered_end()); + + for (unsigned long i = 0; i != data.size(); ++i) + BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[i] + data.size()) == q.ordered_end()); + + for (unsigned long i = 0; i != data.size(); ++i) { + BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - i)); + q.pop(); + } + } +} + + +template +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 +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 +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 +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 +void run_concept_check(void) +{ + BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue)); +} + +template +void run_common_heap_tests(void) +{ + pri_queue_test_sequential_push(); + pri_queue_test_sequential_reverse_push(); + pri_queue_test_random_push(); + pri_queue_test_equality(); + pri_queue_test_inequality(); + pri_queue_test_less(); + pri_queue_test_clear(); + + pri_queue_test_emplace(); +} + +template +void run_iterator_heap_tests(void) +{ + pri_queue_test_iterators(); +} + + +template +void run_copyable_heap_tests(void) +{ + pri_queue_test_copyconstructor (); + pri_queue_test_assignment(); + pri_queue_test_swap(); +} + + +template +void run_moveable_heap_tests(void) +{ + pri_queue_test_moveconstructor (); + pri_queue_test_move_assignment (); +} + + +template +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); +} + +#endif // COMMON_HEAP_TESTS_HPP_INCLUDED diff --git a/libs/heap/test/d_ary_heap_test.cpp b/libs/heap/test/d_ary_heap_test.cpp new file mode 100644 index 0000000000..18a4248888 --- /dev/null +++ b/libs/heap/test/d_ary_heap_test.cpp @@ -0,0 +1,102 @@ +#define BOOST_TEST_MAIN +#include + +#include + +#include + +#include "common_heap_tests.hpp" +#include "stable_heap_tests.hpp" +#include "mutable_heap_tests.hpp" +#include "merge_heap_tests.hpp" + + +template +void run_d_ary_heap_test(void) +{ + typedef boost::heap::d_ary_heap, + boost::heap::stable, + boost::heap::compare >, + boost::heap::allocator > > pri_queue; + + BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue)); + + run_concept_check(); + run_common_heap_tests(); + run_iterator_heap_tests(); + run_copyable_heap_tests(); + run_moveable_heap_tests(); + run_reserve_heap_tests(); + run_merge_tests(); + + run_ordered_iterator_tests(); + + if (stable) { + typedef boost::heap::d_ary_heap, + boost::heap::stable + > stable_pri_queue; + + run_stable_heap_tests(); + } +} + + +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 +void run_d_ary_heap_mutable_test(void) +{ + typedef boost::heap::d_ary_heap, + boost::heap::arity, + boost::heap::stable + > pri_queue; + + BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue)); + + run_common_heap_tests(); + run_moveable_heap_tests(); + run_reserve_heap_tests(); + run_mutable_heap_tests(); + + run_merge_tests(); + + run_ordered_iterator_tests(); + + if (stable) { + typedef boost::heap::d_ary_heap, + boost::heap::arity, + boost::heap::stable + > stable_pri_queue; + run_stable_heap_tests(); + } +} + +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>(); +} diff --git a/libs/heap/test/fibonacci_heap_test.cpp b/libs/heap/test/fibonacci_heap_test.cpp new file mode 100644 index 0000000000..7429a24a49 --- /dev/null +++ b/libs/heap/test/fibonacci_heap_test.cpp @@ -0,0 +1,51 @@ +#define BOOST_TEST_MAIN +#include + +#include + +#include + +#include "common_heap_tests.hpp" +#include "stable_heap_tests.hpp" +#include "mutable_heap_tests.hpp" +#include "merge_heap_tests.hpp" + + +template +void run_fibonacci_heap_test(void) +{ + typedef boost::heap::fibonacci_heap, + boost::heap::compare >, + boost::heap::allocator >, + boost::heap::constant_time_size + > pri_queue; + + BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue)); + BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue)); + + run_common_heap_tests(); + run_iterator_heap_tests(); + run_copyable_heap_tests(); + run_moveable_heap_tests(); + + run_merge_tests(); + + run_mutable_heap_tests(); + run_ordered_iterator_tests(); + + if (stable) { + typedef boost::heap::fibonacci_heap, + boost::heap::constant_time_size + > stable_pri_queue; + run_stable_heap_tests(); + } +} + +BOOST_AUTO_TEST_CASE( fibonacci_heap_test ) +{ + run_fibonacci_heap_test(); + run_fibonacci_heap_test(); + + run_fibonacci_heap_test(); + run_fibonacci_heap_test(); +} diff --git a/libs/heap/test/merge_heap_tests.hpp b/libs/heap/test/merge_heap_tests.hpp new file mode 100644 index 0000000000..c7b9f99834 --- /dev/null +++ b/libs/heap/test/merge_heap_tests.hpp @@ -0,0 +1,67 @@ +#include "common_heap_tests.hpp" +#include + +#define GENERATE_TEST_DATA(INDEX) \ + test_data data = make_test_data(test_size, 0, 1); \ + std::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 +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 +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 +void run_merge_tests(void) +{ + boost::mpl::if_c, + dummy_run + >::type::run(); + + pri_queue_test_heap_merge::run(); +} diff --git a/libs/heap/test/mutable_heap_test.cpp b/libs/heap/test/mutable_heap_test.cpp new file mode 100644 index 0000000000..b7827fc7c8 --- /dev/null +++ b/libs/heap/test/mutable_heap_test.cpp @@ -0,0 +1,134 @@ +#define BOOST_TEST_MAIN +#include + +#include +#include +#include +#include +#include + +using namespace boost::heap; + + +typedef fibonacci_heap::handle_type handle_type_1; +typedef d_ary_heap, mutable_ >::handle_type handle_type_2; +typedef pairing_heap::handle_type handle_type_3; +typedef binomial_heap::handle_type handle_type_4; +typedef skew_heap >::handle_type handle_type_5; + +template +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::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 >(); +} + +struct d_heap_data +{ + typedef d_ary_heap, mutable_ >::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, mutable_ > >(); +} + +struct pairing_heap_data +{ + typedef pairing_heap::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 >(); +} + + +struct binomial_heap_data +{ + typedef binomial_heap::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 >(); +} + +struct skew_heap_data +{ + typedef skew_heap >::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 > >(); +} diff --git a/libs/heap/test/mutable_heap_tests.hpp b/libs/heap/test/mutable_heap_tests.hpp new file mode 100644 index 0000000000..6cee60d4a9 --- /dev/null +++ b/libs/heap/test/mutable_heap_tests.hpp @@ -0,0 +1,303 @@ +// random uses boost.fusion, which clashes with boost.test +//#define USE_BOOST_RANDOM + +#ifdef USE_BOOST_RANDOM +#include +#else +#include +#endif + +#include "common_heap_tests.hpp" + + +#define PUSH_WITH_HANDLES(HANDLES, Q, DATA) \ + std::vector HANDLES; \ + \ + for (unsigned int k = 0; k != data.size(); ++k) \ + HANDLES.push_back(Q.push(DATA[k])); + + + +template +void pri_queue_test_update_decrease(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + *handles[i] = -1; + data[i] = -1; + q.update(handles[i]); + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + +template +void pri_queue_test_update_decrease_function(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + data[i] = -1; + q.update(handles[i], -1); + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + +template +void pri_queue_test_update_function_identity(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + q.update(handles[i], data[i]); + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + +template +void pri_queue_test_update_shuffled(void) +{ + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + test_data shuffled (data); + std::random_shuffle(shuffled.begin(), shuffled.end()); + + for (int i = 0; i != test_size; ++i) + q.update(handles[i], shuffled[i]); + + check_q(q, data); +} + + +template +void pri_queue_test_update_increase(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + data[i] = data.back()+1; + *handles[i] = data[i]; + q.update(handles[i]); + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + +template +void pri_queue_test_update_increase_function(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + data[i] = data.back()+1; + q.update(handles[i], data[i]); + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + +template +void pri_queue_test_decrease(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + *handles[i] = -1; + data[i] = -1; + q.decrease(handles[i]); + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + +template +void pri_queue_test_decrease_function(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + data[i] = -1; + q.decrease(handles[i], -1); + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + +template +void pri_queue_test_decrease_function_identity(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + q.decrease(handles[i], data[i]); + + check_q(q, data); + } +} + + +template +void pri_queue_test_increase(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + data[i] = data.back()+1; + *handles[i] = data[i]; + q.increase(handles[i]); + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + +template +void pri_queue_test_increase_function(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + data[i] = data.back()+1; + q.increase(handles[i], data[i]); + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + +template +void pri_queue_test_increase_function_identity(void) +{ + for (int i = 0; i != test_size; ++i) { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + q.increase(handles[i], data[i]); + + check_q(q, data); + } +} + +template +void pri_queue_test_erase(void) +{ +#ifdef USE_BOOST_RANDOM + boost::mt19937 rng; +#endif + + for (int i = 0; i != test_size; ++i) + { + pri_queue q; + test_data data = make_test_data(test_size); + PUSH_WITH_HANDLES(handles, q, data); + + for (int j = 0; j != i; ++j) + { +#ifdef USE_BOOST_RANDOM + boost::uniform_int<> range(0, data.size() - 1); + boost::variate_generator > gen(rng, range); + + int index = gen(); +#else + int index = rand() % (data.size() - 1); +#endif + q.erase(handles[index]); + handles.erase(handles.begin() + index); + data.erase(data.begin() + index); + } + + std::sort(data.begin(), data.end()); + check_q(q, data); + } +} + + +template +void run_mutable_heap_update_tests(void) +{ + pri_queue_test_update_increase(); + pri_queue_test_update_decrease(); + + pri_queue_test_update_shuffled(); +} + +template +void run_mutable_heap_update_function_tests(void) +{ + pri_queue_test_update_increase_function(); + pri_queue_test_update_decrease_function(); + pri_queue_test_update_function_identity(); +} + + +template +void run_mutable_heap_decrease_tests(void) +{ + pri_queue_test_decrease(); + pri_queue_test_decrease_function(); + pri_queue_test_decrease_function_identity(); +} + +template +void run_mutable_heap_increase_tests(void) +{ + pri_queue_test_increase(); + pri_queue_test_increase_function(); + pri_queue_test_increase_function_identity(); +} + +template +void run_mutable_heap_erase_tests(void) +{ + pri_queue_test_erase(); +} + + +template +void run_mutable_heap_tests(void) +{ + run_mutable_heap_update_function_tests(); + run_mutable_heap_update_tests(); + run_mutable_heap_decrease_tests(); + run_mutable_heap_increase_tests(); + run_mutable_heap_erase_tests(); +} + +template +void run_ordered_iterator_tests() +{ + pri_queue_test_ordered_iterators(); +} diff --git a/libs/heap/test/pairing_heap_tests.cpp b/libs/heap/test/pairing_heap_tests.cpp new file mode 100644 index 0000000000..bb7132d0df --- /dev/null +++ b/libs/heap/test/pairing_heap_tests.cpp @@ -0,0 +1,49 @@ +#define BOOST_TEST_MAIN +#include + +#include + +#include + +#include "common_heap_tests.hpp" +#include "stable_heap_tests.hpp" +#include "mutable_heap_tests.hpp" +#include "merge_heap_tests.hpp" + +template +void run_pairing_heap_test(void) +{ + typedef boost::heap::pairing_heap, + boost::heap::compare >, + boost::heap::allocator >, + boost::heap::constant_time_size > pri_queue; + + BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue)); + BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue)); + + run_common_heap_tests(); + run_iterator_heap_tests(); + run_copyable_heap_tests(); + run_moveable_heap_tests(); + + run_merge_tests(); + + run_mutable_heap_tests(); + + run_ordered_iterator_tests(); + + if (stable) { + typedef boost::heap::pairing_heap, + boost::heap::constant_time_size + > stable_pri_queue; + run_stable_heap_tests(); + } +} + +BOOST_AUTO_TEST_CASE( pairing_heap_test ) +{ + run_pairing_heap_test(); + run_pairing_heap_test(); + run_pairing_heap_test(); + run_pairing_heap_test(); +} diff --git a/libs/heap/test/priority_queue_test.cpp b/libs/heap/test/priority_queue_test.cpp new file mode 100644 index 0000000000..9ad51421cc --- /dev/null +++ b/libs/heap/test/priority_queue_test.cpp @@ -0,0 +1,35 @@ +#define BOOST_TEST_MAIN +#include + +#include + +#include + +#include "common_heap_tests.hpp" +#include "stable_heap_tests.hpp" +#include "merge_heap_tests.hpp" + +template +void run_common_priority_queue_tests(void) +{ + typedef boost::heap::priority_queue > pri_queue; + BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue)); + + run_concept_check(); + run_common_heap_tests(); + run_iterator_heap_tests(); + run_copyable_heap_tests(); + run_moveable_heap_tests(); + run_merge_tests(); + + if (stable) { + typedef boost::heap::priority_queue > stable_pri_queue; + run_stable_heap_tests(); + } +} + +BOOST_AUTO_TEST_CASE( std_pri_queue_test ) +{ + run_common_priority_queue_tests(); + run_common_priority_queue_tests(); +} diff --git a/libs/heap/test/skew_heap_test.cpp b/libs/heap/test/skew_heap_test.cpp new file mode 100644 index 0000000000..fb79381bb0 --- /dev/null +++ b/libs/heap/test/skew_heap_test.cpp @@ -0,0 +1,95 @@ +#define BOOST_TEST_MAIN +#include + +#include + +#include + +#include "common_heap_tests.hpp" +#include "stable_heap_tests.hpp" +#include "mutable_heap_tests.hpp" +#include "merge_heap_tests.hpp" + +template +void run_skew_heap_test(void) +{ + typedef boost::heap::skew_heap, + boost::heap::compare >, + boost::heap::allocator >, + boost::heap::constant_time_size, + boost::heap::store_parent_pointer + > pri_queue; + + BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue)); + BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue)); + + run_common_heap_tests(); + run_iterator_heap_tests(); + run_copyable_heap_tests(); + run_moveable_heap_tests(); + + run_merge_tests(); + + pri_queue_test_ordered_iterators(); + + if (stable) { + typedef boost::heap::skew_heap, + boost::heap::constant_time_size, + boost::heap::store_parent_pointer + > stable_pri_queue; + run_stable_heap_tests(); + } +} + +template +void run_skew_heap_mutable_test(void) +{ + typedef boost::heap::skew_heap, boost::heap::mutable_, + boost::heap::compare >, + boost::heap::allocator >, + boost::heap::constant_time_size + > pri_queue; + + BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue)); + BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue)); + + run_common_heap_tests(); + run_iterator_heap_tests(); + run_copyable_heap_tests(); + run_moveable_heap_tests(); + + run_merge_tests(); + + run_mutable_heap_tests(); + + run_ordered_iterator_tests(); + + if (stable) { + typedef boost::heap::skew_heap, boost::heap::mutable_, + boost::heap::constant_time_size + > stable_pri_queue; + run_stable_heap_tests(); + } +} + + +BOOST_AUTO_TEST_CASE( skew_heap_test ) +{ + run_skew_heap_test(); + run_skew_heap_test(); + run_skew_heap_test(); + run_skew_heap_test(); + + run_skew_heap_test(); + run_skew_heap_test(); + run_skew_heap_test(); + run_skew_heap_test(); +} + +BOOST_AUTO_TEST_CASE( skew_heap_mutable_test ) +{ + run_skew_heap_mutable_test(); + run_skew_heap_mutable_test(); + run_skew_heap_mutable_test(); + run_skew_heap_mutable_test(); +} diff --git a/libs/heap/test/stable_heap_tests.hpp b/libs/heap/test/stable_heap_tests.hpp new file mode 100644 index 0000000000..4455b9251d --- /dev/null +++ b/libs/heap/test/stable_heap_tests.hpp @@ -0,0 +1,91 @@ +#include +#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 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 +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()); + check_q(q, data); +} + +template +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()); + + fill_q(q, push_data); + + std::stable_sort(data.begin(), data.end(), compare_by_id()); + std::stable_sort(data.begin(), data.end(), std::less()); + + check_q(q, data); +} + + +template +void run_stable_heap_tests(void) +{ + pri_queue_stable_test_sequential_push(); + pri_queue_stable_test_sequential_reverse_push(); +} diff --git a/libs/heap/tools/heap_benchmarks.hpp b/libs/heap/tools/heap_benchmarks.hpp new file mode 100644 index 0000000000..5e1d1bbd3f --- /dev/null +++ b/libs/heap/tools/heap_benchmarks.hpp @@ -0,0 +1,269 @@ +#include +#include + +#include +#include "high_resolution_timer.hpp" + +#include + +#if defined(__GNUC__) && (!defined __INTEL_COMPILER) +#define no_inline __attribute__ ((noinline)) +#else +#define no_inline +#endif + +typedef std::vector 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 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 \ + struct rebind { \ + typedef run_##SUFFIX type; \ + }; \ +}; + + +template +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 +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 +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< +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 +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< handles; +}; + +DEFINE_BENCHMARKS_SELECTOR(sequential_increase) + +template +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< handles; +}; + +DEFINE_BENCHMARKS_SELECTOR(sequential_decrease) + +template +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 +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 +inline double run_benchmark(benchmark & b) +{ + boost::high_resolution_timer timer; + std::vector 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/libs/heap/tools/high_resolution_timer.hpp b/libs/heap/tools/high_resolution_timer.hpp new file mode 100644 index 0000000000..9893b24413 --- /dev/null +++ b/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 +#include + +#if _POSIX_C_SOURCE >= 199309L + +#include "time.h" + +#include +#include + +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::max)()); + } + + double elapsed_min() const // return minimum value for elapsed() + { + return 0.0; + } + +private: + struct timespec start_time; +}; + +} // namespace boost + +#elif defined(__APPLE__) + +#import + + +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::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 +#include +#include + +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::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 +#include + +namespace boost { + typedef boost::timer high_resolution_timer; +} + +#endif + +#endif // !defined(BOOST_HIGH_RESOLUTION_TIMER_HPP) + diff --git a/libs/heap/tools/throughput_benchmarks.cpp b/libs/heap/tools/throughput_benchmarks.cpp new file mode 100644 index 0000000000..74c440a01b --- /dev/null +++ b/libs/heap/tools/throughput_benchmarks.cpp @@ -0,0 +1,240 @@ +#include +#include + + +#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 +void run_benchmarks_immutable(void) +{ + for (int i = 4; i != max_data; ++i) { + for (int j = 0; j != 8; ++j) { + int size = 1<= 4) + size += (1<<(i-1)); + + cout << size << "\t"; + { + typedef typename benchmark_selector:: + template rebind > > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind, boost::heap::mutable_ > > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind, boost::heap::mutable_ > > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind, boost::heap::mutable_ > > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + cout << endl; + } + } +} + +template +void run_benchmarks_mutable(void) +{ + for (int i = 4; i != max_data; ++i) + { + for (int j = 0; j != 8; ++j) + { + int size = 1<= 4) + size += (1<<(i-1)); + + cout << size << "\t"; + { + typedef typename benchmark_selector:: + template rebind, boost::heap::mutable_ > > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind, boost::heap::mutable_ > > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind, boost::heap::mutable_ > > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > + ::type benchmark_functor; + benchmark_functor benchmark(size); + double result = run_benchmark(benchmark); + cout << result << '\t'; + } + + { + typedef typename benchmark_selector:: + template rebind > > + ::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(); + + cout << endl << "sequential pop" << endl; + run_benchmarks_immutable(); + + cout << endl << "sequential increase" << endl; + run_benchmarks_mutable(); + + cout << endl << "sequential decrease" << endl; + run_benchmarks_mutable(); + + cout << endl << "merge_and_clear" << endl; + run_benchmarks_immutable(); + + cout << endl << "equivalence" << endl; + run_benchmarks_immutable(); +} -- cgit v1.2.3