FineKernelToolKit 2.9.0

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

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

全て クラス ネームスペース ファイル 関数 変数 型定義 列挙型 列挙型の値 フレンド マクロ定義 ページ
HeapBase.h
説明を見る。
1 /****************************************************************************
2 *
3 * Copyright (c) 1999-2014, Fine Kernel Project, All rights reserved.
4 *
5 * Redistribution and use in source and binary forms,
6 * with or without modification, are permitted provided that the
7 * following conditions are met:
8 *
9 * - Redistributions of source code must retain the above
10 * copyright notice, this list of conditions and the
11 * following disclaimer.
12 *
13 * - Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the
15 * following disclaimer in the documentation and/or
16 * other materials provided with the distribution.
17 *
18 * - Neither the name of the copyright holders nor the names
19 * of its contributors may be used to endorse or promote
20 * products derived from this software without specific
21 * prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
30 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
32 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
33 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
35 *
36 ****************************************************************************/
37 /****************************************************************************
38 *
39 * Copyright (c) 1999-2014, Fine Kernel Project, All rights reserved.
40 *
41 * 本ソフトウェアおよびソースコードのライセンスは、基本的に
42 * 「修正 BSD ライセンス」に従います。以下にその詳細を記します。
43 *
44 * ソースコード形式かバイナリ形式か、変更するかしないかを問わず、
45 * 以下の条件を満たす場合に限り、再頒布および使用が許可されます。
46 *
47 * - ソースコードを再頒布する場合、上記の著作権表示、本条件一覧、
48 * および下記免責条項を含めること。
49 *
50 * - バイナリ形式で再頒布する場合、頒布物に付属のドキュメント等の
51 * 資料に、上記の著作権表示、本条件一覧、および下記免責条項を
52 * 含めること。
53 *
54 * - 書面による特別の許可なしに、本ソフトウェアから派生した製品の
55 * 宣伝または販売促進に、本ソフトウェアの著作権者の名前または
56 * コントリビューターの名前を使用してはならない。
57 *
58 * 本ソフトウェアは、著作権者およびコントリビューターによって「現
59 * 状のまま」提供されており、明示黙示を問わず、商業的な使用可能性、
60 * および特定の目的に対する適合性に関す暗黙の保証も含め、またそれ
61 * に限定されない、いかなる保証もないものとします。著作権者もコン
62 * トリビューターも、事由のいかんを問わず、損害発生の原因いかんを
63 * 問わず、かつ責任の根拠が契約であるか厳格責任であるか(過失その
64 * 他の)不法行為であるかを問わず、仮にそのような損害が発生する可
65 * 能性を知らされていたとしても、本ソフトウェアの使用によって発生
66 * した(代替品または代用サービスの調達、使用の喪失、データの喪失、
67 * 利益の喪失、業務の中断も含め、またそれに限定されない)直接損害、
68 * 間接損害、偶発的な損害、特別損害、懲罰的損害、または結果損害に
69 * ついて、一切責任を負わないものとします。
70 *
71 ****************************************************************************/
72 #ifndef __FK_HEAP_BASE_HEADER__
73 #define __FK_HEAP_BASE_HEADER__
74
75 #include <vector>
76
78
99 typedef std::vector<int>::size_type _fk_h_s;
100
102
123 template<class TYPE> class fk_HeapBase {
124 private:
125 std::vector<TYPE *> array;
126 std::vector<int> id;
127
128 int Compare(TYPE *a, TYPE *b) {
129 if(*a < *b) return -1;
130 if(*a > *b) return 1;
131 return 0;
132 }
133
134 int HeapData(TYPE *argData, int argS, int argE) {
135 TYPE *pData;
136 int comp;
137 int index;
138
139 if(argE == -1) {
140 pData = new TYPE();
141 *pData = *argData;
142 array.insert(array.begin(), pData);
143 id.insert(id.begin(), 1);
144 return 1;
145 }
146
147 if(argS == argE) {
148 comp = Compare(argData, array[static_cast<_fk_h_s>(argS)]);
149 if(comp == 0) {
150 return id[static_cast<_fk_h_s>(argS)];
151 }
152
153 pData = new TYPE();
154 *pData = *argData;
155 if(comp == -1) {
156 array.insert(array.begin()+argS, pData);
157 id.insert(id.begin()+argS,
158 static_cast<int>(array.size()));
159 } else {
160 array.insert(array.begin()+argS+1, pData);
161 id.insert(id.begin()+argS+1,
162 static_cast<int>(array.size()));
163 }
164 return static_cast<int>(array.size());
165 }
166
167 if(argE - argS == 1) {
168 comp = Compare(argData,
169 array[static_cast<_fk_h_s>(argS)]);
170
171 if(comp == 0) {
172 return id[static_cast<_fk_h_s>(argS)];
173 }
174
175 if(comp == -1) {
176 pData = new TYPE();
177 *pData = *argData;
178 array.insert(array.begin()+argS, pData);
179 id.insert(id.begin()+argS,
180 static_cast<int>(array.size()));
181 return static_cast<int>(array.size());
182 }
183
184 return HeapData(argData, argE, argE);
185 }
186
187 index = (argE-argS)/2 + argS;
188
189 comp = Compare(argData, array[static_cast<_fk_h_s>(index)]);
190
191 if(comp == 0) {
192 return id[static_cast<_fk_h_s>(index)];
193 }
194
195 if(comp == -1) {
196 return HeapData(argData, argS, index);
197 }
198
199 if(comp == 1) {
200 return HeapData(argData, index, argE);
201 }
202
203 return 0;
204 }
205
206
207 public:
208
210 fk_HeapBase(void) { clear(); }
211
213 virtual ~fk_HeapBase() { clear(); }
214
216
220 void clear(void);
221
227 int getSize(void) {
228 return static_cast<int>(array.size());
229 }
230
243 int getID(TYPE *argV) {
244 return HeapData(argV, 0, getSize()-1);
245 }
246 };
247
248 template<class TYPE> void fk_HeapBase<TYPE>::clear(void) {
249 for(unsigned int i = 0; i < array.size(); i++) {
250 delete array[i];
251 }
252
253 array.clear();
254 id.clear();
255 return;
256 }
257
258 #endif // !__FK_HEAP_BASE_HEADER__
259
fk_HeapBase::getSize
int getSize(void)
Definition: HeapBase.h:227
fk_HeapBase::fk_HeapBase
fk_HeapBase(void)
コンストラクタ
Definition: HeapBase.h:210
fk_HeapBase::getID
int getID(TYPE *argV)
Definition: HeapBase.h:243
fk_HeapBase
重複要素に同一IDを与えるための汎用テンプレート
Definition: HeapBase.h:123
_fk_h_s
std::vector< int >::size_type _fk_h_s
重複要素に同一IDを与えるための汎用テンプレート
Definition: HeapBase.h:99
fk_HeapBase::clear
void clear(void)
初期化関数
Definition: HeapBase.h:248
fk_HeapBase::~fk_HeapBase
virtual ~fk_HeapBase()
デストラクタ
Definition: HeapBase.h:213