leopardpm wrote:...
The Basic Functions needed for a Priority Queue are:
ADD element
Access the lowest(highest) element
DEL an element
FIND an element
You're confusing a sorted heap with a priority queue. You can't 'find' an item in a priority queue, since the only value that makes sense is the top of the heap. The rest will be unordered and finding something just amounts to a linear search (thus defeating the purpose of the queue). The only operations allowed in a 'pure' priority queue are pushing and popping of values. And you can also of course peek the TOH without popping it (using the
top() method here):
Code: Select all
#ifndef __FBFRAMEWORK_COLLECTIONS_PRIORITY_QUEUE__
#define __FBFRAMEWORK_COLLECTIONS_PRIORITY_QUEUE__
namespace FbFramework
'' Some definitions needed
type DisposeCallback _
as sub( byval as any ptr )
const as any ptr Null = 0
namespace Collections
/'
Represents an element of the priority queue
There's no need to instantiate or extend this class, as it is
used by the internal heap only.
'/
type QueueElement
public:
declare constructor( _
byval as integer, _
byval as any ptr, _
byval as DisposeCallback = Null )
declare destructor()
declare property priority() as integer
declare property value() as any ptr
private:
declare constructor()
/'
These are disallowed because we really don't want any
direct duplication of these.
'/
declare constructor( _
byref as QueueElement )
declare operator let( _
byref as QueueElement )
'' The priority of this element
m_priority as integer
'' The value associated with this element
m_value as any ptr
'' The callback function for garbage collection
m_disposeCallback as DisposeCallback
end type
constructor QueueElement( _
byval pPriority as integer, _
byval pValue as any ptr, _
byval pDisposeCallback as DisposeCallback = Null )
m_priority = pPriority
m_value = pValue
m_disposeCallback = pDisposeCallback
end constructor
constructor QueueElement()
end constructor
constructor QueueElement( _
byref rhs as QueueElement )
end constructor
operator QueueElement.let( _
byref rhs as QueueElement )
end operator
destructor QueueElement()
/'
Invoke the callback if it exists for disposal of the 'value'
field if required.
'/
if( _
m_disposeCallback <> Null ) then
m_disposeCallback( m_value )
end if
end destructor
property QueueElement.priority() as integer
return( m_priority )
end property
property QueueElement.value() as any ptr
return( m_value )
end property
/'
This is the base class for the Priority Queue class.
The class represents a Queue data structure, implemented
here as a Binary Heap. Look at these links for more info:
https://en.wikipedia.org/wiki/Priority_queue
https://en.wikipedia.org/wiki/Heap_(data_structure)
https://en.wikipedia.org/wiki/Binary_heap
'/
type Queue
public:
'' Public enumeration to express the priority order we want
enum PriorityOrder
Ascending
Descending
end enum
declare constructor( _
byval as uinteger )
declare constructor( _
byval as PriorityOrder )
declare constructor( _
byval as uinteger, _
byval as PriorityOrder )
declare destructor()
declare property size() as uinteger
declare property count() as uinteger
declare property priority() as PriorityOrder
declare function push( _
byval as integer, _
byval as any ptr, _
byval as DisposeCallback = Null _
) as QueueElement ptr
declare function pop() as any ptr
declare function top() as any ptr
private:
declare constructor()
declare sub initializeComponent()
declare sub resize( _
byval as uinteger )
'' The internal heap
as QueueElement ptr _
m_elements( any )
as uinteger _
_ '' Current size and element count
m_size, m_count, _
_ '' Control the resizing mechanism
m_initialSize, m_lowerBound
'' The selected priority order for this instance
as PriorityOrder m_priorityOrder
end type
constructor Queue( _
byval aPriorityOrder as PriorityOrder )
'' The default size is set to 128 items
this.constructor( _
128, _
aPriorityOrder )
end constructor
constructor Queue( _
byval aSize as uinteger )
/'
Note that the default priority order is set to 'Descending'
since this property is usually understood as 'the higher
the value, the higher the priority'
'/
this.constructor( _
aSize, _
PriorityOrder.Ascending )
end constructor
constructor Queue( _
byval aSize as uinteger, _
byval aPriorityOrder as Queue.PriorityOrder )
/'
Primary constructor
Note that we're using a 1-based array instead of a more common
0-based one. This makes a lot of things easier down the road,
especially adding an element: since we're declaring the element
count as unsigned, leaving a bit of space at the root of the
heap we don't have to check for underflow conditions during the
sifting.
'/
m_size = _
iif( _
aSize < 1, _
1, _
aSize )
m_priorityOrder = aPriorityOrder
redim _
m_elements( 1 to m_size )
m_count = 0
m_initialSize = m_size
m_lowerBound = 1
end constructor
destructor Queue()
'' Delete all elements if the heap
for _
i as integer = 1 to m_count
delete( m_elements( i ) )
next
end destructor
property Queue.count() as uinteger
return( m_count )
end property
property Queue.size() as uinteger
return( m_size )
end property
property Queue.priority() as PriorityOrder
return( m_priorityOrder )
end property
sub Queue.resize( byval newSize as uinteger )
/'
Resizes the internal array used as the heap.
The algorithm works like this:
When you instantiate the list, the initial size is recorded, and
is used to determine when the list is resized, and by how much. In
this case, the array grows every time the number of items exceed
the initial value by half, and shrinks every time that the previous
size is exceeded also by half.
This way, you'll always have a 'window', centered around the current
item count. Hence, most of the resizing will happen during bulk
addition or deletion operations, not when there's a relatively
balanced number of them.
'/
newSize = _
iif( _
newSize < m_initialSize, _
m_initialSize, _
newSize )
m_size = newSize
m_lowerBound = _
m_size - m_initialSize - ( m_initialSize shr 1 )
m_lowerBound = _
iif( _
m_lowerBound < m_initialSize, _
1, _
m_lowerBound )
redim preserve _
m_elements( 1 to m_size )
end sub
function Queue.push( _
byval pPriority as integer, _
byval pValue as any ptr, _
byval pDisposeCallback as sub( byval as any ptr ) = Null _
) as QueueElement ptr
/'
Enqueues (adds) an element to the tail of the heap
Whenever one adds an element to a binary heap, the heap has to be
rebalanced (a process known as 'sifting') to leave it in a valid
state. The procedure starts at the tail and proceeds towards the root.
Look here for a reference on how this is implemented:
https://en.wikipedia.org/wiki/Heap_(data_structure)#Implementation
'/
'' This will hold the added element
dim as QueueElement ptr newElement
'' Increment the number of elements in the heap
m_count += 1
'' Resize the internal heap if needed
if( _
m_count > m_size - m_initialSize shr 1 ) then
resize( m_size + m_initialSize )
end if
'' Set the current element position to the tail of the heap
dim as uinteger elementPosition = m_count
'' Creates the QueueElement associated with this position
newElement = new QueueElement( _
pPriority, _
pValue )
m_elements( elementPosition ) = newElement
'' The parent position of this element
dim as uinteger parentPosition
'' Controls if the element needs to be swapped with its parent
dim as boolean needSwap
/'
Sift the heap until the enqueued element reaches its correct
position or it bubbles all the way to the root of the heap.
The parent position of the considered element can be computed
as the considered element position \ 2 in a 1-based array.
'/
do
parentPosition = elementPosition shr 1
if( _
parentPosition > 0 ) then
'' Reset the boolean flag
needSwap = false
/'
Depending on the priority order, see if we need to swap the
considered element with its parent.
'/
select case as const m_priorityOrder
case PriorityOrder.Ascending
if( _
m_elements( elementPosition )->priority < _
m_elements( parentPosition )->priority ) then
/'
Swap positions if the considered element's priority is
*lower* than that of its parent
'/
needSwap = true
end if
case PriorityOrder.Descending
if( _
m_elements( elementPosition )->priority > _
m_elements( parentPosition )->priority ) then
/'
Swap positions if the considered element's priority is
*higher* than that of its parent
'/
needSwap = true
end if
end select
/'
Swap the considered element with its parent and update the
element's position to that of its parent to continue the
sifting.
'/
if( _
needSwap ) then
swap _
m_elements( elementPosition ), _
m_elements( parentPosition )
elementPosition = parentPosition
else
'' No need to swap, element is already at the correct position
exit do
end if
else
'' Element is already at the root, end the sifting
exit do
end if
loop
/'
Returns the newly enqueued element
This allows to cache the element for fast lookups if needed. Be
careful how you use this!
'/
return( newElement )
end function
function Queue.pop() as any ptr
/'
Dequeues (removes) an element from the heap
The heap has to be sifted also when removing elements, this time
starting from the head (the root) element and proceeding towards
the tail.
'/
if( _
m_count > 0 ) then
'' Fetch the 'value' at the root of the heap
dim as any ptr elementValue = m_elements( 1 )->value
'' Delete the QueueElement associated with it
delete( m_elements( 1 ) )
m_elements( 1 ) = Null
'' Then, bring the element on the tail of the heap to the root
swap _
m_elements( 1 ), _
m_elements( m_count )
'' Decrement the element count to account for the removed element
m_count -= 1
'' Resize the internal heap if needed
if( _
m_count < m_lowerBound ) then
resize( m_size - m_initialSize )
end if
/'
Here, the element at the root of the heap is successively checked
against its two siblings to swap their positions if necessary. The
current element position is set at the root of the heap to start
the sifting.
'/
dim as uinteger _
elementPosition = 1, _
_ '' The computed positions of both siblings of the considered element
child1Position, child2Position, _
_ '' The potentially new position the element could take
newPosition
'' Flag to determine if we swap the element or not
dim as boolean needSwap
/'
If there's still elements remaining in the heap, we need to reorder them
to account for the removal of it's previous root element. The sifting
direction depends on how the class was instantiated (in 'Ascending' or
'Descending' priority order).
'/
do _
while( m_count > 0 )
'' Compute the positions of the two siblings of the element
child1Position = elementPosition shl 1
child2Position = child1Position + 1
'' Check if the element has one or two siblings
if( _
child1Position <= m_count ) then
if( _
child2Position <= m_count ) then
/'
The element has two siblings, see which of the two we need to swap
according to the desired priority order, and record its position.
'/
select case as const m_priorityOrder
case PriorityOrder.Ascending
'' Set the new potential position to the *lowest* of the two siblings
newPosition = _
iif( _
m_elements( child1Position )->priority < m_elements( child2Position )->priority, _
child1Position, _
child2Position )
case PriorityOrder.Descending
'' Set the new potential position to the *highest* of the two siblings
newPosition = _
iif( _
m_elements( child1Position )->priority > m_elements( child2Position )->priority, _
child1Position, _
child2Position )
end select
else
'' Only one sibling left, always record its position
newPosition = child1Position
end if
'' Reset the flag
needSwap = false
'' Check to see if we need to swap the element with its sibling
select case as const m_priorityOrder
case PriorityOrder.Ascending
needSwap = _
iif( _
m_elements( elementPosition )->priority > m_elements( newPosition )->priority, _
true, _
false )
case PriorityOrder.Descending
needSwap = _
iif( _
m_elements( elementPosition )->priority < m_elements( newPosition )->priority, _
true, _
false )
end select
/'
If needed, swap the considered element's position with the new position computed
above, and set the current element position to the new one to continue the sifting
from there.
'/
if( _
needSwap ) then
swap _
m_elements( elementPosition ), _
m_elements( newPosition )
elementPosition = newPosition
else
'' Element is already in its correct position
exit do
end if
else
'' Element bubbled to the tail of the heap
exit do
end if
loop
'' Return the root element value
return( elementValue )
end if
'' If there's no elements in the heap, return a null pointer
return( Null )
end function
function Queue.top() as any ptr
/'
Peeks the top value field of the root of the heap, without removing it.
If you specified a dispose callback for elements in the heap, be
careful not to delete them manually using this method or you'll crash
the app when the heap is deleted (since it'll invoke a function pointer
on an element that's not there anymore).
It will return a null pointer if the heap is empty.
'/
if( _
m_count > 0 ) then
return( m_elements( 1 )->value )
else
return( Null )
end if
end function
end namespace
end namespace
#endif
/'
Test code
'/
var pq = FbFrameWork.Collections.Queue( _
FbFramework.Collections.Queue.PriorityOrder.Descending )
dim as integer _
numElements = 1000
'' Add some elements to the queue
for _
i as integer = 1 to numElements
dim as integer _
priority = rnd() * numElements
pq.push( _
priority, _
cptr( any ptr, priority ) )
next
'' Retrieve them
for _
i as integer = 0 to pq.count - 1
? pq.pop()
next
sleep()
As you can see, it has nothing to do with maintaining the
whole heap sorted, only a few elements are sorted upon insertion and retrieval. The implementation shown here is fully abstract, meaning that it stores a
pointer to something (in your case, the cells the pathing algorithm is considering in its 'open' list). Here I just cast the priority to a pointer to store it, for demonstration purposes.
You can also specify a callback in case you need to also dispose of the elements stored upon popping them (not very useful in this case, IMO, but the possibility is there anyway, to maintain orthogonality with other data structures in my framework).