<?php
/**
* @see https://github.com/laminas/laminas-stdlib for the canonical source repository
* @copyright https://github.com/laminas/laminas-stdlib/blob/master/COPYRIGHT.md
* @license https://github.com/laminas/laminas-stdlib/blob/master/LICENSE.md New BSD License
*/
namespace Laminas\Stdlib;
use Countable;
use IteratorAggregate;
use Serializable;
/**
* Re-usable, serializable priority queue implementation
*
* SplPriorityQueue acts as a heap; on iteration, each item is removed from the
* queue. If you wish to re-use such a queue, you need to clone it first. This
* makes for some interesting issues if you wish to delete items from the queue,
* or, as already stated, iterate over it multiple times.
*
* This class aggregates items for the queue itself, but also composes an
* "inner" iterator in the form of an SplPriorityQueue object for performing
* the actual iteration.
*/
class PriorityQueue implements Countable, IteratorAggregate, Serializable
{
const EXTR_DATA = 0x00000001;
const EXTR_PRIORITY = 0x00000002;
const EXTR_BOTH = 0x00000003;
/**
* Inner queue class to use for iteration
* @var string
*/
protected $queueClass = 'Laminas\Stdlib\SplPriorityQueue';
/**
* Actual items aggregated in the priority queue. Each item is an array
* with keys "data" and "priority".
* @var array
*/
protected $items = [];
/**
* Inner queue object
* @var SplPriorityQueue
*/
protected $queue;
/**
* Insert an item into the queue
*
* Priority defaults to 1 (low priority) if none provided.
*
* @param mixed $data
* @param int $priority
* @return PriorityQueue
*/
public function insert($data, $priority = 1)
{
$priority = (int) $priority;
$this->items[] = [
'data' => $data,
'priority' => $priority,
];
$this->getQueue()->insert($data, $priority);
return $this;
}
/**
* Remove an item from the queue
*
* This is different than {@link extract()}; its purpose is to dequeue an
* item.
*
* This operation is potentially expensive, as it requires
* re-initialization and re-population of the inner queue.
*
* Note: this removes the first item matching the provided item found. If
* the same item has been added multiple times, it will not remove other
* instances.
*
* @param mixed $datum
* @return bool False if the item was not found, true otherwise.
*/
public function remove($datum)
{
$found = false;
foreach ($this->items as $key => $item) {
if ($item['data'] === $datum) {
$found = true;
break;
}
}
if ($found) {
unset($this->items[$key]);
$this->queue = null;
if (! $this->isEmpty()) {
$queue = $this->getQueue();
foreach ($this->items as $item) {
$queue->insert($item['data'], $item['priority']);
}
}
return true;
}
return false;
}
/**
* Is the queue empty?
*
* @return bool
*/
public function isEmpty()
{
return (0 === $this->count());
}
/**
* How many items are in the queue?
*
* @return int
*/
#[\ReturnTypeWillChange]
public function count()
{
return count($this->items);
}
/**
* Peek at the top node in the queue, based on priority.
*
* @return mixed
*/
public function top()
{
return $this->getIterator()->top();
}
/**
* Extract a node from the inner queue and sift up
*
* @return mixed
*/
public function extract()
{
return $this->getQueue()->extract();
}
/**
* Retrieve the inner iterator
*
* SplPriorityQueue acts as a heap, which typically implies that as items
* are iterated, they are also removed. This does not work for situations
* where the queue may be iterated multiple times. As such, this class
* aggregates the values, and also injects an SplPriorityQueue. This method
* retrieves the inner queue object, and clones it for purposes of
* iteration.
*
* @return SplPriorityQueue
*/
#[\ReturnTypeWillChange]
public function getIterator()
{
$queue = $this->getQueue();
return clone $queue;
}
/**
* Serialize the data structure
*
* @return string
*/
#[\ReturnTypeWillChange]
public function serialize()
{
return serialize($this->items);
}
/**
* Unserialize a string into a PriorityQueue object
*
* Serialization format is compatible with {@link Laminas\Stdlib\SplPriorityQueue}
*
* @param string $data
* @return void
*/
#[\ReturnTypeWillChange]
public function unserialize($data)
{
foreach (unserialize($data) as $item) {
$this->insert($item['data'], $item['priority']);
}
}
/**
* Serialize to an array
*
* By default, returns only the item data, and in the order registered (not
* sorted). You may provide one of the EXTR_* flags as an argument, allowing
* the ability to return priorities or both data and priority.
*
* @param int $flag
* @return array
*/
public function toArray($flag = self::EXTR_DATA)
{
switch ($flag) {
case self::EXTR_BOTH:
return $this->items;
case self::EXTR_PRIORITY:
return array_map(function ($item) {
return $item['priority'];
}, $this->items);
case self::EXTR_DATA:
default:
return array_map(function ($item) {
return $item['data'];
}, $this->items);
}
}
/**
* Specify the internal queue class
*
* Please see {@link getIterator()} for details on the necessity of an
* internal queue class. The class provided should extend SplPriorityQueue.
*
* @param string $class
* @return PriorityQueue
*/
public function setInternalQueueClass($class)
{
$this->queueClass = (string) $class;
return $this;
}
/**
* Does the queue contain the given datum?
*
* @param mixed $datum
* @return bool
*/
public function contains($datum)
{
foreach ($this->items as $item) {
if ($item['data'] === $datum) {
return true;
}
}
return false;
}
/**
* Does the queue have an item with the given priority?
*
* @param int $priority
* @return bool
*/
public function hasPriority($priority)
{
foreach ($this->items as $item) {
if ($item['priority'] === $priority) {
return true;
}
}
return false;
}
/**
* Get the inner priority queue instance
*
* @throws Exception\DomainException
* @return SplPriorityQueue
*/
protected function getQueue()
{
if (null === $this->queue) {
$this->queue = new $this->queueClass();
if (! $this->queue instanceof \SplPriorityQueue) {
throw new Exception\DomainException(sprintf(
'PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
get_class($this->queue)
));
}
}
return $this->queue;
}
/**
* Add support for deep cloning
*
* @return void
*/
public function __clone()
{
if (null !== $this->queue) {
$this->queue = clone $this->queue;
}
}
}