binary_heap.h File Reference

Go to the source code of this file.

Data Structures
struct	cvx_container
struct	binary_heap_vtabv
struct	binary_heap
struct	binary_heap_iter

Typedefs
typedef struct cvx_container	cvx_container

Enumerations
enum	cvx_flags {   CVX_FLAG_OK = 0 , CVX_FLAG_VTAB = 1 , CVX_FLAG_WRONG_TAG = 2 , CVX_FLAG_ALLOC = 3 ,   CVX_FLAG_EMPTY = 4 , CVX_FLAG_FULL = 5 , CVX_FLAG_RANGE = 6 , CVX_FLAG_NOT_FOUND = 7 ,   CVX_FLAG_INVALID = 8 , CVX_FLAG_DUPLICATE = 9 , CVX_FLAG_ERROR = 10 }
	binary_heap.h More...
enum	cvx_heap_order { CVX_MAX_HEAP = 1 , CVX_MIN_HEAP = -1 }
	enum cvx_heap_order More...

Functions
void	bh_init (struct binary_heap *self, struct binary_heap_vtabv *vtabv, enum cvx_heap_order HO, size_t capacity)
	IMPLEMENTATIONS.
void	bh_clone (struct binary_heap *orig, struct binary_heap *clone)
void	bh_drop (struct binary_heap *_self_)
enum cvx_flags	bh_flag (struct binary_heap *_self_)
enum cvx_heap_order	bh_heap_order (struct binary_heap *_self_)
size_t	bh_count (struct binary_heap *_self_)
size_t	bh_capacity (struct binary_heap *_self_)
_Bool	bh_empty (struct binary_heap *_self_)
_Bool	bh_full (struct binary_heap *_self_)
void	bh_push (struct binary_heap *_self_, TVal _item_)
TVal	bh_pop (struct binary_heap *_self_)
TVal	bh_peek (struct binary_heap *_self_)
struct binary_heap_iter	bh_iter_init_start (struct binary_heap *_target_)
	ITERATOR.
struct binary_heap_iter	bh_iter_init_end (struct binary_heap *_target_)
struct binary_heap_iter *	bh_iter_start (struct binary_heap *_target_)
struct binary_heap_iter *	bh_iter_end (struct binary_heap *_target_)
void	bh_iter_drop (struct binary_heap_iter *_iter_)
_Bool	bh_iter_at_start (struct binary_heap_iter *_iter_)
_Bool	bh_iter_at_end (struct binary_heap_iter *_iter_)
size_t	bh_iter_count (struct binary_heap_iter *_iter_)
void	bh_iter_to_start (struct binary_heap_iter *_iter_)
void	bh_iter_to_end (struct binary_heap_iter *_iter_)
void	bh_iter_next (struct binary_heap_iter *_iter_)
void	bh_iter_prev (struct binary_heap_iter *_iter_)
void	bh_iter_forward (struct binary_heap_iter *_iter_, size_t _steps_)
void	bh_iter_backward (struct binary_heap_iter *_iter_, size_t _steps_)
void	bh_iter_go_to (struct binary_heap_iter *_iter_, size_t _index_)
TVal	bh_iter_value (struct binary_heap_iter *_iter_)
size_t	bh_iter_index (struct binary_heap_iter *_iter_)
void	bh__float_up (struct binary_heap *_self_, size_t index)
void	bh__float_down (struct binary_heap *_self_, size_t index)
_Bool	bh__assert_capacity (struct binary_heap *self)
	PRIVATE FUNCTIONS.
_Bool	bh__assert_buffer (struct binary_heap *self, size_t capacity)
void	bh__proxy_clone (cvx_container *_orig_, cvx_container *_clone_)
	PROXY FUNCTIONS (cvx_container * interface with tag guards)
void	bh__proxy_drop (cvx_container *_col_)
enum cvx_flags	bh__proxy_flag (cvx_container *_col_)
size_t	bh__proxy_count (cvx_container *_col_)
size_t	bh__proxy_capacity (cvx_container *_col_)
_Bool	bh__proxy_empty (cvx_container *_col_)
_Bool	bh__proxy_full (cvx_container *_col_)
void	bh__proxy_push (cvx_container *_col_, TVal _item_)
TVal	bh__proxy_pop (cvx_container *_col_)
TVal	bh__proxy_peek (cvx_container *_col_)
cvx_container *	bh__proxy_iter_start (cvx_container *_col_)
cvx_container *	bh__proxy_iter_end (cvx_container *_col_)
void	bh__proxy_iter_drop (cvx_container *_col_)
_Bool	bh__proxy_iter_at_start (cvx_container *_col_)
_Bool	bh__proxy_iter_at_end (cvx_container *_col_)
size_t	bh__proxy_iter_count (cvx_container *_col_)
void	bh__proxy_iter_to_start (cvx_container *_col_)
void	bh__proxy_iter_to_end (cvx_container *_col_)
void	bh__proxy_iter_next (cvx_container *_col_)
void	bh__proxy_iter_prev (cvx_container *_col_)
void	bh__proxy_iter_forward (cvx_container *_col_, size_t _steps_)
void	bh__proxy_iter_backward (cvx_container *_col_, size_t _steps_)
void	bh__proxy_iter_go_to (cvx_container *_col_, size_t _index_)
TVal	bh__proxy_iter_value (cvx_container *_col_)
size_t	bh__proxy_iter_index (cvx_container *_col_)
struct binary_heap_iter	bh__proxy_iter_init_start (cvx_container *_col_)
struct binary_heap_iter	bh__proxy_iter_init_end (cvx_container *_col_)

