Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(214)

Side by Side Diff: sdk/lib/core/queue.dart

Issue 11867024: Move some core classes to collection library. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Update status files with bug number. Created 7 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « sdk/lib/core/map.dart ('k') | sdk/lib/core/set.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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 }
OLDNEW
« no previous file with comments | « sdk/lib/core/map.dart ('k') | sdk/lib/core/set.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698