diff options
Diffstat (limited to 'vendor/zendframework/zend-stdlib/src/PriorityQueue.php')
-rw-r--r-- | vendor/zendframework/zend-stdlib/src/PriorityQueue.php | 301 |
1 files changed, 0 insertions, 301 deletions
diff --git a/vendor/zendframework/zend-stdlib/src/PriorityQueue.php b/vendor/zendframework/zend-stdlib/src/PriorityQueue.php deleted file mode 100644 index 1baf44e..0000000 --- a/vendor/zendframework/zend-stdlib/src/PriorityQueue.php +++ /dev/null @@ -1,301 +0,0 @@ -<?php -/** - * Zend Framework (http://framework.zend.com/) - * - * @link http://github.com/zendframework/zf2 for the canonical source repository - * @copyright Copyright (c) 2005-2015 Zend Technologies USA Inc. (http://www.zend.com) - * @license http://framework.zend.com/license/new-bsd New BSD License - */ - -namespace Zend\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 = '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 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 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 - */ - 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 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(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; - } - } -} |