aboutsummaryrefslogtreecommitdiff
path: root/src/stable/heap.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/stable/heap.h')
-rw-r--r--src/stable/heap.h612
1 files changed, 612 insertions, 0 deletions
diff --git a/src/stable/heap.h b/src/stable/heap.h
new file mode 100644
index 0000000..afe8be6
--- /dev/null
+++ b/src/stable/heap.h
@@ -0,0 +1,612 @@
1/*
2 * Copyright (C) 2007-2011 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#ifndef BU_HEAP_H
9#define BU_HEAP_H
10
11#include <stddef.h>
12#include <memory>
13#include "bu/exceptionbase.h"
14#include "bu/util.h"
15#include "bu/queue.h"
16#include "bu/sharedcore.h"
17
18namespace Bu
19{
20 subExceptionDecl( HeapException );
21
22 template<typename item, typename cmpfunc, typename itemalloc>
23 class Heap;
24
25 /** @cond DEVEL */
26 template<typename item, typename cmpfunc, typename itemalloc>
27 class HeapCore
28 {
29 friend class Heap<item, cmpfunc, itemalloc>;
30 friend class SharedCore<
31 Heap<item, cmpfunc, itemalloc>, HeapCore<item, cmpfunc, itemalloc>
32 >;
33 private:
34 HeapCore() :
35 iSize( 0 ),
36 iFill( 0 ),
37 aItem( NULL )
38 {
39 }
40
41 virtual ~HeapCore()
42 {
43 clear();
44 }
45
46 void init()
47 {
48 if( iSize > 0 )
49 return;
50
51 iSize = 7;
52 iFill = 0;
53 aItem = ia.allocate( iSize );
54 }
55
56 void init( int iCap )
57 {
58 if( iSize > 0 )
59 return;
60
61 for( iSize = 1; iSize < iCap; iSize=iSize*2+1 ) { }
62 iFill = 0;
63 aItem = ia.allocate( iSize );
64 }
65
66 void clear()
67 {
68 if( iSize == 0 )
69 return;
70
71 for( int j = 0; j < iFill; j++ )
72 ia.destroy( &aItem[j] );
73 ia.deallocate( aItem, iSize );
74 aItem = NULL;
75 iSize = 0;
76 iFill = 0;
77 }
78
79 void upSize()
80 {
81 if( iSize == 0 )
82 {
83 init();
84 return;
85 }
86
87 item *aNewItems = ia.allocate( iSize*2+1 );
88 //
89 // We cannot use a memcopy here because we don't know what kind
90 // of datastructures are being used, we have to copy them one at
91 // a time.
92 //
93 for( int j = 0; j < iFill; j++ )
94 {
95 ia.construct( &aNewItems[j], aItem[j] );
96 ia.destroy( &aItem[j] );
97 }
98 ia.deallocate( aItem, iSize );
99 aItem = aNewItems;
100 iSize = iSize*2+1;
101 }
102
103 virtual void enqueue( const item &it )
104 {
105 item i = it; // TODO: This is a silly workaround, put the i item
106 // at the end.
107 if( iFill+1 >= iSize )
108 upSize();
109
110 for( int j = 0; j < iFill; )
111 {
112 if( cmp( i, aItem[j] ) )
113 {
114 Bu::swap( i, aItem[j] );
115 }
116
117 if( j*2+1 >= iFill )
118 break;
119 if( cmp( i, aItem[j*2+1] ) )
120 {
121 j = j*2+1;
122 }
123 else
124 {
125 j = j*2+2;
126 }
127 }
128 ia.construct( &aItem[iFill], i );
129 if( iFill > 0 )
130 {
131 for( int j = iFill; j >= 0; )
132 {
133 int k = (j-1)/2;
134 if( j == k )
135 break;
136 if( cmp( aItem[k], aItem[j] ) )
137 break;
138
139 Bu::swap( aItem[k], aItem[j] );
140 j = k;
141 }
142 }
143 iFill++;
144 }
145
146 virtual item dequeue()
147 {
148 if( iFill == 0 )
149 throw HeapException("Heap empty.");
150 item iRet = aItem[0];
151 int j;
152 for( j = 0; j < iFill; )
153 {
154 int k = j*2+1;
155 if( k+1 < iFill && cmp( aItem[k+1], aItem[k] ) )
156 {
157 if( k+1 < iFill-1 && cmp( aItem[iFill-1], aItem[k+1] ) )
158 break;
159 aItem[j] = aItem[k+1];
160 j = k+1;
161 }
162 else if( k < iFill )
163 {
164 if( k < iFill-1 && cmp( aItem[iFill-1], aItem[k] ) )
165 break;
166 aItem[j] = aItem[k];
167 j = k;
168 }
169 else
170 break;
171 }
172 if( j < iFill-1 )
173 aItem[j] = aItem[iFill-1];
174 ia.destroy( &aItem[iFill-1] );
175 iFill--;
176
177 return iRet;
178 }
179
180 private:
181 int iSize;
182 int iFill;
183 item *aItem;
184 cmpfunc cmp;
185 itemalloc ia;
186 };
187 /** @endcond */
188
189 /**
190 * A priority queue that allows for an unlimited number of priorities. All
191 * objects enqueued must support less-than-comparison. Then every time an
192 * item is dequeued it is always the least item in the heap. The heap
193 * operates using a binary tree for storage, which allows most operations
194 * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins
195 * whereas peeking is constant time.
196 *
197 * This heap implementation allows iterating, however please note that any
198 * enqueue or dequeue operation will invalidate the iterator and make it
199 * unusable (if it still works, you shouldn't trust the results). Also,
200 * the items are not stored in memory in order, they are optomized into a
201 * tree. This means that the items will be in effectively random order
202 * while iterating through them, and the order cannot be trusted. Also,
203 * modifying an item in the heap will not cause that item to be re-sorted.
204 * If you want to change the position of an item in the heap you will have
205 * to dequeue every item before it, dequeue that item, change it, and
206 * re-enqueue all of the items removed.
207 */
208 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
209 class Heap : public Queue<item>, public SharedCore<
210 Heap<item, cmpfunc, itemalloc>,
211 HeapCore<item, cmpfunc, itemalloc>
212 >
213 {
214 private:
215 typedef class Heap<item,cmpfunc,itemalloc> MyType;
216 typedef class HeapCore<item,cmpfunc,itemalloc> Core;
217
218 protected:
219 using SharedCore<MyType, Core>::core;
220 using SharedCore<MyType, Core>::_hardCopy;
221 using SharedCore<MyType, Core>::_resetCore;
222 using SharedCore<MyType, Core>::_allocateCore;
223
224 public:
225 Heap()
226 {
227 }
228
229 Heap( cmpfunc cmpin )
230 {
231 core->cmp = cmpin;
232 }
233
234 Heap( int iInitialCapacity )
235 {
236 core->init( iInitialCapacity );
237 }
238
239 Heap( cmpfunc cmpin, int iInitialCapacity )
240 {
241 core->cmp = cmpin;
242 core->init( iInitialCapacity );
243 }
244
245 Heap( const MyType &rSrc ) :
246 SharedCore<MyType, Core>( rSrc )
247 {
248 }
249
250 virtual ~Heap()
251 {
252 }
253
254 virtual void enqueue( const item &it )
255 {
256 _hardCopy();
257
258 core->enqueue( it );
259 }
260
261 virtual item &peek()
262 {
263 _hardCopy();
264
265 if( core->iFill == 0 )
266 throw HeapException("Heap empty.");
267 return core->aItem[0];
268 }
269
270 virtual const item &peek() const
271 {
272 if( core->iFill == 0 )
273 throw HeapException("Heap empty.");
274 return core->aItem[0];
275 }
276
277 virtual item dequeue()
278 {
279 _hardCopy();
280
281 return core->dequeue();
282 }
283
284 virtual bool isEmpty() const
285 {
286 return (core->iFill==0);
287 }
288
289 virtual int getSize() const
290 {
291 return core->iFill;
292 }
293
294 class iterator
295 {
296 friend class const_iterator;
297 friend class Heap<item, cmpfunc, itemalloc>;
298 private:
299 Heap<item, cmpfunc, itemalloc> *pHeap;
300 int iIndex;
301
302 iterator( Heap<item, cmpfunc, itemalloc> *pHeap, int iIndex ) :
303 pHeap( pHeap ), iIndex( iIndex )
304 {
305 }
306
307 void checkValid()
308 {
309 if( pHeap == NULL )
310 throw Bu::ExceptionBase("Iterator not initialized.");
311 if( iIndex < 0 || iIndex >= pHeap->core->iFill )
312 throw Bu::ExceptionBase("Iterator out of bounds.");
313 }
314
315 public:
316 iterator() :
317 pHeap( NULL ),
318 iIndex( -1 )
319 {
320 }
321
322 iterator( const iterator &i ) :
323 pHeap( i.pHeap ),
324 iIndex( i.iIndex )
325 {
326 }
327
328 bool operator==( const iterator &oth ) const
329 {
330 return (oth.pHeap == pHeap) && (oth.iIndex == iIndex);
331 }
332
333 bool operator!=( const iterator &oth ) const
334 {
335 return (oth.pHeap != pHeap) || (oth.iIndex != iIndex);
336 }
337
338 item &operator*()
339 {
340 pHeap->_hardCopy();
341
342 return pHeap->core->aItem[iIndex];
343 }
344
345 item *operator->()
346 {
347 pHeap->_hardCopy();
348
349 return &(pHeap->core->aItem[iIndex]);
350 }
351
352 iterator &operator++()
353 {
354 checkValid();
355 iIndex++;
356 if( iIndex >= pHeap->iFill )
357 iIndex = -1;
358
359 return *this;
360 }
361
362 iterator &operator--()
363 {
364 checkValid();
365 iIndex--;
366
367 return *this;
368 }
369
370 iterator &operator++( int )
371 {
372 checkValid();
373 iIndex++;
374 if( iIndex >= pHeap->core->iFill )
375 iIndex = -1;
376
377 return *this;
378 }
379
380 iterator &operator--( int )
381 {
382 checkValid();
383 iIndex--;
384
385 return *this;
386 }
387
388 iterator operator+( int iDelta )
389 {
390 checkValid();
391 iterator ret( *this );
392 ret.iIndex += iDelta;
393 if( ret.iIndex >= pHeap->core->iFill )
394 ret.iIndex = -1;
395 return ret;
396 }
397
398 iterator operator-( int iDelta )
399 {
400 checkValid();
401 iterator ret( *this );
402 ret.iIndex -= iDelta;
403 if( ret.iIndex < 0 )
404 ret.iIndex = -1;
405 return ret;
406 }
407
408 operator bool() const
409 {
410 return iIndex != -1;
411 }
412
413 bool isValid() const
414 {
415 return iIndex != -1;
416 }
417
418 iterator &operator=( const iterator &oth )
419 {
420 pHeap = oth.pHeap;
421 iIndex = oth.iIndex;
422 }
423 };
424
425 class const_iterator
426 {
427 friend class Heap<item, cmpfunc, itemalloc>;
428 private:
429 Heap<item, cmpfunc, itemalloc> *pHeap;
430 int iIndex;
431
432 const_iterator( Heap<item, cmpfunc, itemalloc> *pHeap,
433 int iIndex ) :
434 pHeap( pHeap ), iIndex( iIndex )
435 {
436 }
437
438 void checkValid()
439 {
440 if( pHeap == NULL )
441 throw Bu::ExceptionBase("Iterator not initialized.");
442 if( iIndex < 0 || iIndex >= pHeap->core->iFill )
443 throw Bu::ExceptionBase("Iterator out of bounds.");
444 }
445
446 public:
447 const_iterator() :
448 pHeap( NULL ),
449 iIndex( -1 )
450 {
451 }
452
453 const_iterator( const const_iterator &i ) :
454 pHeap( i.pHeap ),
455 iIndex( i.iIndex )
456 {
457 }
458
459 const_iterator( const iterator &i ) :
460 pHeap( i.pHeap ),
461 iIndex( i.iIndex )
462 {
463 }
464
465 bool operator==( const const_iterator &oth ) const
466 {
467 return (oth.pHeap == pHeap) && (oth.iIndex == iIndex);
468 }
469
470 bool operator!=( const const_iterator &oth ) const
471 {
472 return (oth.pHeap != pHeap) || (oth.iIndex != iIndex);
473 }
474
475 const item &operator*()
476 {
477 pHeap->_hardCopy();
478
479 return pHeap->core->aItem[iIndex];
480 }
481
482 const item *operator->()
483 {
484 pHeap->_hardCopy();
485
486 return &(pHeap->core->aItem[iIndex]);
487 }
488
489 const_iterator &operator++()
490 {
491 checkValid();
492 iIndex++;
493 if( iIndex >= pHeap->core->iFill )
494 iIndex = -1;
495
496 return *this;
497 }
498
499 const_iterator &operator--()
500 {
501 checkValid();
502 iIndex--;
503
504 return *this;
505 }
506
507 const_iterator &operator++( int )
508 {
509 checkValid();
510 iIndex++;
511 if( iIndex >= pHeap->core->iFill )
512 iIndex = -1;
513
514 return *this;
515 }
516
517 const_iterator &operator--( int )
518 {
519 checkValid();
520 iIndex--;
521
522 return *this;
523 }
524
525 const_iterator operator+( int iDelta )
526 {
527 checkValid();
528 const_iterator ret( *this );
529 ret.iIndex += iDelta;
530 if( ret.iIndex >= pHeap->iFill )
531 ret.iIndex = -1;
532 return ret;
533 }
534
535 const_iterator operator-( int iDelta )
536 {
537 checkValid();
538 const_iterator ret( *this );
539 ret.iIndex -= iDelta;
540 if( ret.iIndex < 0 )
541 ret.iIndex = -1;
542 return ret;
543 }
544
545 operator bool() const
546 {
547 return iIndex != -1;
548 }
549
550 bool isValid() const
551 {
552 return iIndex != -1;
553 }
554
555 const_iterator &operator=( const const_iterator &oth )
556 {
557 pHeap = oth.pHeap;
558 iIndex = oth.iIndex;
559 }
560
561 const_iterator &operator=( const iterator &oth )
562 {
563 pHeap = oth.pHeap;
564 iIndex = oth.iIndex;
565 }
566 };
567
568 iterator begin()
569 {
570 if( core->iFill == 0 )
571 return end();
572 return iterator( this, 0 );
573 }
574
575 const_iterator begin() const
576 {
577 if( core->iFill == 0 )
578 return end();
579 return const_iterator( this, 0 );
580 }
581
582 iterator end()
583 {
584 return iterator( this, -1 );
585 }
586
587 const_iterator end() const
588 {
589 return const_iterator( this, -1 );
590 }
591
592
593 protected:
594 virtual Core *_copyCore( Core *src )
595 {
596 Core *pRet = _allocateCore();
597
598 pRet->iSize = src->iSize;
599 pRet->iFill = src->iFill;
600 pRet->cmp = src->cmp;
601 pRet->aItem = pRet->ia.allocate( pRet->iSize );
602 for( int j = 0; j < pRet->iFill; j++ )
603 {
604 pRet->ia.construct( &pRet->aItem[j], src->aItem[j] );
605 }
606
607 return pRet;
608 }
609 };
610};
611
612#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-21 10:43:19 +0000