3 * Zend Framework (http://framework.zend.com/)
5 * @link http://github.com/zendframework/zf2 for the canonical source repository
6 * @copyright Copyright (c) 2005-2015 Zend Technologies USA Inc. (http://www.zend.com)
7 * @license http://framework.zend.com/license/new-bsd New BSD License
10 namespace Zend\Stdlib;
13 use IteratorAggregate;
17 * Re-usable, serializable priority queue implementation
19 * SplPriorityQueue acts as a heap; on iteration, each item is removed from the
20 * queue. If you wish to re-use such a queue, you need to clone it first. This
21 * makes for some interesting issues if you wish to delete items from the queue,
22 * or, as already stated, iterate over it multiple times.
24 * This class aggregates items for the queue itself, but also composes an
25 * "inner" iterator in the form of an SplPriorityQueue object for performing
26 * the actual iteration.
28 class PriorityQueue implements Countable, IteratorAggregate, Serializable
30 const EXTR_DATA = 0x00000001;
31 const EXTR_PRIORITY = 0x00000002;
32 const EXTR_BOTH = 0x00000003;
35 * Inner queue class to use for iteration
38 protected $queueClass = 'Zend\Stdlib\SplPriorityQueue';
41 * Actual items aggregated in the priority queue. Each item is an array
42 * with keys "data" and "priority".
45 protected $items = [];
49 * @var SplPriorityQueue
54 * Insert an item into the queue
56 * Priority defaults to 1 (low priority) if none provided.
59 * @param int $priority
60 * @return PriorityQueue
62 public function insert($data, $priority = 1)
64 $priority = (int) $priority;
67 'priority' => $priority,
69 $this->getQueue()->insert($data, $priority);
74 * Remove an item from the queue
76 * This is different than {@link extract()}; its purpose is to dequeue an
79 * This operation is potentially expensive, as it requires
80 * re-initialization and re-population of the inner queue.
82 * Note: this removes the first item matching the provided item found. If
83 * the same item has been added multiple times, it will not remove other
87 * @return bool False if the item was not found, true otherwise.
89 public function remove($datum)
92 foreach ($this->items as $key => $item) {
93 if ($item['data'] === $datum) {
99 unset($this->items[$key]);
102 if (! $this->isEmpty()) {
103 $queue = $this->getQueue();
104 foreach ($this->items as $item) {
105 $queue->insert($item['data'], $item['priority']);
114 * Is the queue empty?
118 public function isEmpty()
120 return (0 === $this->count());
124 * How many items are in the queue?
128 public function count()
130 return count($this->items);
134 * Peek at the top node in the queue, based on priority.
138 public function top()
140 return $this->getIterator()->top();
144 * Extract a node from the inner queue and sift up
148 public function extract()
150 return $this->getQueue()->extract();
154 * Retrieve the inner iterator
156 * SplPriorityQueue acts as a heap, which typically implies that as items
157 * are iterated, they are also removed. This does not work for situations
158 * where the queue may be iterated multiple times. As such, this class
159 * aggregates the values, and also injects an SplPriorityQueue. This method
160 * retrieves the inner queue object, and clones it for purposes of
163 * @return SplPriorityQueue
165 public function getIterator()
167 $queue = $this->getQueue();
172 * Serialize the data structure
176 public function serialize()
178 return serialize($this->items);
182 * Unserialize a string into a PriorityQueue object
184 * Serialization format is compatible with {@link Zend\Stdlib\SplPriorityQueue}
186 * @param string $data
189 public function unserialize($data)
191 foreach (unserialize($data) as $item) {
192 $this->insert($item['data'], $item['priority']);
197 * Serialize to an array
199 * By default, returns only the item data, and in the order registered (not
200 * sorted). You may provide one of the EXTR_* flags as an argument, allowing
201 * the ability to return priorities or both data and priority.
206 public function toArray($flag = self::EXTR_DATA)
209 case self::EXTR_BOTH:
211 case self::EXTR_PRIORITY:
212 return array_map(function ($item) {
213 return $item['priority'];
215 case self::EXTR_DATA:
217 return array_map(function ($item) {
218 return $item['data'];
224 * Specify the internal queue class
226 * Please see {@link getIterator()} for details on the necessity of an
227 * internal queue class. The class provided should extend SplPriorityQueue.
229 * @param string $class
230 * @return PriorityQueue
232 public function setInternalQueueClass($class)
234 $this->queueClass = (string) $class;
239 * Does the queue contain the given datum?
241 * @param mixed $datum
244 public function contains($datum)
246 foreach ($this->items as $item) {
247 if ($item['data'] === $datum) {
255 * Does the queue have an item with the given priority?
257 * @param int $priority
260 public function hasPriority($priority)
262 foreach ($this->items as $item) {
263 if ($item['priority'] === $priority) {
271 * Get the inner priority queue instance
273 * @throws Exception\DomainException
274 * @return SplPriorityQueue
276 protected function getQueue()
278 if (null === $this->queue) {
279 $this->queue = new $this->queueClass();
280 if (! $this->queue instanceof \SplPriorityQueue) {
281 throw new Exception\DomainException(sprintf(
282 'PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
283 get_class($this->queue)
291 * Add support for deep cloning
295 public function __clone()
297 if (null !== $this->queue) {
298 $this->queue = clone $this->queue;