class PriorityQueue in Zircon Profile 8

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

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

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

Name	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