From fc5ba037dfabbe41eeea4f12237974538b373716 Mon Sep 17 00:00:00 2001
From: erg <devnull@localhost>
Date: Fri, 28 Apr 2006 19:03:46 +0000
Subject: [PATCH] Add the vpsc library for IPSEPCOLA features

---
 lib/vpsc/pairingheap/PairingHeap.h  | 125 ++++++++++++++++++++++++++++
 lib/vpsc/pairingheap/dsexceptions.h |   9 ++
 2 files changed, 134 insertions(+)
 create mode 100644 lib/vpsc/pairingheap/PairingHeap.h
 create mode 100644 lib/vpsc/pairingheap/dsexceptions.h

diff --git a/lib/vpsc/pairingheap/PairingHeap.h b/lib/vpsc/pairingheap/PairingHeap.h
new file mode 100644
index 000000000..08e29bee8
--- /dev/null
+++ b/lib/vpsc/pairingheap/PairingHeap.h
@@ -0,0 +1,125 @@
+/**
+ * \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 <tgdwyer@gmail.com>
+ *
+ * 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
diff --git a/lib/vpsc/pairingheap/dsexceptions.h b/lib/vpsc/pairingheap/dsexceptions.h
new file mode 100644
index 000000000..bef2c78c5
--- /dev/null
+++ b/lib/vpsc/pairingheap/dsexceptions.h
@@ -0,0 +1,9 @@
+#ifndef DSEXCEPTIONS_H_
+#define DSEXCEPTIONS_H_
+
+class Underflow { };
+class Overflow  { };
+class OutOfMemory { };
+class BadIterator { };
+
+#endif
-- 
2.40.0