Revision 1025,
1.4 KB
checked in by gumbau, 18 years ago
(diff) |
namespace simplif
|
Line | |
---|
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 |
|
---|
14 | namespace simplif
|
---|
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.