--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/web/lib/Zend/Stdlib/SplPriorityQueue.php Thu Mar 21 19:52:38 2013 +0100
@@ -0,0 +1,499 @@
+<?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
+ */
+
+if (version_compare(PHP_VERSION, '5.3.0', '<')) {
+ /**
+ * SplPriorityQueue
+ *
+ * PHP 5.2.X userland implementation of PHP's SplPriorityQueue
+ */
+ class SplPriorityQueue implements Iterator , Countable
+ {
+ /**
+ * Extract data only
+ */
+ const EXTR_DATA = 0x00000001;
+
+ /**
+ * Extract priority only
+ */
+ const EXTR_PRIORITY = 0x00000002;
+
+ /**
+ * Extract an array of ('data' => $value, 'priority' => $priority)
+ */
+ const EXTR_BOTH = 0x00000003;
+
+ /**
+ * Count of items in the queue
+ * @var int
+ */
+ protected $count = 0;
+
+ /**
+ * Flag indicating what should be returned when iterating or extracting
+ * @var int
+ */
+ protected $extractFlags = self::EXTR_DATA;
+
+ /**
+ * @var bool|array
+ */
+ protected $preparedQueue = false;
+
+ /**
+ * All items in the queue
+ * @var array
+ */
+ protected $queue = array();
+
+ /**
+ * Constructor
+ *
+ * Creates a new, empty queue
+ *
+ * @return void
+ */
+ public function __construct()
+ {
+ }
+
+ /**
+ * Compare two priorities
+ *
+ * Returns positive integer if $priority1 is greater than $priority2, 0
+ * if equal, negative otherwise.
+ *
+ * Unused internally, and only included in order to retain the same
+ * interface as PHP's SplPriorityQueue.
+ *
+ * @param mixed $priority1
+ * @param mixed $priority2
+ * @return int
+ */
+ public function compare($priority1, $priority2)
+ {
+ if ($priority1 > $priority2) {
+ return 1;
+ }
+ if ($priority1 == $priority2) {
+ return 0;
+ }
+
+ return -1;
+ }
+
+ /**
+ * Countable: return number of items composed in the queue
+ *
+ * @return int
+ */
+ public function count()
+ {
+ return $this->count;
+ }
+
+ /**
+ * Iterator: return current item
+ *
+ * @return mixed
+ */
+ public function current()
+ {
+ if (!$this->preparedQueue) {
+ $this->rewind();
+ }
+ if (!$this->count) {
+ throw new OutOfBoundsException('Cannot iterate SplPriorityQueue; no elements present');
+ }
+
+if (!is_array($this->preparedQueue)) {
+ throw new DomainException(sprintf(
+ "Queue was prepared, but is empty?\n PreparedQueue: %s\n Internal Queue: %s\n",
+ var_export($this->preparedQueue, 1),
+ var_export($this->queue, 1)
+ ));
+}
+
+ $return = array_shift($this->preparedQueue);
+ $priority = $return['priority'];
+ $priorityKey = $return['priorityKey'];
+ $key = $return['key'];
+ unset($return['key']);
+ unset($return['priorityKey']);
+ unset($this->queue[$priorityKey][$key]);
+
+ switch ($this->extractFlags) {
+ case self::EXTR_DATA:
+ return $return['data'];
+ case self::EXTR_PRIORITY:
+ return $return['priority'];
+ case self::EXTR_BOTH:
+ default:
+ return $return;
+ };
+ }
+
+ /**
+ * Extract a node from top of the heap and sift up
+ *
+ * Returns either the value, the priority, or both, depending on the extract flag.
+ *
+ * @return mixed;
+ */
+ public function extract()
+ {
+ if (!$this->count) {
+ return null;
+ }
+
+ if (!$this->preparedQueue) {
+ $this->prepareQueue();
+ }
+
+ if (empty($this->preparedQueue)) {
+ return null;
+ }
+
+ $return = array_shift($this->preparedQueue);
+ $priority = $return['priority'];
+ $priorityKey = $return['priorityKey'];
+ $key = $return['key'];
+ unset($return['key']);
+ unset($return['priorityKey']);
+ unset($this->queue[$priorityKey][$key]);
+ $this->count--;
+
+ switch ($this->extractFlags) {
+ case self::EXTR_DATA:
+ return $return['data'];
+ case self::EXTR_PRIORITY:
+ return $return['priority'];
+ case self::EXTR_BOTH:
+ default:
+ return $return;
+ };
+ }
+
+ /**
+ * Insert a value into the heap, at the specified priority
+ *
+ * @param mixed $value
+ * @param mixed $priority
+ * @return void
+ */
+ public function insert($value, $priority)
+ {
+ if (!is_scalar($priority)) {
+ $priority = serialize($priority);
+ }
+ if (!isset($this->queue[$priority])) {
+ $this->queue[$priority] = array();
+ }
+ $this->queue[$priority][] = $value;
+ $this->count++;
+ $this->preparedQueue = false;
+ }
+
+ /**
+ * Is the queue currently empty?
+ *
+ * @return bool
+ */
+ public function isEmpty()
+ {
+ return (0 == $this->count);
+ }
+
+ /**
+ * Iterator: return current key
+ *
+ * @return mixed Usually an int or string
+ */
+ public function key()
+ {
+ return $this->count;
+ }
+
+ /**
+ * Iterator: Move pointer forward
+ *
+ * @return void
+ */
+ public function next()
+ {
+ $this->count--;
+ }
+
+ /**
+ * Recover from corrupted state and allow further actions on the queue
+ *
+ * Unimplemented, and only included in order to retain the same interface as PHP's
+ * SplPriorityQueue.
+ *
+ * @return void
+ */
+ public function recoverFromCorruption()
+ {
+ }
+
+ /**
+ * Iterator: Move pointer to first item
+ *
+ * @return void
+ */
+ public function rewind()
+ {
+ if (!$this->preparedQueue) {
+ $this->prepareQueue();
+ }
+ }
+
+ /**
+ * Set the extract flags
+ *
+ * Defines what is extracted by SplPriorityQueue::current(),
+ * SplPriorityQueue::top() and SplPriorityQueue::extract().
+ *
+ * - SplPriorityQueue::EXTR_DATA (0x00000001): Extract the data
+ * - SplPriorityQueue::EXTR_PRIORITY (0x00000002): Extract the priority
+ * - SplPriorityQueue::EXTR_BOTH (0x00000003): Extract an array containing both
+ *
+ * The default mode is SplPriorityQueue::EXTR_DATA.
+ *
+ * @param int $flags
+ * @return void
+ */
+ public function setExtractFlags($flags)
+ {
+ $expected = array(
+ self::EXTR_DATA => true,
+ self::EXTR_PRIORITY => true,
+ self::EXTR_BOTH => true,
+ );
+ if (!isset($expected[$flags])) {
+ throw new InvalidArgumentException(sprintf('Expected an EXTR_* flag; received %s', $flags));
+ }
+ $this->extractFlags = $flags;
+ }
+
+ /**
+ * Return the value or priority (or both) of the top node, depending on
+ * the extract flag
+ *
+ * @return mixed
+ */
+ public function top()
+ {
+ $this->sort();
+ $keys = array_keys($this->queue);
+ $key = array_shift($keys);
+ if (preg_match('/^(a|O):/', $key)) {
+ $key = unserialize($key);
+ }
+
+ if ($this->extractFlags == self::EXTR_PRIORITY) {
+ return $key;
+ }
+
+ if ($this->extractFlags == self::EXTR_DATA) {
+ return $this->queue[$key][0];
+ }
+
+ return array(
+ 'data' => $this->queue[$key][0],
+ 'priority' => $key,
+ );
+ }
+
+ /**
+ * Iterator: is the current position valid for the queue
+ *
+ * @return bool
+ */
+ public function valid()
+ {
+ return (bool) $this->count;
+ }
+
+ /**
+ * Sort the queue
+ *
+ * @return void
+ */
+ protected function sort()
+ {
+ krsort($this->queue);
+ }
+
+ /**
+ * Prepare the queue for iteration and/or extraction
+ *
+ * @return void
+ */
+ protected function prepareQueue()
+ {
+ $this->sort();
+ $count = $this->count;
+ $queue = array();
+ foreach ($this->queue as $priority => $values) {
+ $priorityKey = $priority;
+ if (preg_match('/^(a|O):/', $priority)) {
+ $priority = unserialize($priority);
+ }
+ foreach ($values as $key => $value) {
+ $queue[$count] = array(
+ 'data' => $value,
+ 'priority' => $priority,
+ 'priorityKey' => $priorityKey,
+ 'key' => $key,
+ );
+ $count--;
+ }
+ }
+ $this->preparedQueue = $queue;
+ }
+ }
+}
+
+/**
+ * Serializable version of SplPriorityQueue
+ *
+ * Also, provides predictable heap order for datums added with the same priority
+ * (i.e., they will be emitted in the same order they are enqueued).
+ *
+ * @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_SplPriorityQueue extends SplPriorityQueue implements Serializable
+{
+ /**
+ * @var int Seed used to ensure queue order for items of the same priority
+ */
+ protected $serial = PHP_INT_MAX;
+
+ /**
+ * @var bool
+ */
+ protected $isPhp53;
+
+ /**
+ * Constructor
+ *
+ * @return void
+ */
+ public function __construct()
+ {
+ $this->isPhp53 = version_compare(PHP_VERSION, '5.3', '>=');
+ }
+
+ /**
+ * Insert a value with a given priority
+ *
+ * Utilizes {@var $serial} to ensure that values of equal priority are
+ * emitted in the same order in which they are inserted.
+ *
+ * @param mixed $datum
+ * @param mixed $priority
+ * @return void
+ */
+ public function insert($datum, $priority)
+ {
+ // If using the native PHP SplPriorityQueue implementation, we need to
+ // hack around it to ensure that items registered at the same priority
+ // return in the order registered. In the userland version, this is not
+ // necessary.
+ if ($this->isPhp53) {
+ if (!is_array($priority)) {
+ $priority = array($priority, $this->serial--);
+ }
+ }
+ parent::insert($datum, $priority);
+ }
+
+ /**
+ * Serialize to an array
+ *
+ * Array will be priority => data pairs
+ *
+ * @return array
+ */
+ public function toArray()
+ {
+ $this->setExtractFlags(self::EXTR_BOTH);
+ $array = array();
+ while ($this->valid()) {
+ $array[] = $this->current();
+ $this->next();
+ }
+ $this->setExtractFlags(self::EXTR_DATA);
+
+ // Iterating through a priority queue removes items
+ foreach ($array as $item) {
+ $this->insert($item['data'], $item['priority']);
+ }
+
+ // Return only the data
+ $return = array();
+ foreach ($array as $item) {
+ $return[] = $item['data'];
+ }
+
+ return $return;
+ }
+
+ /**
+ * Serialize
+ *
+ * @return string
+ */
+ public function serialize()
+ {
+ $data = array();
+ $this->setExtractFlags(self::EXTR_BOTH);
+ while ($this->valid()) {
+ $data[] = $this->current();
+ $this->next();
+ }
+ $this->setExtractFlags(self::EXTR_DATA);
+
+ // Iterating through a priority queue removes items
+ foreach ($data as $item) {
+ $this->insert($item['data'], $item['priority']);
+ }
+
+ return serialize($data);
+ }
+
+ /**
+ * Deserialize
+ *
+ * @param string $data
+ * @return void
+ */
+ public function unserialize($data)
+ {
+ foreach (unserialize($data) as $item) {
+ $this->insert($item['data'], $item['priority']);
+ }
+ }
+}