Typedef Documentation

cvx_container

typedef struct cvx_container cvx_container

Enumeration Type Documentation

cvx_flags

enum cvx_flags

binary_heap.h

Status

[x] concept [x] v1 [ ] tests [ ] refine [ ] stabilize

This is a Binary Heap implementation that uses a contiguous array to store its elements. The indices are a simulated to form a binary tree.

Given a node I at an index i, you can find: Parent(I) = (i - 1) / 2, { for i > 0 } Left(I) = 2i + 1 Right(I) = 2i + 2

Visual structure (representation):

          [ 95 ]                    <-- Root (Level 0)
         /      ///         [ 70 ]      [ 80 ]              <-- Level 1 

/ \ / /// [ 40 ] [ 50 ] [ 10 ] [ 30 ] <– Level 2 Array-based structure (actual structure in memory):

Index: 0 1 2 3 4 5 6 +---—+---—+---—+---—+---—+---—+---—+ Array: | 95 | 70 | 80 | 40 | 50 | 10 | 30 | +---—+---—+---—+---—+---—+---—+---—+ ^ ^ ^ ^ ^ ^ ^ Root L-Child R-Child ... ... ... ...

The heap is by default a Max heap, but it can be initialized with an enum of type cvx_heap_order that is going to multiply the result of your compare function by 1 or -1. This is usefull to keep a single comparison function for the custom type, while being able to check at runtime if a heap is MIN or MAX.

Status and error flags for the CVX library.

Error Handling

Enumerator
CVX_FLAG_OK	No errors.
CVX_FLAG_VTAB	Required vtab function was not provided.
CVX_FLAG_WRONG_TAG	Tags are checked so you don't pass the wrong struct to a function.
CVX_FLAG_ALLOC	Allocation failed.
CVX_FLAG_EMPTY	Operation can not proceed because the container is empty.
CVX_FLAG_FULL	When a container that doesn't resize is full.
CVX_FLAG_RANGE	Index out of range.
CVX_FLAG_NOT_FOUND	Key or value not found.
CVX_FLAG_INVALID	Invalid argument or operation.
CVX_FLAG_DUPLICATE	Duplicate key or value.
CVX_FLAG_ERROR	Generic error, or unknown error.

cvx_heap_order

enum cvx_heap_order

enum cvx_heap_order

Defines the two possible heaps:

• Max Heap has the greatest element at the top
• Min Heap has the smallest element at the top

Enumerator
CVX_MAX_HEAP
CVX_MIN_HEAP

Function Documentation

bh__assert_buffer()

_Bool bh__assert_buffer	(	struct binary_heap *	self,
		size_t	capacity
	)

bh__assert_capacity()

_Bool bh__assert_capacity

(

struct binary_heap *

_self_

)

PRIVATE FUNCTIONS.

bh__float_down()

void bh__float_down	(	struct binary_heap *	_self_,
		size_t	index
	)

bh__float_up()

void bh__float_up	(	struct binary_heap *	_self_,
		size_t	index
	)

bh__proxy_capacity()

size_t bh__proxy_capacity

(

cvx_container *

_col_

)

bh__proxy_clone()

void bh__proxy_clone	(	cvx_container *	_orig_,
		cvx_container *	_clone_
	)

PROXY FUNCTIONS (cvx_container * interface with tag guards)

bh__proxy_count()

size_t bh__proxy_count

(

cvx_container *

_col_

)

bh__proxy_drop()

void bh__proxy_drop

(

cvx_container *

_col_

)

bh__proxy_empty()

_Bool bh__proxy_empty

(

cvx_container *

_col_

)

bh__proxy_flag()

enum cvx_flags bh__proxy_flag

(

cvx_container *

_col_

)

bh__proxy_full()

_Bool bh__proxy_full

(

cvx_container *

_col_

)

bh__proxy_iter_at_end()

_Bool bh__proxy_iter_at_end

(

cvx_container *

_col_

)

bh__proxy_iter_at_start()

_Bool bh__proxy_iter_at_start

(

cvx_container *

_col_

)

bh__proxy_iter_backward()

void bh__proxy_iter_backward	(	cvx_container *	_col_,
		size_t	_steps_
	)

bh__proxy_iter_count()

size_t bh__proxy_iter_count

(

cvx_container *

_col_

)

bh__proxy_iter_drop()

void bh__proxy_iter_drop

