Mercurial > projects > ldc

comparison tango/tango/util/collection/LinkSeq.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
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