Table of Contents
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.
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.
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.