c99194061f
[SVN r81319]
262 lines
5.5 KiB
C++
262 lines
5.5 KiB
C++
/*=============================================================================
|
|
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();
|
|
}
|