Graph Drawing Toolkit
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 //#include <stdio.h> 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 //list_item *heap; 00047 std::vector <list_item> heap; 00048 gdtlist<Data> data; 00049 00050 Size heap_size; 00051 Size length; 00052 00053 //***************************************************** 00054 // Utility 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 // Gestione memoria 00064 //*************************************************** 00065 00066 void init(Size new_size) { 00067 assert(heap.size()==0 && data.empty()); 00068 //heap = new list_item[new_size]; 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 //heap = (list_item*) realloc(heap, length * sizeof(list_item)); 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 //heap = (list_item*) realloc(heap, length * sizeof(list_item)); 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 // Gestione dello heap 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); //Togliere la ricorsione 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 //free(heap); 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 //Erase item and assign to buffer 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 { //i != last() 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 //Restituisce un riferimento ad un buffer 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 //* Debug 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 * Iteration methods * 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
1.5.3