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";