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 Countable;
Chris@0: use IteratorAggregate;
Chris@0: use Serializable;
Chris@0: 
Chris@0: /**
Chris@0:  * Re-usable, serializable priority queue implementation
Chris@0:  *
Chris@0:  * SplPriorityQueue acts as a heap; on iteration, each item is removed from the
Chris@0:  * queue. If you wish to re-use such a queue, you need to clone it first. This
Chris@0:  * makes for some interesting issues if you wish to delete items from the queue,
Chris@0:  * or, as already stated, iterate over it multiple times.
Chris@0:  *
Chris@0:  * This class aggregates items for the queue itself, but also composes an
Chris@0:  * "inner" iterator in the form of an SplPriorityQueue object for performing
Chris@0:  * the actual iteration.
Chris@0:  */
Chris@0: class PriorityQueue implements Countable, IteratorAggregate, Serializable
Chris@0: {
Chris@0:     const EXTR_DATA     = 0x00000001;
Chris@0:     const EXTR_PRIORITY = 0x00000002;
Chris@0:     const EXTR_BOTH     = 0x00000003;
Chris@0: 
Chris@0:     /**
Chris@0:      * Inner queue class to use for iteration
Chris@0:      * @var string
Chris@0:      */
Chris@0:     protected $queueClass = 'Zend\Stdlib\SplPriorityQueue';
Chris@0: 
Chris@0:     /**
Chris@0:      * Actual items aggregated in the priority queue. Each item is an array
Chris@0:      * with keys "data" and "priority".
Chris@0:      * @var array
Chris@0:      */
Chris@0:     protected $items      = [];
Chris@0: 
Chris@0:     /**
Chris@0:      * Inner queue object
Chris@0:      * @var SplPriorityQueue
Chris@0:      */
Chris@0:     protected $queue;
Chris@0: 
Chris@0:     /**
Chris@0:      * Insert an item into the queue
Chris@0:      *
Chris@0:      * Priority defaults to 1 (low priority) if none provided.
Chris@0:      *
Chris@0:      * @param  mixed $data
Chris@0:      * @param  int $priority
Chris@0:      * @return PriorityQueue
Chris@0:      */
Chris@0:     public function insert($data, $priority = 1)
Chris@0:     {
Chris@0:         $priority = (int) $priority;
Chris@0:         $this->items[] = [
Chris@0:             'data'     => $data,
Chris@0:             'priority' => $priority,
Chris@0:         ];
Chris@0:         $this->getQueue()->insert($data, $priority);
Chris@0:         return $this;
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:      * This operation is potentially expensive, as it requires
Chris@0:      * re-initialization and re-population of the inner queue.
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@0:         $found = false;
Chris@0:         foreach ($this->items as $key => $item) {
Chris@0:             if ($item['data'] === $datum) {
Chris@0:                 $found = true;
Chris@0:                 break;
Chris@0:             }
Chris@0:         }
Chris@0:         if ($found) {
Chris@0:             unset($this->items[$key]);
Chris@0:             $this->queue = null;
Chris@0: 
Chris@12:             if (! $this->isEmpty()) {
Chris@0:                 $queue = $this->getQueue();
Chris@0:                 foreach ($this->items as $item) {
Chris@0:                     $queue->insert($item['data'], $item['priority']);
Chris@0:                 }
Chris@0:             }
Chris@0:             return true;
Chris@0:         }
Chris@0:         return false;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Is the queue empty?
Chris@0:      *
Chris@0:      * @return bool
Chris@0:      */
Chris@0:     public function isEmpty()
Chris@0:     {
Chris@0:         return (0 === $this->count());
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * How many items are in the queue?
Chris@0:      *
Chris@0:      * @return int
Chris@0:      */
Chris@0:     public function count()
Chris@0:     {
Chris@0:         return count($this->items);
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Peek at the top node in the queue, based on priority.
Chris@0:      *
Chris@0:      * @return mixed
Chris@0:      */
Chris@0:     public function top()
Chris@0:     {
Chris@0:         return $this->getIterator()->top();
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Extract a node from the inner queue and sift up
Chris@0:      *
Chris@0:      * @return mixed
Chris@0:      */
Chris@0:     public function extract()
Chris@0:     {
Chris@0:         return $this->getQueue()->extract();
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Retrieve the inner iterator
Chris@0:      *
Chris@0:      * SplPriorityQueue acts as a heap, which typically implies that as items
Chris@0:      * are iterated, they are also removed. This does not work for situations
Chris@0:      * where the queue may be iterated multiple times. As such, this class
Chris@0:      * aggregates the values, and also injects an SplPriorityQueue. This method
Chris@0:      * retrieves the inner queue object, and clones it for purposes of
Chris@0:      * iteration.
Chris@0:      *
Chris@0:      * @return SplPriorityQueue
Chris@0:      */
Chris@0:     public function getIterator()
Chris@0:     {
Chris@0:         $queue = $this->getQueue();
Chris@0:         return clone $queue;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Serialize the data structure
Chris@0:      *
Chris@0:      * @return string
Chris@0:      */
Chris@0:     public function serialize()
Chris@0:     {
Chris@0:         return serialize($this->items);
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Unserialize a string into a PriorityQueue object
Chris@0:      *
Chris@0:      * Serialization format is compatible with {@link Zend\Stdlib\SplPriorityQueue}
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:      * Serialize to an array
Chris@0:      *
Chris@0:      * By default, returns only the item data, and in the order registered (not
Chris@0:      * sorted). You may provide one of the EXTR_* flags as an argument, allowing
Chris@0:      * the ability to return priorities or both data and priority.
Chris@0:      *
Chris@0:      * @param  int $flag
Chris@0:      * @return array
Chris@0:      */
Chris@0:     public function toArray($flag = self::EXTR_DATA)
Chris@0:     {
Chris@0:         switch ($flag) {
Chris@0:             case self::EXTR_BOTH:
Chris@0:                 return $this->items;
Chris@0:             case self::EXTR_PRIORITY:
Chris@0:                 return array_map(function ($item) {
Chris@0:                     return $item['priority'];
Chris@0:                 }, $this->items);
Chris@0:             case self::EXTR_DATA:
Chris@0:             default:
Chris@0:                 return array_map(function ($item) {
Chris@0:                     return $item['data'];
Chris@0:                 }, $this->items);
Chris@0:         }
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Specify the internal queue class
Chris@0:      *
Chris@0:      * Please see {@link getIterator()} for details on the necessity of an
Chris@0:      * internal queue class. The class provided should extend SplPriorityQueue.
Chris@0:      *
Chris@0:      * @param  string $class
Chris@0:      * @return PriorityQueue
Chris@0:      */
Chris@0:     public function setInternalQueueClass($class)
Chris@0:     {
Chris@0:         $this->queueClass = (string) $class;
Chris@0:         return $this;
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->items as $item) {
Chris@0:             if ($item['data'] === $datum) {
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:         foreach ($this->items as $item) {
Chris@0:             if ($item['priority'] === $priority) {
Chris@0:                 return true;
Chris@0:             }
Chris@0:         }
Chris@0:         return false;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Get the inner priority queue instance
Chris@0:      *
Chris@0:      * @throws Exception\DomainException
Chris@0:      * @return SplPriorityQueue
Chris@0:      */
Chris@0:     protected function getQueue()
Chris@0:     {
Chris@0:         if (null === $this->queue) {
Chris@0:             $this->queue = new $this->queueClass();
Chris@12:             if (! $this->queue instanceof \SplPriorityQueue) {
Chris@0:                 throw new Exception\DomainException(sprintf(
Chris@0:                     'PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
Chris@0:                     get_class($this->queue)
Chris@0:                 ));
Chris@0:             }
Chris@0:         }
Chris@0:         return $this->queue;
Chris@0:     }
Chris@0: 
Chris@0:     /**
Chris@0:      * Add support for deep cloning
Chris@0:      *
Chris@0:      * @return void
Chris@0:      */
Chris@0:     public function __clone()
Chris@0:     {
Chris@0:         if (null !== $this->queue) {
Chris@0:             $this->queue = clone $this->queue;
Chris@0:         }
Chris@0:     }
Chris@0: }