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 = 0;
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 a positive integer
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 = 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)
136 while ($this->valid()) {
137 if (current($this->values[$this->maxPriority]) === $datum) {
138 $index = key($this->values[$this->maxPriority]);
139 unset($this->values[$this->maxPriority][$index]);
149 * Get the total number of elements in the queue
153 public function count()
159 * Get the current element in the queue
163 public function current()
165 switch ($this->extractFlag) {
166 case self::EXTR_DATA:
167 return current($this->values[$this->maxPriority]);
168 case self::EXTR_PRIORITY:
169 return $this->maxPriority;
170 case self::EXTR_BOTH:
172 'data' => current($this->values[$this->maxPriority]),
173 'priority' => $this->maxPriority
179 * Get the index of the current element in the queue
183 public function key()
189 * Set the iterator pointer to the next element in the queue
190 * removing the previous element
192 protected function nextAndRemove()
194 if (false === next($this->values[$this->maxPriority])) {
195 unset($this->priorities[$this->maxPriority]);
196 unset($this->values[$this->maxPriority]);
197 $this->maxPriority = empty($this->priorities) ? 0 : max($this->priorities);
198 $this->subIndex = -1;
206 * Set the iterator pointer to the next element in the queue
207 * without removing the previous element
209 public function next()
211 if (false === next($this->values[$this->maxPriority])) {
212 unset($this->subPriorities[$this->maxPriority]);
213 reset($this->values[$this->maxPriority]);
214 $this->maxPriority = empty($this->subPriorities) ? 0 : max($this->subPriorities);
215 $this->subIndex = -1;
222 * Check if the current iterator is valid
226 public function valid()
228 return isset($this->values[$this->maxPriority]);
232 * Rewind the current iterator
234 public function rewind()
236 $this->subPriorities = $this->priorities;
237 $this->maxPriority = empty($this->priorities) ? 0 : max($this->priorities);
243 * Serialize to an array
245 * Array will be priority => data pairs
249 public function toArray()
252 foreach (clone $this as $item) {
263 public function serialize()
265 $clone = clone $this;
266 $clone->setExtractFlags(self::EXTR_BOTH);
269 foreach ($clone as $item) {
273 return serialize($data);
279 * @param string $data
282 public function unserialize($data)
284 foreach (unserialize($data) as $item) {
285 $this->insert($item['data'], $item['priority']);
290 * Set the extract flag
292 * @param integer $flag
294 public function setExtractFlags($flag)
297 case self::EXTR_DATA:
298 case self::EXTR_PRIORITY:
299 case self::EXTR_BOTH:
300 $this->extractFlag = $flag;
303 throw new Exception\InvalidArgumentException("The extract flag specified is not valid");
308 * Check if the queue is empty
312 public function isEmpty()
314 return empty($this->values);
318 * Does the queue contain the given datum?
320 * @param mixed $datum
323 public function contains($datum)
325 foreach ($this->values as $values) {
326 if (in_array($datum, $values)) {
334 * Does the queue have an item with the given priority?
336 * @param int $priority
339 public function hasPriority($priority)
341 return isset($this->values[$priority]);