Chris@0: <?php
Chris@0: /**
Chris@0:  * Zend Framework (http://framework.zend.com/)
Chris@0:  *
Chris@0:  * @link      http://github.com/zendframework/zf2 for the canonical source repository
Chris@0:  * @copyright Copyright (c) 2005-2015 Zend Technologies USA Inc. (http://www.zend.com)
Chris@0:  * @license   http://framework.zend.com/license/new-bsd New BSD License
Chris@0:  */
Chris@0: 
Chris@0: namespace Zend\Stdlib;
Chris@0: 
Chris@0: use Iterator;
Chris@0: use Countable;
Chris@0: use Serializable;
Chris@0: use SplPriorityQueue as PhpSplPriorityQueue;
Chris@0: 
Chris@0: /**
Chris@0:  * This is an efficient implementation of an integer priority queue in PHP
Chris@0:  *
Chris@0:  * This class acts like a queue with insert() and extract(), removing the
Chris@0:  * elements from the queue and it also acts like an Iterator without removing
Chris@0:  * the elements. This behaviour can be used in mixed scenarios with high
Chris@0:  * performance boost.
Chris@0:  */
Chris@0: class FastPriorityQueue implements Iterator, Countable, Serializable
Chris@0: {
Chris@0:     const EXTR_DATA     = PhpSplPriorityQueue::EXTR_DATA;
Chris@0:     const EXTR_PRIORITY = PhpSplPriorityQueue::EXTR_PRIORITY;
Chris@0:     const EXTR_BOTH     = PhpSplPriorityQueue::EXTR_BOTH;
Chris@0: 
Chris@0:     /**
Chris@0:      * @var integer
Chris@0:      */
Chris@0:     protected $extractFlag = self::EXTR_DATA;
Chris@0: 
Chris@0:     /**
Chris@0:      * Elements of the queue, divided by priorities
Chris@0:      *
Chris@0:      * @var array
Chris@0:      */
Chris@0:     protected $values = [];
Chris@0: 
Chris@0:     /**
Chris@0:      * Array of priorities
Chris@0:      *
Chris@0:      * @var array
Chris@0:      */
Chris@0:     protected $priorities = [];
Chris@0: 
Chris@0:     /**
Chris@0:      * Array of priorities used for the iteration
Chris@0:      *
Chris@0:      * @var array
Chris@0:      */
Chris@0:     protected $subPriorities = [];
Chris@0: 
Chris@0:     /**
Chris@0:      * Max priority
Chris@0:      *
Chris@13:      * @var integer|null
Chris@0:      */
Chris@13:     protected $maxPriority = null;
Chris@0: 
Chris@0:     /**
Chris@0:      * Total number of elements in the queue
Chris@0:      *
Chris@0:      * @var integer
Chris@0:      */
Chris@0:     protected $count = 0;
Chris@0: 
Chris@0:     /**
Chris@0:      * Index of the current element in the queue
Chris@0:      *
Chris@0:      * @var integer
Chris@0:      */
Chris@0:     protected $index = 0;
Chris@0: 
Chris@0:     /**
Chris@0:      * Sub index of the current element in the same priority level
Chris@0:      *
Chris@0:      * @var integer
Chris@0:      */
Chris@0:     protected $subIndex = 0;
Chris@0: 
Chris@0:     /**
Chris@0:      * Insert an element in the queue with a specified priority
Chris@0:      *
Chris@0:      * @param mixed $value
Chris@13:      * @param integer $priority
Chris@0:      */
Chris@0:     public function insert($value, $priority)
Chris@0:     {
Chris@0:         if (! is_int($priority)) {
Chris@0:             throw new Exception\InvalidArgumentException('The priority must be an integer');
Chris@0:         }
Chris@0:         $this->values[$priority][] = $value;
Chris@0:         if (! isset($this->priorities[$priority])) {
Chris@0:             $this->priorities[$priority] = $priority;
Chris@13:             $this->maxPriority           = $this->maxPriority === null ? $priority : max($priority, $this->maxPriority);
Chris@0:         }
Chris@0:         ++$this->count;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Extract an element in the queue according to the priority and the
Chris@0:      * order of insertion
Chris@0:      *
Chris@0:      * @return mixed
Chris@0:      */
Chris@0:     public function extract()
Chris@0:     {
Chris@0:         if (! $this->valid()) {
Chris@0:             return false;
Chris@0:         }
Chris@0:         $value = $this->current();
Chris@0:         $this->nextAndRemove();
Chris@0:         return $value;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Remove an item from the queue
Chris@0:      *
Chris@0:      * This is different than {@link extract()}; its purpose is to dequeue an
Chris@0:      * item.
Chris@0:      *
Chris@0:      * Note: this removes the first item matching the provided item found. If
Chris@0:      * the same item has been added multiple times, it will not remove other
Chris@0:      * instances.
Chris@0:      *
Chris@0:      * @param  mixed $datum
Chris@0:      * @return bool False if the item was not found, true otherwise.
Chris@0:      */
Chris@0:     public function remove($datum)
Chris@0:     {
Chris@13:         $currentIndex    = $this->index;
Chris@13:         $currentSubIndex = $this->subIndex;
Chris@13:         $currentPriority = $this->maxPriority;
Chris@13: 
Chris@0:         $this->rewind();
Chris@0:         while ($this->valid()) {
Chris@0:             if (current($this->values[$this->maxPriority]) === $datum) {
Chris@0:                 $index = key($this->values[$this->maxPriority]);
Chris@0:                 unset($this->values[$this->maxPriority][$index]);
Chris@13: 
Chris@13:                 // The `next()` method advances the internal array pointer, so we need to use the `reset()` function,
Chris@13:                 // otherwise we would lose all elements before the place the pointer points.
Chris@13:                 reset($this->values[$this->maxPriority]);
Chris@13: 
Chris@13:                 $this->index    = $currentIndex;
Chris@13:                 $this->subIndex = $currentSubIndex;
Chris@13: 
Chris@13:                 // If the array is empty we need to destroy the unnecessary priority,
Chris@13:                 // otherwise we would end up with an incorrect value of `$this->count`
Chris@13:                 // {@see \Zend\Stdlib\FastPriorityQueue::nextAndRemove()}.
Chris@13:                 if (empty($this->values[$this->maxPriority])) {
Chris@13:                     unset($this->values[$this->maxPriority]);
Chris@13:                     unset($this->priorities[$this->maxPriority]);
Chris@13:                     if ($this->maxPriority === $currentPriority) {
Chris@13:                         $this->subIndex = 0;
Chris@13:                     }
Chris@13:                 }
Chris@13: 
Chris@13:                 $this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
Chris@0:                 --$this->count;
Chris@0:                 return true;
Chris@0:             }
Chris@0:             $this->next();
Chris@0:         }
Chris@0:         return false;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Get the total number of elements in the queue
Chris@0:      *
Chris@0:      * @return integer
Chris@0:      */
Chris@0:     public function count()
Chris@0:     {
Chris@0:         return $this->count;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Get the current element in the queue
Chris@0:      *
Chris@0:      * @return mixed
Chris@0:      */
Chris@0:     public function current()
Chris@0:     {
Chris@0:         switch ($this->extractFlag) {
Chris@0:             case self::EXTR_DATA:
Chris@0:                 return current($this->values[$this->maxPriority]);
Chris@0:             case self::EXTR_PRIORITY:
Chris@0:                 return $this->maxPriority;
Chris@0:             case self::EXTR_BOTH:
Chris@0:                 return [
Chris@0:                     'data'     => current($this->values[$this->maxPriority]),
Chris@0:                     'priority' => $this->maxPriority
Chris@0:                 ];
Chris@0:         }
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Get the index of the current element in the queue
Chris@0:      *
Chris@0:      * @return integer
Chris@0:      */
Chris@0:     public function key()
Chris@0:     {
Chris@0:         return $this->index;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Set the iterator pointer to the next element in the queue
Chris@0:      * removing the previous element
Chris@0:      */
Chris@0:     protected function nextAndRemove()
Chris@0:     {
Chris@13:         $key = key($this->values[$this->maxPriority]);
Chris@13: 
Chris@0:         if (false === next($this->values[$this->maxPriority])) {
Chris@0:             unset($this->priorities[$this->maxPriority]);
Chris@0:             unset($this->values[$this->maxPriority]);
Chris@13:             $this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
Chris@0:             $this->subIndex    = -1;
Chris@13:         } else {
Chris@13:             unset($this->values[$this->maxPriority][$key]);
Chris@0:         }
Chris@0:         ++$this->index;
Chris@0:         ++$this->subIndex;
Chris@0:         --$this->count;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Set the iterator pointer to the next element in the queue
Chris@0:      * without removing the previous element
Chris@0:      */
Chris@0:     public function next()
Chris@0:     {
Chris@0:         if (false === next($this->values[$this->maxPriority])) {
Chris@0:             unset($this->subPriorities[$this->maxPriority]);
Chris@0:             reset($this->values[$this->maxPriority]);
Chris@13:             $this->maxPriority = empty($this->subPriorities) ? null : max($this->subPriorities);
Chris@0:             $this->subIndex    = -1;
Chris@0:         }
Chris@0:         ++$this->index;
Chris@0:         ++$this->subIndex;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Check if the current iterator is valid
Chris@0:      *
Chris@0:      * @return boolean
Chris@0:      */
Chris@0:     public function valid()
Chris@0:     {
Chris@0:         return isset($this->values[$this->maxPriority]);
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Rewind the current iterator
Chris@0:      */
Chris@0:     public function rewind()
Chris@0:     {
Chris@0:         $this->subPriorities = $this->priorities;
Chris@0:         $this->maxPriority   = empty($this->priorities) ? 0 : max($this->priorities);
Chris@0:         $this->index         = 0;
Chris@0:         $this->subIndex      = 0;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Serialize to an array
Chris@0:      *
Chris@0:      * Array will be priority => data pairs
Chris@0:      *
Chris@0:      * @return array
Chris@0:      */
Chris@0:     public function toArray()
Chris@0:     {
Chris@0:         $array = [];
Chris@0:         foreach (clone $this as $item) {
Chris@0:             $array[] = $item;
Chris@0:         }
Chris@0:         return $array;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Serialize
Chris@0:      *
Chris@0:      * @return string
Chris@0:      */
Chris@0:     public function serialize()
Chris@0:     {
Chris@0:         $clone = clone $this;
Chris@0:         $clone->setExtractFlags(self::EXTR_BOTH);
Chris@0: 
Chris@0:         $data = [];
Chris@0:         foreach ($clone as $item) {
Chris@0:             $data[] = $item;
Chris@0:         }
Chris@0: 
Chris@0:         return serialize($data);
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Deserialize
Chris@0:      *
Chris@0:      * @param  string $data
Chris@0:      * @return void
Chris@0:      */
Chris@0:     public function unserialize($data)
Chris@0:     {
Chris@0:         foreach (unserialize($data) as $item) {
Chris@0:             $this->insert($item['data'], $item['priority']);
Chris@0:         }
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Set the extract flag
Chris@0:      *
Chris@0:      * @param integer $flag
Chris@0:      */
Chris@0:     public function setExtractFlags($flag)
Chris@0:     {
Chris@0:         switch ($flag) {
Chris@0:             case self::EXTR_DATA:
Chris@0:             case self::EXTR_PRIORITY:
Chris@0:             case self::EXTR_BOTH:
Chris@0:                 $this->extractFlag = $flag;
Chris@0:                 break;
Chris@0:             default:
Chris@0:                 throw new Exception\InvalidArgumentException("The extract flag specified is not valid");
Chris@0:         }
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Check if the queue is empty
Chris@0:      *
Chris@0:      * @return boolean
Chris@0:      */
Chris@0:     public function isEmpty()
Chris@0:     {
Chris@0:         return empty($this->values);
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Does the queue contain the given datum?
Chris@0:      *
Chris@0:      * @param  mixed $datum
Chris@0:      * @return bool
Chris@0:      */
Chris@0:     public function contains($datum)
Chris@0:     {
Chris@0:         foreach ($this->values as $values) {
Chris@0:             if (in_array($datum, $values)) {
Chris@0:                 return true;
Chris@0:             }
Chris@0:         }
Chris@0:         return false;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Does the queue have an item with the given priority?
Chris@0:      *
Chris@0:      * @param  int $priority
Chris@0:      * @return bool
Chris@0:      */
Chris@0:     public function hasPriority($priority)
Chris@0:     {
Chris@0:         return isset($this->values[$priority]);
Chris@0:     }
Chris@0: }