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