Phabstractic: Priority Queue Data Type

asherwunk/phabstractic now has a priority queue implementation in pure PHP.

Priority Queues

I quote Wikipedia for the definition of a priority queue:

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

Many priority queues are implemented using a heap, but in my implementation, I used an array that self-sorts, as previously written about it.  For more information on heaps, have a look at Wikipedia.  A heap is a special type of abstract data structure I hope to implement in the future, but I feel it’s a little bit of complicated overkill for the basic functionality needed by a priority queue in the PHP language.

First, let’s review the structure of a list in the phabstractic library.  Every list implements the ListInterface (Github):

We add and remove elements onto the list using  ->push()  and  ->pop() , and we index into the list using  ->index()  and  ->indexReference() .  In our implementation we’re going to have more methods than this, in fact, we inherit from AbstractList (Github):

For this particular implementation, it is important that the list sorts itself according to the priorities associated with each element.  In order to be a self-sorting list, we must inherit from AbstractSortedList, which in turn inherits from AbstractRestrictedList.  This is in order to ensure proper data types are stored and compared (in this case priorities) (Github):

Remember that these implemented abstract methods are meant to be called using parent:: to check certain values, but the actual addition of the data to the list should be done in the implementation.

So that brings us to the final AbstractSortedList.  Remember that the sorted list doesn’t sort itself when data is input into the list, but when the list is called to be represented (Github):

Remember again that these methods are meant to be called from the child object using parent::, otherwise, they don’t really do much on their own.

So what do we sort?

Priority

We want to sort elements of a list pointing to some data by their priority.  That means we have to associate a priority index with a piece of data.  This is the job of the Priority object.  It’s fairly simple, it has two properties, one for data and one for a priority index (github):

PriorityQueue

The priority queue class is a restricted list, confining itself only to Priority objects (as defined above).  The idea is that the lower a priority is, the more urgent or ‘soon’ it has to happen.  This means we need to override and implement the comparison method as put forward in the AbstractSortedList.  Since we know that we are going to be using Priority objects, we only need to be concerned about those (github):

Note that as a sanity check we do one last check of all the values to make sure they really are what we want them to be (Priority objects).

Indexing a PriorityQueue

Delving into a PriorityQueue is an interesting endeavor.  The issue is that multiple items may have the same priority, and the priorities are definitely not always consecutive.  We can provide a snapshot of a PriorityQueue where we access all the priorities from 0 up, but we might also want to query for priorities above a certain amount or within a certain range.  The PriorityQueue class defines three constants to help with indexing.

We use these to index into the array.  Because it is more complicated than specifying a single index number, we don’t implement \ArrayAccess.  Rather we re-implement the index and indexReference methods to include the constants.  We also have the ability to access a range of priorities, so we add two new methods to the arsenal:

Another alternative to indexing into a priority queue is to return the first priority object that matches a piece of data.  This is the purpose of retrievePriority:

Usage

Using a PriorityQueue is a simple affair.  We have to encapsulate every piece of data into a priority, but that is easily done using the static function provided by the Priority class:

So let’s say we want to add four priority items, it would go something like this:

Say we wanted to change the priority of one of the items in the list?  We have two options, save the Priority object and add it to the list via reference, or find the data and set the priority returned.  The list will appear to automatically ‘update’, (in reality, it’s just sorting on demand):

Conclusion

Priority Queues are very useful and usually, are implemented using heaps.  This Priority Queue is implemented using an array that sorts itself rather than an overly complicated binary tree or heap.  A priority queue is very useful for event-oriented programming, multitasking processes, and online message queues.  Lining anything up in order but leaving it able to be edited in place through priority is important to any responsive system.

This is part of the Phabstractic Library.

If you appreciate my programming please help support me through my Patreon.

photo credit: Seattle Metro 2005 NFI DE60LF 2778 University Way at NE 44 – 2 via photopin (license)

kadar

I'm just a wunk, trying to enjoy life. I am a cofounder of http//originalpursuitssoc.com/ and I like computers, code, creativity, and friends.

You may also like...

Leave a Reply

%d bloggers like this: