Mercurial > projects > ldc

comparison tango/tango/util/collection/CircularSeq.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: 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 }