www.aleph1.co.uk Git - yaffs-website/blob - vendor/zendframework/zend-stdlib/src/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|null
  61      */
  62     protected $maxPriority = null;
  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
  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           = $this->maxPriority === null ? $priority : 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         $currentIndex    = $this->index;
 136         $currentSubIndex = $this->subIndex;
 137         $currentPriority = $this->maxPriority;
 138
 139         $this->rewind();
 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]);
 144
 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]);
 148
 149                 $this->index    = $currentIndex;
 150                 $this->subIndex = $currentSubIndex;
 151
 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) {
 159                         $this->subIndex = 0;
 160                     }
 161                 }
 162
 163                 $this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
 164                 --$this->count;
 165                 return true;
 166             }
 167             $this->next();
 168         }
 169         return false;
 170     }
 171
 172     /**
 173      * Get the total number of elements in the queue
 174      *
 175      * @return integer
 176      */
 177     public function count()
 178     {
 179         return $this->count;
 180     }
 181
 182     /**
 183      * Get the current element in the queue
 184      *
 185      * @return mixed
 186      */
 187     public function current()
 188     {
 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:
 195                 return [
 196                     'data'     => current($this->values[$this->maxPriority]),
 197                     'priority' => $this->maxPriority
 198                 ];
 199         }
 200     }
 201
 202     /**
 203      * Get the index of the current element in the queue
 204      *
 205      * @return integer
 206      */
 207     public function key()
 208     {
 209         return $this->index;
 210     }
 211
 212     /**
 213      * Set the iterator pointer to the next element in the queue
 214      * removing the previous element
 215      */
 216     protected function nextAndRemove()
 217     {
 218         $key = key($this->values[$this->maxPriority]);
 219
 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;
 225         } else {
 226             unset($this->values[$this->maxPriority][$key]);
 227         }
 228         ++$this->index;
 229         ++$this->subIndex;
 230         --$this->count;
 231     }
 232
 233     /**
 234      * Set the iterator pointer to the next element in the queue
 235      * without removing the previous element
 236      */
 237     public function next()
 238     {
 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;
 244         }
 245         ++$this->index;
 246         ++$this->subIndex;
 247     }
 248
 249     /**
 250      * Check if the current iterator is valid
 251      *
 252      * @return boolean
 253      */
 254     public function valid()
 255     {
 256         return isset($this->values[$this->maxPriority]);
 257     }
 258
 259     /**
 260      * Rewind the current iterator
 261      */
 262     public function rewind()
 263     {
 264         $this->subPriorities = $this->priorities;
 265         $this->maxPriority   = empty($this->priorities) ? 0 : max($this->priorities);
 266         $this->index         = 0;
 267         $this->subIndex      = 0;
 268     }
 269
 270     /**
 271      * Serialize to an array
 272      *
 273      * Array will be priority => data pairs
 274      *
 275      * @return array
 276      */
 277     public function toArray()
 278     {
 279         $array = [];
 280         foreach (clone $this as $item) {
 281             $array[] = $item;
 282         }
 283         return $array;
 284     }
 285
 286     /**
 287      * Serialize
 288      *
 289      * @return string
 290      */
 291     public function serialize()
 292     {
 293         $clone = clone $this;
 294         $clone->setExtractFlags(self::EXTR_BOTH);
 295
 296         $data = [];
 297         foreach ($clone as $item) {
 298             $data[] = $item;
 299         }
 300
 301         return serialize($data);
 302     }
 303
 304     /**
 305      * Deserialize
 306      *
 307      * @param  string $data
 308      * @return void
 309      */
 310     public function unserialize($data)
 311     {
 312         foreach (unserialize($data) as $item) {
 313             $this->insert($item['data'], $item['priority']);
 314         }
 315     }
 316
 317     /**
 318      * Set the extract flag
 319      *
 320      * @param integer $flag
 321      */
 322     public function setExtractFlags($flag)
 323     {
 324         switch ($flag) {
 325             case self::EXTR_DATA:
 326             case self::EXTR_PRIORITY:
 327             case self::EXTR_BOTH:
 328                 $this->extractFlag = $flag;
 329                 break;
 330             default:
 331                 throw new Exception\InvalidArgumentException("The extract flag specified is not valid");
 332         }
 333     }
 334
 335     /**
 336      * Check if the queue is empty
 337      *
 338      * @return boolean
 339      */
 340     public function isEmpty()
 341     {
 342         return empty($this->values);
 343     }
 344
 345     /**
 346      * Does the queue contain the given datum?
 347      *
 348      * @param  mixed $datum
 349      * @return bool
 350      */
 351     public function contains($datum)
 352     {
 353         foreach ($this->values as $values) {
 354             if (in_array($datum, $values)) {
 355                 return true;
 356             }
 357         }
 358         return false;
 359     }
 360
 361     /**
 362      * Does the queue have an item with the given priority?
 363      *
 364      * @param  int $priority
 365      * @return bool
 366      */
 367     public function hasPriority($priority)
 368     {
 369         return isset($this->values[$priority]);
 370     }
 371 }