--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/web/lib/Zend/Stdlib/PriorityQueue.php Thu Mar 21 19:52:38 2013 +0100
@@ -0,0 +1,319 @@
+<?php
+/**
+ * Zend Framework
+ *
+ * LICENSE
+ *
+ * This source file is subject to the new BSD license that is bundled
+ * with this package in the file LICENSE.txt.
+ * It is also available through the world-wide-web at this URL:
+ * http://framework.zend.com/license/new-bsd
+ * If you did not receive a copy of the license and are unable to
+ * obtain it through the world-wide-web, please send an email
+ * to license@zend.com so we can send you a copy immediately.
+ *
+ * @category Zend
+ * @package Zend_Stdlib
+ * @copyright Copyright (c) 2005-2012 Zend Technologies USA Inc. (http://www.zend.com)
+ * @license http://framework.zend.com/license/new-bsd New BSD License
+ */
+
+require_once 'Zend/Stdlib/SplPriorityQueue.php';
+
+/**
+ * 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.
+ *
+ * @category Zend
+ * @package Zend_Stdlib
+ * @copyright Copyright (c) 2005-2012 Zend Technologies USA Inc. (http://www.zend.com)
+ * @license http://framework.zend.com/license/new-bsd New BSD License
+ */
+class Zend_Stdlib_PriorityQueue implements Countable, IteratorAggregate, Serializable
+{
+ const EXTR_DATA = 0x00000001;
+ const EXTR_PRIORITY = 0x00000002;
+ const EXTR_BOTH = 0x00000003;
+
+ /**
+ * 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 = array();
+
+ /**
+ * 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 Zend_Stdlib_PriorityQueue
+ */
+ public function insert($data, $priority = 1)
+ {
+ $priority = (int) $priority;
+ $this->items[] = array(
+ '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 boolean 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;
+ $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 Zend_Stdlib_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(array($this, 'returnPriority'), $this->items);
+ case self::EXTR_DATA:
+ default:
+ return array_map(array($this, 'returnData'), $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 Zend_Stdlib_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
+ *
+ * @return Zend_Stdlib_SplPriorityQueue
+ */
+ protected function getQueue()
+ {
+ if (null === $this->queue) {
+ $this->queue = new $this->queueClass();
+ if (!$this->queue instanceof SplPriorityQueue) {
+ throw new DomainException(sprintf(
+ 'Zend_Stdlib_PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
+ get_class($this->queue)
+ ));
+ }
+ }
+ return $this->queue;
+ }
+
+ /**
+ * Return priority from an internal item
+ *
+ * Used as a lambda in toArray().
+ *
+ * @param array $item
+ * @return mixed
+ */
+ public function returnPriority($item)
+ {
+ return $item['priority'];
+ }
+
+ /**
+ * Return data from an internal item
+ *
+ * Used as a lambda in toArray().
+ *
+ * @param array $item
+ * @return mixed
+ */
+ public function returnData($item)
+ {
+ return $item['data'];
+ }
+}