[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 | {
|
---|
[1526] | 18 | private:
|
---|
[774] | 19 |
|
---|
[1526] | 20 | int token;
|
---|
[774] | 21 |
|
---|
[1526] | 22 | public:
|
---|
[774] | 23 |
|
---|
[1526] | 24 | Heapable() { notInHeap(); }
|
---|
[774] | 25 |
|
---|
[1526] | 26 | inline int isInHeap() { return token!=NOT_IN_HEAP; }
|
---|
| 27 | inline void notInHeap() { token = NOT_IN_HEAP; }
|
---|
| 28 | inline int getHeapPos() { return token; }
|
---|
| 29 | inline void setHeapPos(int t) { token=t; }
|
---|
[774] | 30 | };
|
---|
| 31 |
|
---|
[1526] | 32 | class heap_node
|
---|
| 33 | {
|
---|
| 34 | public:
|
---|
[2291] | 35 |
|
---|
[1526] | 36 | float import;
|
---|
| 37 | Heapable *obj;
|
---|
[774] | 38 |
|
---|
[1526] | 39 | heap_node() { obj=NULL; import=0.0; }
|
---|
| 40 | heap_node(Heapable *t, float i=0.0) { obj=t; import=i; }
|
---|
| 41 | heap_node(const heap_node& h) { import=h.import; obj=h.obj; }
|
---|
| 42 | };
|
---|
[774] | 43 |
|
---|
[1526] | 44 | class Heap : public array<heap_node>
|
---|
| 45 | {
|
---|
[774] | 46 | //
|
---|
| 47 | // The actual size of the heap. array::length()
|
---|
| 48 | // simply returns the amount of allocated space
|
---|
| 49 | int size;
|
---|
| 50 |
|
---|
| 51 | void swap(int i, int j);
|
---|
| 52 |
|
---|
| 53 | int parent(int i) { return (i-1)/2; }
|
---|
| 54 | int left(int i) { return 2*i+1; }
|
---|
| 55 | int right(int i) { return 2*i+2; }
|
---|
| 56 |
|
---|
| 57 | void upheap(int i);
|
---|
| 58 | void downheap(int i);
|
---|
| 59 |
|
---|
[1526] | 60 | public:
|
---|
[774] | 61 |
|
---|
| 62 | Heap() { size=0; }
|
---|
| 63 | Heap(int s) : array<heap_node>(s) { size=0; }
|
---|
| 64 |
|
---|
| 65 | void insert(Heapable *, float);
|
---|
| 66 | void update(Heapable *, float);
|
---|
| 67 |
|
---|
| 68 | heap_node *extract();
|
---|
[1526] | 69 |
|
---|
[774] | 70 | heap_node *top() { return size<1 ? (heap_node *)NULL : &ref(0); }
|
---|
| 71 | heap_node *kill(int i);
|
---|
[1526] | 72 |
|
---|
| 73 | // Gets heap size.
|
---|
| 74 | int getSize(){return size;}
|
---|
| 75 |
|
---|
| 76 | // Gets element at position i.
|
---|
| 77 | heap_node *getElement(int i){return &ref(i);}
|
---|
| 78 |
|
---|
[774] | 79 | };
|
---|
| 80 |
|
---|
| 81 | }
|
---|
| 82 |
|
---|
| 83 | // GFXTOOLS_HEAP_INCLUDED
|
---|
| 84 | #endif
|
---|
[1526] | 85 |
|
---|