source: GTP/trunk/Lib/Vis/OnlineCullingCHC/src/FlexibleHeap.h @ 2360

Revision 2360, 4.7 KB checked in by mattausch, 17 years ago (diff)
RevLine 
[2360]1#ifndef FLEXIBLEHEAP_H
2#define FLEXIBLEHEAP_H
3
4#include <vector>
5
6
7namespace GtpVisibility {
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:
17        Heapable(): mPriority(0) { NotInHeap(); SetPriority(0.0f); }
18
19        inline bool IsInHeap() { return mPosition != NOT_IN_HEAP; }
20        inline void NotInHeap() { mPosition = NOT_IN_HEAP; }
21        inline int GetHeapPos() { return mPosition; }
22        inline void SetHeapPos(const int t) { mPosition = t; }
23
24        inline void  SetPriority(const float k) { mPriority = k; }
25        virtual float GetPriority() const = 0;
26
27protected:
28
29        float mPriority;
30        int mPosition;
31};
32
33
34/** This class implements a flexible heap for
35        use as a priority queue.
36
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.
40*/
41template<typename T>
42class FlexibleHeap
43{
44public:
45        FlexibleHeap() { }
46        FlexibleHeap(const unsigned int n): mBuffer(n) { }
47
48        void Push(T t) { Push(t, t->GetPriority()); }
49        void Push(T t, const float priority);
50        bool Update(T t) { return Update(t, t->GetPriority()); }
51        bool Update(T t, const float priority);
52
53        unsigned int Size() const { return (unsigned int)mBuffer.size(); }
54        bool Empty() const {return mBuffer.empty(); }
55        T Item(const unsigned int i) { return mBuffer[i]; }
56        const T Item(const unsigned int i) const { return mBuffer[i]; }
57        T Pop();
58        T Top() const { return (mBuffer.empty() ? (T)NULL : mBuffer.front()); }
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
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
195        Swap(0, (int)mBuffer.size() - 1);
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// FLEXIBLEHEAP_H
231#endif
Note: See TracBrowser for help on using the repository browser.