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 Iterator;
|
Chris@0
|
13 use Countable;
|
Chris@0
|
14 use Serializable;
|
Chris@0
|
15 use SplPriorityQueue as PhpSplPriorityQueue;
|
Chris@0
|
16
|
Chris@0
|
17 /**
|
Chris@0
|
18 * This is an efficient implementation of an integer priority queue in PHP
|
Chris@0
|
19 *
|
Chris@0
|
20 * This class acts like a queue with insert() and extract(), removing the
|
Chris@0
|
21 * elements from the queue and it also acts like an Iterator without removing
|
Chris@0
|
22 * the elements. This behaviour can be used in mixed scenarios with high
|
Chris@0
|
23 * performance boost.
|
Chris@0
|
24 */
|
Chris@0
|
25 class FastPriorityQueue implements Iterator, Countable, Serializable
|
Chris@0
|
26 {
|
Chris@0
|
27 const EXTR_DATA = PhpSplPriorityQueue::EXTR_DATA;
|
Chris@0
|
28 const EXTR_PRIORITY = PhpSplPriorityQueue::EXTR_PRIORITY;
|
Chris@0
|
29 const EXTR_BOTH = PhpSplPriorityQueue::EXTR_BOTH;
|
Chris@0
|
30
|
Chris@0
|
31 /**
|
Chris@0
|
32 * @var integer
|
Chris@0
|
33 */
|
Chris@0
|
34 protected $extractFlag = self::EXTR_DATA;
|
Chris@0
|
35
|
Chris@0
|
36 /**
|
Chris@0
|
37 * Elements of the queue, divided by priorities
|
Chris@0
|
38 *
|
Chris@0
|
39 * @var array
|
Chris@0
|
40 */
|
Chris@0
|
41 protected $values = [];
|
Chris@0
|
42
|
Chris@0
|
43 /**
|
Chris@0
|
44 * Array of priorities
|
Chris@0
|
45 *
|
Chris@0
|
46 * @var array
|
Chris@0
|
47 */
|
Chris@0
|
48 protected $priorities = [];
|
Chris@0
|
49
|
Chris@0
|
50 /**
|
Chris@0
|
51 * Array of priorities used for the iteration
|
Chris@0
|
52 *
|
Chris@0
|
53 * @var array
|
Chris@0
|
54 */
|
Chris@0
|
55 protected $subPriorities = [];
|
Chris@0
|
56
|
Chris@0
|
57 /**
|
Chris@0
|
58 * Max priority
|
Chris@0
|
59 *
|
Chris@13
|
60 * @var integer|null
|
Chris@0
|
61 */
|
Chris@13
|
62 protected $maxPriority = null;
|
Chris@0
|
63
|
Chris@0
|
64 /**
|
Chris@0
|
65 * Total number of elements in the queue
|
Chris@0
|
66 *
|
Chris@0
|
67 * @var integer
|
Chris@0
|
68 */
|
Chris@0
|
69 protected $count = 0;
|
Chris@0
|
70
|
Chris@0
|
71 /**
|
Chris@0
|
72 * Index of the current element in the queue
|
Chris@0
|
73 *
|
Chris@0
|
74 * @var integer
|
Chris@0
|
75 */
|
Chris@0
|
76 protected $index = 0;
|
Chris@0
|
77
|
Chris@0
|
78 /**
|
Chris@0
|
79 * Sub index of the current element in the same priority level
|
Chris@0
|
80 *
|
Chris@0
|
81 * @var integer
|
Chris@0
|
82 */
|
Chris@0
|
83 protected $subIndex = 0;
|
Chris@0
|
84
|
Chris@0
|
85 /**
|
Chris@0
|
86 * Insert an element in the queue with a specified priority
|
Chris@0
|
87 *
|
Chris@0
|
88 * @param mixed $value
|
Chris@13
|
89 * @param integer $priority
|
Chris@0
|
90 */
|
Chris@0
|
91 public function insert($value, $priority)
|
Chris@0
|
92 {
|
Chris@0
|
93 if (! is_int($priority)) {
|
Chris@0
|
94 throw new Exception\InvalidArgumentException('The priority must be an integer');
|
Chris@0
|
95 }
|
Chris@0
|
96 $this->values[$priority][] = $value;
|
Chris@0
|
97 if (! isset($this->priorities[$priority])) {
|
Chris@0
|
98 $this->priorities[$priority] = $priority;
|
Chris@13
|
99 $this->maxPriority = $this->maxPriority === null ? $priority : max($priority, $this->maxPriority);
|
Chris@0
|
100 }
|
Chris@0
|
101 ++$this->count;
|
Chris@0
|
102 }
|
Chris@0
|
103
|
Chris@0
|
104 /**
|
Chris@0
|
105 * Extract an element in the queue according to the priority and the
|
Chris@0
|
106 * order of insertion
|
Chris@0
|
107 *
|
Chris@0
|
108 * @return mixed
|
Chris@0
|
109 */
|
Chris@0
|
110 public function extract()
|
Chris@0
|
111 {
|
Chris@0
|
112 if (! $this->valid()) {
|
Chris@0
|
113 return false;
|
Chris@0
|
114 }
|
Chris@0
|
115 $value = $this->current();
|
Chris@0
|
116 $this->nextAndRemove();
|
Chris@0
|
117 return $value;
|
Chris@0
|
118 }
|
Chris@0
|
119
|
Chris@0
|
120 /**
|
Chris@0
|
121 * Remove an item from the queue
|
Chris@0
|
122 *
|
Chris@0
|
123 * This is different than {@link extract()}; its purpose is to dequeue an
|
Chris@0
|
124 * item.
|
Chris@0
|
125 *
|
Chris@0
|
126 * Note: this removes the first item matching the provided item found. If
|
Chris@0
|
127 * the same item has been added multiple times, it will not remove other
|
Chris@0
|
128 * instances.
|
Chris@0
|
129 *
|
Chris@0
|
130 * @param mixed $datum
|
Chris@0
|
131 * @return bool False if the item was not found, true otherwise.
|
Chris@0
|
132 */
|
Chris@0
|
133 public function remove($datum)
|
Chris@0
|
134 {
|
Chris@13
|
135 $currentIndex = $this->index;
|
Chris@13
|
136 $currentSubIndex = $this->subIndex;
|
Chris@13
|
137 $currentPriority = $this->maxPriority;
|
Chris@13
|
138
|
Chris@0
|
139 $this->rewind();
|
Chris@0
|
140 while ($this->valid()) {
|
Chris@0
|
141 if (current($this->values[$this->maxPriority]) === $datum) {
|
Chris@0
|
142 $index = key($this->values[$this->maxPriority]);
|
Chris@0
|
143 unset($this->values[$this->maxPriority][$index]);
|
Chris@13
|
144
|
Chris@13
|
145 // The `next()` method advances the internal array pointer, so we need to use the `reset()` function,
|
Chris@13
|
146 // otherwise we would lose all elements before the place the pointer points.
|
Chris@13
|
147 reset($this->values[$this->maxPriority]);
|
Chris@13
|
148
|
Chris@13
|
149 $this->index = $currentIndex;
|
Chris@13
|
150 $this->subIndex = $currentSubIndex;
|
Chris@13
|
151
|
Chris@13
|
152 // If the array is empty we need to destroy the unnecessary priority,
|
Chris@13
|
153 // otherwise we would end up with an incorrect value of `$this->count`
|
Chris@13
|
154 // {@see \Zend\Stdlib\FastPriorityQueue::nextAndRemove()}.
|
Chris@13
|
155 if (empty($this->values[$this->maxPriority])) {
|
Chris@13
|
156 unset($this->values[$this->maxPriority]);
|
Chris@13
|
157 unset($this->priorities[$this->maxPriority]);
|
Chris@13
|
158 if ($this->maxPriority === $currentPriority) {
|
Chris@13
|
159 $this->subIndex = 0;
|
Chris@13
|
160 }
|
Chris@13
|
161 }
|
Chris@13
|
162
|
Chris@13
|
163 $this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
|
Chris@0
|
164 --$this->count;
|
Chris@0
|
165 return true;
|
Chris@0
|
166 }
|
Chris@0
|
167 $this->next();
|
Chris@0
|
168 }
|
Chris@0
|
169 return false;
|
Chris@0
|
170 }
|
Chris@0
|
171
|
Chris@0
|
172 /**
|
Chris@0
|
173 * Get the total number of elements in the queue
|
Chris@0
|
174 *
|
Chris@0
|
175 * @return integer
|
Chris@0
|
176 */
|
Chris@0
|
177 public function count()
|
Chris@0
|
178 {
|
Chris@0
|
179 return $this->count;
|
Chris@0
|
180 }
|
Chris@0
|
181
|
Chris@0
|
182 /**
|
Chris@0
|
183 * Get the current element in the queue
|
Chris@0
|
184 *
|
Chris@0
|
185 * @return mixed
|
Chris@0
|
186 */
|
Chris@0
|
187 public function current()
|
Chris@0
|
188 {
|
Chris@0
|
189 switch ($this->extractFlag) {
|
Chris@0
|
190 case self::EXTR_DATA:
|
Chris@0
|
191 return current($this->values[$this->maxPriority]);
|
Chris@0
|
192 case self::EXTR_PRIORITY:
|
Chris@0
|
193 return $this->maxPriority;
|
Chris@0
|
194 case self::EXTR_BOTH:
|
Chris@0
|
195 return [
|
Chris@0
|
196 'data' => current($this->values[$this->maxPriority]),
|
Chris@0
|
197 'priority' => $this->maxPriority
|
Chris@0
|
198 ];
|
Chris@0
|
199 }
|
Chris@0
|
200 }
|
Chris@0
|
201
|
Chris@0
|
202 /**
|
Chris@0
|
203 * Get the index of the current element in the queue
|
Chris@0
|
204 *
|
Chris@0
|
205 * @return integer
|
Chris@0
|
206 */
|
Chris@0
|
207 public function key()
|
Chris@0
|
208 {
|
Chris@0
|
209 return $this->index;
|
Chris@0
|
210 }
|
Chris@0
|
211
|
Chris@0
|
212 /**
|
Chris@0
|
213 * Set the iterator pointer to the next element in the queue
|
Chris@0
|
214 * removing the previous element
|
Chris@0
|
215 */
|
Chris@0
|
216 protected function nextAndRemove()
|
Chris@0
|
217 {
|
Chris@13
|
218 $key = key($this->values[$this->maxPriority]);
|
Chris@13
|
219
|
Chris@0
|
220 if (false === next($this->values[$this->maxPriority])) {
|
Chris@0
|
221 unset($this->priorities[$this->maxPriority]);
|
Chris@0
|
222 unset($this->values[$this->maxPriority]);
|
Chris@13
|
223 $this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
|
Chris@0
|
224 $this->subIndex = -1;
|
Chris@13
|
225 } else {
|
Chris@13
|
226 unset($this->values[$this->maxPriority][$key]);
|
Chris@0
|
227 }
|
Chris@0
|
228 ++$this->index;
|
Chris@0
|
229 ++$this->subIndex;
|
Chris@0
|
230 --$this->count;
|
Chris@0
|
231 }
|
Chris@0
|
232
|
Chris@0
|
233 /**
|
Chris@0
|
234 * Set the iterator pointer to the next element in the queue
|
Chris@0
|
235 * without removing the previous element
|
Chris@0
|
236 */
|
Chris@0
|
237 public function next()
|
Chris@0
|
238 {
|
Chris@0
|
239 if (false === next($this->values[$this->maxPriority])) {
|
Chris@0
|
240 unset($this->subPriorities[$this->maxPriority]);
|
Chris@0
|
241 reset($this->values[$this->maxPriority]);
|
Chris@13
|
242 $this->maxPriority = empty($this->subPriorities) ? null : max($this->subPriorities);
|
Chris@0
|
243 $this->subIndex = -1;
|
Chris@0
|
244 }
|
Chris@0
|
245 ++$this->index;
|
Chris@0
|
246 ++$this->subIndex;
|
Chris@0
|
247 }
|
Chris@0
|
248
|
Chris@0
|
249 /**
|
Chris@0
|
250 * Check if the current iterator is valid
|
Chris@0
|
251 *
|
Chris@0
|
252 * @return boolean
|
Chris@0
|
253 */
|
Chris@0
|
254 public function valid()
|
Chris@0
|
255 {
|
Chris@0
|
256 return isset($this->values[$this->maxPriority]);
|
Chris@0
|
257 }
|
Chris@0
|
258
|
Chris@0
|
259 /**
|
Chris@0
|
260 * Rewind the current iterator
|
Chris@0
|
261 */
|
Chris@0
|
262 public function rewind()
|
Chris@0
|
263 {
|
Chris@0
|
264 $this->subPriorities = $this->priorities;
|
Chris@0
|
265 $this->maxPriority = empty($this->priorities) ? 0 : max($this->priorities);
|
Chris@0
|
266 $this->index = 0;
|
Chris@0
|
267 $this->subIndex = 0;
|
Chris@0
|
268 }
|
Chris@0
|
269
|
Chris@0
|
270 /**
|
Chris@0
|
271 * Serialize to an array
|
Chris@0
|
272 *
|
Chris@0
|
273 * Array will be priority => data pairs
|
Chris@0
|
274 *
|
Chris@0
|
275 * @return array
|
Chris@0
|
276 */
|
Chris@0
|
277 public function toArray()
|
Chris@0
|
278 {
|
Chris@0
|
279 $array = [];
|
Chris@0
|
280 foreach (clone $this as $item) {
|
Chris@0
|
281 $array[] = $item;
|
Chris@0
|
282 }
|
Chris@0
|
283 return $array;
|
Chris@0
|
284 }
|
Chris@0
|
285
|
Chris@0
|
286 /**
|
Chris@0
|
287 * Serialize
|
Chris@0
|
288 *
|
Chris@0
|
289 * @return string
|
Chris@0
|
290 */
|
Chris@0
|
291 public function serialize()
|
Chris@0
|
292 {
|
Chris@0
|
293 $clone = clone $this;
|
Chris@0
|
294 $clone->setExtractFlags(self::EXTR_BOTH);
|
Chris@0
|
295
|
Chris@0
|
296 $data = [];
|
Chris@0
|
297 foreach ($clone as $item) {
|
Chris@0
|
298 $data[] = $item;
|
Chris@0
|
299 }
|
Chris@0
|
300
|
Chris@0
|
301 return serialize($data);
|
Chris@0
|
302 }
|
Chris@0
|
303
|
Chris@0
|
304 /**
|
Chris@0
|
305 * Deserialize
|
Chris@0
|
306 *
|
Chris@0
|
307 * @param string $data
|
Chris@0
|
308 * @return void
|
Chris@0
|
309 */
|
Chris@0
|
310 public function unserialize($data)
|
Chris@0
|
311 {
|
Chris@0
|
312 foreach (unserialize($data) as $item) {
|
Chris@0
|
313 $this->insert($item['data'], $item['priority']);
|
Chris@0
|
314 }
|
Chris@0
|
315 }
|
Chris@0
|
316
|
Chris@0
|
317 /**
|
Chris@0
|
318 * Set the extract flag
|
Chris@0
|
319 *
|
Chris@0
|
320 * @param integer $flag
|
Chris@0
|
321 */
|
Chris@0
|
322 public function setExtractFlags($flag)
|
Chris@0
|
323 {
|
Chris@0
|
324 switch ($flag) {
|
Chris@0
|
325 case self::EXTR_DATA:
|
Chris@0
|
326 case self::EXTR_PRIORITY:
|
Chris@0
|
327 case self::EXTR_BOTH:
|
Chris@0
|
328 $this->extractFlag = $flag;
|
Chris@0
|
329 break;
|
Chris@0
|
330 default:
|
Chris@0
|
331 throw new Exception\InvalidArgumentException("The extract flag specified is not valid");
|
Chris@0
|
332 }
|
Chris@0
|
333 }
|
Chris@0
|
334
|
Chris@0
|
335 /**
|
Chris@0
|
336 * Check if the queue is empty
|
Chris@0
|
337 *
|
Chris@0
|
338 * @return boolean
|
Chris@0
|
339 */
|
Chris@0
|
340 public function isEmpty()
|
Chris@0
|
341 {
|
Chris@0
|
342 return empty($this->values);
|
Chris@0
|
343 }
|
Chris@0
|
344
|
Chris@0
|
345 /**
|
Chris@0
|
346 * Does the queue contain the given datum?
|
Chris@0
|
347 *
|
Chris@0
|
348 * @param mixed $datum
|
Chris@0
|
349 * @return bool
|
Chris@0
|
350 */
|
Chris@0
|
351 public function contains($datum)
|
Chris@0
|
352 {
|
Chris@0
|
353 foreach ($this->values as $values) {
|
Chris@0
|
354 if (in_array($datum, $values)) {
|
Chris@0
|
355 return true;
|
Chris@0
|
356 }
|
Chris@0
|
357 }
|
Chris@0
|
358 return false;
|
Chris@0
|
359 }
|
Chris@0
|
360
|
Chris@0
|
361 /**
|
Chris@0
|
362 * Does the queue have an item with the given priority?
|
Chris@0
|
363 *
|
Chris@0
|
364 * @param int $priority
|
Chris@0
|
365 * @return bool
|
Chris@0
|
366 */
|
Chris@0
|
367 public function hasPriority($priority)
|
Chris@0
|
368 {
|
Chris@0
|
369 return isset($this->values[$priority]);
|
Chris@0
|
370 }
|
Chris@0
|
371 }
|