Heaps

Interface for an abstract implementation of a heap data structure. More...

Detailed Description

Interface for an abstract implementation of a heap data structure.

Collaboration diagram for Heaps:

Files
file	heap.h
	Implementation of an abstract heap data structure.

Typedefs
typedef struct vrna_heap_s *	vrna_heap_t
	An abstract heap data structure. More...
typedef int(	vrna_callback_heap_cmp) (const void *a, const void *b, void *data)
	Heap compare function prototype. More...
typedef size_t(	vrna_callback_heap_get_pos) (const void *a, void *data)
	Retrieve the position of a particular heap entry within the heap. More...
typedef void(	vrna_callback_heap_set_pos) (const void *a, size_t pos, void *data)
	Store the position of a particular heap entry within the heap. More...

Functions
vrna_heap_t	vrna_heap_init (size_t n, vrna_callback_heap_cmp *cmp, vrna_callback_heap_get_pos *get_entry_pos, vrna_callback_heap_set_pos *set_entry_pos, void *data)
	Initialize a heap data structure. More...
void	vrna_heap_free (vrna_heap_t h)
	Free memory occupied by a heap data structure. More...
size_t	vrna_heap_size (struct vrna_heap_s *h)
	Get the size of a heap data structure, i.e. the number of stored elements. More...
void	vrna_heap_insert (vrna_heap_t h, void *v)
	Insert an element into the heap. More...
void *	vrna_heap_pop (vrna_heap_t h)
	Pop (remove and return) the object at the root of the heap. More...
const void *	vrna_heap_top (vrna_heap_t h)
	Get the object at the root of the heap. More...
void *	vrna_heap_remove (vrna_heap_t h, const void *v)
	Remove an arbitrary element within the heap. More...
void *	vrna_heap_update (vrna_heap_t h, void *v)
	Update an arbitrary element within the heap. More...

Typedef Documentation

typedef struct vrna_heap_s* vrna_heap_t

#include <ViennaRNA/datastructures/heap.h>

An abstract heap data structure.

See also

vrna_heap_init(), vrna_heap_free(), vrna_heap_insert(), vrna_heap_pop(), vrna_heap_top(), vrna_heap_remove(), vrna_heap_update()

typedef int( vrna_callback_heap_cmp) (const void *a, const void *b, void *data)

#include <ViennaRNA/datastructures/heap.h>

Heap compare function prototype.

Use this prototype to design the compare function for the heap implementation. The arbitrary data pointer data may be used to get access to further information required to actually compare the two values a and b.

Note

The heap implementation acts as a min-heap, therefore, the minimum element will be present at the heap's root. In case a max-heap is required, simply reverse the logic of this compare function.

Parameters

a	The first object to compare
b	The second object to compare
data	An arbitrary data pointer passed through from the heap implementation

Returns

A value less than zero if a < b, a value greater than zero if a > b, and 0 otherwise

typedef size_t( vrna_callback_heap_get_pos) (const void *a, void *data)

#include <ViennaRNA/datastructures/heap.h>

Retrieve the position of a particular heap entry within the heap.

Parameters

a	The object to look-up within the heap
data	An arbitrary data pointer passed through from the heap implementation

Returns

The position of the element a within the heap, or 0 if it is not in the heap

typedef void( vrna_callback_heap_set_pos) (const void *a, size_t pos, void *data)

#include <ViennaRNA/datastructures/heap.h>

Store the position of a particular heap entry within the heap.

Parameters

a	The object whose position shall be stored
pos	The current position of a within the heap, or 0 if a was deleted
data	An arbitrary data pointer passed through from the heap implementation

Function Documentation

vrna_heap_t vrna_heap_init	(	size_t	n,
		vrna_callback_heap_cmp *	cmp,
		vrna_callback_heap_get_pos *	get_entry_pos,
		vrna_callback_heap_set_pos *	set_entry_pos,
		void *	data
	)

#include <ViennaRNA/datastructures/heap.h>

Initialize a heap data structure.

This function initializes a heap data structure. The implementation is based on a min-heap, i.e. the minimal element is located at the root of the heap. However, by reversing the logic of the compare function, one can easily transform this into a max-heap implementation.

Beside the regular operations on a heap data structure, we implement removal and update of arbitrary elements within the heap. For that purpose, however, one requires a reverse-index lookup system that, (i) for a given element stores the current position in the heap, and (ii) allows for fast lookup of an elements current position within the heap. The corresponding getter- and setter- functions may be provided through the arguments get_entry_pos and set_entry_pos, respectively.

