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

Revision 1313, 4.8 KB checked in by mattausch, 18 years ago (diff)
Line 
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/*****************************************************************************/
81/*                         MyHeap implementation                             *
82/*****************************************************************************/
83
84template <typename T>
85inline void FlexibleHeap<T>::Place(T x, const unsigned int i)
86{
87        mBuffer[i] = x;
88        x->SetHeapPos(i);
89}
90
91
92template <typename T>
93void FlexibleHeap<T>::Swap(const unsigned int i, const unsigned int j)
94{
95        T tmp = mBuffer[i];
96
97        Place(mBuffer[j], i);
98        Place(tmp, j);
99}
100
101
102template <typename T>
103void FlexibleHeap<T>::UpHeap(const unsigned int i)
104{
105        T moving = mBuffer[i];
106        unsigned int index = i;
107        unsigned int p = Parent(i);
108
109        while ((index > 0) && (moving->GetPriority() > mBuffer[p]->GetPriority()))
110        {
111                Place(mBuffer[p], index);
112                index = p;
113                p = Parent(p);
114        }
115
116        if (index != i)
117        {
118                Place(moving, index);
119        }
120}
121
122template <typename T>
123void FlexibleHeap<T>::DownHeap(const unsigned int i)
124{
125        T moving = mBuffer[i];
126
127        unsigned int index = i;
128        unsigned int l = Left(i);
129        unsigned int r = Right(i);
130        unsigned int largest;
131
132        while (l < (int)mBuffer.size())
133        {
134                if ((r < (unsigned int)mBuffer.size()) && (mBuffer[l]->GetPriority() < mBuffer[r]->GetPriority()))
135                        largest = r;
136                else
137                        largest = l;
138
139                if (moving->GetPriority() < mBuffer[largest]->GetPriority())
140                {
141                        Place(mBuffer[largest], index);
142                        index = largest;
143                        l = Left(index);
144                        r = Right(index);
145                }
146                else
147                {
148                        break;
149                }
150        }
151
152        if (index != i)
153        {
154                Place(moving, index);
155        }
156}
157
158
159template <typename T>
160void FlexibleHeap<T>::Push(T t, const float v)
161{
162        t->SetPriority(v);
163
164        unsigned int i = (unsigned int)mBuffer.size();
165
166        t->SetHeapPos(i);
167        mBuffer.push_back(t);
168
169        UpHeap(i);
170}
171
172template <typename T>
173bool FlexibleHeap<T>::Update(T t, const float v)
174{
175        if (t->IsInHeap())
176                return false;
177
178        t->SetPriority(v);
179
180        const unsigned int i = t->GetHeapPos();
181
182        if ((i > 0) && (v > mBuffer[Parent(i)]->GetPriority()))
183                UpHeap(i);
184        else
185                DownHeap(i);
186
187        return true;
188}
189
190template <typename T>
191T FlexibleHeap<T>::Pop()
192{
193        if (mBuffer.empty())
194                return NULL;
195
196        Swap(0, (int)mBuffer.size() - 1);
197
198        T dead = mBuffer.back();
199        mBuffer.pop_back();
200
201        DownHeap(0);
202        dead->NotInHeap();
203
204        return dead;
205}
206
207
208template <typename T>
209T FlexibleHeap<T>::Erase(T t)
210{
211        if (!t->IsInHeap())
212                return (T)NULL;
213
214        const int i = t->GetHeapPos();
215
216        Swap(i, (int)mBuffer.size() - 1);
217       
218        mBuffer.pop_back();
219        t->NotInHeap();
220
221        if (mBuffer[i]->GetPriority() < t->GetPriority())
222                DownHeap(i);
223        else
224                UpHeap(i);
225
226        return t;
227}
228
229}
230
231// FLEXIBLEHEAP_H
232#endif
Note: See TracBrowser for help on using the repository browser.