Revision 1025,
2.1 KB
checked in by gumbau, 18 years ago
(diff) |
namespace simplif
|
Line | |
---|
1 | //#include <iostream.h>
|
---|
2 | #include <gfx/std.h>
|
---|
3 | #include <gfx/tools/Heap.h>
|
---|
4 |
|
---|
5 | using namespace simplif;
|
---|
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.