2. Priority Queues - Heap,PQueue

DevTools provides modules for managing priority queues. The Heap module provides an augmented heap data structure for double precision values. The implementation associates an integer index with each value and allows values to be removed by index. The PQueue module provides an approximation to a priority queue using a set of discrete "bins".

Table of Contents

2.1 Heaps - Heap

The Heap module holds a set of double precision numbers and associated integer indices. Each double precision number may be interpreted as a priority for each associated integer index. Examples of priorities are time, size, error, etc. The Heap module allows indices to be extracted by minimum or maximum value. The priority queue is implemented so that indices may be efficiently inserted and extracted dynamically.

Begin and end an instance of an object, return object error flag

*vsy_HeapBegin    - create an instance of a Heap object
vsy_HeapEnd       - destroy an instance of a Heap object
vsy_HeapError     - return Heap object error flag

Set and query indices

vsy_HeapDef       - define number of indices and min or max heap
        Inq       - get number of indices and min or max heap
vsy_HeapClear     - remove all indices from the Heap object
vsy_HeapInsert    - insert index with specified priority value
vsy_HeapLookup    - find priority value inserted at a specified index
vsy_HeapRef       - query for index with extreme priority
vsy_HeapRefRemove - query for and remove index with extreme priority
vsy_HeapRemove    - remove an index

Instance a Heap object using vsy_HeapBegin. Once a Heap is instanced, the approximate maximum index to be stored and the declaration of the heap as a minimum or maximum priority heap is defined using vsy_HeapDef.

As indices are inserted the Heap module will expand its internal storage as required. The function vsy_HeapInq returns the number of indices which may be managed by the presently allocated storage. Indices with associated double precision priority values are inserted into the priority queue using vsy_HeapInsert. The priority value of any index may be returned using vsy_HeapLookup without altering the priority queue. The function vsy_HeapRef may be used to query the priority queue for current extreme priority value and associated index. If, for example, the heap has been declared as minimum priority queue, then this function returns the index with the minimum double precision value. The function vsy_HeapRef does not remove the returned index from the priority queue, the function vsy_HeapRemove performs this service. Use vsy_HeapRefRemove to query and remove the extreme valued index in one function call. All indices may be removed using vsy_HeapClear.

Table of Contents

2.2 Function Descriptions

The currently available Heap functions are described in detail in this section.

Table of Contents , Heap

NAME

*vsy_HeapBegin - create an instance of a Heap object

C SPECIFICATION

vsy_Heap *vsy_HeapBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

The function returns a pointer to the newly created Heap object. If the object creation fails, NULL is returned.

DESCRIPTION

Create an instance of an Heap object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a Heap object using

     void vsy_HeapEnd (vsy_Heap *heap)

Return the current value of a Heap object error flag using

     Vint vsy_HeapError (vsy_Heap *heap)

Table of Contents , Heap

NAME

vsy_HeapDef - define number of indices and accumulators

C SPECIFICATION

void vsy_HeapDef (vsy_Heap *heap,
                  Vint maxindex,
                  Vint minmax)

INPUT ARGUMENTS

heap         Pointer to Heap object.
maxindex     Estimated maximum index to be held.
minmax       Type of heap
             =HEAP_MIN    Maintain minimum priority
             =HEAP_MAX    Maintain maximum priority

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated. SYS_ERROR_VALUE is generated if an improper maxindex is specified.

DESCRIPTION

Suggest a maximum index, maxindex to be stored in the Heap. Declare whether the heap is meant to maintain a minimum or maximum priority. If an inserted index is eventually greater than this initial estimate, storage space will dynamically expanded to hold the extra index.

Find the maximum index currently held and heap type using

     void vsy_HeapInq (const vsy_Heap *heap,
                       Vint *maxindex,
                       Vint *minmax)

Table of Contents , Heap

NAME

vsy_HeapClear - remove all indices

C SPECIFICATION

void vsy_HeapClear (vsy_Heap *heap)

INPUT ARGUMENTS

heap         Pointer to Heap object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Clear all indices from the priority queue.

Table of Contents , Heap

NAME

vsy_HeapInsert - insert index with specified priority value

C SPECIFICATION

void vsy_HeapInsert (vsy_Heap *heap,
                     Vint index,
                     Vdouble val)

INPUT ARGUMENTS

heap         Pointer to Heap object.
index        Index of value to insert
val          Double precision priority value

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_VALUE is generated if an improper index is specified. SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Insert integer index with associated priority value, val. If the index is already contained in the priority queue its priority value is changed to val.

Table of Contents , Heap

NAME

vsy_HeapLookup - find priority value inserted at a specified index

C SPECIFICATION

