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