1 #include "ltfat.h"
2 #include "ltfat/types.h"
3 #include "ltfat/macros.h"
4
LTFAT_NAME(heap)5 struct LTFAT_NAME(heap)
6 {
7 ltfat_int* h;
8 ltfat_int heapsize;
9 ltfat_int totalheapsize;
10 const LTFAT_REAL* s;
11 };
12
LTFAT_NAME(heap)13 LTFAT_API LTFAT_NAME(heap)*
14 LTFAT_NAME(heap_init)(ltfat_int initmaxsize, const LTFAT_REAL* s)
15 {
16 LTFAT_NAME(heap)* h = (LTFAT_NAME(heap)*) ltfat_malloc(sizeof * h);
17
18 h->totalheapsize = initmaxsize;
19 h->h = (ltfat_int*) ltfat_malloc(h->totalheapsize * sizeof * h->h);
20 h->s = s;
21 h->heapsize = 0;
22 return h;
23 }
24
25 LTFAT_API void
LTFAT_NAME(heap_done)26 LTFAT_NAME(heap_done)(LTFAT_NAME(heap)* h)
27 {
28 ltfat_free(h->h);
29 ltfat_free(h);
30 }
31
32 LTFAT_API void
LTFAT_NAME(heap_reset)33 LTFAT_NAME(heap_reset)(LTFAT_NAME(heap)* h, const LTFAT_REAL* news)
34 {
35 h->s = news;
36 h->heapsize = 0;
37 }
38
39 LTFAT_API void
LTFAT_NAME(heap_grow)40 LTFAT_NAME(heap_grow)(LTFAT_NAME(heap)* h, int factor)
41 {
42 h->totalheapsize *= factor;
43 h->h = (ltfat_int*)ltfat_realloc((void*)h->h,
44 h->totalheapsize * sizeof * h->h / factor,
45 h->totalheapsize * sizeof * h->h);
46 }
47
48 LTFAT_API void
LTFAT_NAME(heap_insert)49 LTFAT_NAME(heap_insert)(LTFAT_NAME(heap) *h, ltfat_int key)
50 {
51 ltfat_int pos, pos2;
52
53 /* Grow heap if necessary */
54 if (h->totalheapsize == h->heapsize)
55 LTFAT_NAME(heap_grow)( h, 2);
56
57 pos = h->heapsize;
58 h->heapsize++;
59
60 LTFAT_REAL val = h->s[key];
61
62 while (pos > 0)
63 {
64 /* printf("pos %i\n",pos); */
65 pos2 = (pos - 1) >> 1;
66
67 if (h->s[h->h[pos2]] < val )
68 h->h[pos] = h->h[pos2];
69 else
70 break;
71
72 pos = pos2;
73 }
74
75 h->h[pos] = key;
76 }
77
78 LTFAT_API ltfat_int
LTFAT_NAME(heap_get)79 LTFAT_NAME(heap_get)(LTFAT_NAME(heap) *h)
80 {
81 if (h->heapsize == 0) return LTFATERR_UNDERFLOW;
82 return h->h[0];
83 }
84
85 LTFAT_API ltfat_int
LTFAT_NAME(heap_delete)86 LTFAT_NAME(heap_delete)(LTFAT_NAME(heap) *h)
87 {
88
89 ltfat_int pos, pos2, retkey, key;
90 LTFAT_REAL maxchildkey, val;
91
92 if (h->heapsize == 0) return LTFATERR_UNDERFLOW;
93 /* Extract first element */
94 retkey = h->h[0];
95 key = h->h[h->heapsize - 1];
96 val = h->s[key];
97
98 h->heapsize--;
99
100 pos = 0;
101 pos2 = 1;
102
103 while (pos2 < h->heapsize)
104 {
105 if ( (pos2 + 2 > h->heapsize) ||
106 (h->s[h->h[pos2]] >= h->s[h->h[pos2 + 1]]) )
107 maxchildkey = h->s[h->h[pos2]];
108 else
109 maxchildkey = h->s[h->h[++pos2]];
110
111 if (maxchildkey > val)
112 h->h[pos] = h->h[pos2];
113 else
114 break;
115
116 pos = pos2;
117 pos2 = (pos << 1) + 1;
118 }
119
120 h->h[pos] = key;
121
122 return retkey;
123 }
124
125