You are here

class PriorityQueue in Zircon Profile 8

Same name and namespace in other branches
  1. 8.0 vendor/zendframework/zend-stdlib/src/PriorityQueue.php \Zend\Stdlib\PriorityQueue

Re-usable, serializable priority queue implementation

SplPriorityQueue acts as a heap; on iteration, each item is removed from the queue. If you wish to re-use such a queue, you need to clone it first. This makes for some interesting issues if you wish to delete items from the queue, or, as already stated, iterate over it multiple times.

This class aggregates items for the queue itself, but also composes an "inner" iterator in the form of an SplPriorityQueue object for performing the actual iteration.

Hierarchy

  • class \Zend\Stdlib\PriorityQueue implements \Countable, \IteratorAggregate, \Serializable

Expanded class hierarchy of PriorityQueue

3 files declare their use of PriorityQueue
ExtractPriorityQueue.php in vendor/zendframework/zend-stdlib/benchmark/ExtractPriorityQueue.php
InsertPriorityQueue.php in vendor/zendframework/zend-stdlib/benchmark/InsertPriorityQueue.php
RemovePriorityQueue.php in vendor/zendframework/zend-stdlib/benchmark/RemovePriorityQueue.php

File

vendor/zendframework/zend-stdlib/src/PriorityQueue.php, line 28

Namespace

Zend\Stdlib
View source
class PriorityQueue implements Countable, IteratorAggregate, Serializable {
  const EXTR_DATA = 0x1;
  const EXTR_PRIORITY = 0x2;
  const EXTR_BOTH = 0x3;

  /**
   * Inner queue class to use for iteration
   * @var string
   */
  protected $queueClass = 'Zend\\Stdlib\\SplPriorityQueue';

  /**
   * Actual items aggregated in the priority queue. Each item is an array
   * with keys "data" and "priority".
   * @var array
   */
  protected $items = [];

  /**
   * Inner queue object
   * @var SplPriorityQueue
   */
  protected $queue;

  /**
   * Insert an item into the queue
   *
   * Priority defaults to 1 (low priority) if none provided.
   *
   * @param  mixed $data
   * @param  int $priority
   * @return PriorityQueue
   */
  public function insert($data, $priority = 1) {
    $priority = (int) $priority;
    $this->items[] = [
      'data' => $data,
      'priority' => $priority,
    ];
    $this
      ->getQueue()
      ->insert($data, $priority);
    return $this;
  }

  /**
   * Remove an item from the queue
   *
   * This is different than {@link extract()}; its purpose is to dequeue an
   * item.
   *
   * This operation is potentially expensive, as it requires
   * re-initialization and re-population of the inner queue.
   *
   * Note: this removes the first item matching the provided item found. If
   * the same item has been added multiple times, it will not remove other
   * instances.
   *
   * @param  mixed $datum
   * @return bool False if the item was not found, true otherwise.
   */
  public function remove($datum) {
    $found = false;
    foreach ($this->items as $key => $item) {
      if ($item['data'] === $datum) {
        $found = true;
        break;
      }
    }
    if ($found) {
      unset($this->items[$key]);
      $this->queue = null;
      if (!$this
        ->isEmpty()) {
        $queue = $this
          ->getQueue();
        foreach ($this->items as $item) {
          $queue
            ->insert($item['data'], $item['priority']);
        }
      }
      return true;
    }
    return false;
  }

  /**
   * Is the queue empty?
   *
   * @return bool
   */
  public function isEmpty() {
    return 0 === $this
      ->count();
  }

  /**
   * How many items are in the queue?
   *
   * @return int
   */
  public function count() {
    return count($this->items);
  }

  /**
   * Peek at the top node in the queue, based on priority.
   *
   * @return mixed
   */
  public function top() {
    return $this
      ->getIterator()
      ->top();
  }

  /**
   * Extract a node from the inner queue and sift up
   *
   * @return mixed
   */
  public function extract() {
    return $this
      ->getQueue()
      ->extract();
  }

  /**
   * Retrieve the inner iterator
   *
   * SplPriorityQueue acts as a heap, which typically implies that as items
   * are iterated, they are also removed. This does not work for situations
   * where the queue may be iterated multiple times. As such, this class
   * aggregates the values, and also injects an SplPriorityQueue. This method
   * retrieves the inner queue object, and clones it for purposes of
   * iteration.
   *
   * @return SplPriorityQueue
   */
  public function getIterator() {
    $queue = $this
      ->getQueue();
    return clone $queue;
  }

