[Summary view] [Print] [Text view]

   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      = array();
  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[] = array(
  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  }