My Project: dynamics.mod/NewtonDynamics/source/core/dgHeap.h Source File

My Project

dgHeap.h
Go to the documentation of this file.
1 /* Copyright (c) <2003-2011> <Julio Jerez, Newton Game Dynamics>
2 *
3 * This software is provided 'as-is', without any express or implied
4 * warranty. In no event will the authors be held liable for any damages
5 * arising from the use of this software.
6 *
7 * Permission is granted to anyone to use this software for any purpose,
8 * including commercial applications, and to alter it and redistribute it
9 * freely, subject to the following restrictions:
10 *
11 * 1. The origin of this software must not be misrepresented; you must not
12 * claim that you wrote the original software. If you use this software
13 * in a product, an acknowledgment in the product documentation would be
14 * appreciated but is not required.
15 *
16 * 2. Altered source versions must be plainly marked as such, and must not be
17 * misrepresented as being the original software.
18 *
19 * 3. This notice may not be removed or altered from any source distribution.
20 */
21
22 /****************************************************************************
23 *
24 * Visual C++ 6.0 created by: Julio Jerez
25 *
26 ****************************************************************************/
27 #ifndef __dgHeapBase__
28 #define __dgHeapBase__
29
30 #include "dgStdafx.h"
31 #include "dgMemory.h"
32
33
34 //#define DG_HEAP_SANITY_CHECK
35
36 template <class OBJECT, class KEY>
37 class dgHeapBase
38 {
39 protected:
40 struct RECORD
41 {
42 KEY m_key;
43 OBJECT m_obj;
44
45 RECORD (KEY key, const OBJECT& obj)
46 :m_key(key), m_obj(obj)
47 {
48 }
49 };
50
51 dgHeapBase (dgInt32 maxElements, dgMemoryAllocator* const allocator);
52 dgHeapBase (const void * const buffer, dgInt32 sizeInBytes);
53 ~dgHeapBase ();
54
55 public:
56 DG_CLASS_ALLOCATOR(allocator)
57
58 void Flush ();
59 KEY MaxValue() const;
60 KEY Value(dgInt32 i = 0) const;
61 dgInt32 GetCount() const;
62 dgInt32 GetMaxCount() const;
63 const OBJECT& operator[] (dgInt32 i) const;
64 dgInt32 Find (OBJECT &obj);
65 dgInt32 Find (KEY key);
66
67 dgInt32 m_curCount;
68 dgInt32 m_maxCount;
69 dgMemoryAllocator* m_allocator;
70 RECORD *m_pool;
71 };
72
73 template <class OBJECT, class KEY>
74 class dgDownHeap: public dgHeapBase<OBJECT, KEY>
75 {
76 public:
77 dgDownHeap (dgInt32 maxElements, dgMemoryAllocator* const allocator);
78 dgDownHeap (const void * const buffer, dgInt32 sizeInBytes);
79
80 void Pop ();
81 void Push (OBJECT &obj, KEY key);
82 void Sort ();
83 void Remove (dgInt32 Index);
84
85 #ifdef DG_HEAP_SANITY_CHECK
86 bool SanityCheck();
87 #endif
88 };
89
90 template <class OBJECT, class KEY>
91 class dgUpHeap: public dgHeapBase<OBJECT, KEY>
92 {
93 public:
94 dgUpHeap (dgInt32 maxElements, dgMemoryAllocator* const allocator);
95 dgUpHeap (const void * const buffer, dgInt32 sizeInBytes);
96
97 void Pop ();
98 void Push (OBJECT &obj, KEY key);
99 void Sort ();
100 void Remove (dgInt32 Index);
101
102 #ifdef DG_HEAP_SANITY_CHECK
103 bool SanityCheck();
104 #endif
105 };
106
107
108
109 template <class OBJECT, class KEY>
110 dgHeapBase<OBJECT,KEY>::dgHeapBase (dgInt32 maxElements, dgMemoryAllocator* const allocator)
111 {
112 m_allocator = allocator;
113 m_pool = (RECORD *)m_allocator->Malloc (maxElements * sizeof (RECORD));
114 m_maxCount = maxElements;
115 Flush();
116 }
117
118 template <class OBJECT, class KEY>
119 dgHeapBase<OBJECT,KEY>::dgHeapBase (const void * const buffer, dgInt32 sizeInBytes)
120 {
121 m_allocator = NULL;
122 m_pool = (RECORD *) buffer;
123 m_maxCount = dgInt32 (sizeInBytes / sizeof (RECORD));
124 Flush();
125 }
126
127 template <class OBJECT, class KEY>
128 dgHeapBase<OBJECT,KEY>::~dgHeapBase ()
129 {
130 if (m_allocator) {
131 m_allocator->Free (m_pool);
132 }
133 }
134
135
136 template <class OBJECT, class KEY>
137 KEY dgHeapBase<OBJECT,KEY>::Value(dgInt32 i) const
138 {
139 return m_pool[i].m_key;
140 }
141
142
143 template <class OBJECT, class KEY>
144 dgInt32 dgHeapBase<OBJECT,KEY>::GetCount() const
145 {
146 return m_curCount;
147 }
148
149
150 template <class OBJECT, class KEY>
151 void dgHeapBase<OBJECT,KEY>::Flush ()
152 {
153 m_curCount = 0;
154
155 #ifdef _DEBUG
156 // dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_key = KEY (0);
157 #endif
158 }
159
160
161 template <class OBJECT, class KEY>
162 KEY dgHeapBase<OBJECT,KEY>::MaxValue() const
163 {
164 return m_pool[0].m_key;
165 }
166
167
168 template <class OBJECT, class KEY>
169 dgInt32 dgHeapBase<OBJECT,KEY>::GetMaxCount() const
170 {
171 return m_maxCount;
172 }
173
174
175 template <class OBJECT, class KEY>
176 dgInt32 dgHeapBase<OBJECT,KEY>::Find (OBJECT &obj)
177 {
178 // For now let perform a linear search
179 // this is efficient if the size of the heap is small
180 // ex: m_curCount < 32
181 // this will be change to a binary search in the heap should the
182 // the size of the heap get larger than 32
183 // dgAssert (m_curCount <= 32);
184 for (dgInt32 i = 0; i < m_curCount; i ++) {
185 if (m_pool[i].obj == obj) {
186 return i;
187 }
188 }
189 return - 1;
190 }
191
192
193 template <class OBJECT, class KEY>
194 dgInt32 dgHeapBase<OBJECT,KEY>::Find (KEY key)
195 {
196 // ex: m_curCount < 32
197 // this will be change to a binary search in the heap shoud the
198 // the size of the heap get larger than 32
199 dgAssert (m_curCount <= 32);
200 for (dgInt32 i = 0; i < m_curCount; i ++) {
201 if (m_pool[i].m_key == key) {
202 return i;
203 }
204 }
205 return - 1;
206 }
207
208
209 template <class OBJECT, class KEY>
210 const OBJECT& dgHeapBase<OBJECT,KEY>::operator[] (dgInt32 i) const
211 {
212 dgAssert (i<= m_curCount);
213 return m_pool[i].m_obj;
214 }
215
216
217 // **************************************************************************
218 //
219 // down Heap
220 //
221 // **************************************************************************
222 template <class OBJECT, class KEY>
223 dgDownHeap<OBJECT,KEY>::dgDownHeap (dgInt32 maxElements, dgMemoryAllocator* const allocator)
224 :dgHeapBase<OBJECT, KEY> (maxElements, allocator)
225 {
226 }
227
228 template <class OBJECT, class KEY>
229 dgDownHeap<OBJECT,KEY>::dgDownHeap (const void * const buffer, dgInt32 sizeInBytes)
230 :dgHeapBase<OBJECT, KEY> (buffer, sizeInBytes)
231 {
232 }
233
234
235 template <class OBJECT, class KEY>
236 void dgDownHeap<OBJECT,KEY>::Push (OBJECT &obj, KEY key)
237 {
238 #ifdef _DEBUG
239 dgInt32 cc = dgHeapBase<OBJECT,KEY>::m_curCount;
240 dgInt32 cm = dgHeapBase<OBJECT,KEY>::m_maxCount;
241 dgAssert (cc < cm);
242 #endif
243
244 dgHeapBase<OBJECT,KEY>::m_curCount ++;
245
246 dgInt32 j;
247 dgInt32 i = dgHeapBase<OBJECT,KEY>::m_curCount;
248 for (; i; i = j) {
249 j = i >> 1;
250 if (!j || (dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key > key)) {
251 break;
252 }
253 dgHeapBase<OBJECT,KEY>::m_pool[i - 1] = dgHeapBase<OBJECT,KEY>::m_pool[j - 1];
254 }
255 dgAssert (i);
256 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_key = key;
257 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_obj = obj;
258
259 #ifdef DG_HEAP_SANITY_CHECK
260 dgAssert (SanityCheck());
261 #endif
262 }
263
264
265 template <class OBJECT, class KEY>
266 void dgDownHeap<OBJECT,KEY>::Remove (dgInt32 index)
267 {
268 dgHeapBase<OBJECT,KEY>::m_curCount--;
269 KEY key (dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_key);
270
271 dgInt32 j;
272 dgInt32 i = index + 1;
273 for (; i <= (dgHeapBase<OBJECT,KEY>::m_curCount>>1); i = j) {
274 j = i + i;
275 if ((j < dgHeapBase<OBJECT,KEY>::m_curCount) &&
276 (dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key < dgHeapBase<OBJECT,KEY>::m_pool[j].m_key)) {
277 j ++;
278 }
279 if (key >= dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key) {
280 break;
281 }
282 dgHeapBase<OBJECT,KEY>::m_pool[i - 1] = dgHeapBase<OBJECT,KEY>::m_pool[j - 1];
283 }
284 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_key = key;
285 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_obj = dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_obj;
286
287 #ifdef DG_HEAP_SANITY_CHECK
288 dgAssert (SanityCheck());
289 #endif
290
291 }
292
293 template <class OBJECT, class KEY>
294 void dgDownHeap<OBJECT,KEY>::Pop ()
295 {
296 dgHeapBase<OBJECT,KEY>::m_curCount--;
297 KEY key (dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_key);
298
299 dgInt32 j;
300 dgInt32 i = 1;
301 for (; i <= (dgHeapBase<OBJECT,KEY>::m_curCount>>1); i = j) {
302 j = i + i;
303 if ((j < dgHeapBase<OBJECT,KEY>::m_curCount) &&
304 (dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key < dgHeapBase<OBJECT,KEY>::m_pool[j].m_key)) {
305 j ++;
306 }
307 if (key >= dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key) {
308 break;
309 }
310 dgHeapBase<OBJECT,KEY>::m_pool[i - 1] = dgHeapBase<OBJECT,KEY>::m_pool[j - 1];
311 }
312 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_key = key;
313 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_obj = dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_obj;
314
315 #ifdef DG_HEAP_SANITY_CHECK
316 dgAssert (SanityCheck());
317 #endif
318 }
319
320
321
322 template <class OBJECT, class KEY>
323 void dgDownHeap<OBJECT,KEY>::Sort ()
324 {
325
326 dgInt32 count = dgHeapBase<OBJECT,KEY>::m_curCount;
327 for (dgInt32 i = 1; i < count; i ++) {
328 KEY key (dgHeapBase<OBJECT,KEY>::m_pool[0].m_key);
329 OBJECT obj (dgHeapBase<OBJECT,KEY>::m_pool[0].m_obj);
330
331 Pop();
332
333 dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_key = key;
334 dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_obj = obj;
335 }
336
337 dgHeapBase<OBJECT,KEY>::m_curCount = count;
338 for (dgInt32 i = 0; i < count / 2; i ++) {
339 KEY key (dgHeapBase<OBJECT,KEY>::m_pool[i].m_key);
340 OBJECT obj (dgHeapBase<OBJECT,KEY>::m_pool[i].m_obj);
341
342 dgHeapBase<OBJECT,KEY>::m_pool[i].m_key = dgHeapBase<OBJECT,KEY>::m_pool[count - i - 1].m_key;
343 dgHeapBase<OBJECT,KEY>::m_pool[i].m_obj = dgHeapBase<OBJECT,KEY>::m_pool[count - i - 1].m_obj;
344
345 dgHeapBase<OBJECT,KEY>::m_pool[count - i - 1].m_key = key;
346 dgHeapBase<OBJECT,KEY>::m_pool[count - i - 1].m_obj = obj;
347 }
348 #ifdef DG_HEAP_SANITY_CHECK
349 dgAssert (SanityCheck());
350 #endif
351 }
352
353 #ifdef DG_HEAP_SANITY_CHECK
354 template <class OBJECT, class KEY>
355 bool dgDownHeap<OBJECT,KEY>::SanityCheck()
356 {
357 for (dgInt32 i = 0; i < dgHeapBase<OBJECT,KEY>::m_curCount / 2; i ++) {
358 if (dgHeapBase<OBJECT,KEY>::m_pool[i].m_key < dgHeapBase<OBJECT,KEY>::m_pool[i * 2 + 1].m_key) {
359 return false;
360 }
361 if ((i * 2 + 2) < dgHeapBase<OBJECT,KEY>::m_curCount) {
362 if (dgHeapBase<OBJECT,KEY>::m_pool[i].m_key < dgHeapBase<OBJECT,KEY>::m_pool[i * 2 + 2].m_key) {
363 return false;
364 }
365 }
366 }
367
368 return true;
369 }
370 #endif
371
372
373
374
375 // **************************************************************************
376 //
377 // down Heap
378 //
379 // **************************************************************************
380 template <class OBJECT, class KEY>
381 dgUpHeap<OBJECT,KEY>::dgUpHeap (dgInt32 maxElements, dgMemoryAllocator* const allocator)
382 :dgHeapBase<OBJECT, KEY> (maxElements, allocator)
383 {
384 }
385
386 template <class OBJECT, class KEY>
387 dgUpHeap<OBJECT,KEY>::dgUpHeap (const void * const buffer, dgInt32 sizeInBytes)
388 :dgHeapBase<OBJECT, KEY> (buffer, sizeInBytes)
389 {
390 }
391
392 #ifdef DG_HEAP_SANITY_CHECK
393 template <class OBJECT, class KEY>
394 bool dgUpHeap<OBJECT,KEY>::SanityCheck()
395 {
396 for (dgInt32 i = 0; i < dgHeapBase<OBJECT,KEY>::m_curCount / 2; i ++) {
397 if (dgHeapBase<OBJECT,KEY>::m_pool[i].m_key > dgHeapBase<OBJECT,KEY>::m_pool[i * 2 + 1].m_key) {
398 return false;
399 }
400 if ((i * 2 + 2) < dgHeapBase<OBJECT,KEY>::m_curCount) {
401 if (dgHeapBase<OBJECT,KEY>::m_pool[i].m_key > dgHeapBase<OBJECT,KEY>::m_pool[i * 2 + 2].m_key) {
402 return false;
403 }
404 }
405 }
406
407 return true;
408 }
409 #endif
410
411 template <class OBJECT, class KEY>
412 void dgUpHeap<OBJECT,KEY>::Push (OBJECT &obj, KEY key)
413 {
414 #ifdef _DEBUG
415 dgInt32 cc = dgHeapBase<OBJECT,KEY>::m_curCount;
416 dgInt32 cm = dgHeapBase<OBJECT,KEY>::m_maxCount;
417 dgAssert (cc < cm);
418 #endif
419 dgHeapBase<OBJECT,KEY>::m_curCount ++;
420
421 dgInt32 j;
422 dgInt32 i = dgHeapBase<OBJECT,KEY>::m_curCount;
423 for (; i; i = j) {
424 j = i >> 1;
425 if (!j || (dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key < key)) {
426 break;
427 }
428 dgHeapBase<OBJECT,KEY>::m_pool[i - 1] = dgHeapBase<OBJECT,KEY>::m_pool[j - 1];
429 }
430 dgAssert (i);
431 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_key = key;
432 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_obj = obj;
433
434 #ifdef DG_HEAP_SANITY_CHECK
435 dgAssert (SanityCheck());
436 #endif
437 }
438
439
440 template <class OBJECT, class KEY>
441 void dgUpHeap<OBJECT,KEY>::Sort ()
442 {
443 dgInt32 count = dgHeapBase<OBJECT,KEY>::m_curCount;
444 for (dgInt32 i = 1; i < count; i ++) {
445 KEY key (dgHeapBase<OBJECT,KEY>::m_pool[0].m_key);
446 OBJECT obj (dgHeapBase<OBJECT,KEY>::m_pool[0].m_obj);
447
448 Pop();
449
450 dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_key = key;
451 dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_obj = obj;
452 }
453
454 dgHeapBase<OBJECT,KEY>::m_curCount = count;
455 for (dgInt32 i = 0; i < count / 2; i ++) {
456 KEY key (dgHeapBase<OBJECT,KEY>::m_pool[i].m_key);
457 OBJECT obj (dgHeapBase<OBJECT,KEY>::m_pool[i].m_obj);
458
459 dgHeapBase<OBJECT,KEY>::m_pool[i].m_key = dgHeapBase<OBJECT,KEY>::m_pool[count - i - 1].m_key;
460 dgHeapBase<OBJECT,KEY>::m_pool[i].m_obj = dgHeapBase<OBJECT,KEY>::m_pool[count - i - 1].m_obj;
461
462 dgHeapBase<OBJECT,KEY>::m_pool[count - i - 1].m_key = key;
463 dgHeapBase<OBJECT,KEY>::m_pool[count - i - 1].m_obj = obj;
464 }
465 #ifdef DG_HEAP_SANITY_CHECK
466 dgAssert (SanityCheck());
467 #endif
468 }
469
470
471 template <class OBJECT, class KEY>
472 void dgUpHeap<OBJECT,KEY>::Remove (dgInt32 index)
473 {
474 dgHeapBase<OBJECT,KEY>::m_curCount--;
475
476 dgInt32 j;
477 dgInt32 i = index + 1;
478 KEY key (dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_key);
479 for (; i <= (dgHeapBase<OBJECT,KEY>::m_curCount>>1); i = j) {
480 j = i + i;
481 if ((j < dgHeapBase<OBJECT,KEY>::m_curCount) &&
482 (dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key > dgHeapBase<OBJECT,KEY>::m_pool[j].m_key)) {
483 j ++;
484 }
485 if (key <= dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key) {
486 break;
487 }
488 dgHeapBase<OBJECT,KEY>::m_pool[i - 1] = dgHeapBase<OBJECT,KEY>::m_pool[j - 1];
489 }
490 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_key = key;
491 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_obj = dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_obj;
492
493 #ifdef DG_HEAP_SANITY_CHECK
494 dgAssert (SanityCheck());
495 #endif
496 }
497
498
499 template <class OBJECT, class KEY>
500 void dgUpHeap<OBJECT,KEY>::Pop ()
501 {
502 dgHeapBase<OBJECT,KEY>::m_curCount--;
503 KEY key (dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_key);
504
505 dgInt32 j;
506 dgInt32 i = 1;
507 for (; i <= (dgHeapBase<OBJECT,KEY>::m_curCount>>1); i = j) {
508 j = i + i;
509 if ((j < dgHeapBase<OBJECT,KEY>::m_curCount) &&
510 (dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key > dgHeapBase<OBJECT,KEY>::m_pool[j].m_key)) {
511 j ++;
512 }
513 if (key <= dgHeapBase<OBJECT,KEY>::m_pool[j - 1].m_key) {
514 break;
515 }
516 dgHeapBase<OBJECT,KEY>::m_pool[i - 1] = dgHeapBase<OBJECT,KEY>::m_pool[j - 1];
517 }
518 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_key = key;
519 dgHeapBase<OBJECT,KEY>::m_pool[i - 1].m_obj = dgHeapBase<OBJECT,KEY>::m_pool[dgHeapBase<OBJECT,KEY>::m_curCount].m_obj;
520
521 #ifdef DG_HEAP_SANITY_CHECK
522 dgAssert (SanityCheck());
523 #endif
524 }
525
526
527 #endif
528
529
dgMemory.h
dgDownHeap::Pop
void Pop()
Definition: dgHeap.h:294
dgHeapBase::~dgHeapBase
~dgHeapBase()
Definition: dgHeap.h:128
dgHeapBase::dgHeapBase
dgHeapBase(dgInt32 maxElements, dgMemoryAllocator *const allocator)
Definition: dgHeap.h:110
dgAssert
#define dgAssert(x)
Definition: dgTypes.h:158
dgInt32
int dgInt32
Definition: dgTypes.h:218
dgHeapBase::RECORD::m_key
KEY m_key
Definition: dgHeap.h:42
dgUpHeap::dgUpHeap
dgUpHeap(dgInt32 maxElements, dgMemoryAllocator *const allocator)
Definition: dgHeap.h:381
dgHeapBase::Flush
void Flush()
Definition: dgHeap.h:151
dgHeapBase::Value
KEY Value(dgInt32 i=0) const
Definition: dgHeap.h:137
DG_CLASS_ALLOCATOR
#define DG_CLASS_ALLOCATOR(allocator)
Definition: dgMemory.h:60
dgHeapBase::RECORD::RECORD
RECORD(KEY key, const OBJECT &obj)
Definition: dgHeap.h:45
dgHeapBase::RECORD
Definition: dgHeap.h:40
dgHeapBase::Find
dgInt32 Find(OBJECT &obj)
Definition: dgHeap.h:176
dgMemoryAllocator::Malloc
void * Malloc(dgInt32 memsize)
Definition: dgMemory.cpp:172
dgUpHeap::Push
void Push(OBJECT &obj, KEY key)
Definition: dgHeap.h:412
dgDownHeap::Sort
void Sort()
Definition: dgHeap.h:323
dgUpHeap::Pop
void Pop()
Definition: dgHeap.h:500
dgUpHeap::Remove
void Remove(dgInt32 Index)
Definition: dgHeap.h:472
dgHeapBase::GetCount
dgInt32 GetCount() const
Definition: dgHeap.h:144
dgStdafx.h
dgDownHeap::Push
void Push(OBJECT &obj, KEY key)
Definition: dgHeap.h:236
dgDownHeap
Definition: dgHeap.h:74
dgHeapBase
Definition: dgHeap.h:37
dgHeapBase::GetMaxCount
dgInt32 GetMaxCount() const
Definition: dgHeap.h:169
dgMemoryAllocator::Free
void Free(void *const retPtr)
Definition: dgMemory.cpp:245
dgDownHeap::Remove
void Remove(dgInt32 Index)
Definition: dgHeap.h:266
dgUpHeap
Definition: dgHeap.h:91
dgDownHeap::dgDownHeap
dgDownHeap(dgInt32 maxElements, dgMemoryAllocator *const allocator)
Definition: dgHeap.h:223
dgMemoryAllocator
Definition: dgMemory.h:73
dgHeapBase::RECORD::m_obj
OBJECT m_obj
Definition: dgHeap.h:43
dgHeapBase::m_pool
RECORD * m_pool
Definition: dgHeap.h:70
dgHeapBase::MaxValue
KEY MaxValue() const
Definition: dgHeap.h:162
dgUpHeap::Sort
void Sort()
Definition: dgHeap.h:441
dgHeapBase::operator[]
const OBJECT & operator[](dgInt32 i) const
Definition: dgHeap.h:210
dgHeapBase::m_curCount
dgInt32 m_curCount
Definition: dgHeap.h:67
dgHeapBase::m_allocator
dgMemoryAllocator * m_allocator
Definition: dgHeap.h:69
dgHeapBase::m_maxCount
dgInt32 m_maxCount
Definition: dgHeap.h:68