source: GTP/trunk/Lib/Vis/Preprocessing/src/MyHeap.cpp @ 1099

Revision 1099, 2.5 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include "MyHeap.h"
2
3
4namespace GtpVisibilityPreprocessor {
5
6
7/*****************************************************************************/
8/*                         MyHeap implementation                             *
9/*****************************************************************************/
10
11
12
13inline void MyHeap::Place(Heapable *x, unsigned int i)
14{
15    mBuffer[i] = x;
16    x->SetHeapPos(i);
17}
18
19
20void MyHeap::Swap(unsigned int i, unsigned int j)
21{
22    Heapable *tmp = mBuffer[i];
23
24    Place(mBuffer[j], i);
25    Place(tmp, j);
26}
27
28
29void MyHeap::UpHeap(unsigned int i)
30{
31    Heapable *moving = mBuffer[i];
32    unsigned int index = i;
33    unsigned int p = Parent(i);
34
35    while ((index > 0) && (moving->SetPriority() > mBuffer[p]->SetPriority()))
36    {
37                Place(mBuffer[p], index);
38                index = p;
39                p = Parent(p);
40    }
41
42    if (index != i)
43        {
44                Place(moving, index);
45        }
46}
47
48
49void MyHeap::DownHeap(unsigned int i)
50{
51    Heapable *moving = mBuffer[i];
52
53    unsigned int index = i;
54    unsigned int l = Left(i);
55    unsigned int r = Right(i);
56    unsigned int largest;
57
58        while (l < (int)mBuffer.size())
59        {
60                if ((r < (unsigned int)mBuffer.size()) && (mBuffer[l]->SetPriority() < mBuffer[r]->SetPriority()))
61                        largest = r;
62                else
63                        largest = l;
64
65                if (moving->SetPriority() < mBuffer[largest]->SetPriority())
66                {
67                        Place(mBuffer[largest], index);
68                        index = largest;
69                        l = Left(index);
70                        r = Right(index);
71                }
72                else
73                {
74                        break;
75                }
76        }
77
78    if (index != i)
79        {
80                Place(moving, index);
81        }
82}
83
84
85void MyHeap::Push(Heapable *t, float v)
86{
87    t->SetPriority(v);
88
89        unsigned int i = (unsigned int)mBuffer.size();
90
91        t->SetHeapPos(i);
92        mBuffer.push_back(t);
93   
94    UpHeap(i);
95}
96
97
98bool MyHeap::Update(Heapable *t, float v)
99{
100    if (t->IsInHeap())
101                return false;
102
103    t->SetPriority(v);
104
105    unsigned int i = t->GetHeapPos();
106
107    if ((i > 0) && (v > mBuffer[Parent(i)]->SetPriority()))
108                UpHeap(i);
109    else
110                DownHeap(i);
111
112        return true;
113}
114
115
116Heapable *MyHeap::Pop()
117{
118    if (mBuffer.empty())
119                return NULL;
120
121    Swap(0, mBuffer.size() - 1);
122   
123        Heapable *dead = mBuffer.back();
124        mBuffer.pop_back();
125
126    DownHeap(0);
127    dead->NotInHeap();
128
129    return dead;
130}
131
132
133Heapable *MyHeap::Erase(Heapable *t)
134{
135    if (!t->IsInHeap())
136                return NULL;
137
138    int i = t->GetHeapPos();
139
140    Swap(i, mBuffer.size() - 1);
141
142        mBuffer.pop_back();
143    t->NotInHeap();
144
145    if (mBuffer[i]->SetPriority() < t->SetPriority())
146                DownHeap(i);
147        else
148                UpHeap(i);
149
150    return t;
151}
152}
Note: See TracBrowser for help on using the repository browser.