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 |
|
---|
20 | int token;
|
---|
21 |
|
---|
22 | public:
|
---|
23 |
|
---|
24 | Heapable() { notInHeap(); }
|
---|
25 |
|
---|
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; }
|
---|
30 | };
|
---|
31 |
|
---|
32 | class heap_node
|
---|
33 | {
|
---|
34 | public:
|
---|
35 |
|
---|
36 | float import;
|
---|
37 | Heapable *obj;
|
---|
38 |
|
---|
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 | };
|
---|
43 |
|
---|
44 | class Heap : public array<heap_node>
|
---|
45 | {
|
---|
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 |
|
---|
60 | public:
|
---|
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();
|
---|
69 |
|
---|
70 | heap_node *top() { return size<1 ? (heap_node *)NULL : &ref(0); }
|
---|
71 | heap_node *kill(int i);
|
---|
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 |
|
---|
79 | };
|
---|
80 |
|
---|
81 | }
|
---|
82 |
|
---|
83 | // GFXTOOLS_HEAP_INCLUDED
|
---|
84 | #endif
|
---|
85 |
|
---|