annotate vendor/zendframework/zend-stdlib/src/PriorityQueue.php @ 19:fa3358dc1485 tip

Add ndrum files
author Chris Cannam
date Wed, 28 Aug 2019 13:14:47 +0100
parents 7a779792577d
children
rev   line source
Chris@0 1 <?php
Chris@0 2 /**
Chris@0 3 * Zend Framework (http://framework.zend.com/)
Chris@0 4 *
Chris@0 5 * @link http://github.com/zendframework/zf2 for the canonical source repository
Chris@0 6 * @copyright Copyright (c) 2005-2015 Zend Technologies USA Inc. (http://www.zend.com)
Chris@0 7 * @license http://framework.zend.com/license/new-bsd New BSD License
Chris@0 8 */
Chris@0 9
Chris@0 10 namespace Zend\Stdlib;
Chris@0 11
Chris@0 12 use Countable;
Chris@0 13 use IteratorAggregate;
Chris@0 14 use Serializable;
Chris@0 15
Chris@0 16 /**
Chris@0 17 * Re-usable, serializable priority queue implementation
Chris@0 18 *
Chris@0 19 * SplPriorityQueue acts as a heap; on iteration, each item is removed from the
Chris@0 20 * queue. If you wish to re-use such a queue, you need to clone it first. This
Chris@0 21 * makes for some interesting issues if you wish to delete items from the queue,
Chris@0 22 * or, as already stated, iterate over it multiple times.
Chris@0 23 *
Chris@0 24 * This class aggregates items for the queue itself, but also composes an
Chris@0 25 * "inner" iterator in the form of an SplPriorityQueue object for performing
Chris@0 26 * the actual iteration.
Chris@0 27 */
Chris@0 28 class PriorityQueue implements Countable, IteratorAggregate, Serializable
Chris@0 29 {
Chris@0 30 const EXTR_DATA = 0x00000001;
Chris@0 31 const EXTR_PRIORITY = 0x00000002;
Chris@0 32 const EXTR_BOTH = 0x00000003;
Chris@0 33
Chris@0 34 /**
Chris@0 35 * Inner queue class to use for iteration
Chris@0 36 * @var string
Chris@0 37 */
Chris@0 38 protected $queueClass = 'Zend\Stdlib\SplPriorityQueue';
Chris@0 39
Chris@0 40 /**
Chris@0 41 * Actual items aggregated in the priority queue. Each item is an array
Chris@0 42 * with keys "data" and "priority".
Chris@0 43 * @var array
Chris@0 44 */
Chris@0 45 protected $items = [];
Chris@0 46
Chris@0 47 /**
Chris@0 48 * Inner queue object
Chris@0 49 * @var SplPriorityQueue
Chris@0 50 */
Chris@0 51 protected $queue;
Chris@0 52
Chris@0 53 /**
Chris@0 54 * Insert an item into the queue
Chris@0 55 *
Chris@0 56 * Priority defaults to 1 (low priority) if none provided.
Chris@0 57 *
Chris@0 58 * @param mixed $data
Chris@0 59 * @param int $priority
Chris@0 60 * @return PriorityQueue
Chris@0 61 */
Chris@0 62 public function insert($data, $priority = 1)
Chris@0 63 {
Chris@0 64 $priority = (int) $priority;
Chris@0 65 $this->items[] = [
Chris@0 66 'data' => $data,
Chris@0 67 'priority' => $priority,
Chris@0 68 ];
Chris@0 69 $this->getQueue()->insert($data, $priority);
Chris@0 70 return $this;
Chris@0 71 }
Chris@0 72
Chris@0 73 /**
Chris@0 74 * Remove an item from the queue
Chris@0 75 *
Chris@0 76 * This is different than {@link extract()}; its purpose is to dequeue an
Chris@0 77 * item.
Chris@0 78 *
Chris@0 79 * This operation is potentially expensive, as it requires
Chris@0 80 * re-initialization and re-population of the inner queue.
Chris@0 81 *
Chris@0 82 * Note: this removes the first item matching the provided item found. If
Chris@0 83 * the same item has been added multiple times, it will not remove other
Chris@0 84 * instances.
Chris@0 85 *
Chris@0 86 * @param mixed $datum
Chris@0 87 * @return bool False if the item was not found, true otherwise.
Chris@0 88 */
Chris@0 89 public function remove($datum)
Chris@0 90 {
Chris@0 91 $found = false;
Chris@0 92 foreach ($this->items as $key => $item) {
Chris@0 93 if ($item['data'] === $datum) {
Chris@0 94 $found = true;
Chris@0 95 break;
Chris@0 96 }
Chris@0 97 }
Chris@0 98 if ($found) {
Chris@0 99 unset($this->items[$key]);
Chris@0 100 $this->queue = null;
Chris@0 101
Chris@12 102 if (! $this->isEmpty()) {
Chris@0 103 $queue = $this->getQueue();
Chris@0 104 foreach ($this->items as $item) {
Chris@0 105 $queue->insert($item['data'], $item['priority']);
Chris@0 106 }
Chris@0 107 }
Chris@0 108 return true;
Chris@0 109 }
Chris@0 110 return false;
Chris@0 111 }
Chris@0 112
Chris@0 113 /**
Chris@0 114 * Is the queue empty?
Chris@0 115 *
Chris@0 116 * @return bool
Chris@0 117 */
Chris@0 118 public function isEmpty()
Chris@0 119 {
Chris@0 120 return (0 === $this->count());
Chris@0 121 }
Chris@0 122
Chris@0 123 /**
Chris@0 124 * How many items are in the queue?
Chris@0 125 *
Chris@0 126 * @return int
Chris@0 127 */
Chris@0 128 public function count()
Chris@0 129 {
Chris@0 130 return count($this->items);
Chris@0 131 }
Chris@0 132
Chris@0 133 /**
Chris@0 134 * Peek at the top node in the queue, based on priority.
Chris@0 135 *
Chris@0 136 * @return mixed
Chris@0 137 */
Chris@0 138 public function top()
Chris@0 139 {
Chris@0 140 return $this->getIterator()->top();
Chris@0 141 }
Chris@0 142
Chris@0 143 /**
Chris@0 144 * Extract a node from the inner queue and sift up
Chris@0 145 *
Chris@0 146 * @return mixed
Chris@0 147 */
Chris@0 148 public function extract()
Chris@0 149 {
Chris@0 150 return $this->getQueue()->extract();
Chris@0 151 }
Chris@0 152
Chris@0 153 /**
Chris@0 154 * Retrieve the inner iterator
Chris@0 155 *
Chris@0 156 * SplPriorityQueue acts as a heap, which typically implies that as items
Chris@0 157 * are iterated, they are also removed. This does not work for situations
Chris@0 158 * where the queue may be iterated multiple times. As such, this class
Chris@0 159 * aggregates the values, and also injects an SplPriorityQueue. This method
Chris@0 160 * retrieves the inner queue object, and clones it for purposes of
Chris@0 161 * iteration.
Chris@0 162 *
Chris@0 163 * @return SplPriorityQueue
Chris@0 164 */
Chris@0 165 public function getIterator()
Chris@0 166 {
Chris@0 167 $queue = $this->getQueue();
Chris@0 168 return clone $queue;
Chris@0 169 }
Chris@0 170
Chris@0 171 /**
Chris@0 172 * Serialize the data structure
Chris@0 173 *
Chris@0 174 * @return string
Chris@0 175 */
Chris@0 176 public function serialize()
Chris@0 177 {
Chris@0 178 return serialize($this->items);
Chris@0 179 }
Chris@0 180
Chris@0 181 /**
Chris@0 182 * Unserialize a string into a PriorityQueue object
Chris@0 183 *
Chris@0 184 * Serialization format is compatible with {@link Zend\Stdlib\SplPriorityQueue}
Chris@0 185 *
Chris@0 186 * @param string $data
Chris@0 187 * @return void
Chris@0 188 */
Chris@0 189 public function unserialize($data)
Chris@0 190 {
Chris@0 191 foreach (unserialize($data) as $item) {
Chris@0 192 $this->insert($item['data'], $item['priority']);
Chris@0 193 }
Chris@0 194 }
Chris@0 195
Chris@0 196 /**
Chris@0 197 * Serialize to an array
Chris@0 198 *
Chris@0 199 * By default, returns only the item data, and in the order registered (not
Chris@0 200 * sorted). You may provide one of the EXTR_* flags as an argument, allowing
Chris@0 201 * the ability to return priorities or both data and priority.
Chris@0 202 *
Chris@0 203 * @param int $flag
Chris@0 204 * @return array
Chris@0 205 */
Chris@0 206 public function toArray($flag = self::EXTR_DATA)
Chris@0 207 {
Chris@0 208 switch ($flag) {
Chris@0 209 case self::EXTR_BOTH:
Chris@0 210 return $this->items;
Chris@0 211 case self::EXTR_PRIORITY:
Chris@0 212 return array_map(function ($item) {
Chris@0 213 return $item['priority'];
Chris@0 214 }, $this->items);
Chris@0 215 case self::EXTR_DATA:
Chris@0 216 default:
Chris@0 217 return array_map(function ($item) {
Chris@0 218 return $item['data'];
Chris@0 219 }, $this->items);
Chris@0 220 }
Chris@0 221 }
Chris@0 222
Chris@0 223 /**
Chris@0 224 * Specify the internal queue class
Chris@0 225 *
Chris@0 226 * Please see {@link getIterator()} for details on the necessity of an
Chris@0 227 * internal queue class. The class provided should extend SplPriorityQueue.
Chris@0 228 *
Chris@0 229 * @param string $class
Chris@0 230 * @return PriorityQueue
Chris@0 231 */
Chris@0 232 public function setInternalQueueClass($class)
Chris@0 233 {
Chris@0 234 $this->queueClass = (string) $class;
Chris@0 235 return $this;
Chris@0 236 }
Chris@0 237
Chris@0 238 /**
Chris@0 239 * Does the queue contain the given datum?
Chris@0 240 *
Chris@0 241 * @param mixed $datum
Chris@0 242 * @return bool
Chris@0 243 */
Chris@0 244 public function contains($datum)
Chris@0 245 {
Chris@0 246 foreach ($this->items as $item) {
Chris@0 247 if ($item['data'] === $datum) {
Chris@0 248 return true;
Chris@0 249 }
Chris@0 250 }
Chris@0 251 return false;
Chris@0 252 }
Chris@0 253
Chris@0 254 /**
Chris@0 255 * Does the queue have an item with the given priority?
Chris@0 256 *
Chris@0 257 * @param int $priority
Chris@0 258 * @return bool
Chris@0 259 */
Chris@0 260 public function hasPriority($priority)
Chris@0 261 {
Chris@0 262 foreach ($this->items as $item) {
Chris@0 263 if ($item['priority'] === $priority) {
Chris@0 264 return true;
Chris@0 265 }
Chris@0 266 }
Chris@0 267 return false;
Chris@0 268 }
Chris@0 269
Chris@0 270 /**
Chris@0 271 * Get the inner priority queue instance
Chris@0 272 *
Chris@0 273 * @throws Exception\DomainException
Chris@0 274 * @return SplPriorityQueue
Chris@0 275 */
Chris@0 276 protected function getQueue()
Chris@0 277 {
Chris@0 278 if (null === $this->queue) {
Chris@0 279 $this->queue = new $this->queueClass();
Chris@12 280 if (! $this->queue instanceof \SplPriorityQueue) {
Chris@0 281 throw new Exception\DomainException(sprintf(
Chris@0 282 'PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
Chris@0 283 get_class($this->queue)
Chris@0 284 ));
Chris@0 285 }
Chris@0 286 }
Chris@0 287 return $this->queue;
Chris@0 288 }
Chris@0 289
Chris@0 290 /**
Chris@0 291 * Add support for deep cloning
Chris@0 292 *
Chris@0 293 * @return void
Chris@0 294 */
Chris@0 295 public function __clone()
Chris@0 296 {
Chris@0 297 if (null !== $this->queue) {
Chris@0 298 $this->queue = clone $this->queue;
Chris@0 299 }
Chris@0 300 }
Chris@0 301 }