aleph1.co.uk Git - yaffs-website/blob - vendor/zendframework/zend-stdlib/src/PriorityQueue.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 Countable;
  13 use IteratorAggregate;
  14 use Serializable;
  15
  16 /**
  17  * Re-usable, serializable priority queue implementation
  18  *
  19  * SplPriorityQueue acts as a heap; on iteration, each item is removed from the
  20  * queue. If you wish to re-use such a queue, you need to clone it first. This
  21  * makes for some interesting issues if you wish to delete items from the queue,
  22  * or, as already stated, iterate over it multiple times.
  23  *
  24  * This class aggregates items for the queue itself, but also composes an
  25  * "inner" iterator in the form of an SplPriorityQueue object for performing
  26  * the actual iteration.
  27  */
  28 class PriorityQueue implements Countable, IteratorAggregate, Serializable
  29 {
  30     const EXTR_DATA     = 0x00000001;
  31     const EXTR_PRIORITY = 0x00000002;
  32     const EXTR_BOTH     = 0x00000003;
  33
  34     /**
  35      * Inner queue class to use for iteration
  36      * @var string
  37      */
  38     protected $queueClass = 'Zend\Stdlib\SplPriorityQueue';
  39
  40     /**
  41      * Actual items aggregated in the priority queue. Each item is an array
  42      * with keys "data" and "priority".
  43      * @var array
  44      */
  45     protected $items      = [];
  46
  47     /**
  48      * Inner queue object
  49      * @var SplPriorityQueue
  50      */
  51     protected $queue;
  52
  53     /**
  54      * Insert an item into the queue
  55      *
  56      * Priority defaults to 1 (low priority) if none provided.
  57      *
  58      * @param  mixed $data
  59      * @param  int $priority
  60      * @return PriorityQueue
  61      */
  62     public function insert($data, $priority = 1)
  63     {
  64         $priority = (int) $priority;
  65         $this->items[] = [
  66             'data'     => $data,
  67             'priority' => $priority,
  68         ];
  69         $this->getQueue()->insert($data, $priority);
  70         return $this;
  71     }
  72
  73     /**
  74      * Remove an item from the queue
  75      *
  76      * This is different than {@link extract()}; its purpose is to dequeue an
  77      * item.
  78      *
  79      * This operation is potentially expensive, as it requires
  80      * re-initialization and re-population of the inner queue.
  81      *
  82      * Note: this removes the first item matching the provided item found. If
  83      * the same item has been added multiple times, it will not remove other
  84      * instances.
  85      *
  86      * @param  mixed $datum
  87      * @return bool False if the item was not found, true otherwise.
  88      */
  89     public function remove($datum)
  90     {
  91         $found = false;
  92         foreach ($this->items as $key => $item) {
  93             if ($item['data'] === $datum) {
  94                 $found = true;
  95                 break;
  96             }
  97         }
  98         if ($found) {
  99             unset($this->items[$key]);
 100             $this->queue = null;
 101
 102             if (! $this->isEmpty()) {
 103                 $queue = $this->getQueue();
 104                 foreach ($this->items as $item) {
 105                     $queue->insert($item['data'], $item['priority']);
 106                 }
 107             }
 108             return true;
 109         }
 110         return false;
 111     }
 112
 113     /**
 114      * Is the queue empty?
 115      *
 116      * @return bool
 117      */
 118     public function isEmpty()
 119     {
 120         return (0 === $this->count());
 121     }
 122
 123     /**
 124      * How many items are in the queue?
 125      *
 126      * @return int
 127      */
 128     public function count()
 129     {
 130         return count($this->items);
 131     }
 132
 133     /**
 134      * Peek at the top node in the queue, based on priority.
 135      *
 136      * @return mixed
 137      */
 138     public function top()
 139     {
 140         return $this->getIterator()->top();
 141     }
 142
 143     /**
 144      * Extract a node from the inner queue and sift up
 145      *
 146      * @return mixed
 147      */
 148     public function extract()
 149     {
 150         return $this->getQueue()->extract();
 151     }
 152
 153     /**
 154      * Retrieve the inner iterator
 155      *
 156      * SplPriorityQueue acts as a heap, which typically implies that as items
 157      * are iterated, they are also removed. This does not work for situations
 158      * where the queue may be iterated multiple times. As such, this class
 159      * aggregates the values, and also injects an SplPriorityQueue. This method
 160      * retrieves the inner queue object, and clones it for purposes of
 161      * iteration.
 162      *
 163      * @return SplPriorityQueue
 164      */
 165     public function getIterator()
 166     {
 167         $queue = $this->getQueue();
 168         return clone $queue;
 169     }
 170
 171     /**
 172      * Serialize the data structure
 173      *
 174      * @return string
 175      */
 176     public function serialize()
 177     {
 178         return serialize($this->items);
 179     }
 180
 181     /**
 182      * Unserialize a string into a PriorityQueue object
 183      *
 184      * Serialization format is compatible with {@link Zend\Stdlib\SplPriorityQueue}
 185      *
 186      * @param  string $data
 187      * @return void
 188      */
 189     public function unserialize($data)
 190     {
 191         foreach (unserialize($data) as $item) {
 192             $this->insert($item['data'], $item['priority']);
 193         }
 194     }
 195
 196     /**
 197      * Serialize to an array
 198      *
 199      * By default, returns only the item data, and in the order registered (not
 200      * sorted). You may provide one of the EXTR_* flags as an argument, allowing
 201      * the ability to return priorities or both data and priority.
 202      *
 203      * @param  int $flag
 204      * @return array
 205      */
 206     public function toArray($flag = self::EXTR_DATA)
 207     {
 208         switch ($flag) {
 209             case self::EXTR_BOTH:
 210                 return $this->items;
 211             case self::EXTR_PRIORITY:
 212                 return array_map(function ($item) {
 213                     return $item['priority'];
 214                 }, $this->items);
 215             case self::EXTR_DATA:
 216             default:
 217                 return array_map(function ($item) {
 218                     return $item['data'];
 219                 }, $this->items);
 220         }
 221     }
 222
 223     /**
 224      * Specify the internal queue class
 225      *
 226      * Please see {@link getIterator()} for details on the necessity of an
 227      * internal queue class. The class provided should extend SplPriorityQueue.
 228      *
 229      * @param  string $class
 230      * @return PriorityQueue
 231      */
 232     public function setInternalQueueClass($class)
 233     {
 234         $this->queueClass = (string) $class;
 235         return $this;
 236     }
 237
 238     /**
 239      * Does the queue contain the given datum?
 240      *
 241      * @param  mixed $datum
 242      * @return bool
 243      */
 244     public function contains($datum)
 245     {
 246         foreach ($this->items as $item) {
 247             if ($item['data'] === $datum) {
 248                 return true;
 249             }
 250         }
 251         return false;
 252     }
 253
 254     /**
 255      * Does the queue have an item with the given priority?
 256      *
 257      * @param  int $priority
 258      * @return bool
 259      */
 260     public function hasPriority($priority)
 261     {
 262         foreach ($this->items as $item) {
 263             if ($item['priority'] === $priority) {
 264                 return true;
 265             }
 266         }
 267         return false;
 268     }
 269
 270     /**
 271      * Get the inner priority queue instance
 272      *
 273      * @throws Exception\DomainException
 274      * @return SplPriorityQueue
 275      */
 276     protected function getQueue()
 277     {
 278         if (null === $this->queue) {
 279             $this->queue = new $this->queueClass();
 280             if (! $this->queue instanceof \SplPriorityQueue) {
 281                 throw new Exception\DomainException(sprintf(
 282                     'PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
 283                     get_class($this->queue)
 284                 ));
 285             }
 286         }
 287         return $this->queue;
 288     }
 289
 290     /**
 291      * Add support for deep cloning
 292      *
 293      * @return void
 294      */
 295     public function __clone()
 296     {
 297         if (null !== $this->queue) {
 298             $this->queue = clone $this->queue;
 299         }
 300     }
 301 }