Editors Note, February 14th 2022: This project is now ABANDONED and no longer supported or updated.

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

namespace Phabstractic\Data\Types\Resource
{
    interface ListInterface extends \Countable {
        
        public function top(); 
        
        public function &topReference();
        
        public function push();
        
        public function pushReference(&$a); 
        
        public function pop();
        
        public function &popReference(); 
        
        public function index($i);
        
        public function &indexReference($i); 
        
        public function count();
        
        public function isEmpty();
        
        public function clear();

        public function getList();
        
    }
    
}

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

namespace Phabstractic\Data\Types\Resource
{    
    abstract class AbstractList implements ListInterface
    {
        protected $list = array();
        
        public function __construct($data = null) 
        {
            if (is_array($data)) { 
                $this->list = $data; 
            } elseif ($data instanceof AbstractList) { 
                $this->list = $data->getList(); 
            } elseif ( $data ) { 
                $this->list = array($data);
            } else { 
                $this->list = array();
            }
            
        } 
        
        abstract public function top();
        
        abstract public function &topReference();
        
        abstract public function push();
        
        abstract public function pushReference( &$a );
        
        abstract public function pop();
        
        abstract public function &popReference();
        
        abstract public function index($i);
        
        abstract public function &indexReference($i); 
        
        public function count()
        {
            return count($this->list);
        }
        
        public function isEmpty()
        { 
            return empty($this->list); 
        } 
    
        public function clear()
        { 
            $this->list = array();
            return $this;
        }
        
        public function remove($value)
        {
            if ($key = array_search($value, $this->list)) {
                unset($this->list[$key]);
            }
            
            // resets indices
            $this->list = array_merge($this->list, array());
            return $this->list;
        }
        
        public function getList()
        {
            return $this->list;
        }
        
        abstract public function exchange();
         
        abstract public function duplicate();
        
        abstract function roll($i);
    }     
}

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

namespace Phabstractic\Data\Types\Resource
{
    use Phabstractic\Data\Types;
    use Phabstractic\Data\Types\Exception as TypesException;
    use Phabstractic\Features;
    
    abstract class AbstractRestrictedList extends AbstractList
    {
        use Features\ConfigurationTrait;
        
        protected $restrictions = null;
        
        public function getRestrictions()
        {
            return $this->restrictions;
        }
        
        public function __construct(
            $data = null,
            FilterInterface $restrictions = null,
            $options = array()) 
        {
            $this->configure($options);
            
            // If there are no restrictions given, build basic free form restrictions
            // Default doesn't allow Type::TYPED_OBJECT    
            if (!$restrictions) {
                $restrictions = Types\Restrictions::getDefaultRestrictions();
            }
            
            $this->restrictions = $restrictions;
            if ( is_array( $data ) ) {
                // Plain Array
                
                /* Check input values for any illegal types
                   If false, throw error because this is a constructor and can't
                   really return anything. */
                if (!$this->restrictions::checkElements(
                        $data,
                        $this->restrictions,
                        $this->conf->strict)) {
                    throw new TypesException\InvalidArgumentException(
                        'Phabstractic\\Data\\Types\\Resource\\' .
                        'AbstractRestrictedList->__construct: Illegal Value');
                }
            } else if ($data instanceof AbstractList) {
                // Phabstractic\Data\Types\Resource\AbstractList
                    
                /* Check input values for any illegal types
                   If false, throw error because this is a constructor and can't
                   really return anything. */
                if (!$this->restrictions::checkElements(
                        $data->getList(),
                        $this->restrictions,
                        $this->conf->strict)) {
                    throw new TypesException\InvalidArgumentException(
                        'Phabstractic\\Data\\Types\\Resource\\' .
                        'AbstractRestrictedList->__construct: Illegal Value');
                }
            } else if ($data) {
                // A scalar value
                
                /* Check input values for any illegal types
                   If false, throw error because this is a constructor and can't
                   really return nothing */
                if (!$this->restrictions::checkElements(
                        array($data),
                        $this->restrictions,
                        $this->conf->strict)) {
                    throw new TypesException\InvalidArgumentException(
                        'Phabstractic\\Data\\Types\\Resource\\' .
                        'AbstractRestrictedList->__construct: Illegal Value');
                }
            }
            
            parent::__construct($data);
        }
        
        protected function check()
        {
            if (!$this->restrictions::checkElements(
                    func_get_args(),
                    $this->restrictions,
                    $this->conf->strict)) {
                if ($this->conf->strict) {
                    throw new TypesException\InvalidArgumentException(
                        'Phabstractic\\Data\\Types\\Resource\\' .
                        'AbstractRestrictedList->check: Value not in ' .
                        'restrictions' );
                } else {
                    return false;
                }
                
            }
            
            return true;
        }
        
        public function push()
        {
            $args = func_get_args();
            return call_user_func_array(array($this, 'check'), $args);
        }
        
        public function pushReference(&$a)
        {
            return $this->check($a);
        }
    }
}

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

namespace Phabstractic\Data\Types\Resource
{
    
    use Phabstractic\Features;
    
    abstract class AbstractSortedList extends AbstractRestrictedList
    {
        use Features\ConfigurationTrait;
        
        public function __construct(
            $data = null,
            FilterInterface $restrictions = null,
            $options = array()
        ) {
            $this->configure($options);
            
            parent::__construct($data, $restrictions, $options);
            
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
        }
    
        abstract protected function cmp($l, $r);
        
        public function top()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function &topReference()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function index($i)
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function &indexReference($i)
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function pop()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function &popReference()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        /**
         * Retrieve the list element of the list
         * 
         * @return array The current internal list member
         * 
         */
        public function getList()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
            return $this->list;
        }
    }
}

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

