src/libvpsc/pairingheap/PairingHeap.h

   1 /**
   2  * \brief Pairing heap datastructure implementation
   3  *
   4  * Based on example code in "Data structures and Algorithm Analysis in C++"
   5  * by Mark Allen Weiss, used and released under the LGPL by permission
   6  * of the author.
   7  *
   8  * No promises about correctness.  Use at your own risk!
   9  *
  10  * Authors:
  11  *   Mark Allen Weiss
  12  *   Tim Dwyer <tgdwyer@gmail.com>
  13  *
  14  * Copyright (C) 2005 Authors
  15  *
  16  * Released under GNU LGPL.  Read the file 'COPYING' for more information.
  17  */
  18 #ifndef PAIRING_HEAP_H_
  19 #define PAIRING_HEAP_H_
  20 #include <stdlib.h>
  21 #include <fstream>
  22 // Pairing heap class
  23 //
  24 // CONSTRUCTION: with no parameters
  25 //
  26 // ******************PUBLIC OPERATIONS*********************
  27 // PairNode & insert( x ) --> Insert x
  28 // deleteMin( minItem )   --> Remove (and optionally return) smallest item
  29 // T findMin( )  --> Return smallest item
  30 // bool isEmpty( )        --> Return true if empty; else false
  31 // bool isFull( )         --> Return true if empty; else false
  32 // void makeEmpty( )      --> Remove all items
  33 // void decreaseKey( PairNode p, newVal )
  34 //                        --> Decrease value in node p
  35 // ******************ERRORS********************************
  36 // Throws Underflow as warranted
  37
  38
  39 // Node and forward declaration because g++ does
  40 // not understand nested classes.
  41 template <class T>
  42 class PairingHeap;
  43
  44 template <class T>
  45 std::ostream& operator<< (std::ostream &os,const PairingHeap<T> &b);
  46
  47 template <class T>
  48 class PairNode
  49 {
  50         friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
  51         T   element;
  52         PairNode    *leftChild;
  53         PairNode    *nextSibling;
  54         PairNode    *prev;
  55
  56         PairNode( const T & theElement ) :
  57                 element( theElement ),
  58                 leftChild(NULL), nextSibling(NULL), prev(NULL)
  59         { }
  60         friend class PairingHeap<T>;
  61 };
  62
  63 template <class T>
  64 class Comparator
  65 {
  66 public:
  67         virtual bool isLessThan(T const &lhs, T const &rhs) const = 0;
  68 };
  69
  70 template <class T>
  71 class PairingHeap
  72 {
  73         friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
  74 public:
  75         PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) );
  76         PairingHeap( const PairingHeap & rhs );
  77     virtual ~PairingHeap( );
  78
  79         bool isEmpty( ) const;
  80         bool isFull( ) const;
  81         int size();
  82
  83         PairNode<T> *insert( const T & x );
  84         const T & findMin( ) const;
  85         void deleteMin( );
  86         const T extractMin( ) {
  87                 T v = findMin();
  88                 deleteMin();
  89                 return v;
  90         }
  91         void makeEmpty( );
  92         void decreaseKey( PairNode<T> *p, const T & newVal );
  93         void merge( PairingHeap<T> *rhs )
  94         {
  95                 PairNode<T> *broot=rhs->getRoot();
  96                 if (root == NULL) {
  97                         if(broot != NULL) {
  98                                 root = broot;
  99                         }
 100                 } else {
 101                         compareAndLink(root, broot);
 102                 }
 103                 counter+=rhs->size();
 104         }
 105
 106         const PairingHeap & operator=( const PairingHeap & rhs );
 107 protected:
 108         PairNode<T> * getRoot() {
 109                 PairNode<T> *r=root;
 110                 root=NULL;
 111                 return r;
 112         }
 113 private:
 114         PairNode<T> *root;
 115         bool (*lessThan)(T const &lhs, T const &rhs);
 116         int counter;
 117         void reclaimMemory( PairNode<T> *t ) const;
 118         void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const;
 119         PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const;
 120         PairNode<T> * clone( PairNode<T> * t ) const;
 121 };
 122
 123 #include "PairingHeap.cpp"
 124 #endif