Revision 1025,
2.1 KB
checked in by gumbau, 18 years ago
(diff) |
namespace simplif
|
Rev | Line | |
---|
[774] | 1 | //#include <iostream.h>
|
---|
| 2 | #include <gfx/std.h>
|
---|
| 3 | #include <gfx/tools/Heap.h>
|
---|
| 4 |
|
---|
[1025] | 5 | using namespace simplif;
|
---|
[774] | 6 |
|
---|
| 7 | void Heap::swap(int i,int j)
|
---|
| 8 | {
|
---|
| 9 | heap_node tmp = ref(i);
|
---|
| 10 |
|
---|
| 11 | ref(i) = ref(j);
|
---|
| 12 | ref(j) = tmp;
|
---|
| 13 |
|
---|
| 14 | ref(i).obj->setHeapPos(i);
|
---|
| 15 | ref(j).obj->setHeapPos(j);
|
---|
| 16 | }
|
---|
| 17 |
|
---|
| 18 | void Heap::upheap(int i)
|
---|
| 19 | {
|
---|
| 20 | if( i==0 ) return;
|
---|
| 21 |
|
---|
| 22 | if( ref(i).import > ref(parent(i)).import ) {
|
---|
| 23 | swap(i,parent(i));
|
---|
| 24 | upheap(parent(i));
|
---|
| 25 | }
|
---|
| 26 | }
|
---|
| 27 |
|
---|
| 28 | void Heap::downheap(int i)
|
---|
| 29 | {
|
---|
| 30 | if (i>=size) return; // perhaps just extracted the last
|
---|
| 31 |
|
---|
| 32 | int largest = i,
|
---|
| 33 | l = left(i),
|
---|
| 34 | r = right(i);
|
---|
| 35 |
|
---|
| 36 | if( l<size && ref(l).import > ref(largest).import ) largest = l;
|
---|
| 37 | if( r<size && ref(r).import > ref(largest).import ) largest = r;
|
---|
| 38 |
|
---|
| 39 | if( largest != i ) {
|
---|
| 40 | swap(i,largest);
|
---|
| 41 | downheap(largest);
|
---|
| 42 | }
|
---|
| 43 | }
|
---|
| 44 |
|
---|
| 45 |
|
---|
| 46 |
|
---|
| 47 | void Heap::insert(Heapable *t,float v)
|
---|
| 48 | {
|
---|
| 49 | if( size == maxLength() )
|
---|
| 50 | {
|
---|
| 51 | std::cerr << "NOTE: Growing heap from " << size << " to " << 2*size << std::endl;
|
---|
| 52 | resize(2*size);
|
---|
| 53 | }
|
---|
| 54 |
|
---|
| 55 | int i = size++;
|
---|
| 56 |
|
---|
| 57 | ref(i).obj = t;
|
---|
| 58 | ref(i).import = v;
|
---|
| 59 |
|
---|
| 60 | ref(i).obj->setHeapPos(i);
|
---|
| 61 |
|
---|
| 62 | upheap(i);
|
---|
| 63 | }
|
---|
| 64 |
|
---|
| 65 | void Heap::update(Heapable *t,float v)
|
---|
| 66 | {
|
---|
| 67 | int i = t->getHeapPos();
|
---|
| 68 |
|
---|
| 69 | if( i >= size )
|
---|
| 70 | {
|
---|
| 71 | std::cerr << "WARNING: Attempting to update past end of heap!" << std::endl;
|
---|
| 72 | return;
|
---|
| 73 | }
|
---|
| 74 | else if( i == NOT_IN_HEAP )
|
---|
| 75 | {
|
---|
| 76 | std::cerr << "WARNING: Attempting to update object not in heap!" << std::endl;
|
---|
| 77 | return;
|
---|
| 78 | }
|
---|
| 79 |
|
---|
| 80 | float old=ref(i).import;
|
---|
| 81 | ref(i).import = v;
|
---|
| 82 |
|
---|
| 83 | if( v<old )
|
---|
| 84 | downheap(i);
|
---|
| 85 | else
|
---|
| 86 | upheap(i);
|
---|
| 87 | }
|
---|
| 88 |
|
---|
| 89 |
|
---|
| 90 |
|
---|
| 91 | heap_node *Heap::extract()
|
---|
| 92 | {
|
---|
| 93 | if( size<1 ) return 0;
|
---|
| 94 |
|
---|
| 95 | swap(0,size-1);
|
---|
| 96 | size--;
|
---|
| 97 |
|
---|
| 98 | downheap(0);
|
---|
| 99 |
|
---|
| 100 | ref(size).obj->notInHeap();
|
---|
| 101 |
|
---|
| 102 | return &ref(size);
|
---|
| 103 | }
|
---|
| 104 |
|
---|
| 105 | heap_node *Heap::kill(int i)
|
---|
| 106 | {
|
---|
| 107 | if( i>=size )
|
---|
| 108 | std::cerr << "WARNING: Attempt to delete invalid heap node." << std::endl;
|
---|
| 109 |
|
---|
| 110 | swap(i, size-1);
|
---|
| 111 | size--;
|
---|
| 112 | ref(size).obj->notInHeap();
|
---|
| 113 |
|
---|
| 114 | if( ref(i).import < ref(size).import )
|
---|
| 115 | downheap(i);
|
---|
| 116 | else
|
---|
| 117 | upheap(i);
|
---|
| 118 |
|
---|
| 119 |
|
---|
| 120 | return &ref(size);
|
---|
| 121 | }
|
---|
Note: See
TracBrowser
for help on using the repository browser.