// NOTE: based on this code: https://gist.github.com/martinkunev/1365481
(* ****** ****** *)
%{
typedef int type;
typedef struct heap
{
unsigned int size; // Size of the allocated memory (in number of items)
unsigned int count; // Count of the elements in the heap
type *data; // Array with the elements
} heap_t;
#define CMP(a, b) ((a) >= (b))
static const unsigned int base_size = 4;
// Prepares the heap for use
void heap_init(atsrefarg1_type(heap_t) h)
{
*(heap_t*)h = (struct heap){
.size = base_size,
.count = 0,
.data = malloc(sizeof(type) * base_size)
};
if (!((heap_t*)h)->data) _exit(1); // Exit if the memory allocation fails
}
// Inserts element to the heap
void heap_push(atsrefarg1_type(heap_t) h, type value)
{
unsigned int index, parent;
// Resize the heap if it is too small to hold all the data
if (((heap_t*)h)->count == ((heap_t*)h)->size)
{
((heap_t*)h)->size <<= 1;
((heap_t*)h)->data = realloc(((heap_t*)h)->data, sizeof(type) * ((heap_t*)h)->size);
if (!((heap_t*)h)->data) _exit(1); // Exit if the memory allocation fails
}
// Find out where to put the element and put it
for(index = ((heap_t*)h)->count++; index; index = parent)
{
parent = (index - 1) >> 1;
if CMP(((heap_t*)h)->data[parent], value) break;
((heap_t*)h)->data[index] = ((heap_t*)h)->data[parent];
}
((heap_t*)h)->data[index] = value;
}
// Removes the biggest element from the heap
void heap_pop(atsrefarg1_type(heap_t) h)
{
unsigned int index, swap, other;
// Remove the biggest element
type temp = ((heap_t*)h)->data[--((heap_t*)h)->count];
// Resize the heap if it's consuming too much memory
if ((((heap_t*)h)->count <= (((heap_t*)h)->size >> 2)) && (((heap_t*)h)->size > base_size))
{
((heap_t*)h)->size >>= 1;
((heap_t*)h)->data = realloc(((heap_t*)h)->data, sizeof(type) * ((heap_t*)h)->size);
if (!((heap_t*)h)->data) _exit(1); // Exit if the memory allocation fails
}
// Reorder the elements
for(index = 0; 1; index = swap)
{
// Find the child to swap with
swap = (index << 1) + 1;
if (swap >= ((heap_t*)h)->count) break; // If there are no children, the heap is reordered
other = swap + 1;
if ((other < ((heap_t*)h)->count) && CMP(((heap_t*)h)->data[other], ((heap_t*)h)->data[swap])) swap = other;
if CMP(temp, ((heap_t*)h)->data[swap]) break; // If the bigger child is less than or equal to its parent, the heap is reordered
((heap_t*)h)->data[index] = ((heap_t*)h)->data[swap];
}
((heap_t*)h)->data[index] = temp;
}
// Heapifies a non-empty array
void heapify(type* data, unsigned int count)
{
unsigned int item, index, swap, other;
type temp;
// Move every non-leaf element to the right position in its subtree
item = (count >> 1) - 1;
while (1)
{
// Find the position of the current element in its subtree
temp = data[item];
for(index = item; 1; index = swap)
{
// Find the child to swap with
swap = (index << 1) + 1;
if (swap >= count) break; // If there are no children, the current element is positioned
other = swap + 1;
if ((other < count) && CMP(data[other], data[swap])) swap = other;
if CMP(temp, data[swap]) break; // If the bigger child is smaller than or equal to the parent, the heap is reordered
data[index] = data[swap];
}
if (index != item) data[index] = temp;
if (!item) return;
--item;
}
}
// Returns the biggest element in the heap
#define heap_front(h) ( *(h)->data)
// Frees the allocated memory
#define heap_term(h) (free((h)->data))
%}
(* ****** ****** *)
typedef T = int
abst@ype heap = $extype_struct"heap_t" of {size=int, count=int, data= ptr}
extern
fun
heap_init (&heap? >> _): void = "ext#"
extern
fun
heap_push (&heap, T): void = "ext#"
extern
fun
heap_pop (&heap): void = "ext#"
extern
fun
heap_front (&heap): T = "mac#"
extern
fun
heap_term (&heap >> _?): void = "mac#"
extern
fun
heapify {n:int} (&(@[T][n]) >> @[T][n], int n): void = "ext#"
(* ****** ****** *)
implement main0 () = let
var h: heap
val () = heap_init (h)
val () = heap_push (h, 5)
val () = heap_push (h, 4)
val () = heap_push (h, 6)
val () = heap_push (h, 10)
val () = println!("front: ", heap_front(h))
val () = heap_pop (h)
val () = println!("front:", heap_front(h))
val () = heap_pop (h)
val () = println!("front: ", heap_front(h))
val () = heap_pop (h)
val () = println!("front: ", heap_front(h))
val () = heap_pop (h)
val () = heap_term (h)
in
print"Hello World!\n"
end
