ext/OGDF/ogdf/basic/MinPriorityQueue.h

   1 /*
   2  * $Revision: 2524 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of a base class for planar representations
  11  *        of graphs and cluster graphs.
  12  *
  13  * \author Hoi-Ming Wong
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48
  49
  50 #ifndef OGDF_MIN_PRIORITY_QUEUE_H
  51 #define OGDF_MIN_PRIORITY_QUEUE_H
  52
  53 #include<ogdf/basic/Array.h>
  54
  55
  56 namespace ogdf {
  57
  58
  59 template<class Score, class X>
  60 class HeapElement {
  61
  62         template<class T1, class T2> friend class MinPriorityQueue;
  63
  64         private:
  65                 Score v;
  66                 X x;
  67                 int pos; // the position in the heapElement array
  68         public:
  69                 HeapElement(){}
  70                 //copy constructor
  71                 HeapElement(const HeapElement<Score, X> &orig): v(orig.v), x(orig.x), pos(orig.pos) {}
  72                 HeapElement(Score vt, X xt) : v(vt), x(xt) {}
  73
  74                 //return the score
  75                 Score score_value() const { return v; }
  76                 // return the element
  77                 X element() const { return x;}
  78 };
  79
  80
  81
  82 // using min heaps
  83 // follow the pseudo code of "introduction to algorithms"
  84 template <class Score, class X>
  85 class MinPriorityQueue {
  86
  87         private :
  88
  89         HeapElement<Score, X> **heapElements;
  90
  91         int number; // the number of elements in the Queue
  92         int s; // size
  93
  94         void swap(int pos1, int pos2) {
  95                 HeapElement<Score, X> *tmp = heapElements[pos1];
  96                 heapElements[pos1] = heapElements[pos2];
  97                 heapElements[pos2] = tmp;
  98                 // update the position
  99                 heapElements[pos2]->pos = pos2;
 100                 heapElements[pos1]->pos = pos1;
 101         }
 102
 103         void minHeapify(int pos) {
 104                 int l = getLeft(pos);
 105                 int r = getRight(pos);
 106                 int smallest;
 107                 if (l <= number && heapElements[l]->score_value() < heapElements[pos]->score_value() )
 108                         smallest = l;
 109                 else
 110                         smallest = pos;
 111                 if (r <= number && heapElements[r]->score_value() < heapElements[smallest]->score_value())
 112                         smallest = r;
 113                 if (smallest != pos) {
 114                         swap(pos, smallest);
 115                         minHeapify(smallest);
 116                 }
 117         }
 118
 119         int getParent(int pos) const {return pos/2;}
 120         int getLeft(int pos) const {return pos*2;}
 121         int getRight(int pos) const {return pos*2+1;}
 122
 123
 124         public:
 125
 126         // contructor, only fixed size
 127         MinPriorityQueue(int _size) : number(0), s(_size) {
 128                 heapElements = new HeapElement<Score, X>* [_size+1]; // allocate
 129                 for (int i = 0; i < s+1; ++i) {
 130                         heapElements[i] = 0;
 131                 }
 132         }
 133
 134
 135         ~MinPriorityQueue() {
 136                 for (int i = 0; i < s+1; ++i) {
 137                         if (heapElements[i] != 0) {
 138                                 delete heapElements[i];
 139                                 heapElements[i] = 0;
 140                         }
 141                 }
 142                 delete [] heapElements;
 143         }
 144
 145
 146         bool empty() const { return number == 0; }
 147         int count() const { return number; }
 148         int size() const { return s; }
 149
 150         //return the Object with the min. score
 151         const X & getMin() const {
 152                 return heapElements[1]->element();
 153         }
 154
 155
 156
 157         void decreasePriority(const HeapElement<Score, X> *elem, // handle to the element
 158                                                         Score sc // new score, muss be smaller then the old score
 159                                                         ) {
 160                 int i = elem->pos;
 161                 OGDF_ASSERT(i <= s);
 162                 if (heapElements[i]->score_value() < sc)
 163                         throw "New key is greater than current key.";
 164                 heapElements[i]->v = sc;
 165                 while (i > 1 && (heapElements[getParent(i)]->score_value() > heapElements[i]->score_value()) ) {
 166                         swap(i, getParent(i));
 167                         i = getParent(i);
 168                 }
 169         }
 170
 171
 172         // return a handle to the new inserted element
 173         const HeapElement<Score, X> * insert(const HeapElement<Score, X> &elem) {
 174                 HeapElement<Score, X> *h_elem = new HeapElement<Score, X>(elem); // make a copy
 175                 ++number;
 176                 OGDF_ASSERT(number <= s);
 177                 h_elem->pos = number; // store the position
 178                 heapElements[number] = h_elem;
 179                 int i = number;
 180                 while ( (i > 1) && ( heapElements[getParent(i)]->score_value() > heapElements[i]->score_value()) ) {
 181                         swap(i, getParent(i));
 182                         i = getParent(i);
 183                 }
 184                 return h_elem;
 185         }
 186
 187
 188         // return the smallest element and remove it from the queue
 189         HeapElement<Score, X> pop() {
 190                 if (empty())
 191                         throw "Heap underflow error!";
 192                 HeapElement<Score, X> obj = *heapElements[1];
 193                 HeapElement<Score, X> * p = heapElements[1];
 194                 swap(1, number);
 195                 --number;
 196                 delete p;
 197                 minHeapify(1);
 198                 OGDF_ASSERT(number+1 <= s);
 199                 heapElements[number+1] = 0;
 200                 return obj;
 201         }
 202
 203
 204
 205         /*********************************************************************************/
 206         // debug
 207         void outHeap() {
 208                 cout << "\nHeap Array: \n";
 209                 for (int i = 0; i < s+1; i++) {
 210                         HeapElement<Score, X> *obj = heapElements[i];
 211                         if (obj != NULL)
 212                                 cout << "score: " << obj->score_value() << "; elem: " << obj->element() << "; index "<< i << "; pos: " << obj->pos << endl << flush;
 213                         else
 214                                 cout << "index: " << i << " value: null;" <<  endl << flush;
 215                 }
 216         }
 217 };
 218
 219
 220 }// namespace
 221
 222 #endif