Revision 1025,
1.4 KB
checked in by gumbau, 18 years ago
(diff) |
namespace simplif
|
Rev | Line | |
---|
[774] | 1 | #ifndef GFXTOOLS_HEAP_INCLUDED // -*- C++ -*-
|
---|
| 2 | #define GFXTOOLS_HEAP_INCLUDED
|
---|
| 3 |
|
---|
| 4 | #include <gfx/tools/Array.h>
|
---|
| 5 |
|
---|
| 6 | #define NOT_IN_HEAP -47
|
---|
| 7 |
|
---|
| 8 | //
|
---|
| 9 | //
|
---|
| 10 | // This file extracted from Terra
|
---|
| 11 | //
|
---|
| 12 | //
|
---|
| 13 |
|
---|
[1025] | 14 | namespace simplif
|
---|
[774] | 15 | {
|
---|
| 16 | class Heapable
|
---|
| 17 | {
|
---|
| 18 | private:
|
---|
| 19 | int token;
|
---|
| 20 |
|
---|
| 21 | public:
|
---|
| 22 | Heapable() { notInHeap(); }
|
---|
| 23 |
|
---|
| 24 | inline int isInHeap() { return token!=NOT_IN_HEAP; }
|
---|
| 25 | inline void notInHeap() { token = NOT_IN_HEAP; }
|
---|
| 26 | inline int getHeapPos() { return token; }
|
---|
| 27 | inline void setHeapPos(int t) { token=t; }
|
---|
| 28 | };
|
---|
| 29 |
|
---|
| 30 |
|
---|
| 31 | class heap_node {
|
---|
| 32 | public:
|
---|
| 33 | float import;
|
---|
| 34 | Heapable *obj;
|
---|
| 35 |
|
---|
| 36 | heap_node() { obj=NULL; import=0.0; }
|
---|
| 37 | heap_node(Heapable *t, float i=0.0) { obj=t; import=i; }
|
---|
| 38 | heap_node(const heap_node& h) { import=h.import; obj=h.obj; }
|
---|
| 39 | };
|
---|
| 40 |
|
---|
| 41 |
|
---|
| 42 |
|
---|
| 43 | class Heap : public array<heap_node> {
|
---|
| 44 |
|
---|
| 45 | //
|
---|
| 46 | // The actual size of the heap. array::length()
|
---|
| 47 | // simply returns the amount of allocated space
|
---|
| 48 | int size;
|
---|
| 49 |
|
---|
| 50 | void swap(int i, int j);
|
---|
| 51 |
|
---|
| 52 | int parent(int i) { return (i-1)/2; }
|
---|
| 53 | int left(int i) { return 2*i+1; }
|
---|
| 54 | int right(int i) { return 2*i+2; }
|
---|
| 55 |
|
---|
| 56 | void upheap(int i);
|
---|
| 57 | void downheap(int i);
|
---|
| 58 |
|
---|
| 59 | public:
|
---|
| 60 |
|
---|
| 61 | Heap() { size=0; }
|
---|
| 62 | Heap(int s) : array<heap_node>(s) { size=0; }
|
---|
| 63 |
|
---|
| 64 |
|
---|
| 65 | void insert(Heapable *, float);
|
---|
| 66 | void update(Heapable *, float);
|
---|
| 67 |
|
---|
| 68 | heap_node *extract();
|
---|
| 69 | heap_node *top() { return size<1 ? (heap_node *)NULL : &ref(0); }
|
---|
| 70 | heap_node *kill(int i);
|
---|
| 71 | };
|
---|
| 72 |
|
---|
| 73 | }
|
---|
| 74 |
|
---|
| 75 |
|
---|
| 76 | // GFXTOOLS_HEAP_INCLUDED
|
---|
| 77 | #endif
|
---|
Note: See
TracBrowser
for help on using the repository browser.