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;
15 use SplPriorityQueue as PhpSplPriorityQueue;
18 * This is an efficient implementation of an integer priority queue in PHP
20 * This class acts like a queue with insert() and extract(), removing the
21 * elements from the queue and it also acts like an Iterator without removing
22 * the elements. This behaviour can be used in mixed scenarios with high
25 class FastPriorityQueue implements Iterator, Countable, Serializable
27 const EXTR_DATA = PhpSplPriorityQueue::EXTR_DATA;
28 const EXTR_PRIORITY = PhpSplPriorityQueue::EXTR_PRIORITY;
29 const EXTR_BOTH = PhpSplPriorityQueue::EXTR_BOTH;
34 protected $extractFlag = self::EXTR_DATA;
37 * Elements of the queue, divided by priorities
41 protected $values = [];
48 protected $priorities = [];
51 * Array of priorities used for the iteration
55 protected $subPriorities = [];
62 protected $maxPriority = null;
65 * Total number of elements in the queue
72 * Index of the current element in the queue
79 * Sub index of the current element in the same priority level
83 protected $subIndex = 0;
86 * Insert an element in the queue with a specified priority
89 * @param integer $priority
91 public function insert($value, $priority)
93 if (! is_int($priority)) {
94 throw new Exception\InvalidArgumentException('The priority must be an integer');
96 $this->values[$priority][] = $value;
97 if (! isset($this->priorities[$priority])) {
98 $this->priorities[$priority] = $priority;
99 $this->maxPriority = $this->maxPriority === null ? $priority : max($priority, $this->maxPriority);
105 * Extract an element in the queue according to the priority and the
110 public function extract()
112 if (! $this->valid()) {
115 $value = $this->current();
116 $this->nextAndRemove();
121 * Remove an item from the queue
123 * This is different than {@link extract()}; its purpose is to dequeue an
126 * Note: this removes the first item matching the provided item found. If
127 * the same item has been added multiple times, it will not remove other
130 * @param mixed $datum
131 * @return bool False if the item was not found, true otherwise.
133 public function remove($datum)
135 $currentIndex = $this->index;
136 $currentSubIndex = $this->subIndex;
137 $currentPriority = $this->maxPriority;
140 while ($this->valid()) {
141 if (current($this->values[$this->maxPriority]) === $datum) {
142 $index = key($this->values[$this->maxPriority]);
143 unset($this->values[$this->maxPriority][$index]);
145 // The `next()` method advances the internal array pointer, so we need to use the `reset()` function,
146 // otherwise we would lose all elements before the place the pointer points.
147 reset($this->values[$this->maxPriority]);
149 $this->index = $currentIndex;
150 $this->subIndex = $currentSubIndex;
152 // If the array is empty we need to destroy the unnecessary priority,
153 // otherwise we would end up with an incorrect value of `$this->count`
154 // {@see \Zend\Stdlib\FastPriorityQueue::nextAndRemove()}.
155 if (empty($this->values[$this->maxPriority])) {
156 unset($this->values[$this->maxPriority]);
157 unset($this->priorities[$this->maxPriority]);
158 if ($this->maxPriority === $currentPriority) {
163 $this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
173 * Get the total number of elements in the queue
177 public function count()
183 * Get the current element in the queue
187 public function current()
189 switch ($this->extractFlag) {
190 case self::EXTR_DATA:
191 return current($this->values[$this->maxPriority]);
192 case self::EXTR_PRIORITY:
193 return $this->maxPriority;
194 case self::EXTR_BOTH:
196 'data' => current($this->values[$this->maxPriority]),
197 'priority' => $this->maxPriority
203 * Get the index of the current element in the queue
207 public function key()
213 * Set the iterator pointer to the next element in the queue
214 * removing the previous element
216 protected function nextAndRemove()
218 $key = key($this->values[$this->maxPriority]);
220 if (false === next($this->values[$this->maxPriority])) {
221 unset($this->priorities[$this->maxPriority]);
222 unset($this->values[$this->maxPriority]);
223 $this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
224 $this->subIndex = -1;
226 unset($this->values[$this->maxPriority][$key]);
234 * Set the iterator pointer to the next element in the queue
235 * without removing the previous element
237 public function next()
239 if (false === next($this->values[$this->maxPriority])) {
240 unset($this->subPriorities[$this->maxPriority]);
241 reset($this->values[$this->maxPriority]);
242 $this->maxPriority = empty($this->subPriorities) ? null : max($this->subPriorities);
243 $this->subIndex = -1;
250 * Check if the current iterator is valid
254 public function valid()
256 return isset($this->values[$this->maxPriority]);
260 * Rewind the current iterator
262 public function rewind()
264 $this->subPriorities = $this->priorities;
265 $this->maxPriority = empty($this->priorities) ? 0 : max($this->priorities);
271 * Serialize to an array
273 * Array will be priority => data pairs
277 public function toArray()
280 foreach (clone $this as $item) {
291 public function serialize()
293 $clone = clone $this;
294 $clone->setExtractFlags(self::EXTR_BOTH);
297 foreach ($clone as $item) {
301 return serialize($data);
307 * @param string $data
310 public function unserialize($data)
312 foreach (unserialize($data) as $item) {
313 $this->insert($item['data'], $item['priority']);
318 * Set the extract flag
320 * @param integer $flag
322 public function setExtractFlags($flag)
325 case self::EXTR_DATA:
326 case self::EXTR_PRIORITY:
327 case self::EXTR_BOTH:
328 $this->extractFlag = $flag;
331 throw new Exception\InvalidArgumentException("The extract flag specified is not valid");
336 * Check if the queue is empty
340 public function isEmpty()
342 return empty($this->values);
346 * Does the queue contain the given datum?
348 * @param mixed $datum
351 public function contains($datum)
353 foreach ($this->values as $values) {
354 if (in_array($datum, $values)) {
362 * Does the queue have an item with the given priority?
364 * @param int $priority
367 public function hasPriority($priority)
369 return isset($this->values[$priority]);