123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261 |
- /*=============================================================================
- 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();
- }
|