<?php
/**
* Zend Framework
*
* LICENSE
*
* This source file is subject to the new BSD license that is bundled
* with this package in the file LICENSE.txt.
* It is also available through the world-wide-web at this URL:
* http://framework.zend.com/license/new-bsd
* If you did not receive a copy of the license and are unable to
* obtain it through the world-wide-web, please send an email
* to [email protected] so we can send you a copy immediately.
*
* @category Zend
* @package Zend_Stdlib
* @copyright Copyright (c) 2005-2014 Zend Technologies USA Inc. (http://www.zend.com)
* @license http://framework.zend.com/license/new-bsd New BSD License
*/
require_once 'Zend/Stdlib/SplPriorityQueue.php';
/**
* 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.
*
* @category Zend
* @package Zend_Stdlib
* @copyright Copyright (c) 2005-2014 Zend Technologies USA Inc. (http://www.zend.com)
* @license http://framework.zend.com/license/new-bsd New BSD License
*/
class Zend_Stdlib_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 = 'Zend_Stdlib_SplPriorityQueue';
/**
* Actual items aggregated in the priority queue. Each item is an array
* with keys "data" and "priority".
* @var array
*/
protected $items = array();
/**
* 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 Zend_Stdlib_PriorityQueue
*/
public function insert($data, $priority = 1)
{
$priority = (int) $priority;
$this->items[] = array(
'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 boolean 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;
$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
*/
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
*/
public function getIterator()
{
$queue = $this->getQueue();
return clone $queue;
}
/**
* Serialize the data structure
*
* @return string
*/
public function serialize()
{
return serialize($this->items);
}
/**
* Unserialize a string into a Zend_Stdlib_PriorityQueue object
*
* Serialization format is compatible with {@link Zend_Stdlib_SplPriorityQueue}
*
* @param string $data
* @return void
*/
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(array($this, 'returnPriority'), $this->items);
case self::EXTR_DATA:
default:
return array_map(array($this, 'returnData'), $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 Zend_Stdlib_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
*
* @return Zend_Stdlib_SplPriorityQueue
*/
protected function getQueue()
{
if (null === $this->queue) {
$this->queue = new $this->queueClass();
if (!$this->queue instanceof SplPriorityQueue) {
throw new DomainException(sprintf(
'Zend_Stdlib_PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
get_class($this->queue)
));
}
}
return $this->queue;
}
/**
* Return priority from an internal item
*
* Used as a lambda in toArray().
*
* @param array $item
* @return mixed
*/
public function returnPriority($item)
{
return $item['priority'];
}
/**
* Return data from an internal item
*
* Used as a lambda in toArray().
*
* @param array $item
* @return mixed
*/
public function returnData($item)
{
return $item['data'];
}
}