pairingheap.h

Graphviz - Graph Drawing Programs from AT&T Research and Lucent Bell Labs See doc/build.html for

/* $Id: PairingHeap.h,v 1.2 2006/04/28 20:33:44 ellson Exp $ $Revision: 1.2 $ */
/* vim:set shiftwidth=4 ts=8: */

/**
 * \brief Pairing heap datastructure implementation
 *
 * Based on example code in "Data structures and Algorithm Analysis in C++"
 * by Mark Allen Weiss, used and released under the LGPL by permission
 * of the author.
 *
 * No promises about correctness.  Use at your own risk!
 *
 * Authors:
 *   Mark Allen Weiss
 *   Tim Dwyer <[e-mail]>
 *
 * Copyright (C) 2005 Authors
 *
 * This version is released under the CPL (Common Public License) with
 * the Graphviz distribution.
 * A version is also available under the LGPL as part of the Adaptagrams
 * project: http://sourceforge.net/projects/adaptagrams.  
 * If you make improvements or bug fixes to this code it would be much
 * appreciated if you could also contribute those changes back to the
 * Adaptagrams repository.
 */
#ifndef PAIRING_HEAP_H_
#define PAIRING_HEAP_H_
#include <stdlib.h>
#include <fstream>
// Pairing heap class
//
// CONSTRUCTION: with no parameters
//
// ******************PUBLIC OPERATIONS*********************
// PairNode & insert( x ) --> Insert x
// deleteMin( minItem )   --> Remove (and optionally return) smallest item
// T findMin( )  --> Return smallest item
// bool isEmpty( )        --> Return true if empty; else false
// bool isFull( )         --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void decreaseKey( PairNode p, newVal )
//                        --> Decrease value in node p
// ******************ERRORS********************************
// Throws Underflow as warranted


// Node and forward declaration because g++ does
// not understand nested classes.
template <class T> 
class PairingHeap;

template <class T>
std::ostream& operator<< (std::ostream &os,const PairingHeap<T> &b);

template <class T>
class PairNode
{
	friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
	T   element;
	PairNode    *leftChild;
	PairNode    *nextSibling;
	PairNode    *prev;

	PairNode( const T & theElement ) :
	       	element( theElement ),
		leftChild(NULL), nextSibling(NULL), prev(NULL)
       	{ }
	friend class PairingHeap<T>;
};

template <class T>
class Comparator
{
public:
	virtual bool isLessThan(T const &lhs, T const &rhs) const = 0;
};

template <class T>
class PairingHeap
{
	friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
public:
	PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) );
	PairingHeap( const PairingHeap & rhs );
	~PairingHeap( );

	bool isEmpty( ) const;
	bool isFull( ) const;
	int size();

	PairNode<T> *insert( const T & x );
	const T & findMin( ) const;
	void deleteMin( );
	void makeEmpty( );
	void decreaseKey( PairNode<T> *p, const T & newVal );
	void merge( PairingHeap<T> *rhs )
	{	
		PairNode<T> *broot=rhs->getRoot();
		if (root == NULL) {
			if(broot != NULL) {
				root = broot;
			}
		} else {
			compareAndLink(root, broot);
		}
		counter+=rhs->size();
	}

	const PairingHeap & operator=( const PairingHeap & rhs );
protected:
	PairNode<T> * getRoot() {
		PairNode<T> *r=root;
		root=NULL;
		return r;
	}
private:
	PairNode<T> *root;
	bool (*lessThan)(T const &lhs, T const &rhs);
	int counter;
	void reclaimMemory( PairNode<T> *t ) const;
	void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const;
	PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const;
	PairNode<T> * clone( PairNode<T> * t ) const;
};

#include "PairingHeap.cpp"
#endif