BinaryHeap.c File Reference

#include "BinaryHeap.h"

Include dependency graph for BinaryHeap.c:

Go to the source code of this file.

Macros
#define	ParentPos(pos)   (pos - 1)/2
#define	ChildrenPos1(pos)   (2*(pos)+1)
#define	ChildrenPos2(pos)   (2*(pos)+2)

Functions
BinaryHeap	BinaryHeap_new (int(*cmp)(void *item1, void *item2))
void	BinaryHeap_delete (BinaryHeap h, void(*del)(void *item))
int	BinaryHeap_insert (BinaryHeap h, void *item)
void *	BinaryHeap_get_min (BinaryHeap h)
void *	BinaryHeap_extract_min (BinaryHeap h)
void *	BinaryHeap_extract_item (BinaryHeap h, int id)
int	BinaryHeap_reset (BinaryHeap h, int id, void *item)
void *	BinaryHeap_get_item (BinaryHeap h, int id)
void	BinaryHeap_sanity_check (BinaryHeap h)
void	BinaryHeap_print (BinaryHeap h, void(*pnt)(void *))

Macro Definition Documentation

#define ChildrenPos1

(

pos

)

(2*(pos)+1)

Definition at line 65 of file BinaryHeap.c.

#define ChildrenPos2

(

pos

)

(2*(pos)+2)

Definition at line 66 of file BinaryHeap.c.

#define ParentPos

(

pos

)

(pos - 1)/2

Definition at line 64 of file BinaryHeap.c.

Referenced by BinaryHeap_sanity_check().

Function Documentation

void BinaryHeap_delete	(	BinaryHeap	h,
		void(*)(void *item)	del
	)

Definition at line 34 of file BinaryHeap.c.

References FREE, BinaryHeap_struct::heap, BinaryHeap_struct::id_stack, BinaryHeap_struct::id_to_pos, IntStack_delete(), BinaryHeap_struct::len, and BinaryHeap_struct::pos_to_id.

void* BinaryHeap_extract_item	(	BinaryHeap	h,
		int	id
	)

Definition at line 175 of file BinaryHeap.c.

References assert, BinaryHeap_struct::heap, BinaryHeap_struct::id_stack, BinaryHeap_struct::id_to_pos, IntStack_push(), BinaryHeap_struct::len, BinaryHeap_struct::max_len, and NULL.

Referenced by BinaryHeap_extract_min().

void* BinaryHeap_extract_min

(

BinaryHeap

h

)

Definition at line 169 of file BinaryHeap.c.

References BinaryHeap_extract_item(), BinaryHeap_struct::len, NULL, and BinaryHeap_struct::pos_to_id.

void* BinaryHeap_get_item	(	BinaryHeap	h,
		int	id
	)

Definition at line 225 of file BinaryHeap.c.

References BinaryHeap_struct::heap, BinaryHeap_struct::id_to_pos, BinaryHeap_struct::max_len, and NULL.

void* BinaryHeap_get_min

(

BinaryHeap

h

)

Definition at line 164 of file BinaryHeap.c.

References BinaryHeap_struct::heap.

int BinaryHeap_insert	(	BinaryHeap	h,
		void *	item
	)

Definition at line 137 of file BinaryHeap.c.

References assert, BinaryHeap_error_malloc, BinaryHeap_struct::heap, BinaryHeap_struct::id_stack, BinaryHeap_struct::id_to_pos, IntStack_pop(), BinaryHeap_struct::len, BinaryHeap_struct::max_len, NULL, and BinaryHeap_struct::pos_to_id.

BinaryHeap BinaryHeap_new

(

int(*)(void *item1, void *item2)

cmp

)

Definition at line 16 of file BinaryHeap.c.

References BinaryHeap_struct::cmp, BinaryHeap_struct::heap, BinaryHeap_struct::id_stack, BinaryHeap_struct::id_to_pos, IntStack_new(), BinaryHeap_struct::len, MALLOC, BinaryHeap_struct::max_len, and BinaryHeap_struct::pos_to_id.

void BinaryHeap_print	(	BinaryHeap	h,
		void(*)(void *)	pnt
	)

Definition at line 273 of file BinaryHeap.c.

References BinaryHeap_struct::heap, BinaryHeap_struct::id_stack, BinaryHeap_struct::id_to_pos, IntStack_struct::last, BinaryHeap_struct::len, BinaryHeap_struct::pos_to_id, and IntStack_struct::stack.

int BinaryHeap_reset	(	BinaryHeap	h,
		int	id,
		void *	item
	)

Definition at line 208 of file BinaryHeap.c.

References BinaryHeap_struct::heap, BinaryHeap_struct::id_to_pos, and BinaryHeap_struct::max_len.

void BinaryHeap_sanity_check

(

BinaryHeap

h

)

Definition at line 237 of file BinaryHeap.c.

References assert, BinaryHeap_struct::cmp, FREE, BinaryHeap_struct::heap, BinaryHeap_struct::id_stack, BinaryHeap_struct::id_to_pos, IntStack_get_length, IntStack_struct::last, BinaryHeap_struct::len, MALLOC, ParentPos, BinaryHeap_struct::pos_to_id, and IntStack_struct::stack.