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 }
|