00001
00003 #ifndef __gdtbinary_heap2__
00004 #define __gdtbinary_heap2__
00005
00006 #include <assert.h>
00007 #include "ptr.h"
00008 #include "gdtlist.h"
00009 #include <iostream>
00010
00011 #include <vector>
00012
00013 #define CHECK(x) if (!(x)) {printf(#x" returned false\n"); return false;};
00014
00015 namespace gdt {
00016
00017 template <class T>
00018 struct stdless {
00019 bool operator () (const T& x, const T& y) {
00020 return x < y;
00021 }
00022 };
00023
00024 typedef list_item heap_item;
00025
00026 template<class P, class I, class less = stdless<P> >
00027 class gdtbinary_heap2 {
00028
00029 private:
00030
00031 typedef unsigned long Index;
00032 typedef unsigned long Size;
00033 Ptr buffer;
00034
00035 struct Data {
00036 Index heap_index;
00037 P prio;
00038 Ptr ptr;
00039
00040 Data() {}
00041
00042 Data(Index _heap_index, P _prio, Ptr _ptr) :
00043 heap_index(_heap_index), prio(_prio), ptr(_ptr) {}
00044 };
00045
00046
00047 std::vector <list_item> heap;
00048 gdtlist<Data> data;
00049
00050 Size heap_size;
00051 Size length;
00052
00053
00054
00055
00056
00057 inline bool less_op(list_item x, list_item y) const {
00058 less op;
00059 return op(data.inf(x).prio, data.inf(y).prio);
00060 }
00061
00062
00063
00064
00065
00066 void init(Size new_size) {
00067 assert(heap.size()==0 && data.empty());
00068
00069 heap= std::vector<list_item>(new_size);
00070 length = new_size;
00071 }
00072
00073 void double_table() {
00074 assert(heap.size()>0 && !data.empty() && length >= 1);
00075 length = length * 2 + 1;
00076 heap.resize(length * sizeof(list_item));
00077
00078 assert(heap.size()!=0);
00079 }
00080
00081 void half_table() {
00082 assert(heap.size()>0 && !data.empty() && length >= 15);
00083 length = ((length + 1) / 2) - 1;
00084 assert(heap_size < length);
00085 heap.resize(length * sizeof(list_item));
00086
00087 assert(heap.size()!=0);
00088 }
00089
00090 inline void swap(Index x, Index y) {
00091 assert(consistent_list());
00092 list_item aux = heap[x];
00093 heap[x] = heap[y];
00094 heap[y] = aux;
00095 data[heap[x]].heap_index = x;
00096 data[heap[y]].heap_index = y;
00097 assert(consistent_list());
00098 }
00099
00100 inline void assign_buffer(list_item x) {
00101 if (buffer) PTR_DELETE(I, buffer);
00102 buffer = data.inf(x).ptr;
00103 }
00104
00105
00106
00107
00108
00109 inline void heapify(Index i) {
00110 Index l = left_child(i);
00111 Index r = right_child(i);
00112 Index largest;
00113 if (l < heap_size && less_op(heap[i], heap[l]))
00114 largest = l;
00115 else
00116 largest = i;
00117 if (r < heap_size && less_op(heap[largest], heap[r]))
00118 largest = r;
00119 if (largest != i) {
00120 swap(largest, i);
00121 heapify(largest);
00122 }
00123 }
00124
00125 inline Index parent(Index i) const {
00126 return (i + 1) / 2 - 1;
00127 }
00128
00129 inline Index left_child(Index i) const {
00130 return i*2 + 1;
00131 }
00132
00133 inline Index right_child(Index i) const {
00134 return i*2 + 2;
00135 }
00136
00137 inline Index last() const {
00138 return heap_size - 1;
00139 }
00140
00141 public:
00142
00143 const P& prio(list_item i) const {
00144 assert(i);
00145 return data[i].prio;
00146 }
00147
00148 const I& inf(list_item i) const {
00149 assert(i);
00150 return PTR_CONST_ACCESS(I, data[i].ptr);
00151 }
00152
00153 gdtbinary_heap2() : buffer(NULL), heap_size(0) {
00154 init(1);
00155 }
00156
00157 ~gdtbinary_heap2() {
00158 heap.clear();
00159
00160 }
00161
00162 void increase_key(heap_item it, const P& p) {
00163 assert(it);
00164 less op;
00165 assert(op (prio(it),p));
00166 data[it].prio = p;
00167 Index i = data[it].heap_index;
00168 while (i > 0 && op (prio(heap[parent(i)]), prio(heap[i]))) {
00169 Index p = parent(i);
00170 swap(i, p);
00171 i = p;
00172 }
00173 heapify(i);
00174 assert(consistency_check());
00175 }
00176
00177
00178 list_item insert(const P& pr, const I& info) {
00179
00180 if (heap_size == length) double_table();
00181 ++heap_size;
00182 Index i = last();
00183 less op;
00184 while (i > 0 && ( op( prio( heap[parent(i)] ), pr ) ) ) {
00185 heap[i] = heap[parent(i)];
00186 data[heap[i]].heap_index = i;
00187 i = parent(i);
00188 }
00189 list_item it = data.append(Data(i, pr, ptr_copy(info)));
00190 heap[i] = it;
00191
00192 assert(consistency_check());
00193
00194 return it;
00195 }
00196
00197 void remove(list_item it) {
00198 assert(consistency_check());
00199
00200 assert(heap_size > 0);
00201 Index i = data.inf(it).heap_index;
00202 assert(i < heap_size && i >= 0);
00203 data.erase(it);
00204
00205
00206 if (i == last()) {
00207 --heap_size;
00208 }
00209 else {
00210 while (i != 0) {
00211 Index p = parent(i);
00212 heap[i] = heap[p];
00213 assert(data[heap[i]].heap_index == p);
00214 data[heap[i]].heap_index = i;
00215 assert(data[heap[i]].heap_index == i);
00216 i = p;
00217 }
00218 heap[0] = heap[heap_size-1];
00219 data[heap[0]].heap_index = 0;
00220 --heap_size;
00221 heapify(0);
00222 }
00223
00224 if (length >= 15 && heap_size == (length + 1) / 4) half_table();
00225 assert(consistency_check());
00226 }
00227
00228
00229 const I& extract_max() {
00230 assert(heap_size > 0);
00231 assign_buffer(heap[0]);
00232 data.erase(heap[0]);
00233
00234 if (heap_size>1) {
00235 heap[0] = heap[heap_size-1];
00236 data[heap[0]].heap_index = 0;
00237 }
00238 --heap_size;
00239 heapify(0);
00240
00241 assert(consistency_check());
00242 if (length >= 15 && heap_size == (length + 1) / 4) half_table();
00243 assert(consistency_check());
00244 return PTR_CONST_ACCESS(I, buffer);
00245 }
00246
00247 const I& get_max() const {
00248 assert(heap_size > 0);
00249 return PTR_CONST_ACCESS(I, heap[0]);
00250 }
00251
00252 heap_item find_max() const {
00253 return heap_size > 0 ? heap[0] : NULL;
00254 }
00255
00256 Size size() const {
00257 return heap_size;
00258 }
00259
00260
00261
00262
00263
00264 bool consistency_check() const {
00265 CHECK(heap_size <= length);
00266 CHECK(heap_size == (unsigned long) data.size());
00267 CHECK(is_heap(0));
00268 CHECK(consistent_list());
00269 return true;
00270 }
00271
00272 bool consistent_list() const {
00273 list_item it;
00274 forall_items(it, data) {
00275 if (heap[data.inf(it).heap_index] != it) return false;
00276 }
00277 return true;
00278 }
00279
00280 bool is_heap(Index i) const {
00281 less op;
00282 bool res = true;
00283 if (right_child(i) < heap_size) {
00284 res = res &&
00285 !(op (prio(heap[i]), prio(heap[right_child(i)]))) &&
00286 is_heap(right_child(i));
00287 }
00288 if (res && (left_child(i) < heap_size) ) {
00289 res = res &&
00290 !(op (prio(heap[i]), prio(heap[left_child(i)]))) &&
00291 is_heap(left_child(i));
00292 }
00293 return res;
00294 }
00295
00296 void show_list() const {
00297 std::cout << "List contents " << std::endl;
00298 list_item it = data.first();
00299 while (it) {
00300 std::cout << "("<< PTR_CONST_ACCESS(I, data[it].ptr)<< ",i" << data[it].heap_index <<")" << " --> ";
00301 it = data.succ(it);
00302 }
00303 std::cout <<"NULL\n";
00304 }
00305
00306 void show_heap() const {
00307 std::cout << "Heap contents " << std::endl;
00308 if (heap_size == 0) std::cout << "empty" << std::endl;
00309 for (int i = 0; i < heap_size; ++i) {
00310 std::cout << PTR_CONST_ACCESS(I, data[heap[i]].ptr) << " ";
00311 }
00312 std::cout << "\n";
00313 }
00314
00315 void show() const {
00316 show_list();
00317 show_heap();
00318 }
00319
00320
00321
00322
00323
00324
00325
00326 typedef heap_item item;
00327
00328 heap_item first_item() const { return data.first(); }
00329 heap_item last_item() const { return data.last(); }
00330 heap_item next_item(heap_item p) const { return data.next_item(p); }
00331 heap_item pred_item(heap_item p) const { return data.pred_item(p); }
00332
00333 };
00334 }
00335
00336 #endif