1 /**************************************************************************** 2 * MeshLab o o * 3 * A versatile mesh processing toolbox o o * 4 * _ O _ * 5 * Copyright(C) 2005 \/)\/ * 6 * Visual Computing Lab /\/| * 7 * ISTI - Italian National Research Council | * 8 * \ * 9 * All rights reserved. * 10 * * 11 * This program is free software; you can redistribute it and/or modify * 12 * it under the terms of the GNU General Public License as published by * 13 * the Free Software Foundation; either version 2 of the License, or * 14 * (at your option) any later version. * 15 * * 16 * This program is distributed in the hope that it will be useful, * 17 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 19 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) * 20 * for more details. * 21 * * 22 ****************************************************************************/ 23 24 #ifndef _PriorityQueue_h_ 25 #define _PriorityQueue_h_ 26 27 /** Implements a bounded-size max priority queue using a heap 28 */ 29 template <typename Index, typename Weight> 30 class HeapMaxPriorityQueue 31 { 32 struct Element 33 { 34 Weight weight; 35 Index index; 36 }; 37 38 public: 39 HeapMaxPriorityQueue(void)40 HeapMaxPriorityQueue(void) 41 { 42 mElements = 0; 43 mMaxSize = 0; 44 } 45 setMaxSize(int maxSize)46 inline void setMaxSize(int maxSize) 47 { 48 if (mMaxSize!=maxSize) 49 { 50 mMaxSize = maxSize; 51 delete[] mElements; 52 mElements = new Element[mMaxSize]; 53 mpOffsetedElements = (mElements-1); 54 } 55 init(); 56 } 57 init()58 inline void init() { mCount = 0; } 59 isFull()60 inline bool isFull() const { return mCount == mMaxSize; } 61 62 /** returns number of elements inserted in queue 63 */ getNofElements()64 inline int getNofElements() const { return mCount; } 65 getWeight(int i)66 inline Weight getWeight(int i) const { return mElements[i].weight; } getIndex(int i)67 inline Index getIndex(int i) const { return mElements[i].index; } 68 getTopWeight()69 inline Weight getTopWeight() const { return mElements[0].weight; } 70 insert(Index index,Weight weight)71 inline void insert(Index index, Weight weight) 72 { 73 if (mCount==mMaxSize) 74 { 75 if (weight<mElements[0].weight) 76 { 77 register int j, k; 78 j = 1; 79 k = 2; 80 while (k <= mMaxSize) 81 { 82 Element* z = &(mpOffsetedElements[k]); 83 if ((k < mMaxSize) && (z->weight < mpOffsetedElements[k+1].weight)) 84 z = &(mpOffsetedElements[++k]); 85 86 if(weight >= z->weight) 87 break; 88 mpOffsetedElements[j] = *z; 89 j = k; 90 k = 2 * j; 91 } 92 mpOffsetedElements[j].weight = weight; 93 mpOffsetedElements[j].index = index; 94 } 95 } 96 else 97 { 98 int i, j; 99 i = ++mCount; 100 while (i >= 2) 101 { 102 j = i >> 1; 103 Element& y = mpOffsetedElements[j]; 104 if(weight <= y.weight) 105 break; 106 mpOffsetedElements[i] = y; 107 i = j; 108 } 109 mpOffsetedElements[i].index = index; 110 mpOffsetedElements[i].weight = weight; 111 } 112 } 113 114 protected: 115 116 int mCount; 117 int mMaxSize; 118 Element* mElements; 119 Element* mpOffsetedElements; 120 }; 121 122 #endif 123