(

cvx_container *

_col_

)

bh__proxy_iter_end()

cvx_container * bh__proxy_iter_end

(

cvx_container *

_col_

)

bh__proxy_iter_forward()

void bh__proxy_iter_forward	(	cvx_container *	_col_,
		size_t	_steps_
	)

bh__proxy_iter_go_to()

void bh__proxy_iter_go_to	(	cvx_container *	_col_,
		size_t	_index_
	)

bh__proxy_iter_index()

size_t bh__proxy_iter_index

(

cvx_container *

_col_

)

bh__proxy_iter_init_end()

struct binary_heap_iter bh__proxy_iter_init_end

(

cvx_container *

_col_

)

bh__proxy_iter_init_start()

struct binary_heap_iter bh__proxy_iter_init_start

(

cvx_container *

_col_

)

bh__proxy_iter_next()

void bh__proxy_iter_next

(

cvx_container *

_col_

)

bh__proxy_iter_prev()

void bh__proxy_iter_prev

(

cvx_container *

_col_

)

bh__proxy_iter_start()

cvx_container * bh__proxy_iter_start

(

cvx_container *

_col_

)

bh__proxy_iter_to_end()

void bh__proxy_iter_to_end

(

cvx_container *

_col_

)

bh__proxy_iter_to_start()

void bh__proxy_iter_to_start

(

cvx_container *

_col_

)

bh__proxy_iter_value()

TVal bh__proxy_iter_value

(

cvx_container *

_col_

)

bh__proxy_peek()

TVal bh__proxy_peek

(

cvx_container *

_col_

)

bh__proxy_pop()

TVal bh__proxy_pop

(

cvx_container *

_col_

)

bh__proxy_push()

void bh__proxy_push	(	cvx_container *	_col_,
		TVal	_item_
	)

bh_capacity()

size_t bh_capacity

(

struct binary_heap *

_self_

)

bh_clone()

void bh_clone	(	struct binary_heap *	orig,
		struct binary_heap *	clone
	)

bh_count()

size_t bh_count

(

struct binary_heap *

_self_

)

bh_drop()

void bh_drop

(

struct binary_heap *

_self_

)

bh_empty()

_Bool bh_empty

(

struct binary_heap *

_self_

)

bh_flag()

enum cvx_flags bh_flag

(

struct binary_heap *

_self_

)

bh_full()

_Bool bh_full

(

struct binary_heap *

_self_

)

bh_heap_order()

enum cvx_heap_order bh_heap_order

(

struct binary_heap *

_self_

)

bh_init()

void bh_init	(	struct binary_heap *	self,
		struct binary_heap_vtabv *	vtabv,
		enum cvx_heap_order	HO,
		size_t	capacity
	)

IMPLEMENTATIONS.

bh_iter_at_end()

_Bool bh_iter_at_end

(

struct binary_heap_iter *

_iter_

)

bh_iter_at_start()

_Bool bh_iter_at_start

(

struct binary_heap_iter *

_iter_

)

bh_iter_backward()

void bh_iter_backward	(	struct binary_heap_iter *	_iter_,
		size_t	_steps_
	)

bh_iter_count()

size_t bh_iter_count

(

struct binary_heap_iter *

_iter_

)

bh_iter_drop()

void bh_iter_drop

(

struct binary_heap_iter *

_iter_

)

bh_iter_end()

struct binary_heap_iter * bh_iter_end

(

struct binary_heap *

_target_

)

bh_iter_forward()

void bh_iter_forward	(	struct binary_heap_iter *	_iter_,
		size_t	_steps_
	)

bh_iter_go_to()

void bh_iter_go_to	(	struct binary_heap_iter *	_iter_,
		size_t	_index_
	)

bh_iter_index()

size_t bh_iter_index

(

struct binary_heap_iter *

_iter_

)

bh_iter_init_end()

struct binary_heap_iter bh_iter_init_end

(

struct binary_heap *

_target_

)

bh_iter_init_start()

struct binary_heap_iter bh_iter_init_start

(

struct binary_heap *

_target_

)

ITERATOR.

bh_iter_next()

void bh_iter_next

(

struct binary_heap_iter *

_iter_

)

bh_iter_prev()

void bh_iter_prev

(

struct binary_heap_iter *

_iter_

)

bh_iter_start()

struct binary_heap_iter * bh_iter_start

(

struct binary_heap *

_target_

)

bh_iter_to_end()

void bh_iter_to_end

(

struct binary_heap_iter *

_iter_

)

bh_iter_to_start()

void bh_iter_to_start

(

struct binary_heap_iter *

_iter_

)

bh_iter_value()

TVal bh_iter_value

(

struct binary_heap_iter *

_iter_

)

bh_peek()

TVal bh_peek

(

struct binary_heap *

_self_

)

bh_pop()

TVal bh_pop

(

struct binary_heap *

_self_

)

bh_push()

void bh_push	(	struct binary_heap *	_self_,
		TVal	_item_
	)