PriorityQueue.php in Zircon Profile 8.0

Namespace

Zend\Stdlib

File

vendor/zendframework/zend-stdlib/src/PriorityQueue.php

<?php

/**
 * Zend Framework (http://framework.zend.com/)
 *
 * @link      http://github.com/zendframework/zf2 for the canonical source repository
 * @copyright Copyright (c) 2005-2015 Zend Technologies USA Inc. (http://www.zend.com)
 * @license   http://framework.zend.com/license/new-bsd New BSD License
 */
namespace Zend\Stdlib;

use Countable;
use IteratorAggregate;
use Serializable;

/**
 * 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.
 */
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;
    }
  }

}

Classes

Name	Description
PriorityQueue	Re-usable, serializable priority queue implementation