FineKernelToolKit
2.8.10
|
00001 /**************************************************************************** 00002 * 00003 * Copyright (c) 1999-2011, Fine Kernel Project, All rights reserved. 00004 * 00005 * Redistribution and use in source and binary forms, 00006 * with or without modification, are permitted provided that the 00007 * following conditions are met: 00008 * 00009 * - Redistributions of source code must retain the above 00010 * copyright notice, this list of conditions and the 00011 * following disclaimer. 00012 * 00013 * - Redistributions in binary form must reproduce the above 00014 * copyright notice, this list of conditions and the 00015 * following disclaimer in the documentation and/or 00016 * other materials provided with the distribution. 00017 * 00018 * - Neither the name of the copyright holders nor the names 00019 * of its contributors may be used to endorse or promote 00020 * products derived from this software without specific 00021 * prior written permission. 00022 * 00023 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00024 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00025 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 00026 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 00027 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 00028 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 00029 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 00030 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00031 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 00032 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 00033 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 00034 * POSSIBILITY OF SUCH DAMAGE. 00035 * 00036 ****************************************************************************/ 00037 /**************************************************************************** 00038 * 00039 * Copyright (c) 1999-2011, Fine Kernel Project, All rights reserved. 00040 * 00041 * 本ソフトウェアおよびソースコードのライセンスは、基本的に 00042 * 「修正 BSD ライセンス」に従います。以下にその詳細を記します。 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 typedef std::vector<int>::size_type _fk_h_s; 00100 00101 template<class TYPE> class fk_HeapBase { 00102 private: 00103 std::vector<TYPE *> array; 00104 std::vector<int> id; 00105 00106 int Compare(TYPE *a, TYPE *b) { 00107 if(*a < *b) return -1; 00108 if(*a > *b) return 1; 00109 return 0; 00110 } 00111 00112 int HeapData(TYPE *argData, int argS, int argE) { 00113 TYPE *pData; 00114 int comp; 00115 int index; 00116 00117 if(argE == -1) { 00118 pData = new TYPE(); 00119 *pData = *argData; 00120 array.insert(array.begin(), pData); 00121 id.insert(id.begin(), 1); 00122 return 1; 00123 } 00124 00125 if(argS == argE) { 00126 comp = Compare(argData, array[static_cast<_fk_h_s>(argS)]); 00127 if(comp == 0) { 00128 return id[static_cast<_fk_h_s>(argS)]; 00129 } 00130 00131 pData = new TYPE(); 00132 *pData = *argData; 00133 if(comp == -1) { 00134 array.insert(array.begin()+argS, pData); 00135 id.insert(id.begin()+argS, 00136 static_cast<int>(array.size())); 00137 } else { 00138 array.insert(array.begin()+argS+1, pData); 00139 id.insert(id.begin()+argS+1, 00140 static_cast<int>(array.size())); 00141 } 00142 return static_cast<int>(array.size()); 00143 } 00144 00145 if(argE - argS == 1) { 00146 comp = Compare(argData, 00147 array[static_cast<_fk_h_s>(argS)]); 00148 00149 if(comp == 0) { 00150 return id[static_cast<_fk_h_s>(argS)]; 00151 } 00152 00153 if(comp == -1) { 00154 pData = new TYPE(); 00155 *pData = *argData; 00156 array.insert(array.begin()+argS, pData); 00157 id.insert(id.begin()+argS, 00158 static_cast<int>(array.size())); 00159 return static_cast<int>(array.size()); 00160 } 00161 00162 return HeapData(argData, argE, argE); 00163 } 00164 00165 index = (argE-argS)/2 + argS; 00166 00167 comp = Compare(argData, array[static_cast<_fk_h_s>(index)]); 00168 00169 if(comp == 0) { 00170 return id[static_cast<_fk_h_s>(index)]; 00171 } 00172 00173 if(comp == -1) { 00174 return HeapData(argData, argS, index); 00175 } 00176 00177 if(comp == 1) { 00178 return HeapData(argData, index, argE); 00179 } 00180 00181 return 0; 00182 } 00183 00184 00185 public: 00186 00188 fk_HeapBase(void) { clear(); } 00189 00191 virtual ~fk_HeapBase() { clear(); } 00192 00194 00198 void clear(void); 00199 00205 int getSize(void) { 00206 return static_cast<int>(array.size()); 00207 } 00208 00221 int getID(TYPE *argV) { 00222 return HeapData(argV, 0, getSize()-1); 00223 } 00224 }; 00225 00226 template<class TYPE> void fk_HeapBase<TYPE>::clear(void) { 00227 for(unsigned int i = 0; i < array.size(); i++) { 00228 delete array[i]; 00229 } 00230 00231 array.clear(); 00232 id.clear(); 00233 return; 00234 } 00235 00236 #endif // !__FK_HEAP_BASE_HEADER__ 00237