|
132
|
1 /*
|
|
|
2 File: CircularSeq.d
|
|
|
3
|
|
|
4 Originally written by Doug Lea and released into the public domain.
|
|
|
5 Thanks for the assistance and support of Sun Microsystems Labs, Agorics
|
|
|
6 Inc, Loral, and everyone contributing, testing, and using this code.
|
|
|
7
|
|
|
8 History:
|
|
|
9 Date Who What
|
|
|
10 24Sep95 dl@cs.oswego.edu Create from store.d working file
|
|
|
11 13Oct95 dl Changed protection statuses
|
|
|
12 */
|
|
|
13
|
|
|
14 module tango.util.collection.CircularSeq;
|
|
|
15
|
|
|
16 private import tango.util.collection.model.Iterator,
|
|
|
17 tango.util.collection.model.GuardIterator;
|
|
|
18
|
|
|
19 private import tango.util.collection.impl.CLCell,
|
|
|
20 tango.util.collection.impl.SeqCollection,
|
|
|
21 tango.util.collection.impl.AbstractIterator;
|
|
|
22
|
|
|
23
|
|
|
24 /**
|
|
|
25 * Circular linked lists. Publically Implement only those
|
|
|
26 * methods defined in interfaces.
|
|
|
27 * author: Doug Lea
|
|
|
28 **/
|
|
|
29 public class CircularSeq(T) : SeqCollection!(T)
|
|
|
30 {
|
|
|
31 alias CLCell!(T) CLCellT;
|
|
|
32
|
|
|
33 alias SeqCollection!(T).remove remove;
|
|
|
34 alias SeqCollection!(T).removeAll removeAll;
|
|
|
35
|
|
|
36 // instance variables
|
|
|
37
|
|
|
38 /**
|
|
|
39 * The head of the list. Null if empty
|
|
|
40 **/
|
|
|
41 package CLCellT list;
|
|
|
42
|
|
|
43 // constructors
|
|
|
44
|
|
|
45 /**
|
|
|
46 * Make an empty list with no element screener
|
|
|
47 **/
|
|
|
48 public this ()
|
|
|
49 {
|
|
|
50 this(null, null, 0);
|
|
|
51 }
|
|
|
52
|
|
|
53 /**
|
|
|
54 * Make an empty list with supplied element screener
|
|
|
55 **/
|
|
|
56 public this (Predicate screener)
|
|
|
57 {
|
|
|
58 this(screener, null, 0);
|
|
|
59 }
|
|
|
60
|
|
|
61 /**
|
|
|
62 * Special version of constructor needed by clone()
|
|
|
63 **/
|
|
|
64 protected this (Predicate s, CLCellT h, int c)
|
|
|
65 {
|
|
|
66 super(s);
|
|
|
67 list = h;
|
|
|
68 count = c;
|
|
|
69 }
|
|
|
70
|
|
|
71 /**
|
|
|
72 * Make an independent copy of the list. Elements themselves are not cloned
|
|
|
73 **/
|
|
|
74 public final CircularSeq duplicate()
|
|
|
75 {
|
|
|
76 if (list is null)
|
|
|
77 return new CircularSeq (screener, null, 0);
|
|
|
78 else
|
|
|
79 return new CircularSeq (screener, list.copyList(), count);
|
|
|
80 }
|
|
|
81
|
|
|
82
|
|
|
83 // Collection methods
|
|
|
84
|
|
|
85 /**
|
|
|
86 * Implements tango.util.collection.impl.Collection.Collection.contains
|
|
|
87 * Time complexity: O(n).
|
|
|
88 * See_Also: tango.util.collection.impl.Collection.Collection.contains
|
|
|
89 **/
|
|
|
90 public final bool contains(T element)
|
|
|
91 {
|
|
|
92 if (!isValidArg(element) || list is null)
|
|
|
93 return false;
|
|
|
94 return list.find(element) !is null;
|
|
|
95 }
|
|
|
96
|
|
|
97 /**
|
|
|
98 * Implements tango.util.collection.impl.Collection.Collection.instances
|
|
|
99 * Time complexity: O(n).
|
|
|
100 * See_Also: tango.util.collection.impl.Collection.Collection.instances
|
|
|
101 **/
|
|
|
102 public final uint instances(T element)
|
|
|
103 {
|
|
|
104 if (!isValidArg(element) || list is null)
|
|
|
105 return 0;
|
|
|
106 return list.count(element);
|
|
|
107 }
|
|
|
108
|
|
|
109 /**
|
|
|
110 * Implements tango.util.collection.impl.Collection.Collection.elements
|
|
|
111 * Time complexity: O(1).
|
|
|
112 * See_Also: tango.util.collection.impl.Collection.Collection.elements
|
|
|
113 **/
|
|
|
114 public final GuardIterator!(T) elements()
|
|
|
115 {
|
|
|
116 return new CellIterator!(T)(this);
|
|
|
117 }
|
|
|
118
|
|
|
119 /**
|
|
|
120 * Implements tango.util.collection.model.View.View.opApply
|
|
|
121 * Time complexity: O(n).
|
|
|
122 * See_Also: tango.util.collection.model.View.View.opApply
|
|
|
123 **/
|
|
|
124 int opApply (int delegate (inout T value) dg)
|
|
|
125 {
|
|
|
126 auto scope iterator = new CellIterator!(T)(this);
|
|
|
127 return iterator.opApply (dg);
|
|
|
128 }
|
|
|
129
|
|
|
130
|
|
|
131 // Seq methods
|
|
|
132
|
|
|
133 /**
|
|
|
134 * Implements tango.util.collection.model.Seq.Seq.head.
|
|
|
135 * Time complexity: O(1).
|
|
|
136 * See_Also: tango.util.collection.model.Seq.Seq.head
|
|
|
137 **/
|
|
|
138 public final T head()
|
|
|
139 {
|
|
|
140 return firstCell().element();
|
|
|
141 }
|
|
|
142
|
|
|
143 /**
|
|
|
144 * Implements tango.util.collection.model.Seq.Seq.tail.
|
|
|
145 * Time complexity: O(1).
|
|
|
146 * See_Also: tango.util.collection.model.Seq.Seq.tail
|
|
|
147 **/
|
|
|
148 public final T tail()
|
|
|
149 {
|
|
|
150 return lastCell().element();
|
|
|
151 }
|
|
|
152
|
|
|
153 /**
|
|
|
154 * Implements tango.util.collection.model.Seq.Seq.get.
|
|
|
155 * Time complexity: O(n).
|
|
|
156 * See_Also: tango.util.collection.model.Seq.Seq.get
|
|
|
157 **/
|
|
|
158 public final T get(int index)
|
|
|
159 {
|
|
|
160 return cellAt(index).element();
|
|
|
161 }
|
|
|
162
|
|
|
163 /**
|
|
|
164 * Implements tango.util.collection.model.Seq.Seq.first.
|
|
|
165 * Time complexity: O(n).
|
|
|
166 * See_Also: tango.util.collection.model.Seq.Seq.first
|
|
|
167 **/
|
|
|
168 public final int first(T element, int startingIndex = 0)
|
|
|
169 {
|
|
|
170 if (startingIndex < 0)
|
|
|
171 startingIndex = 0;
|
|
|
172
|
|
|
173 CLCellT p = list;
|
|
|
174 if (p is null || !isValidArg(element))
|
|
|
175 return -1;
|
|
|
176
|
|
|
177 for (int i = 0; true; ++i)
|
|
|
178 {
|
|
|
179 if (i >= startingIndex && p.element() == (element))
|
|
|
180 return i;
|
|
|
181
|
|
|
182 p = p.next();
|
|
|
183 if (p is list)
|
|
|
184 break;
|
|
|
185 }
|
|
|
186 return -1;
|
|
|
187 }
|
|
|
188
|
|
|
189
|
|
|
190 /**
|
|
|
191 * Implements tango.util.collection.model.Seq.Seq.last.
|
|
|
192 * Time complexity: O(n).
|
|
|
193 * See_Also: tango.util.collection.model.Seq.Seq.last
|
|
|
194 **/
|
|
|
195 public final int last(T element, int startingIndex = 0)
|
|
|
196 {
|
|
|
197 if (!isValidArg(element) || count is 0)
|
|
|
198 return -1;
|
|
|
199
|
|
|
200 if (startingIndex >= size())
|
|
|
201 startingIndex = size() - 1;
|
|
|
202
|
|
|
203 if (startingIndex < 0)
|
|
|
204 startingIndex = 0;
|
|
|
205
|
|
|
206 CLCellT p = cellAt(startingIndex);
|
|
|
207 int i = startingIndex;
|
|
|
208 for (;;)
|
|
|
209 {
|
|
|
210 if (p.element() == (element))
|
|
|
211 return i;
|
|
|
212 else
|
|
|
213 if (p is list)
|
|
|
214 break;
|
|
|
215 else
|
|
|
216 {
|
|
|
217 p = p.prev();
|
|
|
218 --i;
|
|
|
219 }
|
|
|
220 }
|
|
|
221 return -1;
|
|
|
222 }
|
|
|
223
|
|
|
224 /**
|
|
|
225 * Implements tango.util.collection.model.Seq.Seq.subseq.
|
|
|
226 * Time complexity: O(length).
|
|
|
227 * See_Also: tango.util.collection.model.Seq.Seq.subseq
|
|
|
228 **/
|
|
|
229 public final CircularSeq subset (int from, int _length)
|
|
|
230 {
|
|
|
231 if (_length > 0)
|
|
|
232 {
|
|
|
233 checkIndex(from);
|
|
|
234 CLCellT p = cellAt(from);
|
|
|
235 CLCellT newlist = new CLCellT(p.element());
|
|
|
236 CLCellT current = newlist;
|
|
|
237
|
|
|
238 for (int i = 1; i < _length; ++i)
|
|
|
239 {
|
|
|
240 p = p.next();
|
|
|
241 if (p is null)
|
|
|
242 checkIndex(from + i); // force exception
|
|
|
243
|
|
|
244 current.addNext(p.element());
|
|
|
245 current = current.next();
|
|
|
246 }
|
|
|
247 return new CircularSeq (screener, newlist, _length);
|
|
|
248 }
|
|
|
249 else
|
|
|
250 return new CircularSeq ();
|
|
|
251 }
|
|
|
252
|
|
|
253 // MutableCollection methods
|
|
|
254
|
|
|
255 /**
|
|
|
256 * Implements tango.util.collection.impl.Collection.Collection.clear.
|
|
|
257 * Time complexity: O(1).
|
|
|
258 * See_Also: tango.util.collection.impl.Collection.Collection.clear
|
|
|
259 **/
|
|
|
260 public final void clear()
|
|
|
261 {
|
|
|
262 list = null;
|
|
|
263 setCount(0);
|
|
|
264 }
|
|
|
265
|
|
|
266 /**
|
|
|
267 * Implements tango.util.collection.impl.Collection.Collection.exclude.
|
|
|
268 * Time complexity: O(n).
|
|
|
269 * See_Also: tango.util.collection.impl.Collection.Collection.exclude
|
|
|
270 **/
|
|
|
271 public final void removeAll (T element)
|
|
|
272 {
|
|
|
273 remove_(element, true);
|
|
|
274 }
|
|
|
275
|
|
|
276 /**
|
|
|
277 * Implements tango.util.collection.impl.Collection.Collection.removeOneOf.
|
|
|
278 * Time complexity: O(n).
|
|
|
279 * See_Also: tango.util.collection.impl.Collection.Collection.removeOneOf
|
|
|
280 **/
|
|
|
281 public final void remove (T element)
|
|
|
282 {
|
|
|
283 remove_(element, false);
|
|
|
284 }
|
|
|
285
|
|
|
286 /**
|
|
|
287 * Implements tango.util.collection.impl.Collection.Collection.replaceOneOf
|
|
|
288 * Time complexity: O(n).
|
|
|
289 * See_Also: tango.util.collection.impl.Collection.Collection.replaceOneOf
|
|
|
290 **/
|
|
|
291 public final void replace (T oldElement, T newElement)
|
|
|
292 {
|
|
|
293 replace_(oldElement, newElement, false);
|
|
|
294 }
|
|
|
295
|
|
|
296 /**
|
|
|
297 * Implements tango.util.collection.impl.Collection.Collection.replaceAllOf.
|
|
|
298 * Time complexity: O(n).
|
|
|
299 * See_Also: tango.util.collection.impl.Collection.Collection.replaceAllOf
|
|
|
300 **/
|
|
|
301 public final void replaceAll (T oldElement, T newElement)
|
|
|
302 {
|
|
|
303 replace_(oldElement, newElement, true);
|
|
|
304 }
|
|
|
305
|
|
|
306
|
|
|
307 /**
|
|
|
308 * Implements tango.util.collection.impl.Collection.Collection.take.
|
|
|
309 * Time complexity: O(1).
|
|
|
310 * takes the last element on the list.
|
|
|
311 * See_Also: tango.util.collection.impl.Collection.Collection.take
|
|
|
312 **/
|
|
|
313 public final T take()
|
|
|
314 {
|
|
|
315 auto v = tail();
|
|
|
316 removeTail();
|
|
|
317 return v;
|
|
|
318 }
|
|
|
319
|
|
|
320
|
|
|
321
|
|
|
322 // MutableSeq methods
|
|
|
323
|
|
|
324 /**
|
|
|
325 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.prepend.
|
|
|
326 * Time complexity: O(1).
|
|
|
327 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.prepend
|
|
|
328 **/
|
|
|
329 public final void prepend(T element)
|
|
|
330 {
|
|
|
331 checkElement(element);
|
|
|
332 if (list is null)
|
|
|
333 list = new CLCellT(element);
|
|
|
334 else
|
|
|
335 list = list.addPrev(element);
|
|
|
336 incCount();
|
|
|
337 }
|
|
|
338
|
|
|
339 /**
|
|
|
340 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceHead.
|
|
|
341 * Time complexity: O(1).
|
|
|
342 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.replaceHead
|
|
|
343 **/
|
|
|
344 public final void replaceHead(T element)
|
|
|
345 {
|
|
|
346 checkElement(element);
|
|
|
347 firstCell().element(element);
|
|
|
348 incVersion();
|
|
|
349 }
|
|
|
350
|
|
|
351 /**
|
|
|
352 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeHead.
|
|
|
353 * Time complexity: O(1).
|
|
|
354 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeHead
|
|
|
355 **/
|
|
|
356 public final void removeHead()
|
|
|
357 {
|
|
|
358 if (firstCell().isSingleton())
|
|
|
359 list = null;
|
|
|
360 else
|
|
|
361 {
|
|
|
362 auto n = list.next();
|
|
|
363 list.unlink();
|
|
|
364 list = n;
|
|
|
365 }
|
|
|
366 decCount();
|
|
|
367 }
|
|
|
368
|
|
|
369 /**
|
|
|
370 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.append.
|
|
|
371 * Time complexity: O(1).
|
|
|
372 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.append
|
|
|
373 **/
|
|
|
374 public final void append(T element)
|
|
|
375 {
|
|
|
376 if (list is null)
|
|
|
377 prepend(element);
|
|
|
378 else
|
|
|
379 {
|
|
|
380 checkElement(element);
|
|
|
381 list.prev().addNext(element);
|
|
|
382 incCount();
|
|
|
383 }
|
|
|
384 }
|
|
|
385
|
|
|
386 /**
|
|
|
387 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceTail.
|
|
|
388 * Time complexity: O(1).
|
|
|
389 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.replaceTail
|
|
|
390 **/
|
|
|
391 public final void replaceTail(T element)
|
|
|
392 {
|
|
|
393 checkElement(element);
|
|
|
394 lastCell().element(element);
|
|
|
395 incVersion();
|
|
|
396 }
|
|
|
397
|
|
|
398
|
|
|
399 /**
|
|
|
400 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeTail.
|
|
|
401 * Time complexity: O(1).
|
|
|
402 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeTail
|
|
|
403 **/
|
|
|
404 public final void removeTail()
|
|
|
405 {
|
|
|
406 auto l = lastCell();
|
|
|
407 if (l is list)
|
|
|
408 list = null;
|
|
|
409 else
|
|
|
410 l.unlink();
|
|
|
411 decCount();
|
|
|
412 }
|
|
|
413
|
|
|
414 /**
|
|
|
415 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.addAt.
|
|
|
416 * Time complexity: O(n).
|
|
|
417 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.addAt
|
|
|
418 **/
|
|
|
419 public final void addAt(int index, T element)
|
|
|
420 {
|
|
|
421 if (index is 0)
|
|
|
422 prepend(element);
|
|
|
423 else
|
|
|
424 {
|
|
|
425 checkElement(element);
|
|
|
426 cellAt(index - 1).addNext(element);
|
|
|
427 incCount();
|
|
|
428 }
|
|
|
429 }
|
|
|
430
|
|
|
431 /**
|
|
|
432 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceAt.
|
|
|
433 * Time complexity: O(n).
|
|
|
434 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.replaceAt
|
|
|
435 **/
|
|
|
436 public final void replaceAt(int index, T element)
|
|
|
437 {
|
|
|
438 checkElement(element);
|
|
|
439 cellAt(index).element(element);
|
|
|
440 incVersion();
|
|
|
441 }
|
|
|
442
|
|
|
443 /**
|
|
|
444 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeAt.
|
|
|
445 * Time complexity: O(n).
|
|
|
446 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeAt
|
|
|
447 **/
|
|
|
448 public final void removeAt(int index)
|
|
|
449 {
|
|
|
450 if (index is 0)
|
|
|
451 removeHead();
|
|
|
452 else
|
|
|
453 {
|
|
|
454 cellAt(index - 1).unlinkNext();
|
|
|
455 decCount();
|
|
|
456 }
|
|
|
457 }
|
|
|
458
|
|
|
459 /**
|
|
|
460 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.prepend.
|
|
|
461 * Time complexity: O(number of elements in e).
|
|
|
462 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.prepend
|
|
|
463 **/
|
|
|
464 public final void prepend(Iterator!(T) e)
|
|
|
465 {
|
|
|
466 CLCellT hd = null;
|
|
|
467 CLCellT current = null;
|
|
|
468
|
|
|
469 while (e.more())
|
|
|
470 {
|
|
|
471 auto element = e.get();
|
|
|
472 checkElement(element);
|
|
|
473 incCount();
|
|
|
474
|
|
|
475 if (hd is null)
|
|
|
476 {
|
|
|
477 hd = new CLCellT(element);
|
|
|
478 current = hd;
|
|
|
479 }
|
|
|
480 else
|
|
|
481 {
|
|
|
482 current.addNext(element);
|
|
|
483 current = current.next();
|
|
|
484 }
|
|
|
485 }
|
|
|
486
|
|
|
487 if (list is null)
|
|
|
488 list = hd;
|
|
|
489 else
|
|
|
490 if (hd !is null)
|
|
|
491 {
|
|
|
492 auto tl = list.prev();
|
|
|
493 current.next(list);
|
|
|
494 list.prev(current);
|
|
|
495 tl.next(hd);
|
|
|
496 hd.prev(tl);
|
|
|
497 list = hd;
|
|
|
498 }
|
|
|
499 }
|
|
|
500
|
|
|
501 /**
|
|
|
502 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.append.
|
|
|
503 * Time complexity: O(number of elements in e).
|
|
|
504 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.append
|
|
|
505 **/
|
|
|
506 public final void append(Iterator!(T) e)
|
|
|
507 {
|
|
|
508 if (list is null)
|
|
|
509 prepend(e);
|
|
|
510 else
|
|
|
511 {
|
|
|
512 CLCellT current = list.prev();
|
|
|
513 while (e.more())
|
|
|
514 {
|
|
|
515 T element = e.get();
|
|
|
516 checkElement(element);
|
|
|
517 incCount();
|
|
|
518 current.addNext(element);
|
|
|
519 current = current.next();
|
|
|
520 }
|
|
|
521 }
|
|
|
522 }
|
|
|
523
|
|
|
524 /**
|
|
|
525 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.addAt.
|
|
|
526 * Time complexity: O(size() + number of elements in e).
|
|
|
527 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.addAt
|
|
|
528 **/
|
|
|
529 public final void addAt(int index, Iterator!(T) e)
|
|
|
530 {
|
|
|
531 if (list is null || index is 0)
|
|
|
532 prepend(e);
|
|
|
533 else
|
|
|
534 {
|
|
|
535 CLCellT current = cellAt(index - 1);
|
|
|
536 while (e.more())
|
|
|
537 {
|
|
|
538 T element = e.get();
|
|
|
539 checkElement(element);
|
|
|
540 incCount();
|
|
|
541 current.addNext(element);
|
|
|
542 current = current.next();
|
|
|
543 }
|
|
|
544 }
|
|
|
545 }
|
|
|
546
|
|
|
547
|
|
|
548 /**
|
|
|
549 * Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeFromTo.
|
|
|
550 * Time complexity: O(n).
|
|
|
551 * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeFromTo
|
|
|
552 **/
|
|
|
553 public final void removeRange (int fromIndex, int toIndex)
|
|
|
554 {
|
|
|
555 checkIndex(toIndex);
|
|
|
556 CLCellT p = cellAt(fromIndex);
|
|
|
557 CLCellT last = list.prev();
|
|
|
558 for (int i = fromIndex; i <= toIndex; ++i)
|
|
|
559 {
|
|
|
560 decCount();
|
|
|
561 CLCellT n = p.next();
|
|
|
562 p.unlink();
|
|
|
563 if (p is list)
|
|
|
564 {
|
|
|
565 if (p is last)
|
|
|
566 {
|
|
|
567 list = null;
|
|
|
568 return ;
|
|
|
569 }
|
|
|
570 else
|
|
|
571 list = n;
|
|
|
572 }
|
|
|
573 p = n;
|
|
|
574 }
|
|
|
575 }
|
|
|
576
|
|
|
577
|
|
|
578 // helper methods
|
|
|
579
|
|
|
580 /**
|
|
|
581 * return the first cell, or throw exception if empty
|
|
|
582 **/
|
|
|
583 private final CLCellT firstCell()
|
|
|
584 {
|
|
|
585 if (list !is null)
|
|
|
586 return list;
|
|
|
587
|
|
|
588 checkIndex(0);
|
|
|
589 return null; // not reached!
|
|
|
590 }
|
|
|
591
|
|
|
592 /**
|
|
|
593 * return the last cell, or throw exception if empty
|
|
|
594 **/
|
|
|
595 private final CLCellT lastCell()
|
|
|
596 {
|
|
|
597 if (list !is null)
|
|
|
598 return list.prev();
|
|
|
599
|
|
|
600 checkIndex(0);
|
|
|
601 return null; // not reached!
|
|
|
602 }
|
|
|
603
|
|
|
604 /**
|
|
|
605 * return the index'th cell, or throw exception if bad index
|
|
|
606 **/
|
|
|
607 private final CLCellT cellAt(int index)
|
|
|
608 {
|
|
|
609 checkIndex(index);
|
|
|
610 return list.nth(index);
|
|
|
611 }
|
|
|
612
|
|
|
613 /**
|
|
|
614 * helper for remove/exclude
|
|
|
615 **/
|
|
|
616 private final void remove_(T element, bool allOccurrences)
|
|
|
617 {
|
|
|
618 if (!isValidArg(element) || list is null)
|
|
|
619 return;
|
|
|
620
|
|
|
621 CLCellT p = list;
|
|
|
622 for (;;)
|
|
|
623 {
|
|
|
624 CLCellT n = p.next();
|
|
|
625 if (p.element() == (element))
|
|
|
626 {
|
|
|
627 decCount();
|
|
|
628 p.unlink();
|
|
|
629 if (p is list)
|
|
|
630 {
|
|
|
631 if (p is n)
|
|
|
632 {
|
|
|
633 list = null;
|
|
|
634 break;
|
|
|
635 }
|
|
|
636 else
|
|
|
637 list = n;
|
|
|
638 }
|
|
|
639
|
|
|
640 if (! allOccurrences)
|
|
|
641 break;
|
|
|
642 else
|
|
|
643 p = n;
|
|
|
644 }
|
|
|
645 else
|
|
|
646 if (n is list)
|
|
|
647 break;
|
|
|
648 else
|
|
|
649 p = n;
|
|
|
650 }
|
|
|
651 }
|
|
|
652
|
|
|
653
|
|
|
654 /**
|
|
|
655 * helper for replace *
|
|
|
656 **/
|
|
|
657 private final void replace_(T oldElement, T newElement, bool allOccurrences)
|
|
|
658 {
|
|
|
659 if (!isValidArg(oldElement) || list is null)
|
|
|
660 return;
|
|
|
661
|
|
|
662 CLCellT p = list;
|
|
|
663 do {
|
|
|
664 if (p.element() == (oldElement))
|
|
|
665 {
|
|
|
666 checkElement(newElement);
|
|
|
667 incVersion();
|
|
|
668 p.element(newElement);
|
|
|
669 if (! allOccurrences)
|
|
|
670 return;
|
|
|
671 }
|
|
|
672 p = p.next();
|
|
|
673 } while (p !is list);
|
|
|
674 }
|
|
|
675
|
|
|
676 // ImplementationCheckable methods
|
|
|
677
|
|
|
678 /**
|
|
|
679 * Implements tango.util.collection.model.View.View.checkImplementation.
|
|
|
680 * See_Also: tango.util.collection.model.View.View.checkImplementation
|
|
|
681 **/
|
|
|
682
|
|
|
683 public override void checkImplementation()
|
|
|
684 {
|
|
|
685 super.checkImplementation();
|
|
|
686
|
|
|
687 assert(((count is 0) is (list is null)));
|
|
|
688 assert((list is null || list._length() is count));
|
|
|
689
|
|
|
690 if (list is null)
|
|
|
691 return;
|
|
|
692
|
|
|
693 int c = 0;
|
|
|
694 CLCellT p = list;
|
|
|
695 do {
|
|
|
696 assert(p.prev().next() is p);
|
|
|
697 assert(p.next().prev() is p);
|
|
|
698 assert(allows(p.element()));
|
|
|
699 assert(instances(p.element()) > 0);
|
|
|
700 assert(contains(p.element()));
|
|
|
701 p = p.next();
|
|
|
702 ++c;
|
|
|
703 } while (p !is list);
|
|
|
704
|
|
|
705 assert(c is count);
|
|
|
706 }
|
|
|
707
|
|
|
708
|
|
|
709 /***********************************************************************
|
|
|
710
|
|
|
711 opApply() has migrated here to mitigate the virtual call
|
|
|
712 on method get()
|
|
|
713
|
|
|
714 ************************************************************************/
|
|
|
715
|
|
|
716 static class CellIterator(T) : AbstractIterator!(T)
|
|
|
717 {
|
|
|
718 private CLCellT cell;
|
|
|
719
|
|
|
720 public this (CircularSeq seq)
|
|
|
721 {
|
|
|
722 super (seq);
|
|
|
723 cell = seq.list;
|
|
|
724 }
|
|
|
725
|
|
|
726 public final T get()
|
|
|
727 {
|
|
|
728 decRemaining();
|
|
|
729 auto v = cell.element();
|
|
|
730 cell = cell.next();
|
|
|
731 return v;
|
|
|
732 }
|
|
|
733
|
|
|
734 int opApply (int delegate (inout T value) dg)
|
|
|
735 {
|
|
|
736 int result;
|
|
|
737
|
|
|
738 for (auto i=remaining(); i--;)
|
|
|
739 {
|
|
|
740 auto value = get();
|
|
|
741 if ((result = dg(value)) != 0)
|
|
|
742 break;
|
|
|
743 }
|
|
|
744 return result;
|
|
|
745 }
|
|
|
746 }
|
|
|
747 }
|
|
|
748
|
|
|
749
|
|
|
750
|
|
|
751 debug (Test)
|
|
|
752 {
|
|
|
753 import tango.io.Console;
|
|
|
754
|
|
|
755 void main()
|
|
|
756 {
|
|
|
757 auto array = new CircularSeq!(char[]);
|
|
|
758 array.append ("foo");
|
|
|
759 array.append ("bar");
|
|
|
760 array.append ("wumpus");
|
|
|
761
|
|
|
762 foreach (value; array.elements) {}
|
|
|
763
|
|
|
764 auto elements = array.elements();
|
|
|
765 while (elements.more)
|
|
|
766 auto v = elements.get();
|
|
|
767
|
|
|
768 foreach (value; array)
|
|
|
769 Cout (value).newline;
|
|
|
770
|
|
|
771 array.checkImplementation();
|
|
|
772 }
|
|
|
773 }
|
