HeapBase.h

[詳解]

#if !defined(__FK_HEAP_BASE_HEADER__)
#define __FK_HEAP_BASE_HEADER__
 
#include <vector>
 
namespace FK {
#if !defined(FK_DOXYGEN_USER_PROCESS)
    using _fk_h_s = std::vector<int>::size_type;
#endif
 
 
    template<class TYPE> class fk_HeapBase {
    public:
        fk_HeapBase(void) { clear(); }
 
        virtual ~fk_HeapBase() { clear(); }
 
 
        void clear(void);
 
 
        int getSize(void) {
            return int(array.size());
        }
 
 
        int getID(TYPE *argV) {
            return HeapData(argV, 0, getSize()-1);
        }
 
    private:
        std::vector<TYPE *>     array;
        std::vector<int>        id;
 
        int Compare(TYPE *a, TYPE *b) {
            if(*a < *b) return -1;
            if(*a > *b) return 1;
            return 0;
        }
 
        int HeapData(TYPE *argData, int argS, int argE) {
            TYPE    *pData;
            int     comp;
            int     index;
 
            if(argE == -1) {
                pData = new TYPE();
                *pData = *argData;
                array.insert(array.begin(), pData);
                id.insert(id.begin(), 1);
                return 1;
            }
 
            if(argS == argE) {
                comp = Compare(argData, array[_fk_h_s(argS)]);
                if(comp == 0) {
                    return id[_fk_h_s(argS)];
                }
 
                pData = new TYPE();
                *pData = *argData;
                if(comp == -1) {
                    array.insert(array.begin()+argS, pData);
                    id.insert(id.begin()+argS,
                              int(array.size()));
                } else {
                    array.insert(array.begin()+argS+1, pData);
                    id.insert(id.begin()+argS+1,
                              int(array.size()));
                }
                return int(array.size());
            }
 
            if(argE - argS == 1) {
                comp = Compare(argData,
                               array[_fk_h_s(argS)]);
 
                if(comp == 0) {
                    return id[_fk_h_s(argS)];
                }
 
                if(comp == -1) {
                    pData = new TYPE();
                    *pData = *argData;
                    array.insert(array.begin()+argS, pData);
                    id.insert(id.begin()+argS,
                              int(array.size()));
                    return int(array.size());
                }
 
                return HeapData(argData, argE, argE);
            }
 
            index = (argE-argS)/2 + argS;
 
            comp = Compare(argData, array[_fk_h_s(index)]);
 
            if(comp == 0) {
                return id[_fk_h_s(index)];
            }
 
            if(comp == -1) {
                return HeapData(argData, argS, index);
            }
 
            if(comp == 1) {
                return HeapData(argData, index, argE);
            }
 
            return 0;
        }
    };
 
    template<class TYPE> void fk_HeapBase<TYPE>::clear(void) {
        for(unsigned int i = 0; i < array.size(); i++) {
            delete array[i];
        }
 
        array.clear();
        id.clear();
        return;
    }
}
 
#endif // !__FK_HEAP_BASE_HEADER__
 
/****************************************************************************
 *
 *  Copyright (c) 1999-2024, Fine Kernel Project, All rights reserved.
 *
 *  Redistribution and use in source and binary forms,
 *  with or without modification, are permitted provided that the
 *  following conditions are met:
 *
 *      - Redistributions of source code must retain the above
 *          copyright notice, this list of conditions and the
 *          following disclaimer.
 *
 *      - Redistributions in binary form must reproduce the above
 *          copyright notice, this list of conditions and the
 *          following disclaimer in the documentation and/or
 *          other materials provided with the distribution.
 *
 *      - Neither the name of the copyright holders nor the names
 *          of its contributors may be used to endorse or promote
 *          products derived from this software without specific
 *          prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 *  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 *  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 *  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 *  STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 *  IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE. 
 *
 ****************************************************************************/
/****************************************************************************
 *
 *  Copyright (c) 1999-2024, Fine Kernel Project, All rights reserved.
 *
 *  本ソフトウェアおよびソースコードのライセンスは、基本的に
 *  「修正 BSD ライセンス」に従います。以下にその詳細を記します。
 *
 *  ソースコード形式かバイナリ形式か、変更するかしないかを問わず、
 *  以下の条件を満たす場合に限り、再頒布および使用が許可されます。
 *
 *  - ソースコードを再頒布する場合、上記の著作権表示、本条件一覧、
 *      および下記免責条項を含めること。
 *
 *  - バイナリ形式で再頒布する場合、頒布物に付属のドキュメント等の
 *      資料に、上記の著作権表示、本条件一覧、および下記免責条項を
 *      含めること。
 *
 *  - 書面による特別の許可なしに、本ソフトウェアから派生した製品の
 *      宣伝または販売促進に、本ソフトウェアの著作権者の名前または
 *      コントリビューターの名前を使用してはならない。
 *
 *  本ソフトウェアは、著作権者およびコントリビューターによって「現
 *  状のまま」提供されており、明示黙示を問わず、商業的な使用可能性、
 *  および特定の目的に対する適合性に関す暗黙の保証も含め、またそれ
 *  に限定されない、いかなる保証もないものとします。著作権者もコン
 *  トリビューターも、事由のいかんを問わず、損害発生の原因いかんを
 *  問わず、かつ責任の根拠が契約であるか厳格責任であるか(過失その
 *  他の)不法行為であるかを問わず、仮にそのような損害が発生する可
 *  能性を知らされていたとしても、本ソフトウェアの使用によって発生
 *  した(代替品または代用サービスの調達、使用の喪失、データの喪失、
 *  利益の喪失、業務の中断も含め、またそれに限定されない)直接損害、
 *  間接損害、偶発的な損害、特別損害、懲罰的損害、または結果損害に
 *  ついて、一切責任を負わないものとします。
 *
 ****************************************************************************/