namespace Phabstractic\Data\Types
{
    use Phabstractic\Data\Types\Resource as TypesResource;
    
    class Priority implements TypesResource\PriorityInterface
    {
        private $data = null;
        
        private $priority = 0;
        
        public function __construct(&$data, $priority = 0)
        {
            $this->data = &$data;
            $this->priority = $priority;
        }
        
        public function getData()
        {
            return $this->data;
        }
        
        public function &getDataReference()
        {
            return $this->data;
        }
        
        public function getPriority()
        {
            return $this->priority;
        }
        
        public function setPriority($priority)
        {
            $this->priority = $priority;
        }
        
        public static function buildPriority($data, $priority = 0)
        {
            return new Priority($data, $priority);
        }
    }
}

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

protected function cmp($l, $r)
{
    // check against restrictions, v3
    if (!$this->restrictions->isAllowed(Type\getValueType($l)) ||
            !$this->restrictions->isAllowed(Type\getValueType($r))) {
        throw new TypesException\InvalidArgumentException(
            'Phabstractic\\Data\\Types\\PriorityQueue->cmp: ' .
            'Comparison types not allowed');
    }
            
    $lp = $l->getPriority();
    $rp = $r->getPriority();
    
    if ( $lp > $rp ) {
        return 1;
    } else if ( $lp < $rp ) {
        return -1;
    } else {
        return 0;
    }
    
}

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.

/**
 * Return Data Equal To Given Urgency Index?
 * 
 */
const EQUAL = 0;

/**
 * Return Data Equal or Higher To Given Urgency Index?
 * 
 */
const HIGHER = 1;

/**
 * Return Data Equal or Lower to Given Urgency Index?
 * 
 */
const LOWER = -1;

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:

public function index($i, $order = self::EQUAL)
{
    if (empty($this->list)) {
        if ($this->conf->strict) {
            throw new Exception\RangeException(
                'Phabstractic\\Data\\Types\\PriorityQueue->index: ' .
                'call on empty list');
        } else {
            return array(new None());
        }
    } else {
        $return = array();
        foreach ($this->list as $item) {
            switch ($order) {
                /* this stores the results of boolean logic statements
                   allows us to reference the result in one place below */
                case self::HIGHER:
                    $predicate = $item->getPriority() >= $i;
                    break;
                    
                case self::LOWER:
                    $predicate = $item->getPriority() <= $i;
                    break;
                
                case self::EQUAL:
                    $predicate = $item->getPriority() == $i;
                    break;
                    
                default:
                    $predicate = true;
            }
            
            // Do we include the item?
            if ( $predicate ) {
                $return[] = $item->getData();
            }
        }
        
        return $return;
    }
    
}

public function indexRange(Range $r)
{
    return PhabstracticResource\ArrayUtilities::returnUnique(
        Set::intersection($this->index($r->getMinimum(), self::HIGHER),
                          $this->index($r->getMaximum(), self::LOWER)));
}
        
public function &indexReference($i, $order = self::EQUAL)
{
    if (empty($this->list)) {
        if ($this->conf->strict) {
            throw new Exception\RangeException(
                'Phabstractic\\Data\\Types\\PriorityQueue->indexReference: ' .
                'call on empty list');
        } else {
            $arr = array(new None());
            // return value, not literal
            return $arr;
        }
    } else {
        $return = array();
        foreach ($this->list as $item) {
            switch ($order) {
                case self::HIGHER:
                    $predicate = $item->getPriority() >= $i;
                    break;
                    
                case self::LOWER:
                    $predicate = $item->getPriority() <= $i;
                    break;
                
                case self::EQUAL:
                    $predicate = $item->getPriority() == $i;
                    break;
                    
                default:
                    $predicate = true;
            }
            
            // Do we include the item?
            if ( $predicate ) {
                $return[] = &$item->getDataReference();
            }
        }
        
        return $return;
    }
}

public function indexRangeReference( Types\Range $r )
{
    return PhabstracticResource\ArrayUtilities::returnUniqueByReference(
        Set::intersection($this->indexReference($r->getMinimum(), self::HIGHER),
                          $this->indexReference($r->getMaximum(), self::LOWER)));
}

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

public function &retrievePriority($data) {
    foreach ($this->getList() as $key => $priority) {
        if ($priority->getData() == $data) {
            return $this->list[$key];
        }
    }
    
    $none = new None();
    return $none;
}

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:

public static function buildPriority($data, $priority = 0)
{
    return new Priority($data, $priority);
}

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

<?php

use Phabstractic\Data\Types;

$priorityqueue = new Types\PriorityQueue();

$data1 = 5;
$data2 = 'string';
$data3 = false;

$priorityqueue->push(Types\Priority::buildPriority($data1, 1));
$priorityqueue->push(Types\Priority::buildPriority($data2, 5));
$priorityqueue->push(Types\Priority::buildPriority($data3);

var_dump($priorityqueue->getLlist());

// array( Priority(data: false), Priority(data: 5), Priority(data: 'string') )

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

$priority = Types\Priority::buildPriority(false, 7);

$priorityqueue->pushReference($priority);

$priority->setPriority(3);

// or

$priorityref = &$priorityqueue->retrievePriority('string');

$prioriryref->setPriority(8);

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.

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

Asher Wolfstein

Metaverse Resident

About the Author

A metaverse resident, you can find me on Second Life (kadar.talbot) and other online platforms. I write about my digital life, my musings, and my projects as a programmer, webmaster, artist, and game designer. (exist (be wunk) (use rational imagination) (import artist coder maker furry) (conditional (if (eq you asshole) (me (block you))))

View Articles