OLD | NEW |
| (Empty) |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | |
2 // for details. All rights reserved. Use of this source code is governed by a | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 part of dart.core; | |
6 | |
7 /** | |
8 * A [Queue] is a collection that can be manipulated at both ends. One | |
9 * can iterate over the elements of a queue through [forEach] or with | |
10 * an [Iterator]. | |
11 */ | |
12 abstract class Queue<E> extends Collection<E> { | |
13 | |
14 /** | |
15 * Creates a queue. | |
16 */ | |
17 factory Queue() => new DoubleLinkedQueue<E>(); | |
18 | |
19 /** | |
20 * Creates a queue with the elements of [other]. The order in | |
21 * the queue will be the order provided by the iterator of [other]. | |
22 */ | |
23 factory Queue.from(Iterable<E> other) => new DoubleLinkedQueue<E>.from(other); | |
24 | |
25 /** | |
26 * Removes and returns the first element of this queue. Throws an | |
27 * [StateError] exception if this queue is empty. | |
28 */ | |
29 E removeFirst(); | |
30 | |
31 /** | |
32 * Removes and returns the last element of the queue. Throws an | |
33 * [StateError] exception if this queue is empty. | |
34 */ | |
35 E removeLast(); | |
36 | |
37 /** | |
38 * Adds [value] at the beginning of the queue. | |
39 */ | |
40 void addFirst(E value); | |
41 | |
42 /** | |
43 * Adds [value] at the end of the queue. | |
44 */ | |
45 void addLast(E value); | |
46 | |
47 /** | |
48 * Adds [value] at the end of the queue. | |
49 */ | |
50 void add(E value); | |
51 | |
52 /** | |
53 * Adds all elements of [iterable] at the end of the queue. The | |
54 * length of the queue is extended by the length of [iterable]. | |
55 */ | |
56 void addAll(Iterable<E> iterable); | |
57 | |
58 /** | |
59 * Removes all elements in the queue. The size of the queue becomes zero. | |
60 */ | |
61 void clear(); | |
62 } | |
63 | |
64 | |
65 /** | |
66 * An entry in a doubly linked list. It contains a pointer to the next | |
67 * entry, the previous entry, and the boxed element. | |
68 * | |
69 * WARNING: This class is temporary located in dart:core. It'll be removed | |
70 * at some point in the near future. | |
71 */ | |
72 class DoubleLinkedQueueEntry<E> { | |
73 DoubleLinkedQueueEntry<E> _previous; | |
74 DoubleLinkedQueueEntry<E> _next; | |
75 E _element; | |
76 | |
77 DoubleLinkedQueueEntry(E e) { | |
78 _element = e; | |
79 } | |
80 | |
81 void _link(DoubleLinkedQueueEntry<E> p, | |
82 DoubleLinkedQueueEntry<E> n) { | |
83 _next = n; | |
84 _previous = p; | |
85 p._next = this; | |
86 n._previous = this; | |
87 } | |
88 | |
89 void append(E e) { | |
90 new DoubleLinkedQueueEntry<E>(e)._link(this, _next); | |
91 } | |
92 | |
93 void prepend(E e) { | |
94 new DoubleLinkedQueueEntry<E>(e)._link(_previous, this); | |
95 } | |
96 | |
97 E remove() { | |
98 _previous._next = _next; | |
99 _next._previous = _previous; | |
100 _next = null; | |
101 _previous = null; | |
102 return _element; | |
103 } | |
104 | |
105 DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { | |
106 return this; | |
107 } | |
108 | |
109 DoubleLinkedQueueEntry<E> previousEntry() { | |
110 return _previous._asNonSentinelEntry(); | |
111 } | |
112 | |
113 DoubleLinkedQueueEntry<E> nextEntry() { | |
114 return _next._asNonSentinelEntry(); | |
115 } | |
116 | |
117 E get element { | |
118 return _element; | |
119 } | |
120 | |
121 void set element(E e) { | |
122 _element = e; | |
123 } | |
124 } | |
125 | |
126 /** | |
127 * A sentinel in a double linked list is used to manipulate the list | |
128 * at both ends. A double linked list has exactly one sentinel, which | |
129 * is the only entry when the list is constructed. Initially, a | |
130 * sentinel has its next and previous entry point to itself. A | |
131 * sentinel does not box any user element. | |
132 */ | |
133 class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> { | |
134 _DoubleLinkedQueueEntrySentinel() : super(null) { | |
135 _link(this, this); | |
136 } | |
137 | |
138 E remove() { | |
139 throw new StateError("Empty queue"); | |
140 } | |
141 | |
142 DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { | |
143 return null; | |
144 } | |
145 | |
146 void set element(E e) { | |
147 // This setter is unreachable. | |
148 assert(false); | |
149 } | |
150 | |
151 E get element { | |
152 throw new StateError("Empty queue"); | |
153 } | |
154 } | |
155 | |
156 /** | |
157 * Implementation of a double linked list that box list elements into | |
158 * DoubleLinkedQueueEntry objects. | |
159 * | |
160 * WARNING: This class is temporary located in dart:core. It'll be removed | |
161 * at some point in the near future. | |
162 */ | |
163 class DoubleLinkedQueue<E> extends Iterable<E> implements Queue<E> { | |
164 _DoubleLinkedQueueEntrySentinel<E> _sentinel; | |
165 | |
166 DoubleLinkedQueue() { | |
167 _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); | |
168 } | |
169 | |
170 factory DoubleLinkedQueue.from(Iterable<E> other) { | |
171 Queue<E> list = new DoubleLinkedQueue(); | |
172 for (final e in other) { | |
173 list.addLast(e); | |
174 } | |
175 return list; | |
176 } | |
177 | |
178 void addLast(E value) { | |
179 _sentinel.prepend(value); | |
180 } | |
181 | |
182 void addFirst(E value) { | |
183 _sentinel.append(value); | |
184 } | |
185 | |
186 void add(E value) { | |
187 addLast(value); | |
188 } | |
189 | |
190 void addAll(Iterable<E> iterable) { | |
191 for (final e in iterable) { | |
192 add(e); | |
193 } | |
194 } | |
195 | |
196 E removeLast() { | |
197 return _sentinel._previous.remove(); | |
198 } | |
199 | |
200 E removeFirst() { | |
201 return _sentinel._next.remove(); | |
202 } | |
203 | |
204 void remove(Object o) { | |
205 DoubleLinkedQueueEntry<E> entry = firstEntry(); | |
206 while (!identical(entry, _sentinel)) { | |
207 if (entry.element == o) { | |
208 entry.remove(); | |
209 return; | |
210 } | |
211 entry = entry._next; | |
212 } | |
213 } | |
214 | |
215 void removeAll(Iterable elements) { | |
216 // Use this method when remove is slow and removeMatching more efficient. | |
217 IterableMixinWorkaround.removeAllList(this, elements); | |
218 } | |
219 | |
220 void removeMatching(bool test(E element)) { | |
221 DoubleLinkedQueueEntry<E> entry = firstEntry(); | |
222 while (!identical(entry, _sentinel)) { | |
223 DoubleLinkedQueueEntry<E> next = entry._next; | |
224 if (test(entry.element)) { | |
225 entry.remove(); | |
226 } | |
227 entry = next; | |
228 } | |
229 } | |
230 | |
231 void retainMatching(bool test(E element)) { | |
232 DoubleLinkedQueueEntry<E> entry = firstEntry(); | |
233 while (!identical(entry, _sentinel)) { | |
234 DoubleLinkedQueueEntry<E> next = entry._next; | |
235 if (!test(entry.element)) { | |
236 entry.remove(); | |
237 } | |
238 entry = next; | |
239 } | |
240 } | |
241 | |
242 E get first { | |
243 return _sentinel._next.element; | |
244 } | |
245 | |
246 E get last { | |
247 return _sentinel._previous.element; | |
248 } | |
249 | |
250 E get single { | |
251 // Note that this also covers the case where the queue is empty. | |
252 if (identical(_sentinel._next, _sentinel._previous)) { | |
253 return _sentinel._next.element; | |
254 } | |
255 throw new StateError("More than one element"); | |
256 } | |
257 | |
258 DoubleLinkedQueueEntry<E> lastEntry() { | |
259 return _sentinel.previousEntry(); | |
260 } | |
261 | |
262 DoubleLinkedQueueEntry<E> firstEntry() { | |
263 return _sentinel.nextEntry(); | |
264 } | |
265 | |
266 bool get isEmpty { | |
267 return (identical(_sentinel._next, _sentinel)); | |
268 } | |
269 | |
270 void clear() { | |
271 _sentinel._next = _sentinel; | |
272 _sentinel._previous = _sentinel; | |
273 } | |
274 | |
275 void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { | |
276 DoubleLinkedQueueEntry<E> entry = _sentinel._next; | |
277 while (!identical(entry, _sentinel)) { | |
278 DoubleLinkedQueueEntry<E> nextEntry = entry._next; | |
279 f(entry); | |
280 entry = nextEntry; | |
281 } | |
282 } | |
283 | |
284 _DoubleLinkedQueueIterator<E> get iterator { | |
285 return new _DoubleLinkedQueueIterator<E>(_sentinel); | |
286 } | |
287 | |
288 String toString() { | |
289 return Collections.collectionToString(this); | |
290 } | |
291 } | |
292 | |
293 class _DoubleLinkedQueueIterator<E> implements Iterator<E> { | |
294 _DoubleLinkedQueueEntrySentinel<E> _sentinel; | |
295 DoubleLinkedQueueEntry<E> _currentEntry = null; | |
296 E _current; | |
297 | |
298 _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel<E> sentinel) | |
299 : _sentinel = sentinel, _currentEntry = sentinel; | |
300 | |
301 bool moveNext() { | |
302 // When [_currentEntry] it is set to [:null:] then it is at the end. | |
303 if (_currentEntry == null) { | |
304 assert(_current == null); | |
305 return false; | |
306 } | |
307 _currentEntry = _currentEntry._next; | |
308 if (identical(_currentEntry, _sentinel)) { | |
309 _currentEntry = null; | |
310 _current = null; | |
311 _sentinel = null; | |
312 return false; | |
313 } | |
314 _current = _currentEntry.element; | |
315 return true; | |
316 } | |
317 | |
318 E get current => _current; | |
319 } | |
OLD | NEW |