heap/examples/interface.cpp

/*=============================================================================
    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 <iomanip>
#include <iostream>

#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();
}