src/removeoverlap/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 GPL 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 GPL.  Read the file 'COPYING' for more information.
  17  */
  18 #ifndef PAIRING_HEAP_H_
  19 #define PAIRING_HEAP_H_
  20 #include <stdlib.h>
  21 // Pairing heap class
  22 //
  23 // CONSTRUCTION: with no parameters
  24 //
  25 // ******************PUBLIC OPERATIONS*********************
  26 // PairNode & insert( x ) --> Insert x
  27 // deleteMin( minItem )   --> Remove (and optionally return) smallest item
  28 // T findMin( )  --> Return smallest item
  29 // bool isEmpty( )        --> Return true if empty; else false
  30 // bool isFull( )         --> Return true if empty; else false
  31 // void makeEmpty( )      --> Remove all items
  32 // void decreaseKey( PairNode p, newVal )
  33 //                        --> Decrease value in node p
  34 // ******************ERRORS********************************
  35 // Throws Underflow as warranted
  36
  37
  38 // Node and forward declaration because g++ does
  39 // not understand nested classes.
  40 template <class T>
  41 class PairingHeap;
  42
  43 template <class T>
  44 class PairNode
  45 {
  46         T   element;
  47         PairNode    *leftChild;
  48         PairNode    *nextSibling;
  49         PairNode    *prev;
  50
  51         PairNode( const T & theElement ) : element( theElement ),
  52                 leftChild(NULL), nextSibling(NULL), prev(NULL) { }
  53                 friend class PairingHeap<T>;
  54 };
  55
  56 template <class T>
  57 class Comparator
  58 {
  59 public:
  60         virtual bool isLessThan(const T &lhs, const T &rhs) const = 0;
  61 };
  62
  63 template <class T>
  64 class PairingHeap
  65 {
  66 public:
  67         PairingHeap( bool (*lessThan)(T &lhs, T &rhs) );
  68         PairingHeap( const PairingHeap & rhs );
  69         ~PairingHeap( );
  70
  71         bool isEmpty( ) const;
  72         bool isFull( ) const;
  73         int size();
  74
  75         PairNode<T> *insert( const T & x );
  76         const T & findMin( ) const;
  77         void deleteMin( );
  78         void makeEmpty( );
  79         void decreaseKey( PairNode<T> *p, const T & newVal );
  80         void merge( PairingHeap<T> *rhs )
  81         {
  82                 PairNode<T> *broot=rhs->getRoot();
  83                 if (root == NULL) {
  84                         if(broot != NULL) {
  85                                 root = broot;
  86                         }
  87                 } else {
  88                         compareAndLink(root, broot);
  89                 }
  90                 counter+=rhs->size();
  91         }
  92
  93         const PairingHeap & operator=( const PairingHeap & rhs );
  94 protected:
  95         PairNode<T> * getRoot() {
  96                 PairNode<T> *r=root;
  97                 root=NULL;
  98                 return r;
  99         }
 100 private:
 101         PairNode<T> *root;
 102         bool (*lessThan)(T &lhs, T &rhs);
 103         int counter;
 104         void reclaimMemory( PairNode<T> *t ) const;
 105         void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const;
 106         PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const;
 107         PairNode<T> * clone( PairNode<T> * t ) const;
 108 };
 109
 110 #include "PairingHeap.cpp"
 111 #endif