00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072 #ifndef __FK_HEAP_BASE_HEADER__
00073 #define __FK_HEAP_BASE_HEADER__
00074
00075 #include <vector>
00076
00078
00099 template<class TYPE> class fk_HeapBase {
00100 private:
00101 std::vector<TYPE *> array;
00102 std::vector<int> id;
00103
00104 int Compare(TYPE *a, TYPE *b) {
00105 if(*a < *b) return -1;
00106 if(*a > *b) return 1;
00107 return 0;
00108 }
00109
00110 int HeapData(TYPE *argData, int argS, int argE) {
00111 TYPE *pData;
00112 int comp;
00113 int index;
00114
00115 if(argE == -1) {
00116 pData = new TYPE();
00117 *pData = *argData;
00118 array.insert(array.begin(), pData);
00119 id.insert(id.begin(), 1);
00120 return 1;
00121 }
00122
00123 if(argS == argE) {
00124 comp = Compare(argData, array[argS]);
00125 if(comp == 0) {
00126 return id[argS];
00127 }
00128
00129 pData = new TYPE();
00130 *pData = *argData;
00131 if(comp == -1) {
00132 array.insert(array.begin()+argS, pData);
00133 id.insert(id.begin()+argS, array.size());
00134 } else {
00135 array.insert(array.begin()+argS+1, pData);
00136 id.insert(id.begin()+argS+1, array.size());
00137 }
00138 return array.size();
00139 }
00140
00141 if(argE - argS == 1) {
00142 comp = Compare(argData, array[argS]);
00143
00144 if(comp == 0) {
00145 return id[argS];
00146 }
00147
00148 if(comp == -1) {
00149 pData = new TYPE();
00150 *pData = *argData;
00151 array.insert(array.begin()+argS, pData);
00152 id.insert(id.begin()+argS, array.size());
00153 return array.size();
00154 }
00155
00156 return HeapData(argData, argE, argE);
00157 }
00158
00159 index = (argE-argS)/2 + argS;
00160
00161 comp = Compare(argData, array[index]);
00162
00163 if(comp == 0) {
00164 return id[index];
00165 }
00166
00167 if(comp == -1) {
00168 return HeapData(argData, argS, index);
00169 }
00170
00171 if(comp == 1) {
00172 return HeapData(argData, index, argE);
00173 }
00174
00175 return 0;
00176 }
00177
00178
00179 public:
00180
00182 fk_HeapBase(void) { clear(); }
00183
00185 ~fk_HeapBase() { clear(); }
00186
00188
00192 void clear(void);
00193
00199 int getSize(void) {
00200 return array.size();
00201 }
00202
00215 int getID(TYPE *argV) {
00216 return HeapData(argV, 0, getSize()-1);
00217 }
00218 };
00219
00220 template<class TYPE> void fk_HeapBase<TYPE>::clear(void) {
00221 for(unsigned int i = 0; i < array.size(); i++) {
00222 delete array[i];
00223 }
00224
00225 array.clear();
00226 id.clear();
00227 return;
00228 }
00229
00230 #endif // !__FK_HEAP_BASE_HEADER__
00231