3 * Zend Framework (http://framework.zend.com/)
5 * @link http://github.com/zendframework/zf2 for the canonical source repository
6 * @copyright Copyright (c) 2005-2013 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 = array();
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;
65 $this->items
[] = array(
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
:
212 case self
::EXTR_PRIORITY
:
213 return array_map(function ($item) {
214 return $item['priority'];
216 case self
::EXTR_DATA
:
218 return array_map(function ($item) {
219 return $item['data'];
225 * Specify the internal queue class
227 * Please see {@link getIterator()} for details on the necessity of an
228 * internal queue class. The class provided should extend SplPriorityQueue.
230 * @param string $class
231 * @return PriorityQueue
233 public function setInternalQueueClass($class)
235 $this->queueClass
= (string) $class;
240 * Does the queue contain the given datum?
242 * @param mixed $datum
245 public function contains($datum)
247 foreach ($this->items
as $item) {
248 if ($item['data'] === $datum) {
256 * Does the queue have an item with the given priority?
258 * @param int $priority
261 public function hasPriority($priority)
263 foreach ($this->items
as $item) {
264 if ($item['priority'] === $priority) {
272 * Get the inner priority queue instance
274 * @throws Exception\DomainException
275 * @return SplPriorityQueue
277 protected function getQueue()
279 if (null === $this->queue
) {
280 $this->queue
= new $this->queueClass();
281 if (!$this->queue
instanceof \SplPriorityQueue
) {
282 throw new Exception\
DomainException(sprintf(
283 'PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
284 get_class($this->queue
)
292 * Add support for deep cloning
296 public function __clone()
298 if (null !== $this->queue
) {
299 $this->queue
= clone $this->queue
;