ext/OGDF/src/energybased/PQueue.h

   1 /*
   2  * $Revision: 2559 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class PQueue (priority queue).
  11  *
  12  * \author Stefan Hachul
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_PQUEUE_H
  49 #define OGDF_PQUEUE_H
  50
  51 #include <ogdf/basic/List.h>
  52
  53 namespace ogdf {
  54
  55 //Needed for storing entries of the heap.
  56 class HelpRecord
  57 {
  58 public:
  59         HelpRecord() { }  //constructor
  60         ~HelpRecord(){ } //destructor
  61
  62         void set_ListIterator(ListIterator<PackingRowInfo>& it) { iterator = it; }
  63         void set_value (double v) { value = v; }
  64         ListIterator<PackingRowInfo> get_ListIterator() const { return iterator; }
  65         double get_value() const { return value; }
  66
  67 private:
  68         double value;
  69         ListIterator<PackingRowInfo> iterator;
  70 };
  71
  72 class PQueue
  73 {
  74         //Helping data structure that is a priority queue (heap) and holds  double values
  75         //(as comparison values) and iterators of type ListIterator<PackingRowInfo>
  76         //as contents. It is needed in class MAARPacking for the Best_Fit insert strategy.
  77
  78 public:
  79
  80         PQueue() { P.clear(); } //constructor
  81         ~PQueue(){ }            //destructor
  82
  83         //Inserts content with value value into the priority queue and restores the heap.
  84         void insert(double value, ListIterator<PackingRowInfo> iterator)
  85         {
  86                 HelpRecord h;
  87                 h.set_value(value);
  88                 h.set_ListIterator(iterator);
  89                 P.pushBack(h);
  90                 //reheap bottom up
  91                 reheap_bottom_up(P.size()-1);
  92         }
  93
  94         //Deletes the element with the minimum value from the queue and restores
  95         //the heap.
  96         void del_min()
  97         {
  98                 if(P.size() < 1)
  99                         cout<<"Error PQueue:: del_min() ; Heap is empty"<<endl;
 100                 else
 101                 {
 102                         //last element becomes first element
 103                         P.popFront();
 104                         if(!P.empty())
 105                         {
 106                                 P.pushFront(P.back());
 107                                 P.popBack();
 108                                 //reheap top down
 109                                 reheap_top_down(0);
 110                         }
 111                 }
 112         }
 113
 114         //Returns the content with the minimum value.
 115         ListIterator<PackingRowInfo> find_min()
 116         {
 117                 OGDF_ASSERT(P.size() >= 1);
 118                 //if(P.size() < 1)
 119                 //  cout<<"Error PQueue:: find_min() ; Heap is empty"<<endl;
 120                 //else
 121                 return P.front().get_ListIterator();
 122         }
 123
 124 private:
 125         List<HelpRecord> P;//the priority queue;
 126
 127         //Restores the heap property in P starting from position i bottom up.
 128         void reheap_bottom_up(int i)
 129         {
 130                 int parent = (i-1)/2;
 131
 132                 if((i != 0) && ((*P.get(parent)).get_value() > (*P.get(i)).get_value()))
 133                 {
 134                         exchange(i,parent);
 135                         reheap_bottom_up(parent);
 136                 }
 137         }
 138
 139         //Restores the heap property in P starting from position i top down.
 140         void reheap_top_down(int i)
 141         {
 142                 int smallest = i;
 143                 int l = 2*i+1;
 144                 int r = 2*i+2;
 145
 146                 if((l <= P.size()-1) && ((*P.get(l)).get_value() < (*P.get(i)).get_value()))
 147                         smallest = l;
 148                 else
 149                         smallest = i;
 150                 if((r <= P.size()-1) && ((*P.get(r)).get_value() < (*P.get(smallest)).get_value()))
 151                         smallest = r;
 152                 if(smallest != i)//exchange and recursion
 153                 {
 154                         exchange(i,smallest);
 155                         reheap_top_down(smallest);
 156                 }
 157         }
 158
 159         //Exchanges heap entries at positions i and j.
 160         void exchange(int i, int j)
 161         {
 162                 HelpRecord h = *P.get(i);
 163                 *P.get(i) = *P.get(j);
 164                 *P.get(j) = h;
 165         }
 166 };
 167
 168 }//namespace ogdf
 169 #endif
 170
 171
 172
 173