- メインページ
- クラス
- ファイル

- ファイル一覧
- ファイルメンバ

# FK/HeapBase.h

説明を見る。

    00001 /****************************************************************************
    00002  *
    00003  *  Copyright (c) 1999-2009, 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-2009, 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 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