FineKernelToolKit  2.8.10
FK/HeapBase.h
説明を見る。
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 
 全て クラス ネームスペース ファイル 関数 変数 型定義 列挙型 列挙型の値 フレンド マクロ定義