source: GTP/trunk/Lib/Vis/Preprocessing/src/FlexibleHeap.h @ 2542

Revision 2542, 5.4 KB checked in by mattausch, 17 years ago (diff)
RevLine 
[1099]1#ifndef FLEXIBLEHEAP_H
2#define FLEXIBLEHEAP_H
3
4#include <vector>
5
6
7namespace GtpVisibilityPreprocessor {
8
9const static int NOT_IN_HEAP = -100;
10
11/** This class implements an element for a heap.
12        Classes using the heap should be inherited from this class.
13*/
14class Heapable
15{
16public:
[2360]17       
[1099]18        Heapable(): mPriority(0) { NotInHeap(); SetPriority(0.0f); }
19
20        inline bool IsInHeap() { return mPosition != NOT_IN_HEAP; }
21        inline void NotInHeap() { mPosition = NOT_IN_HEAP; }
22        inline int GetHeapPos() { return mPosition; }
23        inline void SetHeapPos(const int t) { mPosition = t; }
24
25        inline void  SetPriority(const float k) { mPriority = k; }
[1667]26        //inline float GetPriority() const  { return mPriority; }
27        virtual float GetPriority() const = 0;
[2360]28
[1099]29protected:
30
31        float mPriority;
32        int mPosition;
33};
34
35
[2542]36/** This class implements a flexible heap for use as a priority queue.
37        Unlike the stl priority_queue, the class allows access to all
38        elements. It implements efficient insertion routines and remove routines
39        of arbitrary elements.
[1099]40*/
41template<typename T>
42class FlexibleHeap
43{
44public:
45        FlexibleHeap() { }
46        FlexibleHeap(const unsigned int n): mBuffer(n) { }
47
[2542]48        void Push(T t);
[1099]49        void Push(T t, const float priority);
[2542]50        bool Update(T t);
[1099]51        bool Update(T t, const float priority);
52
[2542]53        inline unsigned int Size() const;
54        inline bool Empty() const;
55        inline T Item(const unsigned int i);
56        inline const T Item(const unsigned int i) const;
[1099]57        T Pop();
[2542]58        inline T Top() const;
[1099]59        /** Erases the element from the heap.
60        */
61        T Erase(T);
62
63protected:
64
65        void Place(T x, const unsigned int i);
66        void Swap(const unsigned int i, const unsigned int j);
67
68        unsigned int Parent(const unsigned int i) const { return (i - 1) / 2; }
69        unsigned int Left(const unsigned int i) const { return 2 * i + 1; }
70        unsigned int Right(const unsigned int i) const { return 2 * i + 2; }
71
72        void UpHeap(const unsigned int i);
73        void DownHeap(const unsigned int i);
74
75        std::vector<T> mBuffer;
76};
77
[1313]78
[1099]79
[2542]80
81/******************************************************************/
82/*                 FexibleHeap implementation                     */
83/******************************************************************/
84
85
[1099]86template <typename T>
[2542]87void FlexibleHeap<T>::Push(T t)
88{
89        Push(t, t->GetPriority());
90}
91
92
93template <typename T>
94bool FlexibleHeap<T>::Update(T t)
95{
96        return Update(t, t->GetPriority());
97}
98
99
100template <typename T>
101inline unsigned int FlexibleHeap<T>::Size() const
102{
103        return (unsigned int)mBuffer.size();
104}
105
106
107template <typename T>
108inline bool FlexibleHeap<T>::Empty() const
109{
110        return mBuffer.empty();
111}
112
113
114template <typename T>
115inline T FlexibleHeap<T>::Item(const unsigned int i)
116{
117        return mBuffer[i];
118}
119
120
121template <typename T>
122inline const T FlexibleHeap<T>::Item(const unsigned int i) const
123{
124        return mBuffer[i];
125}
126
127
128template <typename T>
129inline T FlexibleHeap<T>::Top() const
130{
131        return (mBuffer.empty() ? (T)NULL : mBuffer.front());
132}
133
134
135template <typename T>
[1099]136inline void FlexibleHeap<T>::Place(T x, const unsigned int i)
137{
138        mBuffer[i] = x;
139        x->SetHeapPos(i);
140}
141
142
143template <typename T>
144void FlexibleHeap<T>::Swap(const unsigned int i, const unsigned int j)
145{
146        T tmp = mBuffer[i];
147
148        Place(mBuffer[j], i);
149        Place(tmp, j);
150}
151
152
153template <typename T>
154void FlexibleHeap<T>::UpHeap(const unsigned int i)
155{
156        T moving = mBuffer[i];
157        unsigned int index = i;
158        unsigned int p = Parent(i);
159
160        while ((index > 0) && (moving->GetPriority() > mBuffer[p]->GetPriority()))
161        {
162                Place(mBuffer[p], index);
163                index = p;
164                p = Parent(p);
165        }
166
167        if (index != i)
168        {
169                Place(moving, index);
170        }
171}
172
[2542]173
[1099]174template <typename T>
175void FlexibleHeap<T>::DownHeap(const unsigned int i)
176{
177        T moving = mBuffer[i];
178
179        unsigned int index = i;
180        unsigned int l = Left(i);
181        unsigned int r = Right(i);
182        unsigned int largest;
183
184        while (l < (int)mBuffer.size())
185        {
186                if ((r < (unsigned int)mBuffer.size()) && (mBuffer[l]->GetPriority() < mBuffer[r]->GetPriority()))
187                        largest = r;
188                else
189                        largest = l;
190
191                if (moving->GetPriority() < mBuffer[largest]->GetPriority())
192                {
193                        Place(mBuffer[largest], index);
194                        index = largest;
195                        l = Left(index);
196                        r = Right(index);
197                }
198                else
199                {
200                        break;
201                }
202        }
203
204        if (index != i)
205        {
206                Place(moving, index);
207        }
208}
209
210
211template <typename T>
212void FlexibleHeap<T>::Push(T t, const float v)
213{
214        t->SetPriority(v);
215
216        unsigned int i = (unsigned int)mBuffer.size();
217
218        t->SetHeapPos(i);
219        mBuffer.push_back(t);
220
221        UpHeap(i);
222}
223
224template <typename T>
225bool FlexibleHeap<T>::Update(T t, const float v)
226{
227        if (t->IsInHeap())
228                return false;
229
230        t->SetPriority(v);
231
232        const unsigned int i = t->GetHeapPos();
233
234        if ((i > 0) && (v > mBuffer[Parent(i)]->GetPriority()))
235                UpHeap(i);
236        else
237                DownHeap(i);
238
239        return true;
240}
241
242template <typename T>
243T FlexibleHeap<T>::Pop()
244{
245        if (mBuffer.empty())
246                return NULL;
247
[1106]248        Swap(0, (int)mBuffer.size() - 1);
[1099]249
250        T dead = mBuffer.back();
251        mBuffer.pop_back();
252
[2542]253        if (!mBuffer.empty())
254                DownHeap(0);
255
[1099]256        dead->NotInHeap();
257
258        return dead;
259}
260
261
262template <typename T>
263T FlexibleHeap<T>::Erase(T t)
264{
265        if (!t->IsInHeap())
266                return (T)NULL;
267
268        const int i = t->GetHeapPos();
269
270        Swap(i, (int)mBuffer.size() - 1);
[1297]271       
[1099]272        mBuffer.pop_back();
273        t->NotInHeap();
274
275        if (mBuffer[i]->GetPriority() < t->GetPriority())
276                DownHeap(i);
277        else
278                UpHeap(i);
279
280        return t;
281}
282
283}
284
285// FLEXIBLEHEAP_H
286#endif
Note: See TracBrowser for help on using the repository browser.