SHOGUN
v1.1.0
|
00001 /* 00002 * This program is free software; you can redistribute it and/or modify 00003 * it under the terms of the GNU General Public License as published by 00004 * the Free Software Foundation; either version 3 of the License, or 00005 * (at your option) any later version. 00006 * 00007 * Written (W) 2011 Evgeniy Andreev (gsomix) 00008 * 00009 * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society 00010 */ 00011 00012 #include <shogun/lib/FibonacciHeap.h> 00013 00014 using namespace shogun; 00015 00016 CFibonacciHeap::CFibonacciHeap() 00017 { 00018 min_root = NULL; 00019 00020 max_num_nodes = 0; 00021 nodes = NULL; 00022 Dn = 0; 00023 00024 num_nodes = 0; 00025 num_trees = 0; 00026 } 00027 00028 CFibonacciHeap::CFibonacciHeap(int32_t capacity) 00029 { 00030 min_root = NULL; 00031 00032 max_num_nodes = capacity; 00033 nodes = SG_MALLOC(FibonacciHeapNode* , max_num_nodes); 00034 for(int32_t i = 0; i < max_num_nodes; i++) 00035 { 00036 nodes[i] = new FibonacciHeapNode; 00037 clear_node(i); 00038 } 00039 00040 Dn = 1 + (int32_t)(CMath::log2(max_num_nodes)); 00041 A = SG_MALLOC(FibonacciHeapNode* , Dn); 00042 for(int32_t i = 0; i < Dn; i++) 00043 { 00044 A[i] = NULL; 00045 } 00046 00047 num_nodes = 0; 00048 num_trees = 0; 00049 } 00050 00051 CFibonacciHeap::~CFibonacciHeap() 00052 { 00053 for(int32_t i = 0; i < max_num_nodes; i++) 00054 { 00055 if(nodes[i] != NULL) 00056 delete nodes[i]; 00057 } 00058 SG_FREE(nodes); 00059 SG_FREE(A); 00060 } 00061 00062 void CFibonacciHeap::insert(int32_t index, float64_t key) 00063 { 00064 if(index >= max_num_nodes || index < 0) 00065 return; 00066 00067 if(nodes[index]->index != -1) 00068 return; // node is not empty 00069 00070 // init "new" node in array 00071 nodes[index]->child = NULL; 00072 nodes[index]->parent = NULL; 00073 00074 nodes[index]->rank = 0; 00075 nodes[index]->index = index; 00076 nodes[index]->key = key; 00077 nodes[index]->marked = false; 00078 00079 add_to_roots(nodes[index]); 00080 num_nodes++; 00081 } 00082 00083 int32_t CFibonacciHeap::extract_min(float64_t &ret_key) 00084 { 00085 FibonacciHeapNode *min_node; 00086 FibonacciHeapNode *child, *next_child; 00087 00088 int32_t result; 00089 00090 if(num_nodes == 0) 00091 return -1; 00092 00093 min_node = min_root; 00094 if(min_node == NULL) 00095 return -1; // heap is empty now 00096 00097 child = min_node->child; 00098 while(child != NULL && child->parent != NULL) 00099 { 00100 next_child = child->right; 00101 00102 // delete current child from childs list 00103 child->left->right = child->right; 00104 child->right->left = child->left; 00105 00106 add_to_roots(child); 00107 00108 // next iteration 00109 child = next_child; 00110 } 00111 00112 // delete minimun from root list 00113 min_node->left->right = min_node->right; 00114 min_node->right->left = min_node->left; 00115 00116 num_trees--; 00117 00118 if(min_node == min_node->right) 00119 { 00120 min_root = NULL; // remove last element 00121 } 00122 else 00123 { 00124 min_root = min_node->right; 00125 consolidate(); 00126 } 00127 00128 result = min_node->index; 00129 ret_key = min_node->key; 00130 clear_node(result); 00131 00132 num_nodes--; 00133 00134 return result; 00135 } 00136 00137 void CFibonacciHeap::clear() 00138 { 00139 min_root = NULL; 00140 00141 // clear all nodes 00142 for(int32_t i = 0; i < max_num_nodes; i++) 00143 { 00144 clear_node(i); 00145 } 00146 00147 num_nodes = 0; 00148 num_trees = 0; 00149 } 00150 00151 int32_t CFibonacciHeap::get_key(int32_t index, float64_t &ret_key) 00152 { 00153 if(index >= max_num_nodes || index < 0) 00154 return -1; 00155 if(nodes[index]->index == -1) 00156 return -1; 00157 00158 int32_t result = nodes[index]->index; 00159 ret_key = nodes[index]->key; 00160 00161 return result; 00162 } 00163 00164 void CFibonacciHeap::decrease_key(int32_t index, float64_t key) 00165 { 00166 FibonacciHeapNode* parent; 00167 00168 if(index >= max_num_nodes || index < 0) 00169 return; 00170 if(nodes[index]->index == -1) 00171 return; // node is empty 00172 if(key > nodes[index]->key) 00173 return; 00174 00175 00176 nodes[index]->key = key; 00177 00178 parent = nodes[index]->parent; 00179 00180 if(parent != NULL && nodes[index]->key < parent->key) 00181 { 00182 cut(nodes[index], parent); 00183 cascading_cut(parent); 00184 } 00185 00186 if(nodes[index]->key < min_root->key) 00187 min_root = nodes[index]; 00188 } 00189 00190 00191 void CFibonacciHeap::add_to_roots(FibonacciHeapNode *up_node) 00192 { 00193 if(min_root == NULL) 00194 { 00195 // if heap is empty, node becomes circular root list 00196 min_root = up_node; 00197 00198 up_node->left = up_node; 00199 up_node->right = up_node; 00200 } 00201 else 00202 { 00203 // insert node to root list 00204 up_node->right = min_root->right; 00205 up_node->left = min_root; 00206 00207 up_node->left->right = up_node; 00208 up_node->right->left = up_node; 00209 00210 // nomination of new minimum node 00211 if(up_node->key < min_root->key) 00212 { 00213 min_root = up_node; 00214 } 00215 } 00216 00217 up_node->parent = NULL; 00218 num_trees++; 00219 } 00220 00221 void CFibonacciHeap::consolidate() 00222 { 00223 FibonacciHeapNode *x, *y, *w; 00224 int32_t d; 00225 00226 for(int32_t i = 0; i < Dn; i++) 00227 { 00228 A[i] = NULL; 00229 } 00230 00231 min_root->left->right = NULL; 00232 min_root->left = NULL; 00233 w = min_root; 00234 00235 do 00236 { 00237 x = w; 00238 d = x->rank; 00239 w = w->right; 00240 00241 while(A[d] != NULL) 00242 { 00243 y = A[d]; 00244 00245 if(y->key < x->key) 00246 { 00247 FibonacciHeapNode *temp; 00248 00249 temp = y; 00250 y = x; 00251 x = temp; 00252 } 00253 00254 link_nodes(y, x); 00255 00256 A[d] = NULL; 00257 d++; 00258 } 00259 A[d] = x; 00260 } 00261 while(w != NULL); 00262 00263 min_root = NULL; 00264 num_trees = 0; 00265 00266 for(int32_t i = 0; i < Dn; i++) 00267 { 00268 if(A[i] != NULL) 00269 { 00270 A[i]->marked = false; 00271 add_to_roots(A[i]); 00272 } 00273 } 00274 } 00275 00276 void CFibonacciHeap::link_nodes(FibonacciHeapNode *y, FibonacciHeapNode *x) 00277 { 00278 if(y->right != NULL) 00279 y->right->left = y->left; 00280 if(y->left != NULL) 00281 y->left->right = y->right; 00282 00283 num_trees--; 00284 00285 y->left = y; 00286 y->right = y; 00287 00288 y->parent = x; 00289 00290 if(x->child == NULL) 00291 { 00292 x->child = y; 00293 } 00294 else 00295 { 00296 y->left = x->child; 00297 y->right = x->child->right; 00298 00299 x->child->right = y; 00300 y->right->left = y; 00301 } 00302 00303 x->rank++; 00304 00305 y->marked = false; 00306 } 00307 00308 void CFibonacciHeap::clear_node(int32_t index) 00309 { 00310 nodes[index]->parent = NULL; 00311 nodes[index]->child = NULL; 00312 nodes[index]->left = NULL; 00313 nodes[index]->right = NULL; 00314 00315 nodes[index]->rank = 0; 00316 nodes[index]->index = -1; 00317 nodes[index]->key = 0; 00318 00319 nodes[index]->marked = false; 00320 } 00321 00322 void CFibonacciHeap::cut(FibonacciHeapNode *child, FibonacciHeapNode *parent) 00323 { 00324 if(parent->child == child) 00325 parent->child = child->right; 00326 00327 if(parent->child == child) 00328 parent->child = NULL; 00329 00330 parent->rank--; 00331 00332 child->left->right = child->right; 00333 child->right->left = child->left; 00334 child->marked = false; 00335 00336 add_to_roots(child); 00337 } 00338 00339 void CFibonacciHeap::cascading_cut(FibonacciHeapNode *tree) 00340 { 00341 FibonacciHeapNode *temp; 00342 00343 temp = tree->parent; 00344 if(temp != NULL) 00345 { 00346 if(!tree->marked) 00347 { 00348 tree->marked = true; 00349 } 00350 else 00351 { 00352 cut(tree, temp); 00353 cascading_cut(temp); 00354 } 00355 } 00356 } 00357 00358 void CFibonacciHeap::debug_print() 00359 { 00360 SG_SPRINT("%d %d\n", num_trees, num_nodes); 00361 for(int32_t i = 0; i < max_num_nodes; i++) 00362 { 00363 if(nodes[i]->index == -1) 00364 { 00365 SG_SPRINT("None\n"); 00366 } 00367 else 00368 { 00369 SG_SPRINT("%f\n",nodes[i]->key); 00370 } 00371 } 00372 }