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 #ifndef FIBONACCI_H_ 00013 #define FIBONACCI_H_ 00014 00015 #include <shogun/base/SGObject.h> 00016 #include <shogun/lib/common.h> 00017 #include <shogun/mathematics/Math.h> 00018 00019 namespace shogun 00020 { 00021 00022 #ifndef DOXYGEN_SHOULD_SKIP_THIS 00023 struct FibonacciHeapNode 00024 { 00026 FibonacciHeapNode* parent; 00027 00029 FibonacciHeapNode* child; 00030 00032 FibonacciHeapNode* left; 00033 00035 FibonacciHeapNode* right; 00036 00038 int32_t rank; 00039 00041 bool marked; 00042 00044 int32_t index; 00045 00047 float64_t key; 00048 }; 00049 00056 class CFibonacciHeap: public CSGObject 00057 { 00058 public: 00059 00060 CFibonacciHeap(); 00061 00063 CFibonacciHeap(int32_t capacity); 00064 00065 virtual inline const char* get_name() const 00066 { 00067 return "FibonacciHeap"; 00068 } 00069 00070 virtual ~CFibonacciHeap(); 00071 00072 00073 int32_t get_num_nodes() const 00074 { 00075 return num_nodes; 00076 } 00077 00078 int32_t get_num_trees() 00079 { 00080 return num_trees; 00081 } 00082 00083 int32_t get_capacity() 00084 { 00085 return max_num_nodes; 00086 } 00087 00091 void insert(int32_t index, float64_t key); 00092 00097 int32_t extract_min(float64_t &ret_key); 00098 00100 void clear(); 00101 00105 int32_t get_key(int32_t index, float64_t &ret_key); 00106 00110 void decrease_key(int32_t index, float64_t key); 00111 00112 void debug_print(); 00113 00114 private: 00116 void add_to_roots(FibonacciHeapNode *up_node); 00117 00119 void consolidate(); 00120 00122 void link_nodes(FibonacciHeapNode *right, FibonacciHeapNode *left); 00123 00125 void clear_node(int32_t index); 00126 00128 void cut(FibonacciHeapNode *child, FibonacciHeapNode *parent); 00129 00130 void cascading_cut(FibonacciHeapNode* tree); 00131 00132 protected: 00134 FibonacciHeapNode* min_root; 00135 00137 FibonacciHeapNode** nodes; 00138 00140 int32_t num_nodes; 00141 00143 int32_t num_trees; 00144 00146 int32_t max_num_nodes; 00147 00149 FibonacciHeapNode **A; 00150 00152 int32_t Dn; 00153 }; 00154 #endif /* DOXYGEN_SHOULD_SKIP_THIS */ 00155 00156 } 00157 #endif /* FIBONACCI_H_ */