heap_api.h

Go to the documentation of this file.

/*
    MIT License
 
    Copyright (c) 2025 Robin A. Onsay
 
    Permission is hereby granted, free of charge, to any person obtaining
    a copy of this software and associated documentation files
    (the "Software"), to deal in the Software without restriction,
    including without limitation the rights to use, copy, modify, merge,
    publish, distribute, sublicense, and/or sell copies of the Software,
    and to permit persons to whom the Software is furnished to do so,
    subject to the following conditions:
 
    The above copyright notice and this permission notice shall be
    included in all copies or substantial portions of the Software.
*/
 
#ifndef JUNO_DS_API_H
#define JUNO_DS_API_H
#include "juno/macros.h"
#include "juno/status.h"
#include "juno/module.h"
#include <stdbool.h>
#include <stddef.h>
#ifdef __cplusplus
extern "C"
{
#endif
 
typedef struct JUNO_DS_HEAP_ROOT_TAG JUNO_DS_HEAP_ROOT_T;   
typedef struct JUNO_DS_HEAP_API_TAG  JUNO_DS_HEAP_API_T;    
JUNO_MODULE_RESULT(JUNO_DS_HEAP_INDEX_RESULT_T, size_t);
 
JUNO_MODULE_OPTION(JUNO_DS_HEAP_INDEX_OPTION_T, size_t);
 
JUNO_MODULE_RESULT(JUNO_DS_HEAP_INDEX_OPTION_RESULT_T, JUNO_DS_HEAP_INDEX_OPTION_T);
 
JUNO_MODULE_RESULT(JUNO_DS_HEAP_COMPARE_RESULT_T, bool);
 
struct JUNO_DS_HEAP_ROOT_TAG JUNO_MODULE_ROOT(JUNO_DS_HEAP_API_T,
    size_t zCapacity;   
    size_t zLength;     
);
 
struct JUNO_DS_HEAP_API_TAG
{
    JUNO_DS_HEAP_COMPARE_RESULT_T (*Compare)(JUNO_DS_HEAP_ROOT_T *ptHeap, size_t parent, size_t child);
    JUNO_STATUS_T (*Swap)(JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iFrom, size_t iTo);
    JUNO_STATUS_T (*Reset)(JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iIndex);
};
 
JUNO_STATUS_T JunoDs_Heap_Update(JUNO_DS_HEAP_ROOT_T *ptHeap);
 
JUNO_STATUS_T JunoDs_Heap_SiftDown(JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iStart);
 
static inline JUNO_STATUS_T JunoDs_Heap_Verify(JUNO_DS_HEAP_ROOT_T *ptHeap)
{
    JUNO_STATUS_T tStatus = JUNO_STATUS_SUCCESS;
    if(!(ptHeap && ptHeap->ptApi && ptHeap->zCapacity))
    {
        tStatus = JUNO_STATUS_NULLPTR_ERROR;
    }
    return tStatus;
}
 
static inline JUNO_STATUS_T JunoDs_Heap_Init(JUNO_DS_HEAP_ROOT_T *ptHeap, const JUNO_DS_HEAP_API_T *ptApi, size_t zCapacity)
{
    JUNO_ASSERT_EXISTS(ptHeap);
    ptHeap->ptApi = ptApi;
    ptHeap->zCapacity = zCapacity;
    ptHeap->zLength = 0;
    return JunoDs_Heap_Verify(ptHeap);
}
 
static inline JUNO_DS_HEAP_INDEX_OPTION_RESULT_T JunoDs_Heap_ChildGetLeft(JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iIndex)
{
    JUNO_DS_HEAP_INDEX_OPTION_RESULT_T tResult = {JUNO_STATUS_SUCCESS, {false, 0}};
    tResult.tStatus = JunoDs_Heap_Verify(ptHeap);
    JUNO_ASSERT_SUCCESS(tResult.tStatus, return tResult);
    iIndex = 2 * iIndex + 1;
    if(iIndex > ptHeap->zCapacity || ptHeap->zLength > ptHeap->zCapacity)
    {
        tResult.tStatus = JUNO_STATUS_ERR;
        return tResult;
    }
    if(iIndex >= ptHeap->zLength)
    {
        tResult.tStatus = JUNO_STATUS_SUCCESS;
        tResult.tOk.bIsSome = false;
        return tResult;
    }
    tResult.tStatus = JUNO_STATUS_SUCCESS;
    tResult.tOk.bIsSome = true;
    tResult.tOk.tSome = iIndex;
    return tResult;
}
 
static inline JUNO_DS_HEAP_INDEX_OPTION_RESULT_T JunoDs_Heap_ChildGetRight(JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iIndex)
{
    JUNO_DS_HEAP_INDEX_OPTION_RESULT_T tResult = {JUNO_STATUS_SUCCESS, {false, 0}};
    tResult.tStatus = JunoDs_Heap_Verify(ptHeap);
    JUNO_ASSERT_SUCCESS(tResult.tStatus, return tResult);
    iIndex = 2 * iIndex + 2;
    if(iIndex > ptHeap->zCapacity || ptHeap->zLength > ptHeap->zCapacity)
    {
        tResult.tStatus = JUNO_STATUS_ERR;
        return tResult;
    }
    if(iIndex >= ptHeap->zLength)
    {
        tResult.tStatus = JUNO_STATUS_SUCCESS;
        tResult.tOk.bIsSome = false;
        return tResult;
    }
    tResult.tStatus = JUNO_STATUS_SUCCESS;
    tResult.tOk.bIsSome = true;
    tResult.tOk.tSome = iIndex;
    return tResult;
}
 
static inline JUNO_DS_HEAP_INDEX_OPTION_RESULT_T JunoDs_Heap_ChildGetParent(JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iIndex)
{
    JUNO_DS_HEAP_INDEX_OPTION_RESULT_T tResult = {JUNO_STATUS_SUCCESS, {false, 0}};
    tResult.tStatus = JunoDs_Heap_Verify(ptHeap);
    JUNO_ASSERT_SUCCESS(tResult.tStatus, return tResult);
    iIndex = (iIndex - 1)/2;
    if(iIndex > ptHeap->zCapacity || ptHeap->zLength > ptHeap->zCapacity)
    {
        tResult.tStatus = JUNO_STATUS_ERR;
        return tResult;
    }
    if(iIndex >= ptHeap->zLength)
    {
        tResult.tStatus = JUNO_STATUS_SUCCESS;
        tResult.tOk.bIsSome = false;
        return tResult;
    }
    tResult.tStatus = JUNO_STATUS_SUCCESS;
    tResult.tOk.bIsSome = true;
    tResult.tOk.tSome = iIndex;
    return tResult;
}
 
static inline JUNO_DS_HEAP_INDEX_RESULT_T JunoDs_Heap_Insert(JUNO_DS_HEAP_ROOT_T *ptHeap)
{
    JUNO_DS_HEAP_INDEX_RESULT_T tResult = {JUNO_STATUS_SUCCESS, 0};
    tResult.tStatus = JunoDs_Heap_Verify(ptHeap);
    JUNO_ASSERT_SUCCESS(tResult.tStatus, return tResult);
    if(ptHeap->zLength >= ptHeap->zCapacity)
    {
        tResult.tStatus = JUNO_STATUS_ERR;
        return tResult;
    }
    tResult.tOk = ptHeap->zLength;
    ptHeap->zLength += 1;
    return tResult;
}
 
static inline JUNO_STATUS_T JunoDs_Heap_Heapify(JUNO_DS_HEAP_ROOT_T *ptHeap)
{
    JUNO_STATUS_T tStatus = JUNO_STATUS_SUCCESS;
    tStatus = JunoDs_Heap_Verify(ptHeap);
    JUNO_ASSERT_SUCCESS(tStatus, return tStatus);
    if(ptHeap->zLength <= 0)
    {
        tStatus = JUNO_STATUS_ERR;
        return tStatus;
    }
    JUNO_DS_HEAP_INDEX_OPTION_RESULT_T iIndexResult = JunoDs_Heap_ChildGetParent(ptHeap, ptHeap->zLength);
    JUNO_ASSERT_SUCCESS(iIndexResult.tStatus, return iIndexResult.tStatus);
    if(!iIndexResult.tOk.bIsSome)
    {
        return tStatus;
    }
    size_t iIndex = iIndexResult.tOk.tSome;
    for(size_t i = 0; i <= iIndex; ++i)
    {
        size_t iCurrentIndex = iIndex - i;
        tStatus = JunoDs_Heap_SiftDown(ptHeap, iCurrentIndex);
        JUNO_ASSERT_SUCCESS(tStatus, continue);
    }
    return tStatus;
}
 
static inline JUNO_STATUS_T JunoDs_Heap_Delete(JUNO_DS_HEAP_ROOT_T *ptHeap)
{
    JUNO_STATUS_T tStatus = JUNO_STATUS_SUCCESS;;
    tStatus = JunoDs_Heap_Verify(ptHeap);
    JUNO_ASSERT_SUCCESS(tStatus, return tStatus);
    if(ptHeap->zLength <= 0)
    {
        tStatus = JUNO_STATUS_ERR;
        return tStatus;
    }
    tStatus = ptHeap->ptApi->Swap(ptHeap, ptHeap->zLength-1, 0);
    JUNO_ASSERT_SUCCESS(tStatus, return tStatus);
    ptHeap->ptApi->Reset(ptHeap, ptHeap->zLength-1);
    JUNO_ASSERT_SUCCESS(tStatus, return tStatus);
    ptHeap->zLength -= 1;
    return JunoDs_Heap_SiftDown(ptHeap, 0);
}
 
#ifdef __cplusplus
}
#endif
#endif // JUNO_DS_API_H