void vsy_HeapLookup (vsy_Heap *heap,
                     Vint index,
                     Vdouble *val)

INPUT ARGUMENTS

heap         Pointer to Heap object.
index        Index of value to lookup

OUTPUT ARGUMENTS

val          Double precision priority value

ERRORS

SYS_ERROR_VALUE is generated if an improper index is specified.

DESCRIPTION

Return priority value, val, associated with index. The index is not removed from the priority queue.

Table of Contents , Heap

NAME

vsy_HeapRef - query for index with extreme priority

C SPECIFICATION

void vsy_HeapRef (vsy_Heap *heap,	
                  Vint *index,
                  Vdouble *val)

INPUT ARGUMENTS

heap         Pointer to Heap object.

OUTPUT ARGUMENTS

index        Index of value
val          Double precision priority value

DESCRIPTION

Query for the index with the extreme priority value. The index is not removed from the priority queue. If the heap is empty a zero index is returned.

Table of Contents , Heap

NAME

vsy_HeapRefRemove - query for and remove index with extreme priority

C SPECIFICATION

void vsy_HeapRefRemove (vsy_Heap *heap,
                        Vint *index,
                        Vdouble *val)

INPUT ARGUMENTS

heap         Pointer to Heap object.

OUTPUT ARGUMENTS

index        Index of value
val          Double precision priority value

DESCRIPTION

Query for the index with the extreme priority value and remove it. If the heap is empty a zero index is returned.

Table of Contents , Heap

NAME

vsy_HeapRemove - remove an index

C SPECIFICATION

void vsy_HeapRemove (vsy_Heap *heap,
                     Vint index)

INPUT ARGUMENTS

heap         Pointer to Heap object.
index        Index to remove

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_VALUE is generated if an improper index is specified.

DESCRIPTION

Remove specified index from the priority queue. If the index has been previously removed from the heap, no operation is performed.

Table of Contents

2.3 Priority Queues - PQueue

The PQueue module holds a set of double precision numbers and associated integer indices. Each double precision number may be interpreted as a priority for each associated integer index. Examples of priorities are time, size, error, etc. The PQueue module allows indices to be extracted by minimum or maximum value. The priority queue is implemented so that indices may be efficiently inserted and extracted dynamically. The PQueue module implements a priority queue only approximately. Rather than using a traditional heap data structure, the PQueue module uses a series of "accumulators" to sort and store indices within discrete ranges of priority values. The limits to the dynamic range of the priority values and the number of accumulators must be specified before priority value insertion can begin. The dynamic range divided by the number of accumulators determines the precision of the priority queue.

Begin and end an instance of an object, return object error flag

*vsy_PQueueBegin    - create an instance of a PQueue object
vsy_PQueueEnd       - destroy an instance of a PQueue object
vsy_PQueueError     - return PQueue object error flag

Set and query indices

vsy_PQueueDef       - define number of indices and accumulators
          Inq       - get number of indices and accumulators
vsy_PQueueClear     - remove all indices from the PQueue object
vsy_PQueueInsert    - insert index with specified priority value
vsy_PQueueLookup    - find priority value inserted at a specified index
vsy_PQueueMinMax    - query for index with minimum or maximum priority
vsy_PQueueRange     - specify dynamic range of priority values
vsy_PQueueRemove    - remove an index

Instance a PQueue object using vsy_PQueueBegin. Once a PQueue is instanced, an approximate number of indices to be stored may be defined using vsy_PQueueDef. The user also specifies in this function the number of accumulators which are to be used by PQueue. The function, vsy_PQueueDef may also be used to reinitialize the PQueue object. As indices are inserted the PQueue module will expand its internal storage as required. The function vsy_PQueueInq returns the number of indices which may be managed by the presently allocated storage. The dynamic range of the priority values is then specified using vsy_PQueueRange. Indices with associated double precision priority values are inserted into the priority queue using vsy_PQueueInsert. The priority value of any index may be returned using vsy_PQueueLookup without altering the priority queue. The function vsy_PQueueMinMax may be used to query the priority queue for either the current minimum or maximum priority value and associated index. Note that the priority value returned may not be the strict minimum or maximum but will be within the precision of the priority queue. For example if the priority queue has been configured to manage priority values of angles between 0. and 60. degrees with 1024 accumulators, the precision will be within 60./1024. of a degree. The function vsy_PQueueMinMax does not remove the returned index from the priority queue, the function vsy_PQueueRemove performs this service. All indices may be removed using vsy_PQueueClear.

Table of Contents

2.4 Function Descriptions

The currently available PQueue functions are described in detail in this section.

Table of Contents , PQueue

NAME

*vsy_PQueueBegin - create an instance of a PQueue object

