Verzeichnisstruktur phpBB-3.2.0
- Veröffentlicht
- 06.01.2017
So funktioniert es
|
|
Auf das letzte Element klicken. Dies geht jeweils ein Schritt zurück |
Auf das Icon klicken, dies öffnet das Verzeichnis. Nochmal klicken schließt das Verzeichnis. |
|
|
(Beispiel Datei-Icons)
|
Auf das Icon klicken um den Quellcode anzuzeigen |
PriorityQueue.php
001 <?php
002 /**
003 * Zend Framework (http://framework.zend.com/)
004 *
005 * @link http://github.com/zendframework/zf2 for the canonical source repository
006 * @copyright Copyright (c) 2005-2015 Zend Technologies USA Inc. (http://www.zend.com)
007 * @license http://framework.zend.com/license/new-bsd New BSD License
008 */
009
010 namespace Zend\Stdlib;
011
012 use Countable;
013 use IteratorAggregate;
014 use Serializable;
015
016 /**
017 * Re-usable, serializable priority queue implementation
018 *
019 * SplPriorityQueue acts as a heap; on iteration, each item is removed from the
020 * queue. If you wish to re-use such a queue, you need to clone it first. This
021 * makes for some interesting issues if you wish to delete items from the queue,
022 * or, as already stated, iterate over it multiple times.
023 *
024 * This class aggregates items for the queue itself, but also composes an
025 * "inner" iterator in the form of an SplPriorityQueue object for performing
026 * the actual iteration.
027 */
028 class PriorityQueue implements Countable, IteratorAggregate, Serializable
029 {
030 const EXTR_DATA = 0x00000001;
031 const EXTR_PRIORITY = 0x00000002;
032 const EXTR_BOTH = 0x00000003;
033
034 /**
035 * Inner queue class to use for iteration
036 * @var string
037 */
038 protected $queueClass = 'Zend\Stdlib\SplPriorityQueue';
039
040 /**
041 * Actual items aggregated in the priority queue. Each item is an array
042 * with keys "data" and "priority".
043 * @var array
044 */
045 protected $items = array();
046
047 /**
048 * Inner queue object
049 * @var SplPriorityQueue
050 */
051 protected $queue;
052
053 /**
054 * Insert an item into the queue
055 *
056 * Priority defaults to 1 (low priority) if none provided.
057 *
058 * @param mixed $data
059 * @param int $priority
060 * @return PriorityQueue
061 */
062 public function insert($data, $priority = 1)
063 {
064 $priority = (int) $priority;
065 $this->items[] = array(
066 'data' => $data,
067 'priority' => $priority,
068 );
069 $this->getQueue()->insert($data, $priority);
070 return $this;
071 }
072
073 /**
074 * Remove an item from the queue
075 *
076 * This is different than {@link extract()}; its purpose is to dequeue an
077 * item.
078 *
079 * This operation is potentially expensive, as it requires
080 * re-initialization and re-population of the inner queue.
081 *
082 * Note: this removes the first item matching the provided item found. If
083 * the same item has been added multiple times, it will not remove other
084 * instances.
085 *
086 * @param mixed $datum
087 * @return bool False if the item was not found, true otherwise.
088 */
089 public function remove($datum)
090 {
091 $found = false;
092 foreach ($this->items as $key => $item) {
093 if ($item['data'] === $datum) {
094 $found = true;
095 break;
096 }
097 }
098 if ($found) {
099 unset($this->items[$key]);
100 $this->queue = null;
101
102 if (!$this->isEmpty()) {
103 $queue = $this->getQueue();
104 foreach ($this->items as $item) {
105 $queue->insert($item['data'], $item['priority']);
106 }
107 }
108 return true;
109 }
110 return false;
111 }
112
113 /**
114 * Is the queue empty?
115 *
116 * @return bool
117 */
118 public function isEmpty()
119 {
120 return (0 === $this->count());
121 }
122
123 /**
124 * How many items are in the queue?
125 *
126 * @return int
127 */
128 public function count()
129 {
130 return count($this->items);
131 }
132
133 /**
134 * Peek at the top node in the queue, based on priority.
135 *
136 * @return mixed
137 */
138 public function top()
139 {
140 return $this->getIterator()->top();
141 }
142
143 /**
144 * Extract a node from the inner queue and sift up
145 *
146 * @return mixed
147 */
148 public function extract()
149 {
150 return $this->getQueue()->extract();
151 }
152
153 /**
154 * Retrieve the inner iterator
155 *
156 * SplPriorityQueue acts as a heap, which typically implies that as items
157 * are iterated, they are also removed. This does not work for situations
158 * where the queue may be iterated multiple times. As such, this class
159 * aggregates the values, and also injects an SplPriorityQueue. This method
160 * retrieves the inner queue object, and clones it for purposes of
161 * iteration.
162 *
163 * @return SplPriorityQueue
164 */
165 public function getIterator()
166 {
167 $queue = $this->getQueue();
168 return clone $queue;
169 }
170
171 /**
172 * Serialize the data structure
173 *
174 * @return string
175 */
176 public function serialize()
177 {
178 return serialize($this->items);
179 }
180
181 /**
182 * Unserialize a string into a PriorityQueue object
183 *
184 * Serialization format is compatible with {@link Zend\Stdlib\SplPriorityQueue}
185 *
186 * @param string $data
187 * @return void
188 */
189 public function unserialize($data)
190 {
191 foreach (unserialize($data) as $item) {
192 $this->insert($item['data'], $item['priority']);
193 }
194 }
195
196 /**
197 * Serialize to an array
198 *
199 * By default, returns only the item data, and in the order registered (not
200 * sorted). You may provide one of the EXTR_* flags as an argument, allowing
201 * the ability to return priorities or both data and priority.
202 *
203 * @param int $flag
204 * @return array
205 */
206 public function toArray($flag = self::EXTR_DATA)
207 {
208 switch ($flag) {
209 case self::EXTR_BOTH:
210 return $this->items;
211 case self::EXTR_PRIORITY:
212 return array_map(function ($item) {
213 return $item['priority'];
214 }, $this->items);
215 case self::EXTR_DATA:
216 default:
217 return array_map(function ($item) {
218 return $item['data'];
219 }, $this->items);
220 }
221 }
222
223 /**
224 * Specify the internal queue class
225 *
226 * Please see {@link getIterator()} for details on the necessity of an
227 * internal queue class. The class provided should extend SplPriorityQueue.
228 *
229 * @param string $class
230 * @return PriorityQueue
231 */
232 public function setInternalQueueClass($class)
233 {
234 $this->queueClass = (string) $class;
235 return $this;
236 }
237
238 /**
239 * Does the queue contain the given datum?
240 *
241 * @param mixed $datum
242 * @return bool
243 */
244 public function contains($datum)
245 {
246 foreach ($this->items as $item) {
247 if ($item['data'] === $datum) {
248 return true;
249 }
250 }
251 return false;
252 }
253
254 /**
255 * Does the queue have an item with the given priority?
256 *
257 * @param int $priority
258 * @return bool
259 */
260 public function hasPriority($priority)
261 {
262 foreach ($this->items as $item) {
263 if ($item['priority'] === $priority) {
264 return true;
265 }
266 }
267 return false;
268 }
269
270 /**
271 * Get the inner priority queue instance
272 *
273 * @throws Exception\DomainException
274 * @return SplPriorityQueue
275 */
276 protected function getQueue()
277 {
278 if (null === $this->queue) {
279 $this->queue = new $this->queueClass();
280 if (!$this->queue instanceof \SplPriorityQueue) {
281 throw new Exception\DomainException(sprintf(
282 'PriorityQueue expects an internal queue of type SplPriorityQueue; received "%s"',
283 get_class($this->queue)
284 ));
285 }
286 }
287 return $this->queue;
288 }
289
290 /**
291 * Add support for deep cloning
292 *
293 * @return void
294 */
295 public function __clone()
296 {
297 if (null !== $this->queue) {
298 $this->queue = clone $this->queue;
299 }
300 }
301 }
302