Mercurial > projects > ldc
diff tango/tango/util/collection/ArrayBag.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/ArrayBag.d Fri Jan 11 17:57:40 2008 +0100 @@ -0,0 +1,617 @@ +/* + File: ArrayBag.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.ArrayBag; + +private import tango.core.Exception; + +private import tango.util.collection.model.GuardIterator; + +private import tango.util.collection.impl.CLCell, + tango.util.collection.impl.BagCollection, + tango.util.collection.impl.AbstractIterator; + + + +/** + * + * Linked Buffer implementation of Bags. The Bag consists of + * any number of buffers holding elements, arranged in a list. + * Each buffer holds an array of elements. The size of each + * buffer is the value of chunkSize that was current during the + * operation that caused the Bag to grow. The chunkSize() may + * be adjusted at any time. (It is not considered a version change.) + * + * <P> + * All but the final buffer is always kept full. + * When a buffer has no elements, it is released (so is + * available for garbage collection). + * <P> + * ArrayBags are good choices for collections in which + * you merely put a lot of things in, and then look at + * them via enumerations, but don't often look for + * particular elements. + * + * + author: Doug Lea + * @version 0.93 + * + * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>. +**/ + +public class ArrayBag(T) : BagCollection!(T) +{ + alias CLCell!(T[]) CLCellT; + + alias BagCollection!(T).remove remove; + alias BagCollection!(T).removeAll removeAll; + + /** + * The default chunk size to use for buffers + **/ + + public static int defaultChunkSize = 32; + + // instance variables + + /** + * The last node of the circular list of chunks. Null if empty. + **/ + + package CLCellT tail; + + /** + * The number of elements of the tail node actually used. (all others + * are kept full). + **/ + protected int lastCount; + + /** + * The chunk size to use for making next buffer + **/ + + protected int chunkSize_; + + // constructors + + /** + * Make an empty buffer. + **/ + public this () + { + this (null, 0, null, 0, defaultChunkSize); + } + + /** + * Make an empty buffer, using the supplied element screener. + **/ + + public this (Predicate s) + { + this (s, 0, null, 0, defaultChunkSize); + } + + /** + * Special version of constructor needed by clone() + **/ + protected this (Predicate s, int n, CLCellT t, int lc, int cs) + { + super (s); + count = n; + tail = t; + lastCount = lc; + chunkSize_ = cs; + } + + /** + * Make an independent copy. Does not clone elements. + **/ + + public final ArrayBag duplicate () + { + if (count is 0) + return new ArrayBag (screener); + else + { + CLCellT h = tail.copyList(); + CLCellT p = h; + + do { + T[] obuff = p.element(); + T[] nbuff = new T[obuff.length]; + + for (int i = 0; i < obuff.length; ++i) + nbuff[i] = obuff[i]; + + p.element(nbuff); + p = p.next(); + } while (p !is h); + + return new ArrayBag (screener, count, h, lastCount, chunkSize_); + } + } + + + /** + * Report the chunk size used when adding new buffers to the list + **/ + + public final int chunkSize() + { + return chunkSize_; + } + + /** + * Set the chunk size to be used when adding new buffers to the + * list during future add() operations. + * Any value greater than 0 is OK. (A value of 1 makes this a + * into very slow simulation of a linked list!) + **/ + + public final void chunkSize (int newChunkSize) + { + if (newChunkSize > 0) + chunkSize_ = newChunkSize; + else + throw new IllegalArgumentException("Attempt to set negative chunk size value"); + } + + // Collection methods + + /* + This code is pretty repetitive, but I don't know a nice way to + separate traversal logic from actions + */ + + /** + * 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) || count is 0) + return false; + + CLCellT p = tail.next(); + + for (;;) + { + T[] buff = p.element(); + bool isLast = p is tail; + + int n; + if (isLast) + n = lastCount; + else + n = buff.length; + + for (int i = 0; i < n; ++i) + { + if (buff[i] == (element)) + return true; + } + + if (isLast) + break; + else + p = p.next(); + } + return false; + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.instances + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.instances + **/ + public final uint instances(T element) + { + if (!isValidArg(element) || count is 0) + return 0; + + uint c = 0; + CLCellT p = tail.next(); + + for (;;) + { + T[] buff = p.element(); + bool isLast = p is tail; + + int n; + if (isLast) + n = lastCount; + else + n = buff.length; + + for (int i = 0; i < n; ++i) + { + if (buff[i] == (element)) + ++c; + } + + if (isLast) + break; + else + p = p.next(); + } + return c; + } + + /** + * 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 ArrayIterator!(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 ArrayIterator!(T)(this); + return iterator.opApply (dg); + } + + // 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() + { + setCount(0); + tail = null; + lastCount = 0; + } + + /** + * Implements tango.util.collection.impl.Collection.Collection.removeAll. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.Collection.Collection.removeAll + **/ + 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 least element. + * See_Also: tango.util.collection.impl.Collection.Collection.take + **/ + public final T take() + { + if (count !is 0) + { + T[] buff = tail.element(); + T v = buff[lastCount -1]; + buff[lastCount -1] = T.init; + shrink_(); + return v; + } + checkIndex(0); + return T.init; // not reached + } + + + + // MutableBag methods + + /** + * Implements tango.util.collection.MutableBag.addIfAbsent. + * Time complexity: O(n). + * See_Also: tango.util.collection.MutableBag.addIfAbsent + **/ + public final void addIf(T element) + { + if (!contains(element)) + add (element); + } + + + /** + * Implements tango.util.collection.MutableBag.add. + * Time complexity: O(1). + * See_Also: tango.util.collection.MutableBag.add + **/ + public final void add (T element) + { + checkElement(element); + + incCount(); + if (tail is null) + { + tail = new CLCellT(new T[chunkSize_]); + lastCount = 0; + } + + T[] buff = tail.element(); + if (lastCount is buff.length) + { + buff = new T[chunkSize_]; + tail.addNext(buff); + tail = tail.next(); + lastCount = 0; + } + + buff[lastCount++] = element; + } + + /** + * helper for remove/exclude + **/ + + private final void remove_(T element, bool allOccurrences) + { + if (!isValidArg(element) || count is 0) + return ; + + CLCellT p = tail; + + for (;;) + { + T[] buff = p.element(); + int i = (p is tail) ? lastCount - 1 : buff.length - 1; + + while (i >= 0) + { + if (buff[i] == (element)) + { + T[] lastBuff = tail.element(); + buff[i] = lastBuff[lastCount -1]; + lastBuff[lastCount -1] = T.init; + shrink_(); + + if (!allOccurrences || count is 0) + return ; + + if (p is tail && i >= lastCount) + i = lastCount -1; + } + else + --i; + } + + if (p is tail.next()) + break; + else + p = p.prev(); + } + } + + private final void replace_(T oldElement, T newElement, bool allOccurrences) + { + if (!isValidArg(oldElement) || count is 0 || oldElement == (newElement)) + return ; + + CLCellT p = tail.next(); + + for (;;) + { + T[] buff = p.element(); + bool isLast = p is tail; + + int n; + if (isLast) + n = lastCount; + else + n = buff.length; + + for (int i = 0; i < n; ++i) + { + if (buff[i] == (oldElement)) + { + checkElement(newElement); + incVersion(); + buff[i] = newElement; + if (!allOccurrences) + return ; + } + } + + if (isLast) + break; + else + p = p.next(); + } + } + + private final void shrink_() + { + decCount(); + lastCount--; + if (lastCount is 0) + { + if (count is 0) + clear(); + else + { + CLCellT tmp = tail; + tail = tail.prev(); + tmp.unlink(); + T[] buff = tail.element(); + lastCount = buff.length; + } + } + } + + // 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(chunkSize_ >= 0); + assert(lastCount >= 0); + assert(((count is 0) is (tail is null))); + + if (tail is null) + return ; + + int c = 0; + CLCellT p = tail.next(); + + for (;;) + { + T[] buff = p.element(); + bool isLast = p is tail; + + int n; + if (isLast) + n = lastCount; + else + n = buff.length; + + c += n; + for (int i = 0; i < n; ++i) + { + auto v = buff[i]; + assert(allows(v) && contains(v)); + } + + if (isLast) + break; + else + p = p.next(); + } + + assert(c is count); + + } + + + + /*********************************************************************** + + opApply() has migrated here to mitigate the virtual call + on method get() + + ************************************************************************/ + + static class ArrayIterator(T) : AbstractIterator!(T) + { + private CLCellT cell; + private T[] buff; + private int index; + + public this (ArrayBag bag) + { + super(bag); + cell = bag.tail; + + if (cell) + buff = cell.element(); + } + + public final T get() + { + decRemaining(); + if (index >= buff.length) + { + cell = cell.next(); + buff = cell.element(); + index = 0; + } + return buff[index++]; + } + + 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 bag = new ArrayBag!(char[]); + bag.add ("foo"); + bag.add ("bar"); + bag.add ("wumpus"); + + foreach (value; bag.elements) {} + + auto elements = bag.elements(); + while (elements.more) + auto v = elements.get(); + + foreach (value; bag) + Cout (value).newline; + + bag.checkImplementation(); + + Cout (bag).newline; + } +}