Branch data Line data Source code
1 : : #ifndef GFXTOOLS_HEAP_INCLUDED // -*- C++ -*-
2 : : #define GFXTOOLS_HEAP_INCLUDED
3 : :
4 : : #include "Array.h"
5 : :
6 : : #define NOT_IN_HEAP -47
7 : :
8 : : //
9 : : //
10 : : // This file extracted from Terra
11 : : //
12 : : //
13 : :
14 : : class Heapable
15 : : {
16 : : private:
17 : : int token;
18 : :
19 : : public:
20 : 30400 : Heapable() { notInHeap(); }
21 : :
22 : 124324 : inline int isInHeap() { return token!=NOT_IN_HEAP; }
23 : 16746 : inline void notInHeap() { token = NOT_IN_HEAP; }
24 : 92836 : inline int getHeapPos() { return token; }
25 : 630528 : inline void setHeapPos(int t) { token=t; }
26 : : };
27 : :
28 : :
29 : : class heap_node {
30 : : public:
31 : : double import;
32 : : Heapable *obj;
33 : :
34 : 15200 : heap_node() { obj=NULL; import=0.0; }
35 : : heap_node(Heapable *t, double i=0.0) { obj=t; import=i; }
36 : 269664 : heap_node(const heap_node& h) { import=h.import; obj=h.obj; }
37 : : };
38 : :
39 : :
40 : :
41 : : class Heap : public array<heap_node> {
42 : :
43 : : //
44 : : // The actual size of the heap. array::length()
45 : : // simply returns the amount of allocated space
46 : : int size;
47 : :
48 : : void swap(int i, int j);
49 : :
50 : 1672584 : int parent(int i) { return (i-1)/2; }
51 : 286320 : int left(int i) { return 2*i+1; }
52 : 286320 : int right(int i) { return 2*i+2; }
53 : :
54 : : void upheap(int i);
55 : : void downheap(int i);
56 : :
57 : : public:
58 : :
59 : : Heap() { size=0; }
60 : 4 : Heap(int s) : array<heap_node>(s) { size=0; }
61 : :
62 : :
63 : : void insert(Heapable *, double);
64 : : void update(Heapable *, double);
65 : :
66 : : heap_node *extract();
67 [ + - ]: 1088 : heap_node *top() { return size<1 ? (heap_node *)NULL : &ref(0); }
68 : : heap_node *kill(int i);
69 : : };
70 : :
71 : :
72 : :
73 : : // GFXTOOLS_HEAP_INCLUDED
74 : : #endif
|