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

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