Skip to content

Instantly share code, notes, and snippets.

@jferrao
Last active October 1, 2021 18:57
Show Gist options
  • Save jferrao/b46b24d3ef8b96a477e4 to your computer and use it in GitHub Desktop.
Save jferrao/b46b24d3ef8b96a477e4 to your computer and use it in GitHub Desktop.
Simple priority queue implementation in PHP
<?php
/**
* A really simple priority queue implementation in PHP.
*
* @author João Ferrão
* @link https://github.com/jferrao
*/
class PnQueue
{
/**
* The array that will act as a queue
* @var array
*/
protected $queue = array();
/**
* Adds an item at the end of the queue or at the end of
* a given priority queue if $priority is set.
* @param mixed $item
* @param int $priority
* @throws Exception If $priority is not a numerical value
*/
public function push($item, $priority = 0)
{
if (!is_numeric($priority)) {
throw new Exception('Numeric priority value expected');
}
isset($this->queue[$priority]) || $this->queue[$priority] = array();
array_push($this->queue[$priority], $item);
ksort($this->queue);
return $this;
}
/**
* Returs the first element of the highest priority set, or
* the first element of a given priority queue if $priority is set.
* @param int $priority
* @return mixed|null
*/
public function pop($priority = null)
{
// Get the first message from the first priority queue
if (null === $priority) {
reset($this->queue);
$priority = key($this->queue);
}
if (is_numeric($priority) && isset($this->queue[$priority])) {
// Avoiding array_shift() since it requires a re-index process
// on the array and it may be slower for large collections of items
$item = array_pop(array_reverse($this->queue[$priority]));
unset($this->queue[$priority][key($this->queue[$priority])]);
// Remove priority queue if it's empty
if (empty($this->queue[$priority])) {
unset($this->queue[$priority]);
}
return $item;
}
return null;
}
/**
* Purge the entire queue or only messages in a given
* priority queue if $priority is set.
* @param int $priority
*/
public function purge($priority = null)
{
if (null === $priority) {
$this->queue = array();
} elseif (is_numeric($priority) && isset($this->queue[$priority])) {
$this->queue[$priority] = array();
}
}
/**
* Returns the number of items in all priority queues or in
* a single priority queue if $priority is set.
* @param int $priority
* @return int
*/
public function count($priority = null)
{
switch ($priority) {
case null:
$count = 0;
foreach ($this->queue as $priorityQueue) {
$count += count($priorityQueue);
}
return $count;
case (is_numeric($priority) && isset($this->queue[$priority])):
return count($this->queue[$priority]);
default:
return 0;
}
}
/**
* Dump the content of the entire queue or a single priority
* queue if $priority is set.
* @param int $priority
* @return array|null
*/
public function dump($priority = null)
{
if (null === $priority) {
return $this->queue;
} elseif (is_numeric($priority) && isset($this->queue[$priority])) {
return $this->queue[$priority];
}
return null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment