FineKernelToolKit: FK/HeapBase.h ソースファイル

FineKernelToolKit 4.3.0

読み取り中…
検索中…
一致する文字列を見つけられません
HeapBase.h
[詳解]
1#if !defined(__FK_HEAP_BASE_HEADER__)
2#define __FK_HEAP_BASE_HEADER__
3
4#include <vector>
5
6namespace FK {
7#if !defined(FK_DOXYGEN_USER_PROCESS)
8 using _fk_h_s = std::vector<int>::size_type;
9#endif
10
12
28
29 template<class TYPE> class fk_HeapBase {
30 public:
32 fk_HeapBase(void) { clear(); }
33
35 virtual ~fk_HeapBase() { clear(); }
36
38
42 void clear(void);
43
45
50 int getSize(void) {
51 return int(array.size());
52 }
53
55
67 int getID(TYPE *argV) {
68 return HeapData(argV, 0, getSize()-1);
69 }
70
71 private:
72 std::vector<TYPE *> array;
73 std::vector<int> id;
74
75 int Compare(TYPE *a, TYPE *b) {
76 if(*a < *b) return -1;
77 if(*a > *b) return 1;
78 return 0;
79 }
80
81 int HeapData(TYPE *argData, int argS, int argE) {
82 TYPE *pData;
83 int comp;
84 int index;
85
86 if(argE == -1) {
87 pData = new TYPE();
88 *pData = *argData;
89 array.insert(array.begin(), pData);
90 id.insert(id.begin(), 1);
91 return 1;
92 }
93
94 if(argS == argE) {
95 comp = Compare(argData, array[_fk_h_s(argS)]);
96 if(comp == 0) {
97 return id[_fk_h_s(argS)];
98 }
99
100 pData = new TYPE();
101 *pData = *argData;
102 if(comp == -1) {
103 array.insert(array.begin()+argS, pData);
104 id.insert(id.begin()+argS,
105 int(array.size()));
106 } else {
107 array.insert(array.begin()+argS+1, pData);
108 id.insert(id.begin()+argS+1,
109 int(array.size()));
110 }
111 return int(array.size());
112 }
113
114 if(argE - argS == 1) {
115 comp = Compare(argData,
116 array[_fk_h_s(argS)]);
117
118 if(comp == 0) {
119 return id[_fk_h_s(argS)];
120 }
121
122 if(comp == -1) {
123 pData = new TYPE();
124 *pData = *argData;
125 array.insert(array.begin()+argS, pData);
126 id.insert(id.begin()+argS,
127 int(array.size()));
128 return int(array.size());
129 }
130
131 return HeapData(argData, argE, argE);
132 }
133
134 index = (argE-argS)/2 + argS;
135
136 comp = Compare(argData, array[_fk_h_s(index)]);
137
138 if(comp == 0) {
139 return id[_fk_h_s(index)];
140 }
141
142 if(comp == -1) {
143 return HeapData(argData, argS, index);
144 }
145
146 if(comp == 1) {
147 return HeapData(argData, index, argE);
148 }
149
150 return 0;
151 }
152 };
153
154 template<class TYPE> void fk_HeapBase<TYPE>::clear(void) {
155 for(unsigned int i = 0; i < array.size(); i++) {
156 delete array[i];
157 }
158
159 array.clear();
160 id.clear();
161 return;
162 }
163}
164
165#endif // !__FK_HEAP_BASE_HEADER__
166
167/****************************************************************************
168 *
169 * Copyright (c) 1999-2024, Fine Kernel Project, All rights reserved.
170 *
171 * Redistribution and use in source and binary forms,
172 * with or without modification, are permitted provided that the
173 * following conditions are met:
174 *
175 * - Redistributions of source code must retain the above
176 * copyright notice, this list of conditions and the
177 * following disclaimer.
178 *
179 * - Redistributions in binary form must reproduce the above
180 * copyright notice, this list of conditions and the
181 * following disclaimer in the documentation and/or
182 * other materials provided with the distribution.
183 *
184 * - Neither the name of the copyright holders nor the names
185 * of its contributors may be used to endorse or promote
186 * products derived from this software without specific
187 * prior written permission.
188 *
189 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
190 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
191 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
192 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
193 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
194 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
195 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
196 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
197 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
198 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
199 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
200 * POSSIBILITY OF SUCH DAMAGE.
201 *
202 ****************************************************************************/
203/****************************************************************************
204 *
205 * Copyright (c) 1999-2024, Fine Kernel Project, All rights reserved.
206 *
207 * 本ソフトウェアおよびソースコードのライセンスは、基本的に
208 * 「修正 BSD ライセンス」に従います。以下にその詳細を記します。
209 *
210 * ソースコード形式かバイナリ形式か、変更するかしないかを問わず、
211 * 以下の条件を満たす場合に限り、再頒布および使用が許可されます。
212 *
213 * - ソースコードを再頒布する場合、上記の著作権表示、本条件一覧、
214 * および下記免責条項を含めること。
215 *
216 * - バイナリ形式で再頒布する場合、頒布物に付属のドキュメント等の
217 * 資料に、上記の著作権表示、本条件一覧、および下記免責条項を
218 * 含めること。
219 *
220 * - 書面による特別の許可なしに、本ソフトウェアから派生した製品の
221 * 宣伝または販売促進に、本ソフトウェアの著作権者の名前または
222 * コントリビューターの名前を使用してはならない。
223 *
224 * 本ソフトウェアは、著作権者およびコントリビューターによって「現
225 * 状のまま」提供されており、明示黙示を問わず、商業的な使用可能性、
226 * および特定の目的に対する適合性に関す暗黙の保証も含め、またそれ
227 * に限定されない、いかなる保証もないものとします。著作権者もコン
228 * トリビューターも、事由のいかんを問わず、損害発生の原因いかんを
229 * 問わず、かつ責任の根拠が契約であるか厳格責任であるか(過失その
230 * 他の)不法行為であるかを問わず、仮にそのような損害が発生する可
231 * 能性を知らされていたとしても、本ソフトウェアの使用によって発生
232 * した(代替品または代用サービスの調達、使用の喪失、データの喪失、
233 * 利益の喪失、業務の中断も含め、またそれに限定されない)直接損害、
234 * 間接損害、偶発的な損害、特別損害、懲罰的損害、または結果損害に
235 * ついて、一切責任を負わないものとします。
236 *
237 ****************************************************************************/
FK::fk_HeapBase::fk_HeapBase
fk_HeapBase(void)
コンストラクタ
Definition HeapBase.h:32
FK::fk_HeapBase::getID
int getID(TYPE *argV)
要素取得関数
Definition HeapBase.h:67
FK::fk_HeapBase::getSize
int getSize(void)
要素数取得関数
Definition HeapBase.h:50
FK::fk_HeapBase::~fk_HeapBase
virtual ~fk_HeapBase()
デストラクタ
Definition HeapBase.h:35
FK::fk_HeapBase::clear
void clear(void)
初期化関数
Definition HeapBase.h:154
FK
Fine Kernel Toolkit 名前空間
Definition Angle.h:6