Heap preprocessor metaprogram. More...

#include "host.h"
#include <assert.h>

Include dependency graph for heap-def.h:

This graph shows which files directly or indirectly include this file:

Defines
#define	VL_HEAP_array VL_HEAP_type*
#define	VL_HEAP_array_const VL_HEAP_type const*
#define	VL_HEAP_cmp VL_XCAT(VL_HEAP_prefix, _cmp)
#define	VL_HEAP_DEF_H
#define	VL_HEAP_down VL_XCAT(VL_HEAP_prefix, _down)
#define	VL_HEAP_pop VL_XCAT(VL_HEAP_prefix, _pop)
#define	VL_HEAP_push VL_XCAT(VL_HEAP_prefix, _push)
#define	VL_HEAP_swap VL_XCAT(VL_HEAP_prefix, _swap)
#define	VL_HEAP_up VL_XCAT(VL_HEAP_prefix, _up)
#define	VL_HEAP_update VL_XCAT(VL_HEAP_prefix, _update)
Functions
VL_INLINE VL_HEAP_type	VL_HEAP_cmp (VL_HEAP_array_const array, vl_uindex indexA, vl_uindex indexB)
	Compare two heap elements.
VL_INLINE void	VL_HEAP_down (VL_HEAP_array array, vl_uindex index)
	Heap down operation.
VL_INLINE vl_uindex	vl_heap_left_child (vl_uindex index)
VL_INLINE vl_uindex	vl_heap_parent (vl_uindex index)
VL_INLINE vl_uindex	VL_HEAP_pop (VL_HEAP_array array, vl_size *heapSize)
	Heap pop operation.
VL_INLINE void	VL_HEAP_push (VL_HEAP_array array, vl_size *heapSize)
	Heap push operation.
VL_INLINE vl_uindex	vl_heap_right_child (vl_uindex index)
VL_INLINE void	VL_HEAP_swap (VL_HEAP_array array, vl_uindex indexA, vl_uindex indexB)
	Swap two heap elements.
VL_INLINE void	VL_HEAP_up (VL_HEAP_array array, vl_size heapSize, vl_uindex index)
	Heap up operation.
VL_INLINE void	VL_HEAP_update (VL_HEAP_array array, vl_size heapSize, vl_uindex index)
	Heap update operation.

Detailed Description

Heap preprocessor metaprogram.

Author:: Andrea Vedaldi

A heap organizes an array of objects in a priority queue. This module is a template metaprogram that defines heap operations on array of generic objects, or even generic object containers.

Overview

To use heap-def.h one must specify at least a prefix and the data type for the heap elements:

 #define VL_HEAP_prefix  my_heap
 #define VL_HEAP_type    float
 #include <vl/heap-def.h>

This code fragment defines a number of functions prefixed by VL_HEAP_prefix, such as my_heap_push (VL_HEAP_push) and my_heap_pop (VL_HEAP_pop), that implement the heap operations. These functions operate on an array that has type VL_HEAP_array. By default, this is defined to be:

 #define VL_HEAP_array VL_HEAP_type*
 #define VL_HEAP_array_const VL_HEAP_type const*

The array itself is accessed uniquely by means of two functions:

VL_HEAP_cmp, that compares two array elements. The default implementation assumes that VL_HEAP_type is numeric.
VL_HEAP_swap, that swaps two array elements. The default implementation assumes that VL_HEAP_type can be copied by the = operator.

The heap state is a integer numElements (of type vl_size) counting the number of elements of the array that are currently part of the heap and the content of the first numElements elements of the array. The portion of the array that constitutes the heap satisfies a certain invariant property (heap property, Technical details). From a user viewpoint, the most important consequence is that the first element of the array (the one of index 0) is also the smallest (according to VL_HEAP_cmp).

Elements are added to the heap by VL_HEAP_push and removed from the heap by VL_HEAP_pop. A push operation adds to the heap the array element immediately after the last element already in the heap (i.e. the element of index numElements) and increases the number of heap elements numElements. Elements in the heap are swapped as required in order to maintain the heap consistency. Similarly, a pop operation removes the first (smaller) element from the heap and decreases the number of heap elements numElements.

The values of nodes currently in the heap can be updated by VL_HEAP_update. Notice however that using this function requires knowing the index of the element that needs to be updated up to the swapping operations that the heap performs to maintain consistency. Typically, this requires redefining VL_HEAP_swap to keep track of such changes (General usage).

General usage

The heap container may be mapped to any type by reimplementing VL_HEAP_cmp and VL_HEAP_swap explicitly. For instance the following code redefines VL_HEAP_cmp to deal with the case in which the heap is an array of structures:

 typedef struct _S { int x ; } S ;
 int s_cmp (S const * v, vl_uindex a, vl_uindex b) {
   return v[a].x - v[b].x ;
 }
 #define VL_HEAP_prefix  s_heap
 #define VL_HEAP_type    S
 #define VL_HEAP_cmp     s_cmp
 #include <vl/heap-def.h>

In the following example, the heap itself is an arbitrary structure:

 typedef struct _H { int* array ; } H ;
 int h_cmp (H const * h, vl_uindex a, vl_uindex b) {
   return h->array[a] - h->array[b] ;
 }
 int h_swap (H * h, vl_uindex a, vl_uindex b) {
   int t = h->array[a] ;
   h->array[a] = h->array[b] ;
   h->array[b] = t ;
 }
 #define VL_HEAP_prefix  h_heap
 #define VL_HEAP_swap    h_swap
 #define VL_HEAP_cmp     h_cmp
 #include <vl/heap-def.h>

Technical details

