Program Listing for File binheap.h

↰ Return to documentation for file (rcsw/ds/binheap.h)

#pragma once

/*******************************************************************************
 * Includes
 ******************************************************************************/
#include <math.h>

#include "rcsw/ds/ds.h"
#include "rcsw/ds/darray.h"
#include "rcsw/common/fpc.h"

/*******************************************************************************
 * Macro Definitions
 ******************************************************************************/
#define RCSW_BINHEAP_LCHILD(i) (2*(i))

#define RCSW_BINHEAP_RCHILD(i) (2*(i)+1)

#define RCSW_BINHEAP_PARENT(i) ((i)/2)

/*******************************************************************************
 * Structure Definitions
 ******************************************************************************/
struct binheap_params {
  int (*cmpe)(const void *const e1, const void *const e2);

  int (*cmpkey)(const void *const e1, const void *const e2);

  void (*printe)(const void *e);

  dptr_t *elements;

  size_t elt_size;

  size_t max_elts;

  uint32_t flags;

  size_t init_size;
};

struct binheap {
  struct darray arr;

  uint32_t flags;
};

/*******************************************************************************
 * API Functions
 ******************************************************************************/
BEGIN_C_DECLS

static inline bool_t binheap_isfull(const struct binheap* const heap) {
    RCSW_FPC_NV(false, NULL != heap);
    return darray_isfull(&heap->arr);
}

static inline bool_t binheap_isempty(const struct binheap* const heap) {
    RCSW_FPC_NV(false, NULL != heap);
    return (darray_size(&heap->arr) == 1);
}

static inline size_t binheap_size(const struct binheap* const heap) {
    RCSW_FPC_NV(0, NULL != heap);
    return darray_size(&heap->arr) - 1; /* -1 for tmp element */
}

static inline size_t binheap_capacity(struct binheap * heap) {
  RCSW_FPC_NV(0, NULL != heap);
  return darray_capacity(&heap->arr);
}

static inline size_t binheap_element_space(size_t max_elts, size_t elt_size) {
  /* +1 is for the tmp element at index 0 */
  return darray_element_space(max_elts, elt_size) + elt_size;
}

static inline status_t binheap_clear(struct binheap * heap) {
    RCSW_FPC_NV(ERROR, heap != NULL);
    return darray_clear(&heap->arr);
}

static inline void* binheap_peek(const struct binheap * heap) {
    RCSW_FPC_NV(NULL, heap != NULL, !binheap_isempty(heap));
    return darray_data_get(&heap->arr, 1);
}

static inline size_t binheap_height(const struct binheap * heap) {
  return (size_t)(log10(binheap_size(heap)) / log10(2));
}

RCSW_API struct binheap *binheap_init(struct binheap *heap_in,
                             const struct binheap_params * params) RCSW_WUR;

RCSW_API void binheap_destroy(struct binheap *heap);

RCSW_API status_t binheap_insert(struct binheap * heap, const void * e);

RCSW_API status_t binheap_make(struct binheap * heap, const void* data,
                       size_t n_elts);

RCSW_API status_t binheap_extract(struct binheap * heap, void * e);


RCSW_API status_t binheap_delete_key(struct binheap* heap, size_t index,
                             const void* minmax);

RCSW_API status_t binheap_update_key(struct binheap* heap, size_t index,
                                     const void* new_val);

RCSW_API void binheap_print(const struct binheap * heap);

END_C_DECLS