C SPECIFICATION

vsy_PQueue *vsy_PQueueBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

The function returns a pointer to the newly created PQueue object. If the object creation fails, NULL is returned.

DESCRIPTION

Create an instance of an PQueue object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a PQueue object using

     void vsy_PQueueEnd (vsy_PQueue *pqueue)

Return the current value of a PQueue object error flag using

     Vint vsy_PQueueError (vsy_PQueue *pqueue)

Table of Contents , PQueue

NAME

vsy_PQueueDef - define number of indices and accumulators

C SPECIFICATION

void vsy_PQueueDef (vsy_PQueue *pqueue,
                    Vint maxindex,
                    Vint numacc)

INPUT ARGUMENTS

pqueue       Pointer to PQueue object.
maxindex     Estimated number of indices to be held.
numacc       Number of accumulators

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated. SYS_ERROR_VALUE is generated if an improper maxindex or numacc is specified.

DESCRIPTION

Suggest a number of indices, maxindex to be stored in the PQueue. If an inserted index is eventually greater than this initial estimate, storage space will dynamically expanded to hold the extra index. The number of accumulators, numacc is also specified. If numacc is entered as zero, the number of accumulators is set to 1024. This function removes any previously entered indices and priority values.

Find the number of indices which may be managed with the presently allocated storage and the number of accumulators using

     void vsy_PQueueInq (const vsy_PQueue *pqueue,
                         Vint *maxindex,
                         Vint *numacc)

Table of Contents , PQueue

NAME

vsy_PQueueClear - remove all indices

C SPECIFICATION

void vsy_PQueueClear (vsy_PQueue *pqueue)

INPUT ARGUMENTS

pqueue       Pointer to PQueue object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Clear all indices from the priority queue.

Table of Contents , PQueue

NAME

vsy_PQueueInsert - insert index with specified priority value

C SPECIFICATION

void vsy_PQueueInsert (vsy_PQueue *pqueue,
                       Vint index,
                       Vdouble val)

INPUT ARGUMENTS

pqueue       Pointer to PQueue object.
index        Index of value to insert
val          Double precision priority value

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_VALUE is generated if an improper index is specified. SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

DESCRIPTION

Insert integer index with associated priority value, val. If the index is already contained in the priority queue its priority value is changed to val.

Table of Contents , PQueue

NAME

vsy_PQueueLookup - find priority value inserted at a specified index

C SPECIFICATION

void vsy_PQueueLookup (vsy_PQueue *pqueue,
                       Vint index,
                       Vdouble *val)

INPUT ARGUMENTS

pqueue       Pointer to PQueue object.
index        Index of value to lookup

OUTPUT ARGUMENTS

val          Double precision priority value

ERRORS

SYS_ERROR_VALUE is generated if an improper index is specified.

DESCRIPTION

Return priority value, val, associated with index. The index is not removed from the priority queue.

Table of Contents , PQueue

NAME

vsy_PQueueMinMax - query for index with minimum or maximum priority

C SPECIFICATION

void vsy_PQueueMinMax (vsy_PQueue *pqueue,	
                       Vint minmax,
                       Vint *index,
                       Vdouble *val)

INPUT ARGUMENTS

pqueue       Pointer to PQueue object.
minmax       Minimum or maximum flag
             =0  Minimum
             =1  Maximum

OUTPUT ARGUMENTS

index        Index of value
val          Double precision priority value

DESCRIPTION

Query for the index with the minimum or maximum priority value. The index is not removed from the priority queue.

Table of Contents , PQueue

NAME

vsy_PQueueRange - specify dynamic range of priority values

C SPECIFICATION

void vsy_PQueueRange (vsy_PQueue *pqueue,
                      Vdouble *minval,
                      Vdouble *maxval)

INPUT ARGUMENTS

pqueue       Pointer to PQueue object.
minval       Minimum priority value
maxval       Maximum priority value

OUTPUT ARGUMENTS

None

DESCRIPTION

Specify the dynamic range of priority values. This function should be called before any priority values are inserted using vsy_PQueueInsert. Any priority values inserted which lie outside of this range will be inserted in the accumulator associated with the limiting value which is exceeded by the inserted priority value. By default the priority value range is (0.,1.).

Table of Contents , PQueue

NAME

vsy_PQueueRemove - remove an index

C SPECIFICATION

void vsy_PQueueRemove (vsy_PQueue *pqueue,
                       Vint index)

INPUT ARGUMENTS

pqueue       Pointer to PQueue object.
index        Index to remove

OUTPUT ARGUMENTS

None

ERRORS

SYS_ERROR_VALUE is generated if an improper index is specified.

DESCRIPTION

Remove specified index from the priority queue.