/* SPDX-License-Identifier: GPL-3.0-or-later */

#pragma once

#include <stddef.h>
#include <stdint.h>

//
// This module implements a binary heap, specifically a min-heap. Each node contains a 64-bit
// value and a pointer to user data (user data is reused when nodes are extracted). All memory
// is a single contiguous chunk.
//
// In a min-heap, the root node always has the smallest value. The root node can be
// acquired with heap_next_extract() and extracted (removed) with heap_extract().
// The runtime of heap_extract() is O(log n).
//
// Prior to insertion, the node that will be inserted can already be obtained with
// heap_next_insert(), which MUST be succeeded by heap_insert() to actually insert the node.
// The runtime of heap_insert() is O(log n).
//

typedef struct {
    uint64_t value;
    void* user;
} heap_node_t; //!< Node in a heap

typedef struct {
    heap_node_t* nodes;
    size_t capacity;
    size_t count;
} heap_t; //!< Min-heap data structure

/// Initialize a min-heap with the given capacity. The user_sizeof parameter specifies the size
/// of user data stored in each node.
/// Returns 0 on success, -1 on allocation failure.
int heap_init(heap_t* heap, size_t capacity, size_t user_sizeof);

/// Obtain the heap node that will be inserted next.
/// Returns heap node on success, or nullptr if the heap is full.
heap_node_t* heap_next_insert(heap_t* heap);

/// Insert a value into the heap.
void heap_insert(heap_t* heap, uint64_t value);

/// Peek the minimum value in the heap without removing it.
/// Returns heap node on success, or nullptr if the heap is empty.
heap_node_t* heap_next_extract(heap_t* heap);

/// Extract a node from the heap.
void heap_extract(heap_t* heap);

/// Free all resources associated with the heap.
void heap_free(heap_t* heap);