2. Priority Queues - Heap, PQueue

CEETRON SAM 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”.

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.

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().

2.2. Function Descriptions

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

vsy_Heap *vsy_HeapBegin(void)

create an instance of a Heap object

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)

Returns

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

void vsy_HeapEnd(vsy_Heap *p)

destroy an instance of a Heap object

See vsy_HeapBegin()

Vint vsy_HeapError(vsy_Heap *p)

return the current value of a Heap object error flag

See vsy_HeapBegin()

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

define number of indices and accumulators

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)

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.

Parameters
  • p – Pointer to Heap object.

  • maxindex – Estimated maximum index to be held.

  • minmax – Type of heap

    x=HEAP_MIN    Maintain minimum priority
     =HEAP_MAX    Maintain maximum priority
    

void vsy_HeapInq(vsy_Heap *p, Vint *nument, Vint *minmax)

find the maximum index currently held and heap type

See vsy_HeapDef()

void vsy_HeapClear(vsy_Heap *p)

remove all indices

Clear all indices from the priority queue.

Parameters

p – Pointer to Heap object.

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

query for index with extreme priority

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.

Parameters
  • p – Pointer to Heap object.

  • index[out] Index of value

  • val[out] Double precision priority value

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

query for and remove index with extreme priority

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

Parameters
  • p – Pointer to Heap object.

  • index[out] Index of value

  • val[out] Double precision priority value

void vsy_HeapRemove(vsy_Heap *p, Vint index)

remove an index

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

Errors

SYS_ERROR_VALUE is generated if an improper index is specified.

Parameters
  • p – Pointer to Heap object.

  • index – Index to remove

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

insert index with specified priority value

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.

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.

Parameters
  • p – Pointer to Heap object.

  • index – Index of value to insert

  • val – Double precision priority value

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

find priority value inserted at a specified index

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

Errors

SYS_ERROR_VALUE is generated if an improper index is specified.

Parameters
  • p – Pointer to Heap object.

  • index – Index of value to lookup

  • val[out] Double precision priority value

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.

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().

2.4. Function Descriptions

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

vsy_PQueue *vsy_PQueueBegin(void)

create an instance of a PQueue object

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

return

The function returns a pointer to the newly created PQueue object. If the object creation fails, NULL 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)

void vsy_PQueueEnd(vsy_PQueue *p)

destroy an instance of a PQueue object

See vsy_PQueueBegin()

Vint vsy_PQueueError(vsy_PQueue *p)

return the current value of a PQueue object error flag

See vsy_PQueueBegin()

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

define number of indices and accumulators

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)

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.

Parameters
  • p – Pointer to PQueue object.

  • maxindex – Estimated number of indices to be held.

  • numacc – Number of accumulators

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

specify dynamic range of priority values

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.).

Parameters
  • p – Pointer to PQueue object.

  • minval – Minimum priority value

  • maxval – Maximum priority value

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

insert index with specified priority value

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.

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.

Parameters
  • p – Pointer to PQueue object.

  • index – Index of value to insert

  • val – Double precision priority value

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

query for index with minimum or maximum priority

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

Parameters
  • p – Pointer to PQueue object.

  • minmax – Minimum or maximum flag

    =1  Maximum
    =0  Minimum
    

  • index[out] Index of value

  • val[out] Double precision priority value

void vsy_PQueueRemove(vsy_PQueue *p, Vint index)

remove an index

Remove specified index from the priority queue.

Errors

SYS_ERROR_VALUE is generated if an improper index is specified.

Parameters
  • p – Pointer to PQueue object.

  • index – Index to remove

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

find priority value inserted at a specified index

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

Errors

SYS_ERROR_VALUE is generated if an improper index is specified.

Parameters
  • p – Pointer to PQueue object.

  • index – Index of value to lookup

  • val[out] Double precision priority value

void vsy_PQueueClear(vsy_PQueue *p)

remove all indices

Clear all indices from the priority queue.

Parameters

p – Pointer to PQueue object.