The heap is organised as a binary tree with the property (heap property) that any node is not larger than any of its children. In particular, the root is the smallest node.

heap-def.h uses the standard binary tree representation as a linear array. Tree nodes are mapped to array elements as follows: array[0] corresponds to the root, array[1] and array[2] to the root left and right children and so on. In this way, the tree structure is fully specified by the total number of nodes N.

Assuming that the heap has N nodes (from array[0] to array[N-1]), adding the node array[N] to the heap is done by a push down operation: if the node array[N] is smaller than its parent (violating the heap property) it is pushed down by swapping it with the parent, and so on recursively.

Removing the smallest element array[0] with an heap of N nodes is done by swapping array[0] with array[N-1]. If then array[0] is larger than any of its children, it is swapped with the smallest of the two and so on recursively (push up operation).

Restoring the heap property after an element array[i] has been modified can be done by a push up or push down operation on that node.

Definition in file heap-def.h.

Define Documentation

#define VL_HEAP_array VL_HEAP_type*

Definition at line 164 of file heap-def.h.

#define VL_HEAP_array_const VL_HEAP_type const*

Definition at line 165 of file heap-def.h.

#define VL_HEAP_cmp VL_XCAT(VL_HEAP_prefix, _cmp)

Definition at line 224 of file heap-def.h.

#define VL_HEAP_DEF_H

Definition at line 182 of file heap-def.h.

#define VL_HEAP_down VL_XCAT(VL_HEAP_prefix, _down)

Definition at line 329 of file heap-def.h.

#define VL_HEAP_pop VL_XCAT(VL_HEAP_prefix, _pop)

Definition at line 382 of file heap-def.h.

#define VL_HEAP_push VL_XCAT(VL_HEAP_prefix, _push)

Definition at line 358 of file heap-def.h.

#define VL_HEAP_swap VL_XCAT(VL_HEAP_prefix, _swap)

Definition at line 249 of file heap-def.h.

#define VL_HEAP_up VL_XCAT(VL_HEAP_prefix, _up)

Definition at line 279 of file heap-def.h.

#define VL_HEAP_update VL_XCAT(VL_HEAP_prefix, _update)

Definition at line 422 of file heap-def.h.

Function Documentation

VL_INLINE VL_HEAP_type VL_HEAP_cmp	(	VL_HEAP_array_const	array,
		vl_uindex	indexA,
		vl_uindex	indexB
	)

Compare two heap elements.

Parameters:

array	heap array.
indexA	index of the first element `A` to compare.
indexB	index of the second element `B` to comapre.

Returns:: a negative number if A<B, 0 if A==B, and a positive number if if A>B.

Definition at line 236 of file heap-def.h.

VL_INLINE void VL_HEAP_down	(	VL_HEAP_array	array,
		vl_uindex	index
	)

Heap down operation.

Parameters:

array	pointer to the heap node array.
index	index of the node to push up.

Definition at line 338 of file heap-def.h.

VL_INLINE vl_uindex vl_heap_left_child ( vl_uindex index )

Definition at line 202 of file heap-def.h.

VL_INLINE vl_uindex vl_heap_parent ( vl_uindex index )

Definition at line 190 of file heap-def.h.

VL_INLINE vl_uindex VL_HEAP_pop	(	VL_HEAP_array	array,
		vl_size *	heapSize
	)

Heap pop operation.

Parameters:

array	pointer to the heap array.
heapSize	(in/out) size of the heap.

Returns:: index of the popped element.

The function extracts from the heap the element of index 0 (the smallest element) and decreases heapSize.

The element extracted is moved as the first element after the heap end (thus it has index heapSize). For convenience, this index is returned by the function.

Popping from an empty heap is undefined.

Definition at line 401 of file heap-def.h.

VL_INLINE void VL_HEAP_push	(	VL_HEAP_array	array,
		vl_size *	heapSize
	)

Heap push operation.

Parameters:

array	pointer to the heap array.
heapSize	(in/out) size of the heap.

The function adds to the heap the element of index heapSize and increments heapSize.

Definition at line 370 of file heap-def.h.

VL_INLINE vl_uindex vl_heap_right_child ( vl_uindex index )

Definition at line 213 of file heap-def.h.

VL_INLINE void VL_HEAP_swap	(	VL_HEAP_array	array,
		vl_uindex	indexA,
		vl_uindex	indexB
	)

Swap two heap elements.

Parameters:

array	array of nodes.
array	heap array.
indexA	index of the first node to swap.
indexB	index of the second node to swap.

The function swaps the two heap elements a and @ b. The function uses a temporary element and the copy operator, which must be well defined for the heap elements.

Definition at line 264 of file heap-def.h.

VL_INLINE void VL_HEAP_up	(	VL_HEAP_array	array,
		vl_size	heapSize,
		vl_uindex	index
	)

Heap up operation.

Parameters:

array	pointer to the heap array.
heapSize	size of the heap.
index	index of the node to push up.

Definition at line 289 of file heap-def.h.

VL_INLINE void VL_HEAP_update	(	VL_HEAP_array	array,
		vl_size	heapSize,
		vl_uindex	index
	)

Heap update operation.

Parameters:

array	pointer to the heap array.
heapSize	size of the heap.
index	index of the node to update.

The function updates the heap to account for a change to the element of index index in the heap.

Notice that using this function requires knowing the index of the heap index of element that was changed. Since the heap swaps elements in the array, this is in general different from the index that that element had originally.

Definition at line 441 of file heap-def.h.

Defines

Functions

Detailed Description

Overview

General usage

Technical details

Define Documentation

Function Documentation