  /**
   * Serialize the data structure
   *
   * @return string
   */
  public function serialize() {
    return serialize($this->items);
  }

  /**
   * Unserialize a string into a PriorityQueue object
   *
   * Serialization format is compatible with {@link Zend\Stdlib\SplPriorityQueue}
   *
   * @param  string $data
   * @return void
   */
  public function unserialize($data) {
    foreach (unserialize($data) as $item) {
      $this
        ->insert($item['data'], $item['priority']);
    }
  }

  /**
   * Serialize to an array
   *
   * By default, returns only the item data, and in the order registered (not
   * sorted). You may provide one of the EXTR_* flags as an argument, allowing
   * the ability to return priorities or both data and priority.
   *
   * @param  int $flag
   * @return array
   */
  public function toArray($flag = self::EXTR_DATA) {
    switch ($flag) {
      case self::EXTR_BOTH:
        return $this->items;
      case self::EXTR_PRIORITY:
        return array_map(function ($item) {
          return $item['priority'];
        }, $this->items);
      case self::EXTR_DATA:
      default:
        return array_map(function ($item) {
          return $item['data'];
        }, $this->items);
    }
  }

  /**
   * Specify the internal queue class
   *
   * Please see {@link getIterator()} for details on the necessity of an
   * internal queue class. The class provided should extend SplPriorityQueue.
   *
   * @param  string $class
   * @return PriorityQueue
   */
  public function setInternalQueueClass($class) {
    $this->queueClass = (string) $class;
    return $this;
  }

  /**
   * Does the queue contain the given datum?
   *
   * @param  mixed $datum
   * @return bool
   */
  public function contains($datum) {
    foreach ($this->items as $item) {
      if ($item['data'] === $datum) {
        return true;
      }
    }
    return false;
  }

  /**
   * Does the queue have an item with the given priority?
   *
   * @param  int $priority
   * @return bool
   */
  public function hasPriority($priority) {
    foreach ($this->items as $item) {
      if ($item['priority'] === $priority) {
        return true;
      }
    }
    return false;
  }

  /**
   * Get the inner priority queue instance
   *
   * @throws Exception\DomainException
   * @return SplPriorityQueue
   */
  protected function getQueue() {
    if (null === $this->queue) {
      $this->queue = new $this->queueClass();
      if (!$this->queue instanceof \SplPriorityQueue) {
        throw new Exception\DomainException(sprintf('PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"', get_class($this->queue)));
      }
    }
    return $this->queue;
  }

  /**
   * Add support for deep cloning
   *
   * @return void
   */
  public function __clone() {
    if (null !== $this->queue) {
      $this->queue = clone $this->queue;
    }
  }

}

Members

Namesort descending Modifiers Type Description Overrides
PriorityQueue::$items protected property Actual items aggregated in the priority queue. Each item is an array with keys "data" and "priority".
PriorityQueue::$queue protected property Inner queue object
PriorityQueue::$queueClass protected property Inner queue class to use for iteration
PriorityQueue::contains public function Does the queue contain the given datum?
PriorityQueue::count public function How many items are in the queue?
PriorityQueue::extract public function Extract a node from the inner queue and sift up
PriorityQueue::EXTR_BOTH constant
PriorityQueue::EXTR_DATA constant
PriorityQueue::EXTR_PRIORITY constant
PriorityQueue::getIterator public function Retrieve the inner iterator
PriorityQueue::getQueue protected function Get the inner priority queue instance
PriorityQueue::hasPriority public function Does the queue have an item with the given priority?
PriorityQueue::insert public function Insert an item into the queue
PriorityQueue::isEmpty public function Is the queue empty?
PriorityQueue::remove public function Remove an item from the queue
PriorityQueue::serialize public function Serialize the data structure
PriorityQueue::setInternalQueueClass public function Specify the internal queue class
PriorityQueue::toArray public function Serialize to an array
PriorityQueue::top public function Peek at the top node in the queue, based on priority.
PriorityQueue::unserialize public function Unserialize a string into a PriorityQueue object
PriorityQueue::__clone public function Add support for deep cloning