1 #ifndef VERTEX_HEAP
2 #define VERTEX_HEAP
3 
4 #include <vector>
5 #include <iostream>
6 
7 class VertexHeap{
8 
9 public:
10 
11     class ErrorValue {
12     public:
13 
14         float value;
15 
16         bool blocked:1;
17 
18     public:
ErrorValue()19         ErrorValue() : value(0), blocked(false){}
20 
21 //      ErrorValue(float err, bool b) : featureLineStatus(0) {
22 //          value   = err;
23 //          blocked = b;
24 //      }
25 
26 
27 
block()28         void block() {blocked = true;}
29 
unblock()30         void unblock() {blocked = false;}
31 
isBlocked()32         bool isBlocked() const {
33             return blocked;
34         }
35 
36         friend int operator > (const ErrorValue& a, const ErrorValue& b) {
37             if (a.isBlocked() == b.isBlocked())
38                 return a.value > b.value;
39             else
40                 return (a.isBlocked()) ? 1 : 0;
41         }
42 
43         friend int operator < (const ErrorValue& a, const ErrorValue& b) {
44             if (a.isBlocked() == b.isBlocked())
45                 return a.value < b.value;
46             else
47                 return (a.isBlocked()) ? 0 : 1;
48         }
49     };
50 
51     class HeapEntry {
52     public:
53 
54         int vertex;
55         ErrorValue    error;
56 
57         //////////////////////////////////
58 
59     };
60 
61 
62 public:
63 
print()64     void print() {
65         for (int i=0; i<heapSize; i++)
66             std::cout << "Nr. " << i << ",   value = " << array[i].error.value << ",   blocked = " << array[i].error.isBlocked() << std::endl;
67     }
68 
buildHeap(const std::vector<ErrorValue> & errors)69     void buildHeap(const std::vector<ErrorValue>& errors) {
70 
71         heapSize = errors.size();
72         array.resize(heapSize);
73         vertexNumbers.resize(heapSize);
74 
75         // enter vertices into array in any order
76         int i;
77         //for (cV=inList.first(); cV; cV=inList.succ(cV), i++) {
78         for (i=0; i<heapSize; i++) {
79             array[i].vertex = i;
80             //cV->number = i;
81             vertexNumbers[i] = i;
82             array[i].error = errors[i];
83         }
84 
85         // heapify the whole thing
86         for (i= (heapSize-2)/2; i>=0; i--)
87             heapify(i);
88     }
89 
90     ///
getMinError()91     float getMinError() const {
92         assert(array.size());
93         return array[0].error.value;
94     }
95 
96     ///
getMinErrorStatus()97     ErrorValue getMinErrorStatus() const {
98         assert(array.size());
99         return array[0].error;
100     }
101 
102     ///
isBlockedMin()103     bool isBlockedMin() const {
104         if (!heapSize)
105             return true;
106 
107         return array[0].error.isBlocked();
108     }
109 
110     ///
getMin()111     int getMin() const {
112         if (array.size())
113             return array[0].vertex;
114         else
115             return -1;
116     }
117 
getError(int v)118     ErrorValue getError(int v) const {
119         return array[vertexNumbers[v]].error;
120     }
121 
122     ///
extractMin()123     int extractMin() {
124 
125         //assert(isHeap(0));
126 
127         if (!array.size())
128             return -1;
129 
130         int min = array[0].vertex;
131         array[0] = array[heapSize-1];
132         //array[0].vertex->number = 0;
133         vertexNumbers[array[0].vertex] = 0;
134 
135         heapSize--;
136         heapify(0);
137         return min;
138     }
139 
140     ///
insert(int v,const ErrorValue & err)141     void insert(int v, const ErrorValue& err) {
142 
143         int i = heapSize;
144         heapSize++;
145 
146         while (i>0 && array[parent(i)].error > err) {
147             array[i] = array[parent(i)];
148             //array[i].vertex->number = i;
149             vertexNumbers[array[i].vertex] = i;
150 
151             i = parent(i);
152         }
153 
154         array[i].vertex  = v;
155         array[i].error   = err;
156         //v->number = i;
157         vertexNumbers[v] = i;
158     }
159 
reposition(int v,const ErrorValue & newError)160     void reposition(int v, const ErrorValue& newError) {
161 
162         //assert(array[v->number].vertex==v);
163         assert(array[vertexNumbers[v]].vertex == v);
164 
165         //ErrorValue oldError = array[v->number].error;
166         ErrorValue oldError = array[vertexNumbers[v]].error;
167 
168         if (newError>oldError){
169             //array[v->number].error   = newError;
170             array[vertexNumbers[v]].error = newError;
171             //heapify(v->number);
172             heapify(vertexNumbers[v]);
173         } else {
174 
175             //int i = v->number;
176             int i = vertexNumbers[v];
177 
178             while (i>0 && array[parent(i)].error > newError) {
179                 array[i] = array[parent(i)];
180                 //array[i].vertex->number = i;
181                 vertexNumbers[array[i].vertex] = i;
182 
183                 i = parent(i);
184             }
185 
186 
187         array[i].vertex = v;
188         array[i].error  = newError;
189         //v->number = i;
190         vertexNumbers[v] = i;
191         }
192     }
193 
194 protected:
195 
196 
heapify(int i)197     void heapify(int i) {
198 
199         int l = left(i);
200         int r = right(i);
201         int smallest;
202 
203         if (l<heapSize && array[l].error < array[i].error)
204             smallest = l;
205         else
206             smallest = i;
207 
208         if (r<heapSize && array[r].error < array[smallest].error)
209             smallest = r;
210 
211         if (smallest!=i){
212             exchange(i, smallest);
213             heapify(smallest);
214         }
215     }
216 
217 
218 
219 
220 
parent(int i)221     int parent(int i) const {return (i-1)/2;}
222 
left(int i)223     int left(int i) const {return 2*i+1;}
224 
right(int i)225     int right(int i) const {return 2*i+2;}
226 
exchange(int k,int l)227     void exchange(int k, int l) {
228         std::swap(array[l], array[k]);
229 
230         vertexNumbers[array[k].vertex] = k;
231         vertexNumbers[array[l].vertex] = l;
232 
233     }
234 
235     int heapSize;
236 
237     std::vector<HeapEntry> array;
238 
239     std::vector<int> vertexNumbers;
240 
241 };
242 
243 #endif
244