Revision 1600,
1.9 KB
checked in by gumbau, 18 years ago
(diff) |
Fixed simplification bug when simplifying to extremely a low factor
|
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 | {
|
---|
24 | swap(i,parent(i));
|
---|
25 | upheap(parent(i));
|
---|
26 | }
|
---|
27 | }
|
---|
28 |
|
---|
29 | void Heap::downheap(int i)
|
---|
30 | {
|
---|
31 | if (i>=size) return; // perhaps just extracted the last
|
---|
32 |
|
---|
33 | int largest = i,
|
---|
34 | l = left(i),
|
---|
35 | r = right(i);
|
---|
36 |
|
---|
37 | if( l<size && ref(l).import > ref(largest).import ) largest = l;
|
---|
38 | if( r<size && ref(r).import > ref(largest).import ) largest = r;
|
---|
39 |
|
---|
40 | if( largest != i ) {
|
---|
41 | swap(i,largest);
|
---|
42 | downheap(largest);
|
---|
43 | }
|
---|
44 | }
|
---|
45 |
|
---|
46 | void Heap::insert(Heapable *t,float v)
|
---|
47 | {
|
---|
48 | if( size == maxLength() )
|
---|
49 | {
|
---|
50 | std::cerr << "NOTE: Growing heap from " << size << " to " << 2*size << std::endl;
|
---|
51 | resize(2*size);
|
---|
52 | }
|
---|
53 |
|
---|
54 | int i = size++;
|
---|
55 |
|
---|
56 | ref(i).obj = t;
|
---|
57 | ref(i).import = v;
|
---|
58 |
|
---|
59 | ref(i).obj->setHeapPos(i);
|
---|
60 |
|
---|
61 | upheap(i);
|
---|
62 | }
|
---|
63 |
|
---|
64 | void Heap::update(Heapable *t,float v)
|
---|
65 | {
|
---|
66 | int i = t->getHeapPos();
|
---|
67 |
|
---|
68 | if( i >= size )
|
---|
69 | {
|
---|
70 | std::cerr << "WARNING: Attempting to update past end of heap!" << std::endl;
|
---|
71 | return;
|
---|
72 | }
|
---|
73 | else if( i == NOT_IN_HEAP )
|
---|
74 | {
|
---|
75 | std::cerr << "WARNING: Attempting to update object not in heap!" << std::endl;
|
---|
76 | return;
|
---|
77 | }
|
---|
78 |
|
---|
79 | float old=ref(i).import;
|
---|
80 | ref(i).import = v;
|
---|
81 |
|
---|
82 | if( v<old )
|
---|
83 | downheap(i);
|
---|
84 | else
|
---|
85 | upheap(i);
|
---|
86 | }
|
---|
87 |
|
---|
88 | heap_node *Heap::extract()
|
---|
89 | {
|
---|
90 | if( size<1 ) return 0;
|
---|
91 |
|
---|
92 | swap(0,size-1);
|
---|
93 | size--;
|
---|
94 |
|
---|
95 | downheap(0);
|
---|
96 |
|
---|
97 | ref(size).obj->notInHeap();
|
---|
98 |
|
---|
99 | return &ref(size);
|
---|
100 | }
|
---|
101 |
|
---|
102 | heap_node *Heap::kill(int i)
|
---|
103 | {
|
---|
104 | if( i>=size )
|
---|
105 | std::cerr << "WARNING: Attempt to delete invalid heap node." << std::endl;
|
---|
106 |
|
---|
107 | swap(i, size-1);
|
---|
108 | size--;
|
---|
109 | ref(size).obj->notInHeap();
|
---|
110 |
|
---|
111 | if( ref(i).import < ref(size).import )
|
---|
112 | downheap(i);
|
---|
113 | else
|
---|
114 | upheap(i);
|
---|
115 |
|
---|
116 | return &ref(size);
|
---|
117 | }
|
---|
118 |
|
---|
Note: See
TracBrowser
for help on using the repository browser.