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