vendor/Zend/Stdlib/FastPriorityQueue.php

   1 <?php
   2 /**
   3  * Zend Framework (http://framework.zend.com/)
   4  *
   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
   8  */
   9
  10 namespace Zend\Stdlib;
  11
  12 use Iterator;
  13 use Countable;
  14 use Serializable;
  15 use SplPriorityQueue as PhpSplPriorityQueue;
  16
  17 /**
  18  * This is an efficient implementation of an integer priority queue in PHP
  19  *
  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
  23  * performance boost.
  24  */
  25 class FastPriorityQueue implements Iterator, Countable, Serializable
  26 {
  27     const EXTR_DATA     = PhpSplPriorityQueue::EXTR_DATA;
  28     const EXTR_PRIORITY = PhpSplPriorityQueue::EXTR_PRIORITY;
  29     const EXTR_BOTH     = PhpSplPriorityQueue::EXTR_BOTH;
  30
  31     /**
  32      * @var integer
  33      */
  34     protected $extractFlag = self::EXTR_DATA;
  35
  36     /**
  37      * Elements of the queue, divided by priorities
  38      *
  39      * @var array
  40      */
  41     protected $values = [];
  42
  43     /**
  44      * Array of priorities
  45      *
  46      * @var array
  47      */
  48     protected $priorities = [];
  49
  50     /**
  51      * Array of priorities used for the iteration
  52      *
  53      * @var array
  54      */
  55     protected $subPriorities = [];
  56
  57     /**
  58      * Max priority
  59      *
  60      * @var integer
  61      */
  62     protected $maxPriority = 0;
  63
  64     /**
  65      * Total number of elements in the queue
  66      *
  67      * @var integer
  68      */
  69     protected $count = 0;
  70
  71     /**
  72      * Index of the current element in the queue
  73      *
  74      * @var integer
  75      */
  76     protected $index = 0;
  77
  78     /**
  79      * Sub index of the current element in the same priority level
  80      *
  81      * @var integer
  82      */
  83     protected $subIndex = 0;
  84
  85     /**
  86      * Insert an element in the queue with a specified priority
  87      *
  88      * @param mixed $value
  89      * @param integer $priority a positive integer
  90      */
  91     public function insert($value, $priority)
  92     {
  93         if (! is_int($priority)) {
  94             throw new Exception\InvalidArgumentException('The priority must be an integer');
  95         }
  96         $this->values[$priority][] = $value;
  97         if (! isset($this->priorities[$priority])) {
  98             $this->priorities[$priority] = $priority;
  99             $this->maxPriority           = max($priority, $this->maxPriority);
 100         }
 101         ++$this->count;
 102     }
 103
 104     /**
 105      * Extract an element in the queue according to the priority and the
 106      * order of insertion
 107      *
 108      * @return mixed
 109      */
 110     public function extract()
 111     {
 112         if (! $this->valid()) {
 113             return false;
 114         }
 115         $value = $this->current();
 116         $this->nextAndRemove();
 117         return $value;
 118     }
 119
 120     /**
 121      * Remove an item from the queue
 122      *
 123      * This is different than {@link extract()}; its purpose is to dequeue an
 124      * item.
 125      *
 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
 128      * instances.
 129      *
 130      * @param  mixed $datum
 131      * @return bool False if the item was not found, true otherwise.
 132      */
 133     public function remove($datum)
 134     {
 135         $this->rewind();
 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]);
 140                 --$this->count;
 141                 return true;
 142             }
 143             $this->next();
 144         }
 145         return false;
 146     }
 147
 148     /**
 149      * Get the total number of elements in the queue
 150      *
 151      * @return integer
 152      */
 153     public function count()
 154     {
 155         return $this->count;
 156     }
 157
 158     /**
 159      * Get the current element in the queue
 160      *
 161      * @return mixed
 162      */
 163     public function current()
 164     {
 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:
 171                 return [
 172                     'data'     => current($this->values[$this->maxPriority]),
 173                     'priority' => $this->maxPriority
 174                 ];
 175         }
 176     }
 177
 178     /**
 179      * Get the index of the current element in the queue
 180      *
 181      * @return integer
 182      */
 183     public function key()
 184     {
 185         return $this->index;
 186     }
 187
 188     /**
 189      * Set the iterator pointer to the next element in the queue
 190      * removing the previous element
 191      */
 192     protected function nextAndRemove()
 193     {
 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;
 199         }
 200         ++$this->index;
 201         ++$this->subIndex;
 202         --$this->count;
 203     }
 204
 205     /**
 206      * Set the iterator pointer to the next element in the queue
 207      * without removing the previous element
 208      */
 209     public function next()
 210     {
 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;
 216         }
 217         ++$this->index;
 218         ++$this->subIndex;
 219     }
 220
 221     /**
 222      * Check if the current iterator is valid
 223      *
 224      * @return boolean
 225      */
 226     public function valid()
 227     {
 228         return isset($this->values[$this->maxPriority]);
 229     }
 230
 231     /**
 232      * Rewind the current iterator
 233      */
 234     public function rewind()
 235     {
 236         $this->subPriorities = $this->priorities;
 237         $this->maxPriority   = empty($this->priorities) ? 0 : max($this->priorities);
 238         $this->index         = 0;
 239         $this->subIndex      = 0;
 240     }
 241
 242     /**
 243      * Serialize to an array
 244      *
 245      * Array will be priority => data pairs
 246      *
 247      * @return array
 248      */
 249     public function toArray()
 250     {
 251         $array = [];
 252         foreach (clone $this as $item) {
 253             $array[] = $item;
 254         }
 255         return $array;
 256     }
 257
 258     /**
 259      * Serialize
 260      *
 261      * @return string
 262      */
 263     public function serialize()
 264     {
 265         $clone = clone $this;
 266         $clone->setExtractFlags(self::EXTR_BOTH);
 267
 268         $data = [];
 269         foreach ($clone as $item) {
 270             $data[] = $item;
 271         }
 272
 273         return serialize($data);
 274     }
 275
 276     /**
 277      * Deserialize
 278      *
 279      * @param  string $data
 280      * @return void
 281      */
 282     public function unserialize($data)
 283     {
 284         foreach (unserialize($data) as $item) {
 285             $this->insert($item['data'], $item['priority']);
 286         }
 287     }
 288
 289     /**
 290      * Set the extract flag
 291      *
 292      * @param integer $flag
 293      */
 294     public function setExtractFlags($flag)
 295     {
 296         switch ($flag) {
 297             case self::EXTR_DATA:
 298             case self::EXTR_PRIORITY:
 299             case self::EXTR_BOTH:
 300                 $this->extractFlag = $flag;
 301                 break;
 302             default:
 303                 throw new Exception\InvalidArgumentException("The extract flag specified is not valid");
 304         }
 305     }
 306
 307     /**
 308      * Check if the queue is empty
 309      *
 310      * @return boolean
 311      */
 312     public function isEmpty()
 313     {
 314         return empty($this->values);
 315     }
 316
 317     /**
 318      * Does the queue contain the given datum?
 319      *
 320      * @param  mixed $datum
 321      * @return bool
 322      */
 323     public function contains($datum)
 324     {
 325         foreach ($this->values as $values) {
 326             if (in_array($datum, $values)) {
 327                 return true;
 328             }
 329         }
 330         return false;
 331     }
 332
 333     /**
 334      * Does the queue have an item with the given priority?
 335      *
 336      * @param  int $priority
 337      * @return bool
 338      */
 339     public function hasPriority($priority)
 340     {
 341         return isset($this->values[$priority]);
 342     }
 343 }