annotate vendor/zendframework/zend-stdlib/src/FastPriorityQueue.php @ 19:fa3358dc1485 tip

Add ndrum files
author Chris Cannam
date Wed, 28 Aug 2019 13:14:47 +0100
parents 5fb285c0d0e3
children
rev   line source
Chris@0 1 <?php
Chris@0 2 /**
Chris@0 3 * Zend Framework (http://framework.zend.com/)
Chris@0 4 *
Chris@0 5 * @link http://github.com/zendframework/zf2 for the canonical source repository
Chris@0 6 * @copyright Copyright (c) 2005-2015 Zend Technologies USA Inc. (http://www.zend.com)
Chris@0 7 * @license http://framework.zend.com/license/new-bsd New BSD License
Chris@0 8 */
Chris@0 9
Chris@0 10 namespace Zend\Stdlib;
Chris@0 11
Chris@0 12 use Iterator;
Chris@0 13 use Countable;
Chris@0 14 use Serializable;
Chris@0 15 use SplPriorityQueue as PhpSplPriorityQueue;
Chris@0 16
Chris@0 17 /**
Chris@0 18 * This is an efficient implementation of an integer priority queue in PHP
Chris@0 19 *
Chris@0 20 * This class acts like a queue with insert() and extract(), removing the
Chris@0 21 * elements from the queue and it also acts like an Iterator without removing
Chris@0 22 * the elements. This behaviour can be used in mixed scenarios with high
Chris@0 23 * performance boost.
Chris@0 24 */
Chris@0 25 class FastPriorityQueue implements Iterator, Countable, Serializable
Chris@0 26 {
Chris@0 27 const EXTR_DATA = PhpSplPriorityQueue::EXTR_DATA;
Chris@0 28 const EXTR_PRIORITY = PhpSplPriorityQueue::EXTR_PRIORITY;
Chris@0 29 const EXTR_BOTH = PhpSplPriorityQueue::EXTR_BOTH;
Chris@0 30
Chris@0 31 /**
Chris@0 32 * @var integer
Chris@0 33 */
Chris@0 34 protected $extractFlag = self::EXTR_DATA;
Chris@0 35
Chris@0 36 /**
Chris@0 37 * Elements of the queue, divided by priorities
Chris@0 38 *
Chris@0 39 * @var array
Chris@0 40 */
Chris@0 41 protected $values = [];
Chris@0 42
Chris@0 43 /**
Chris@0 44 * Array of priorities
Chris@0 45 *
Chris@0 46 * @var array
Chris@0 47 */
Chris@0 48 protected $priorities = [];
Chris@0 49
Chris@0 50 /**
Chris@0 51 * Array of priorities used for the iteration
Chris@0 52 *
Chris@0 53 * @var array
Chris@0 54 */
Chris@0 55 protected $subPriorities = [];
Chris@0 56
Chris@0 57 /**
Chris@0 58 * Max priority
Chris@0 59 *
Chris@13 60 * @var integer|null
Chris@0 61 */
Chris@13 62 protected $maxPriority = null;
Chris@0 63
Chris@0 64 /**
Chris@0 65 * Total number of elements in the queue
Chris@0 66 *
Chris@0 67 * @var integer
Chris@0 68 */
Chris@0 69 protected $count = 0;
Chris@0 70
Chris@0 71 /**
Chris@0 72 * Index of the current element in the queue
Chris@0 73 *
Chris@0 74 * @var integer
Chris@0 75 */
Chris@0 76 protected $index = 0;
Chris@0 77
Chris@0 78 /**
Chris@0 79 * Sub index of the current element in the same priority level
Chris@0 80 *
Chris@0 81 * @var integer
Chris@0 82 */
Chris@0 83 protected $subIndex = 0;
Chris@0 84
Chris@0 85 /**
Chris@0 86 * Insert an element in the queue with a specified priority
Chris@0 87 *
Chris@0 88 * @param mixed $value
Chris@13 89 * @param integer $priority
Chris@0 90 */
Chris@0 91 public function insert($value, $priority)
Chris@0 92 {
Chris@0 93 if (! is_int($priority)) {
Chris@0 94 throw new Exception\InvalidArgumentException('The priority must be an integer');
Chris@0 95 }
Chris@0 96 $this->values[$priority][] = $value;
Chris@0 97 if (! isset($this->priorities[$priority])) {
Chris@0 98 $this->priorities[$priority] = $priority;
Chris@13 99 $this->maxPriority = $this->maxPriority === null ? $priority : max($priority, $this->maxPriority);
Chris@0 100 }
Chris@0 101 ++$this->count;
Chris@0 102 }
Chris@0 103
Chris@0 104 /**
Chris@0 105 * Extract an element in the queue according to the priority and the
Chris@0 106 * order of insertion
Chris@0 107 *
Chris@0 108 * @return mixed
Chris@0 109 */
Chris@0 110 public function extract()
Chris@0 111 {
Chris@0 112 if (! $this->valid()) {
Chris@0 113 return false;
Chris@0 114 }
Chris@0 115 $value = $this->current();
Chris@0 116 $this->nextAndRemove();
Chris@0 117 return $value;
Chris@0 118 }
Chris@0 119
Chris@0 120 /**
Chris@0 121 * Remove an item from the queue
Chris@0 122 *
Chris@0 123 * This is different than {@link extract()}; its purpose is to dequeue an
Chris@0 124 * item.
Chris@0 125 *
Chris@0 126 * Note: this removes the first item matching the provided item found. If
Chris@0 127 * the same item has been added multiple times, it will not remove other
Chris@0 128 * instances.
Chris@0 129 *
Chris@0 130 * @param mixed $datum
Chris@0 131 * @return bool False if the item was not found, true otherwise.
Chris@0 132 */
Chris@0 133 public function remove($datum)
Chris@0 134 {
Chris@13 135 $currentIndex = $this->index;
Chris@13 136 $currentSubIndex = $this->subIndex;
Chris@13 137 $currentPriority = $this->maxPriority;
Chris@13 138
Chris@0 139 $this->rewind();
Chris@0 140 while ($this->valid()) {
Chris@0 141 if (current($this->values[$this->maxPriority]) === $datum) {
Chris@0 142 $index = key($this->values[$this->maxPriority]);
Chris@0 143 unset($this->values[$this->maxPriority][$index]);
Chris@13 144
Chris@13 145 // The `next()` method advances the internal array pointer, so we need to use the `reset()` function,
Chris@13 146 // otherwise we would lose all elements before the place the pointer points.
Chris@13 147 reset($this->values[$this->maxPriority]);
Chris@13 148
Chris@13 149 $this->index = $currentIndex;
Chris@13 150 $this->subIndex = $currentSubIndex;
Chris@13 151
Chris@13 152 // If the array is empty we need to destroy the unnecessary priority,
Chris@13 153 // otherwise we would end up with an incorrect value of `$this->count`
Chris@13 154 // {@see \Zend\Stdlib\FastPriorityQueue::nextAndRemove()}.
Chris@13 155 if (empty($this->values[$this->maxPriority])) {
Chris@13 156 unset($this->values[$this->maxPriority]);
Chris@13 157 unset($this->priorities[$this->maxPriority]);
Chris@13 158 if ($this->maxPriority === $currentPriority) {
Chris@13 159 $this->subIndex = 0;
Chris@13 160 }
Chris@13 161 }
Chris@13 162
Chris@13 163 $this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
Chris@0 164 --$this->count;
Chris@0 165 return true;
Chris@0 166 }
Chris@0 167 $this->next();
Chris@0 168 }
Chris@0 169 return false;
Chris@0 170 }
Chris@0 171
Chris@0 172 /**
Chris@0 173 * Get the total number of elements in the queue
Chris@0 174 *
Chris@0 175 * @return integer
Chris@0 176 */
Chris@0 177 public function count()
Chris@0 178 {
Chris@0 179 return $this->count;
Chris@0 180 }
Chris@0 181
Chris@0 182 /**
Chris@0 183 * Get the current element in the queue
Chris@0 184 *
Chris@0 185 * @return mixed
Chris@0 186 */
Chris@0 187 public function current()
Chris@0 188 {
Chris@0 189 switch ($this->extractFlag) {
Chris@0 190 case self::EXTR_DATA:
Chris@0 191 return current($this->values[$this->maxPriority]);
Chris@0 192 case self::EXTR_PRIORITY:
Chris@0 193 return $this->maxPriority;
Chris@0 194 case self::EXTR_BOTH:
Chris@0 195 return [
Chris@0 196 'data' => current($this->values[$this->maxPriority]),
Chris@0 197 'priority' => $this->maxPriority
Chris@0 198 ];
Chris@0 199 }
Chris@0 200 }
Chris@0 201
Chris@0 202 /**
Chris@0 203 * Get the index of the current element in the queue
Chris@0 204 *
Chris@0 205 * @return integer
Chris@0 206 */
Chris@0 207 public function key()
Chris@0 208 {
Chris@0 209 return $this->index;
Chris@0 210 }
Chris@0 211
Chris@0 212 /**
Chris@0 213 * Set the iterator pointer to the next element in the queue
Chris@0 214 * removing the previous element
Chris@0 215 */
Chris@0 216 protected function nextAndRemove()
Chris@0 217 {
Chris@13 218 $key = key($this->values[$this->maxPriority]);
Chris@13 219
Chris@0 220 if (false === next($this->values[$this->maxPriority])) {
Chris@0 221 unset($this->priorities[$this->maxPriority]);
Chris@0 222 unset($this->values[$this->maxPriority]);
Chris@13 223 $this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
Chris@0 224 $this->subIndex = -1;
Chris@13 225 } else {
Chris@13 226 unset($this->values[$this->maxPriority][$key]);
Chris@0 227 }
Chris@0 228 ++$this->index;
Chris@0 229 ++$this->subIndex;
Chris@0 230 --$this->count;
Chris@0 231 }
Chris@0 232
Chris@0 233 /**
Chris@0 234 * Set the iterator pointer to the next element in the queue
Chris@0 235 * without removing the previous element
Chris@0 236 */
Chris@0 237 public function next()
Chris@0 238 {
Chris@0 239 if (false === next($this->values[$this->maxPriority])) {
Chris@0 240 unset($this->subPriorities[$this->maxPriority]);
Chris@0 241 reset($this->values[$this->maxPriority]);
Chris@13 242 $this->maxPriority = empty($this->subPriorities) ? null : max($this->subPriorities);
Chris@0 243 $this->subIndex = -1;
Chris@0 244 }
Chris@0 245 ++$this->index;
Chris@0 246 ++$this->subIndex;
Chris@0 247 }
Chris@0 248
Chris@0 249 /**
Chris@0 250 * Check if the current iterator is valid
Chris@0 251 *
Chris@0 252 * @return boolean
Chris@0 253 */
Chris@0 254 public function valid()
Chris@0 255 {
Chris@0 256 return isset($this->values[$this->maxPriority]);
Chris@0 257 }
Chris@0 258
Chris@0 259 /**
Chris@0 260 * Rewind the current iterator
Chris@0 261 */
Chris@0 262 public function rewind()
Chris@0 263 {
Chris@0 264 $this->subPriorities = $this->priorities;
Chris@0 265 $this->maxPriority = empty($this->priorities) ? 0 : max($this->priorities);
Chris@0 266 $this->index = 0;
Chris@0 267 $this->subIndex = 0;
Chris@0 268 }
Chris@0 269
Chris@0 270 /**
Chris@0 271 * Serialize to an array
Chris@0 272 *
Chris@0 273 * Array will be priority => data pairs
Chris@0 274 *
Chris@0 275 * @return array
Chris@0 276 */
Chris@0 277 public function toArray()
Chris@0 278 {
Chris@0 279 $array = [];
Chris@0 280 foreach (clone $this as $item) {
Chris@0 281 $array[] = $item;
Chris@0 282 }
Chris@0 283 return $array;
Chris@0 284 }
Chris@0 285
Chris@0 286 /**
Chris@0 287 * Serialize
Chris@0 288 *
Chris@0 289 * @return string
Chris@0 290 */
Chris@0 291 public function serialize()
Chris@0 292 {
Chris@0 293 $clone = clone $this;
Chris@0 294 $clone->setExtractFlags(self::EXTR_BOTH);
Chris@0 295
Chris@0 296 $data = [];
Chris@0 297 foreach ($clone as $item) {
Chris@0 298 $data[] = $item;
Chris@0 299 }
Chris@0 300
Chris@0 301 return serialize($data);
Chris@0 302 }
Chris@0 303
Chris@0 304 /**
Chris@0 305 * Deserialize
Chris@0 306 *
Chris@0 307 * @param string $data
Chris@0 308 * @return void
Chris@0 309 */
Chris@0 310 public function unserialize($data)
Chris@0 311 {
Chris@0 312 foreach (unserialize($data) as $item) {
Chris@0 313 $this->insert($item['data'], $item['priority']);
Chris@0 314 }
Chris@0 315 }
Chris@0 316
Chris@0 317 /**
Chris@0 318 * Set the extract flag
Chris@0 319 *
Chris@0 320 * @param integer $flag
Chris@0 321 */
Chris@0 322 public function setExtractFlags($flag)
Chris@0 323 {
Chris@0 324 switch ($flag) {
Chris@0 325 case self::EXTR_DATA:
Chris@0 326 case self::EXTR_PRIORITY:
Chris@0 327 case self::EXTR_BOTH:
Chris@0 328 $this->extractFlag = $flag;
Chris@0 329 break;
Chris@0 330 default:
Chris@0 331 throw new Exception\InvalidArgumentException("The extract flag specified is not valid");
Chris@0 332 }
Chris@0 333 }
Chris@0 334
Chris@0 335 /**
Chris@0 336 * Check if the queue is empty
Chris@0 337 *
Chris@0 338 * @return boolean
Chris@0 339 */
Chris@0 340 public function isEmpty()
Chris@0 341 {
Chris@0 342 return empty($this->values);
Chris@0 343 }
Chris@0 344
Chris@0 345 /**
Chris@0 346 * Does the queue contain the given datum?
Chris@0 347 *
Chris@0 348 * @param mixed $datum
Chris@0 349 * @return bool
Chris@0 350 */
Chris@0 351 public function contains($datum)
Chris@0 352 {
Chris@0 353 foreach ($this->values as $values) {
Chris@0 354 if (in_array($datum, $values)) {
Chris@0 355 return true;
Chris@0 356 }
Chris@0 357 }
Chris@0 358 return false;
Chris@0 359 }
Chris@0 360
Chris@0 361 /**
Chris@0 362 * Does the queue have an item with the given priority?
Chris@0 363 *
Chris@0 364 * @param int $priority
Chris@0 365 * @return bool
Chris@0 366 */
Chris@0 367 public function hasPriority($priority)
Chris@0 368 {
Chris@0 369 return isset($this->values[$priority]);
Chris@0 370 }
Chris@0 371 }