Priority_Queue :: struct(Value_Type: Type,
given_compare_function: (Value_Type, Value_Type) -> s64) {
count: s64;
items: []Value_Type;
allocator: Allocator;
SIZE_MIN :: 16;
compare_function :: given_compare_function;
}
init :: (pqueue: *Priority_Queue) {
Basic.remember_allocators(pqueue);
}
deinit :: (pqueue: *Priority_Queue) {
if pqueue.items.count > 0 {
Basic.array_free(pqueue.items);
pqueue.items.count = 0;
pqueue.items.data = null;
}
pqueue.count = 0;
}
add :: (pqueue: *Priority_Queue, item: pqueue.Value_Type) {
ensure_unused_capacity(pqueue, 1);
add_unchecked(pqueue, item);
}
add_unchecked :: (pqueue: *Priority_Queue, item: pqueue.Value_Type) {
pqueue.items[pqueue.count] = item;
sift_up(pqueue, xx pqueue.count);
pqueue.count += 1;
}
sift_up :: (pqueue: *Priority_Queue, start_index: u64) {
child := pqueue.items[start_index];
child_index := start_index;
while child_index > 0 {
parent_index := ((child_index - 1) >> 1);
parent := pqueue.items[parent_index];
if pqueue.compare_function(child, parent) >= 0 break;
pqueue.items[child_index] = parent;
child_index = parent_index;
}
pqueue.items[child_index] = child;
}
sift_down :: (pqueue: *Priority_Queue, target_index: u64) {
target_element := pqueue.items[target_index];
index := target_index;
while true {
lesser_child_i := (index * 2) | 1;
if !(xx lesser_child_i < pqueue.count) break;
next_child_i := lesser_child_i + 1;
if next_child_i < xx pqueue.count && pqueue.compare_function(pqueue.items[next_child_i], pqueue.items[lesser_child_i]) < 0 {
lesser_child_i = next_child_i;
}
if pqueue.compare_function(target_element, pqueue.items[lesser_child_i]) < 0 break;
pqueue.items[index] = pqueue.items[lesser_child_i];
index = lesser_child_i;
}
pqueue.items[index] = target_element;
}
ensure_unused_capacity :: (pqueue: *Priority_Queue, additional_count: u64) {
ensure_total_capacity(pqueue, xx pqueue.count + additional_count);
}
ensure_total_capacity :: (pqueue: *Priority_Queue, new_capacity: u64) {
better_capacity := capacity(pqueue);
if better_capacity >= new_capacity return;
while true {
better_capacity += better_capacity / 2 + 8;
if better_capacity >= new_capacity break;
}
if pqueue.items.count == 0 {
pqueue.items = Basic.NewArray(xx better_capacity, pqueue.Value_Type);
} else {
old_items := pqueue.items;
pqueue.items = NewArray(xx better_capacity, pqueue.Value_Type);
memcpy(pqueue.items.data, old_items.data, size_of(pqueue.Value_Type) * old_items.count);
array_free(old_items);
}
}
capacity :: (pqueue: *Priority_Queue) -> u64 {
return xx pqueue.items.count;
}
remove_top :: (pqueue: *Priority_Queue) -> (success: bool, item: pqueue.Value_Type) {
if pqueue.count > 0 {
return true, remove_index(pqueue, 0);
} else {
dummy: pqueue.Value_Type = ---;
return false, dummy;
}
}
remove_index :: (pqueue: *Priority_Queue, index: u64) -> pqueue.Value_Type {
assert(cast(u64)pqueue.count > index);
last := pqueue.items[pqueue.count - 1];
item := pqueue.items[index];
pqueue.items[index] = last;
pqueue.count -= 1;
if index == 0 {
sift_down(pqueue, index);
} else {
parent_index := ((index - 1) >> 1);
parent := pqueue.items[parent_index];
if pqueue.compare_function(last, parent) > 0 {
sift_down(pqueue, index);
} else {
sift_up(pqueue, xx index);
}
}
return item;
}
#scope_file
Basic :: #import "Basic";