src/removeoverlap/pairingheap/PairingHeap.cpp

   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
  19 #include <vector>
  20 #include <list>
  21 #include "dsexceptions.h"
  22 #include "PairingHeap.h"
  23
  24 #ifndef PAIRING_HEAP_CPP
  25 #define PAIRING_HEAP_CPP
  26 using namespace std;
  27 /**
  28 * Construct the pairing heap.
  29 */
  30 template <class T>
  31 PairingHeap<T>::PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) )
  32 {
  33         root = NULL;
  34         counter=0;
  35         this->lessThan=lessThan;
  36 }
  37
  38
  39 /**
  40 * Copy constructor
  41 */
  42 template <class T>
  43 PairingHeap<T>::PairingHeap( const PairingHeap<T> & rhs )
  44 {
  45         root = NULL;
  46         counter=rhs->size();
  47         *this = rhs;
  48 }
  49
  50 /**
  51 * Destroy the leftist heap.
  52 */
  53 template <class T>
  54 PairingHeap<T>::~PairingHeap( )
  55 {
  56         makeEmpty( );
  57 }
  58
  59 /**
  60 * Insert item x into the priority queue, maintaining heap order.
  61 * Return a pointer to the node containing the new item.
  62 */
  63 template <class T>
  64 PairNode<T> *
  65 PairingHeap<T>::insert( const T & x )
  66 {
  67         PairNode<T> *newNode = new PairNode<T>( x );
  68
  69         if( root == NULL )
  70                 root = newNode;
  71         else
  72                 compareAndLink( root, newNode );
  73         counter++;
  74         return newNode;
  75 }
  76 template <class T>
  77 int PairingHeap<T>::size() {
  78         return counter;
  79 }
  80 /**
  81 * Find the smallest item in the priority queue.
  82 * Return the smallest item, or throw Underflow if empty.
  83 */
  84 template <class T>
  85 const T & PairingHeap<T>::findMin( ) const
  86 {
  87         if( isEmpty( ) )
  88                 throw Underflow( );
  89         return root->element;
  90 }
  91 /**
  92  * Remove the smallest item from the priority queue.
  93  * Throws Underflow if empty.
  94  */
  95 template <class T>
  96 void PairingHeap<T>::deleteMin( )
  97 {
  98     if( isEmpty( ) )
  99         throw Underflow( );
 100
 101     PairNode<T> *oldRoot = root;
 102
 103     if( root->leftChild == NULL )
 104         root = NULL;
 105     else
 106         root = combineSiblings( root->leftChild );
 107         counter--;
 108     delete oldRoot;
 109 }
 110
 111 /**
 112 * Test if the priority queue is logically empty.
 113 * Returns true if empty, false otherwise.
 114 */
 115 template <class T>
 116 bool PairingHeap<T>::isEmpty( ) const
 117 {
 118         return root == NULL;
 119 }
 120
 121 /**
 122 * Test if the priority queue is logically full.
 123 * Returns false in this implementation.
 124 */
 125 template <class T>
 126 bool PairingHeap<T>::isFull( ) const
 127 {
 128         return false;
 129 }
 130
 131 /**
 132 * Make the priority queue logically empty.
 133 */
 134 template <class T>
 135 void PairingHeap<T>::makeEmpty( )
 136 {
 137         reclaimMemory( root );
 138         root = NULL;
 139 }
 140
 141 /**
 142 * Deep copy.
 143 */
 144 template <class T>
 145 const PairingHeap<T> &
 146 PairingHeap<T>::operator=( const PairingHeap<T> & rhs )
 147 {
 148         if( this != &rhs )
 149         {
 150                 makeEmpty( );
 151                 root = clone( rhs.root );
 152         }
 153
 154         return *this;
 155 }
 156
 157 /**
 158 * Internal method to make the tree empty.
 159 * WARNING: This is prone to running out of stack space.
 160 */
 161 template <class T>
 162 void PairingHeap<T>::reclaimMemory( PairNode<T> * t ) const
 163 {
 164         if( t != NULL )
 165         {
 166                 reclaimMemory( t->leftChild );
 167                 reclaimMemory( t->nextSibling );
 168                 delete t;
 169         }
 170 }
 171
 172 /**
 173 * Change the value of the item stored in the pairing heap.
 174 * Does nothing if newVal is larger than currently stored value.
 175 * p points to a node returned by insert.
 176 * newVal is the new value, which must be smaller
 177 *    than the currently stored value.
 178 */
 179 template <class T>
 180 void PairingHeap<T>::decreaseKey( PairNode<T> *p,
 181                                                                                   const T & newVal )
 182 {
 183         if( p->element < newVal )
 184                 return;    // newVal cannot be bigger
 185         p->element = newVal;
 186         if( p != root )
 187         {
 188                 if( p->nextSibling != NULL )
 189                         p->nextSibling->prev = p->prev;
 190                 if( p->prev->leftChild == p )
 191                         p->prev->leftChild = p->nextSibling;
 192                 else
 193                         p->prev->nextSibling = p->nextSibling;
 194
 195                 p->nextSibling = NULL;
 196                 compareAndLink( root, p );
 197         }
 198 }
 199
 200 /**
 201 * Internal method that is the basic operation to maintain order.
 202 * Links first and second together to satisfy heap order.
 203 * first is root of tree 1, which may not be NULL.
 204 *    first->nextSibling MUST be NULL on entry.
 205 * second is root of tree 2, which may be NULL.
 206 * first becomes the result of the tree merge.
 207 */
 208 template <class T>
 209 void PairingHeap<T>::
 210 compareAndLink( PairNode<T> * & first,
 211                            PairNode<T> *second ) const
 212 {
 213         if( second == NULL )
 214                 return;
 215         if( lessThan(second->element,first->element) )
 216         {
 217                 // Attach first as leftmost child of second
 218                 second->prev = first->prev;
 219                 first->prev = second;
 220                 first->nextSibling = second->leftChild;
 221                 if( first->nextSibling != NULL )
 222                         first->nextSibling->prev = first;
 223                 second->leftChild = first;
 224                 first = second;
 225         }
 226         else
 227         {
 228                 // Attach second as leftmost child of first
 229                 second->prev = first;
 230                 first->nextSibling = second->nextSibling;
 231                 if( first->nextSibling != NULL )
 232                         first->nextSibling->prev = first;
 233                 second->nextSibling = first->leftChild;
 234                 if( second->nextSibling != NULL )
 235                         second->nextSibling->prev = second;
 236                 first->leftChild = second;
 237         }
 238 }
 239
 240 /**
 241 * Internal method that implements two-pass merging.
 242 * firstSibling the root of the conglomerate;
 243 *     assumed not NULL.
 244 */
 245 template <class T>
 246 PairNode<T> *
 247 PairingHeap<T>::combineSiblings( PairNode<T> *firstSibling ) const
 248 {
 249         if( firstSibling->nextSibling == NULL )
 250                 return firstSibling;
 251
 252         // Allocate the array
 253         static vector<PairNode<T> *> treeArray( 5 );
 254
 255         // Store the subtrees in an array
 256         int numSiblings = 0;
 257         for( ; firstSibling != NULL; numSiblings++ )
 258         {
 259                 if( numSiblings == (int)treeArray.size( ) )
 260                         treeArray.resize( numSiblings * 2 );
 261                 treeArray[ numSiblings ] = firstSibling;
 262                 firstSibling->prev->nextSibling = NULL;  // break links
 263                 firstSibling = firstSibling->nextSibling;
 264         }
 265         if( numSiblings == (int)treeArray.size( ) )
 266                 treeArray.resize( numSiblings + 1 );
 267         treeArray[ numSiblings ] = NULL;
 268
 269         // Combine subtrees two at a time, going left to right
 270         int i = 0;
 271         for( ; i + 1 < numSiblings; i += 2 )
 272                 compareAndLink( treeArray[ i ], treeArray[ i + 1 ] );
 273
 274         int j = i - 2;
 275
 276         // j has the result of last compareAndLink.
 277         // If an odd number of trees, get the last one.
 278         if( j == numSiblings - 3 )
 279                 compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );
 280
 281         // Now go right to left, merging last tree with
 282         // next to last. The result becomes the new last.
 283         for( ; j >= 2; j -= 2 )
 284                 compareAndLink( treeArray[ j - 2 ], treeArray[ j ] );
 285         return treeArray[ 0 ];
 286 }
 287
 288 /**
 289 * Internal method to clone subtree.
 290 * WARNING: This is prone to running out of stack space.
 291 */
 292 template <class T>
 293 PairNode<T> *
 294 PairingHeap<T>::clone( PairNode<T> * t ) const
 295 {
 296         if( t == NULL )
 297                 return NULL;
 298         else
 299         {
 300                 PairNode<T> *p = new PairNode<T>( t->element );
 301                 if( ( p->leftChild = clone( t->leftChild ) ) != NULL )
 302                         p->leftChild->prev = p;
 303                 if( ( p->nextSibling = clone( t->nextSibling ) ) != NULL )
 304                         p->nextSibling->prev = p;
 305                 return p;
 306         }
 307 }
 308 template <class T>
 309 ostream& operator <<(ostream &os, const PairingHeap<T> &b)
 310 {
 311         os<<"Heap:";
 312         if (b.root != NULL) {
 313                 PairNode<T> *r = b.root;
 314                 list<PairNode<T>*> q;
 315                 q.push_back(r);
 316                 while (!q.empty()) {
 317                         r = q.front();
 318                         q.pop_front();
 319                         if (r->leftChild != NULL) {
 320                                 os << *r->element << ">";
 321                                 PairNode<T> *c = r->leftChild;
 322                                 while (c != NULL) {
 323                                         q.push_back(c);
 324                                         os << "," << *c->element;
 325                                         c = c->nextSibling;
 326                                 }
 327                                 os << "|";
 328                         }
 329                 }
 330         }
 331     return os;
 332 }
 333 #endif