Sometimes, it is difficult to simply compare two data structures without any context. Therefore, the compare function is provided with a user-defined data pointer that can hold any context required.

Warning

If any of the arguments get_entry_pos or set_entry_pos is NULL, the operations vrna_heap_update() and vrna_heap_remove() won't work.

See also

vrna_heap_free(), vrna_heap_insert(), vrna_heap_pop(), vrna_heap_top(), vrna_heap_remove(), vrna_heap_update(), vrna_heap_t, vrna_callback_heap_cmp, vrna_callback_heap_get_pos, vrna_callback_heap_set_pos

Parameters

n	The initial size of the heap, i.e. the number of elements to store
cmp	The address of a compare function that will be used to fullfill the partial order requirement
get_entry_pos	The address of a function that retrieves the position of an element within the heap (or NULL)
set_entry_pos	The address of a function that stores the position of an element within the heap (or NULL)
data	An arbitrary data pointer passed through to the compare function cmp, and the set/get functions get_entry_pos / set_entry_pos

Returns

An initialized heap data structure, or NULL on error

void vrna_heap_free

(

vrna_heap_t

h

)

#include <ViennaRNA/datastructures/heap.h>

Free memory occupied by a heap data structure.

See also

vrna_heap_init()

Parameters

h	The heap that should be free'd

size_t vrna_heap_size

(

struct vrna_heap_s *

h

)

#include <ViennaRNA/datastructures/heap.h>

Get the size of a heap data structure, i.e. the number of stored elements.

Parameters

h	The heap data structure

Returns

The number of elements currently stored in the heap, or 0 upon any error

void vrna_heap_insert	(	vrna_heap_t	h,
		void *	v
	)

#include <ViennaRNA/datastructures/heap.h>

Insert an element into the heap.

See also

vrna_heap_init(), vrna_heap_pop(), vrna_heap_top(), vrna_heap_free(), vrna_heap_remove(), vrna_heap_update()

Parameters

h	The heap data structure
v	A pointer to the object that is about to be inserted into the heap

void* vrna_heap_pop

(

vrna_heap_t

h

)

#include <ViennaRNA/datastructures/heap.h>

Pop (remove and return) the object at the root of the heap.

This function removes the root from the heap and returns it to the caller.

See also

vrna_heap_init(), vrna_heap_top(), vrna_heap_insert(), vrna_heap_free() vrna_heap_remove(), vrna_heap_update()

Parameters

h	The heap data structure

Returns

The object at the root of the heap, i.e. the minimal element (or NULL if (a) the heap is empty or (b) any error occurred)

const void* vrna_heap_top

(

vrna_heap_t

h

)

#include <ViennaRNA/datastructures/heap.h>

Get the object at the root of the heap.

See also

vrna_heap_init(), vrna_heap_pop(), vrna_heap_insert(), vrna_heap_free() vrna_heap_remove(), vrna_heap_update()

Parameters

h	The heap data structure

Returns

The object at the root of the heap, i.e. the minimal element (or NULL if (a) the heap is empty or (b) any error occurred)

void* vrna_heap_remove	(	vrna_heap_t	h,
		const void *	v
	)

#include <ViennaRNA/datastructures/heap.h>

Remove an arbitrary element within the heap.

See also

vrna_heap_init(), vrna_callback_heap_get_pos, vrna_callback_heap_set_pos, vrna_heap_pop(), vrna_heap_free()

Warning

This function won't work if the heap was not properly initialized with callback functions for fast reverse-index mapping!

Parameters

h	The heap data structure
v	The object to remove from the heap

Returns

The object that was removed from the heap (or NULL if (a) it wasn't found or (b) any error occurred)

void* vrna_heap_update	(	vrna_heap_t	h,
		void *	v
	)

#include <ViennaRNA/datastructures/heap.h>

Update an arbitrary element within the heap.

Note

If the object that is to be updated is not currently stored in the heap, it will be inserted. In this case, the function returns NULL.

Warning

This function won't work if the heap was not properly initialized with callback functions for fast reverse-index mapping!

See also

vrna_heap_init(), vrna_callback_heap_get_pos, vrna_callback_heap_set_pos vrna_heap_pop(), vrna_heap_remove(), vrna_heap_free()

Parameters

h	The heap data structure
v	The object to update

Returns

The 'previous' object within the heap that now got replaced by v (or NULL if (a) it wasn't found or (b) any error occurred)