Mercurial > projects > ldc
diff tango/tango/util/collection/CircularSeq.d @ 132:1700239cab2e trunk
[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 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tango/tango/util/collection/CircularSeq.d Fri Jan 11 17:57:40 2008 +0100 @@ -0,0 +1,773 @@ +/* + File: CircularSeq.d + + Originally written by Doug Lea and released into the public domain. + Thanks for the assistance and support of Sun Microsystems Labs, Agorics + Inc, Loral, and everyone contributing, testing, and using this code. + + History: + Date Who What + 24Sep95 dl@cs.oswego.edu Create from store.d working file + 13Oct95 dl Changed protection statuses +*/ + +module tango.util.collection.CircularSeq; + +private import tango.util.collection.model.Iterator, + tango.util.collection.model.GuardIterator; + +private import tango.util.collection.impl.CLCell, + tango.util.collection.impl.SeqCollection, + tango.util.collection.impl.AbstractIterator; + + +/** + * Circular linked lists. Publically Implement only those + * methods defined in interfaces. + * author: Doug Lea +**/ +public class CircularSeq(T) : SeqCollection!(T) +{ + alias CLCell!(T) CLCellT; + + alias SeqCollection!(T).remove remove; + alias SeqCollection!(T).removeAll removeAll; + + // instance variables + + /** + * The head of the list. Null if empty + **/ + package CLCellT list; + + // constructors + + /** + * Make an empty list with no element screener + **/ + public this () + { + this(null, null, 0); + } + + /** + * Make an empty list with supplied element screener + **/ + public this (Predicate screener) + { + this(screener, null, 0); + } + + /** + * Special version of constructor needed by clone() + **/ + protected this (Predicate s, CLCellT h, int c) + { + super(s); + list = h; + count = c; + } + + /** + * Make an independent copy of the list. Elements themselves are not cloned + **/ + public final CircularSeq duplicate() + { + if (list is null) + return new CircularSeq (screener, null, 0); + else + return new CircularSeq (screener, list.copyList(), count); + } + + + // Collection methods + + /** + * Implements tango.util.collection.impl.Collection.Collection.contains + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.contains + **/ + public final bool contains(T element) + { + if (!isValidArg(element) || list is null) + return false; + return list.find(element) !is null; + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.instances + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.instances + **/ + public final uint instances(T element) + { + if (!isValidArg(element) || list is null) + return 0; + return list.count(element); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.elements + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.Collection.Collection.elements + **/ + public final GuardIterator!(T) elements() + { + return new CellIterator!(T)(this); + } + + /** + * Implements tango.util.collection.model.View.View.opApply + * Time complexity: O(n). + * See_Also: tango.util.collection.model.View.View.opApply + **/ + int opApply (int delegate (inout T value) dg) + { + auto scope iterator = new CellIterator!(T)(this); + return iterator.opApply (dg); + } + + + // Seq methods + + /** + * Implements tango.util.collection.model.Seq.Seq.head. + * Time complexity: O(1). + * See_Also: tango.util.collection.model.Seq.Seq.head + **/ + public final T head() + { + return firstCell().element(); + } + + /** + * Implements tango.util.collection.model.Seq.Seq.tail. + * Time complexity: O(1). + * See_Also: tango.util.collection.model.Seq.Seq.tail + **/ + public final T tail() + { + return lastCell().element(); + } + + /** + * Implements tango.util.collection.model.Seq.Seq.get. + * Time complexity: O(n). + * See_Also: tango.util.collection.model.Seq.Seq.get + **/ + public final T get(int index) + { + return cellAt(index).element(); + } + + /** + * Implements tango.util.collection.model.Seq.Seq.first. + * Time complexity: O(n). + * See_Also: tango.util.collection.model.Seq.Seq.first + **/ + public final int first(T element, int startingIndex = 0) + { + if (startingIndex < 0) + startingIndex = 0; + + CLCellT p = list; + if (p is null || !isValidArg(element)) + return -1; + + for (int i = 0; true; ++i) + { + if (i >= startingIndex && p.element() == (element)) + return i; + + p = p.next(); + if (p is list) + break; + } + return -1; + } + + + /** + * Implements tango.util.collection.model.Seq.Seq.last. + * Time complexity: O(n). + * See_Also: tango.util.collection.model.Seq.Seq.last + **/ + public final int last(T element, int startingIndex = 0) + { + if (!isValidArg(element) || count is 0) + return -1; + + if (startingIndex >= size()) + startingIndex = size() - 1; + + if (startingIndex < 0) + startingIndex = 0; + + CLCellT p = cellAt(startingIndex); + int i = startingIndex; + for (;;) + { + if (p.element() == (element)) + return i; + else + if (p is list) + break; + else + { + p = p.prev(); + --i; + } + } + return -1; + } + + /** + * Implements tango.util.collection.model.Seq.Seq.subseq. + * Time complexity: O(length). + * See_Also: tango.util.collection.model.Seq.Seq.subseq + **/ + public final CircularSeq subset (int from, int _length) + { + if (_length > 0) + { + checkIndex(from); + CLCellT p = cellAt(from); + CLCellT newlist = new CLCellT(p.element()); + CLCellT current = newlist; + + for (int i = 1; i < _length; ++i) + { + p = p.next(); + if (p is null) + checkIndex(from + i); // force exception + + current.addNext(p.element()); + current = current.next(); + } + return new CircularSeq (screener, newlist, _length); + } + else + return new CircularSeq (); + } + + // MutableCollection methods + + /** + * Implements tango.util.collection.impl.Collection.Collection.clear. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.Collection.Collection.clear + **/ + public final void clear() + { + list = null; + setCount(0); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.exclude. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.exclude + **/ + public final void removeAll (T element) + { + remove_(element, true); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.removeOneOf. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.removeOneOf + **/ + public final void remove (T element) + { + remove_(element, false); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.replaceOneOf + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.replaceOneOf + **/ + public final void replace (T oldElement, T newElement) + { + replace_(oldElement, newElement, false); + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.replaceAllOf. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.replaceAllOf + **/ + public final void replaceAll (T oldElement, T newElement) + { + replace_(oldElement, newElement, true); + } + + + /** + * Implements tango.util.collection.impl.Collection.Collection.take. + * Time complexity: O(1). + * takes the last element on the list. + * See_Also: tango.util.collection.impl.Collection.Collection.take + **/ + public final T take() + { + auto v = tail(); + removeTail(); + return v; + } + + + + // MutableSeq methods + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.prepend. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.prepend + **/ + public final void prepend(T element) + { + checkElement(element); + if (list is null) + list = new CLCellT(element); + else + list = list.addPrev(element); + incCount(); + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceHead. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.replaceHead + **/ + public final void replaceHead(T element) + { + checkElement(element); + firstCell().element(element); + incVersion(); + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeHead. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeHead + **/ + public final void removeHead() + { + if (firstCell().isSingleton()) + list = null; + else + { + auto n = list.next(); + list.unlink(); + list = n; + } + decCount(); + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.append. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.append + **/ + public final void append(T element) + { + if (list is null) + prepend(element); + else + { + checkElement(element); + list.prev().addNext(element); + incCount(); + } + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceTail. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.replaceTail + **/ + public final void replaceTail(T element) + { + checkElement(element); + lastCell().element(element); + incVersion(); + } + + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeTail. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeTail + **/ + public final void removeTail() + { + auto l = lastCell(); + if (l is list) + list = null; + else + l.unlink(); + decCount(); + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.addAt. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.addAt + **/ + public final void addAt(int index, T element) + { + if (index is 0) + prepend(element); + else + { + checkElement(element); + cellAt(index - 1).addNext(element); + incCount(); + } + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceAt. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.replaceAt + **/ + public final void replaceAt(int index, T element) + { + checkElement(element); + cellAt(index).element(element); + incVersion(); + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeAt. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeAt + **/ + public final void removeAt(int index) + { + if (index is 0) + removeHead(); + else + { + cellAt(index - 1).unlinkNext(); + decCount(); + } + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.prepend. + * Time complexity: O(number of elements in e). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.prepend + **/ + public final void prepend(Iterator!(T) e) + { + CLCellT hd = null; + CLCellT current = null; + + while (e.more()) + { + auto element = e.get(); + checkElement(element); + incCount(); + + if (hd is null) + { + hd = new CLCellT(element); + current = hd; + } + else + { + current.addNext(element); + current = current.next(); + } + } + + if (list is null) + list = hd; + else + if (hd !is null) + { + auto tl = list.prev(); + current.next(list); + list.prev(current); + tl.next(hd); + hd.prev(tl); + list = hd; + } + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.append. + * Time complexity: O(number of elements in e). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.append + **/ + public final void append(Iterator!(T) e) + { + if (list is null) + prepend(e); + else + { + CLCellT current = list.prev(); + while (e.more()) + { + T element = e.get(); + checkElement(element); + incCount(); + current.addNext(element); + current = current.next(); + } + } + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.addAt. + * Time complexity: O(size() + number of elements in e). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.addAt + **/ + public final void addAt(int index, Iterator!(T) e) + { + if (list is null || index is 0) + prepend(e); + else + { + CLCellT current = cellAt(index - 1); + while (e.more()) + { + T element = e.get(); + checkElement(element); + incCount(); + current.addNext(element); + current = current.next(); + } + } + } + + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeFromTo. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeFromTo + **/ + public final void removeRange (int fromIndex, int toIndex) + { + checkIndex(toIndex); + CLCellT p = cellAt(fromIndex); + CLCellT last = list.prev(); + for (int i = fromIndex; i <= toIndex; ++i) + { + decCount(); + CLCellT n = p.next(); + p.unlink(); + if (p is list) + { + if (p is last) + { + list = null; + return ; + } + else + list = n; + } + p = n; + } + } + + + // helper methods + + /** + * return the first cell, or throw exception if empty + **/ + private final CLCellT firstCell() + { + if (list !is null) + return list; + + checkIndex(0); + return null; // not reached! + } + + /** + * return the last cell, or throw exception if empty + **/ + private final CLCellT lastCell() + { + if (list !is null) + return list.prev(); + + checkIndex(0); + return null; // not reached! + } + + /** + * return the index'th cell, or throw exception if bad index + **/ + private final CLCellT cellAt(int index) + { + checkIndex(index); + return list.nth(index); + } + + /** + * helper for remove/exclude + **/ + private final void remove_(T element, bool allOccurrences) + { + if (!isValidArg(element) || list is null) + return; + + CLCellT p = list; + for (;;) + { + CLCellT n = p.next(); + if (p.element() == (element)) + { + decCount(); + p.unlink(); + if (p is list) + { + if (p is n) + { + list = null; + break; + } + else + list = n; + } + + if (! allOccurrences) + break; + else + p = n; + } + else + if (n is list) + break; + else + p = n; + } + } + + + /** + * helper for replace * + **/ + private final void replace_(T oldElement, T newElement, bool allOccurrences) + { + if (!isValidArg(oldElement) || list is null) + return; + + CLCellT p = list; + do { + if (p.element() == (oldElement)) + { + checkElement(newElement); + incVersion(); + p.element(newElement); + if (! allOccurrences) + return; + } + p = p.next(); + } while (p !is list); + } + + // ImplementationCheckable methods + + /** + * Implements tango.util.collection.model.View.View.checkImplementation. + * See_Also: tango.util.collection.model.View.View.checkImplementation + **/ + + public override void checkImplementation() + { + super.checkImplementation(); + + assert(((count is 0) is (list is null))); + assert((list is null || list._length() is count)); + + if (list is null) + return; + + int c = 0; + CLCellT p = list; + do { + assert(p.prev().next() is p); + assert(p.next().prev() is p); + assert(allows(p.element())); + assert(instances(p.element()) > 0); + assert(contains(p.element())); + p = p.next(); + ++c; + } while (p !is list); + + assert(c is count); + } + + + /*********************************************************************** + + opApply() has migrated here to mitigate the virtual call + on method get() + + ************************************************************************/ + + static class CellIterator(T) : AbstractIterator!(T) + { + private CLCellT cell; + + public this (CircularSeq seq) + { + super (seq); + cell = seq.list; + } + + public final T get() + { + decRemaining(); + auto v = cell.element(); + cell = cell.next(); + return v; + } + + int opApply (int delegate (inout T value) dg) + { + int result; + + for (auto i=remaining(); i--;) + { + auto value = get(); + if ((result = dg(value)) != 0) + break; + } + return result; + } + } +} + + + +debug (Test) +{ + import tango.io.Console; + + void main() + { + auto array = new CircularSeq!(char[]); + array.append ("foo"); + array.append ("bar"); + array.append ("wumpus"); + + foreach (value; array.elements) {} + + auto elements = array.elements(); + while (elements.more) + auto v = elements.get(); + + foreach (value; array) + Cout (value).newline; + + array.checkImplementation(); + } +}