Mercurial > projects > ldc
diff tango/tango/util/collection/ArraySeq.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/ArraySeq.d Fri Jan 11 17:57:40 2008 +0100 @@ -0,0 +1,924 @@ +/* + File: ArraySeq.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 + 2Oct95 dl@cs.oswego.edu refactored from DASeq.d + 13Oct95 dl Changed protection statuses + +*/ + + +module tango.util.collection.ArraySeq; + +private import tango.util.collection.model.Iterator, + tango.util.collection.model.Sortable, + tango.util.collection.model.Comparator, + tango.util.collection.model.GuardIterator; + +private import tango.util.collection.impl.SeqCollection, + tango.util.collection.impl.AbstractIterator; + + +/** + * + * Dynamically allocated and resized Arrays. + * + * Beyond implementing its interfaces, adds methods + * to adjust capacities. The default heuristics for resizing + * usually work fine, but you can adjust them manually when + * you need to. + * + * ArraySeqs are generally like java.util.Vectors. But unlike them, + * ArraySeqs do not actually allocate arrays when they are constructed. + * Among other consequences, you can adjust the capacity `for free' + * after construction but before adding elements. You can adjust + * it at other times as well, but this may lead to more expensive + * resizing. Also, unlike Vectors, they release their internal arrays + * whenever they are empty. + * + * + author: Doug Lea + * @version 0.93 + * + * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>. + * +**/ + +public class ArraySeq(T) : SeqCollection!(T), Sortable!(T) +{ + alias SeqCollection!(T).remove remove; + alias SeqCollection!(T).removeAll removeAll; + + /** + * The minimum capacity of any non-empty buffer + **/ + + public static int minCapacity = 16; + + + // instance variables + + /** + * The elements, or null if no buffer yet allocated. + **/ + + package T array[]; + + + // constructors + + /** + * Make a new empty ArraySeq. + **/ + + public this () + { + this (null, null, 0); + } + + /** + * Make an empty ArraySeq with given element screener + **/ + + public this (Predicate screener) + { + this (screener, null, 0); + } + + /** + * Special version of constructor needed by clone() + **/ + package this (Predicate s, T[] b, int c) + { + super(s); + array = b; + count = c; + } + + /** + * Make an independent copy. The elements themselves are not cloned + **/ + + public final ArraySeq duplicate() + { + int cap = count; + if (cap is 0) + return new ArraySeq (screener, null, 0); + else + { + if (cap < minCapacity) + cap = minCapacity; + + T newArray[] = new T[cap]; + //System.copy (array[0].sizeof, array, 0, newArray, 0, count); + + newArray[0..count] = array[0..count]; + return new ArraySeq!(T)(screener, newArray, count); + } + } + + // methods introduced _in ArraySeq + + /** + * return the current internal buffer capacity (zero if no buffer allocated). + * Returns: capacity (always greater than or equal to size()) + **/ + + public final int capacity() + { + return (array is null) ? 0 : array.length; + } + + /** + * Set the internal buffer capacity to max(size(), newCap). + * That is, if given an argument less than the current + * number of elements, the capacity is just set to the + * current number of elements. Thus, elements are never lost + * by setting the capacity. + * + * @param newCap the desired capacity. + * Returns: condition: + * <PRE> + * capacity() >= size() && + * version() != PREV(this).version() == (capacity() != PREV(this).capacity()) + * </PRE> + **/ + + public final void capacity(int newCap) + { + if (newCap < count) + newCap = count; + + if (newCap is 0) + { + clear(); + } + else + if (array is null) + { + array = new T[newCap]; + incVersion(); + } + else + if (newCap !is array.length) + { + //T newArray[] = new T[newCap]; + //newArray[0..count] = array[0..count]; + //array = newArray; + array ~= new T[newCap - array.length]; + incVersion(); + } + } + + + // 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)) + return false; + + for (int i = 0; i < count; ++i) + if (array[i] == (element)) + return true; + return false; + } + + /** + * 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)) + return 0; + + uint c = 0; + for (uint i = 0; i < count; ++i) + if (array[i] == (element)) + ++c; + 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); + } + + + // 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() + { + checkIndex(0); + return array[0]; + } + + /** + * 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() + { + checkIndex(count -1); + return array[count -1]; + } + + /** + * Implements tango.util.collection.model.Seq.Seq.get. + * Time complexity: O(1). + * See_Also: tango.util.collection.model.Seq.Seq.get + **/ + public final T get(int index) + in { + checkIndex(index); + } + body + { + return array[index]; + } + + /** + * 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; + + for (int i = startingIndex; i < count; ++i) + if (array[i] == (element)) + return i; + 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 (startingIndex >= count) + startingIndex = count -1; + + for (int i = startingIndex; i >= 0; --i) + if (array[i] == (element)) + return 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 ArraySeq subset (int from, int _length) + { + if (_length > 0) + { + checkIndex(from); + checkIndex(from + _length - 1); + + T newArray[] = new T[_length]; + //System.copy (array[0].sizeof, array, from, newArray, 0, _length); + + newArray[0.._length] = array[from..from+_length]; + return new ArraySeq!(T)(screener, newArray, _length); + } + else + return new ArraySeq!(T)(screener); + } + + + // 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() + { + array = null; + setCount(0); + } + + /** + * 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 * number of replacements). + * 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.exclude. + * Time complexity: O(n * instances(element)). + * 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.take. + * Time complexity: O(1). + * Takes the rightmost element of the array. + * See_Also: tango.util.collection.impl.Collection.Collection.take + **/ + public final T take() + { + T v = tail(); + removeTail(); + return v; + } + + + // SortableCollection methods: + + + /** + * Implements tango.util.collection.SortableCollection.sort. + * Time complexity: O(n log n). + * Uses a quicksort-based algorithm. + * See_Also: tango.util.collection.SortableCollection.sort + **/ + public void sort(Comparator!(T) cmp) + { + if (count > 0) + { + quickSort(array, 0, count - 1, cmp); + incVersion(); + } + } + + + // MutableSeq methods + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.prepend. + * Time complexity: O(n) + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.prepend + **/ + public final void prepend(T element) + { + checkElement(element); + growBy_(1); + for (int i = count -1; i > 0; --i) + array[i] = array[i - 1]; + array[0] = element; + } + + /** + * 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); + array[0] = element; + incVersion(); + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeHead. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeHead + **/ + public final void removeHead() + { + removeAt(0); + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.append. + * Time complexity: normally O(1), but O(n) if size() == capacity(). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.append + **/ + public final void append(T element) + in { + checkElement (element); + } + body + { + int last = count; + growBy_(1); + array[last] = element; + } + + /** + * 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); + array[count -1] = 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() + { + checkIndex(0); + array[count -1] = T.init; + growBy_( -1); + } + + /** + * 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 count) + checkIndex(index); + + checkElement(element); + growBy_(1); + for (int i = count -1; i > index; --i) + array[i] = array[i - 1]; + array[index] = element; + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.remove. + * Time complexity: O(n). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.removeAt + **/ + public final void removeAt(int index) + { + checkIndex(index); + for (int i = index + 1; i < count; ++i) + array[i - 1] = array[i]; + array[count -1] = T.init; + growBy_( -1); + } + + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceAt. + * Time complexity: O(1). + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.replaceAt + **/ + public final void replaceAt(int index, T element) + { + checkIndex(index); + checkElement(element); + array[index] = element; + incVersion(); + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.prepend. + * Time complexity: O(n + number of elements in e) if (e + * instanceof CollectionIterator) else O(n * number of elements in e) + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.prepend + **/ + public final void prepend(Iterator!(T) e) + { + insert_(0, e); + } + + /** + * 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) + { + insert_(count, e); + } + + /** + * Implements tango.util.collection.impl.SeqCollection.SeqCollection.addAt. + * Time complexity: O(n + number of elements in e) if (e + * instanceof CollectionIterator) else O(n * number of elements in e) + * See_Also: tango.util.collection.impl.SeqCollection.SeqCollection.addAt + **/ + public final void addAt(int index, Iterator!(T) e) + { + if (index !is count) + checkIndex(index); + insert_(index, e); + } + + + /** + * 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(fromIndex); + checkIndex(toIndex); + if (fromIndex <= toIndex) + { + int gap = toIndex - fromIndex + 1; + int j = fromIndex; + for (int i = toIndex + 1; i < count; ++i) + array[j++] = array[i]; + + for (int i = 1; i <= gap; ++i) + array[count -i] = T.init; + addToCount( -gap); + } + } + + /** + * An implementation of Quicksort using medians of 3 for partitions. + * Used internally by sort. + * It is public and static so it can be used to sort plain + * arrays as well. + * @param s, the array to sort + * @param lo, the least index to sort from + * @param hi, the greatest index + * @param cmp, the comparator to use for comparing elements + **/ + + public final static void quickSort(T s[], int lo, int hi, Comparator!(T) cmp) + { + if (lo >= hi) + return; + + /* + Use median-of-three(lo, mid, hi) to pick a partition. + Also swap them into relative order while we are at it. + */ + + int mid = (lo + hi) / 2; + + if (cmp.compare(s[lo], s[mid]) > 0) + { + T tmp = s[lo]; + s[lo] = s[mid]; + s[mid] = tmp; // swap + } + + if (cmp.compare(s[mid], s[hi]) > 0) + { + T tmp = s[mid]; + s[mid] = s[hi]; + s[hi] = tmp; // swap + + if (cmp.compare(s[lo], s[mid]) > 0) + { + T tmp2 = s[lo]; + s[lo] = s[mid]; + s[mid] = tmp2; // swap + } + } + + int left = lo + 1; // start one past lo since already handled lo + int right = hi - 1; // similarly + if (left >= right) + return; // if three or fewer we are done + + T partition = s[mid]; + + for (;;) + { + while (cmp.compare(s[right], partition) > 0) + --right; + + while (left < right && cmp.compare(s[left], partition) <= 0) + ++left; + + if (left < right) + { + T tmp = s[left]; + s[left] = s[right]; + s[right] = tmp; // swap + --right; + } + else + break; + } + + quickSort(s, lo, left, cmp); + quickSort(s, left + 1, hi, cmp); + } + + /*********************************************************************** + + expose collection content as an array + + ************************************************************************/ + + override public T[] toArray () + { + return array[0..count].dup; + } + + // helper methods + + /** + * Main method to control buffer sizing. + * The heuristic used for growth is: + * <PRE> + * if out of space: + * if need less than minCapacity, grow to minCapacity + * else grow by average of requested size and minCapacity. + * </PRE> + * <P> + * For small buffers, this causes them to be about 1/2 full. + * while for large buffers, it causes them to be about 2/3 full. + * <P> + * For shrinkage, the only thing we do is unlink the buffer if it is empty. + * @param inc, the amount of space to grow by. Negative values mean shrink. + * Returns: condition: adjust record of count, and if any of + * the above conditions apply, allocate and copy into a new + * buffer of the appropriate size. + **/ + + private final void growBy_(int inc) + { + int needed = count + inc; + if (inc > 0) + { + /* heuristic: */ + int current = capacity(); + if (needed > current) + { + incVersion(); + int newCap = needed + (needed + minCapacity) / 2; + + if (newCap < minCapacity) + newCap = minCapacity; + + if (array is null) + { + array = new T[newCap]; + } + else + { + //T newArray[] = new T[newCap]; + //newArray[0..count] = array[0..count]; + //array = newArray; + array ~= new T[newCap - array.length]; + } + } + } + else + if (needed is 0) + array = null; + + setCount(needed); + } + + + /** + * Utility to splice in enumerations + **/ + + private final void insert_(int index, Iterator!(T) e) + { + if (cast(GuardIterator!(T)) e) + { + // we know size! + int inc = (cast(GuardIterator!(T)) (e)).remaining(); + int oldcount = count; + int oldversion = vershion; + growBy_(inc); + + for (int i = oldcount - 1; i >= index; --i) + array[i + inc] = array[i]; + + int j = index; + while (e.more()) + { + T element = e.get(); + if (!allows (element)) + { // Ugh. Can only do full rollback + for (int i = index; i < oldcount; ++i) + array[i] = array[i + inc]; + + vershion = oldversion; + count = oldcount; + checkElement(element); // force throw + } + array[j++] = element; + } + } + else + if (index is count) + { // next best; we can append + while (e.more()) + { + T element = e.get(); + checkElement(element); + growBy_(1); + array[count -1] = element; + } + } + else + { // do it the slow way + int j = index; + while (e.more()) + { + T element = e.get(); + checkElement(element); + growBy_(1); + + for (int i = count -1; i > j; --i) + array[i] = array[i - 1]; + array[j++] = element; + } + } + } + + private final void remove_(T element, bool allOccurrences) + { + if (! isValidArg(element)) + return; + + for (int i = 0; i < count; ++i) + { + while (i < count && array[i] == (element)) + { + for (int j = i + 1; j < count; ++j) + array[j - 1] = array[j]; + + array[count -1] = T.init; + growBy_( -1); + + if (!allOccurrences || count is 0) + return ; + } + } + } + + private final void replace_(T oldElement, T newElement, bool allOccurrences) + { + if (isValidArg(oldElement) is false || count is 0) + return; + + for (int i = 0; i < count; ++i) + { + if (array[i] == (oldElement)) + { + checkElement(newElement); + array[i] = newElement; + incVersion(); + + if (! allOccurrences) + return; + } + } + } + + /** + * Implements tango.util.collection.model.View.View.checkImplementation. + * See_Also: tango.util.collection.model.View.View.checkImplementation + **/ + public override void checkImplementation() + { + super.checkImplementation(); + assert(!(array is null && count !is 0)); + assert((array is null || count <= array.length)); + + for (int i = 0; i < count; ++i) + { + assert(allows(array[i])); + assert(instances(array[i]) > 0); + assert(contains(array[i])); + } + } + + /*********************************************************************** + + opApply() has migrated here to mitigate the virtual call + on method get() + + ************************************************************************/ + + static class ArrayIterator(T) : AbstractIterator!(T) + { + private int row; + private T[] array; + + public this (ArraySeq seq) + { + super (seq); + array = seq.array; + } + + public final T get() + { + decRemaining(); + return array[row++]; + } + + 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 ArraySeq!(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; + + auto a = array.toArray; + foreach (value; a) + Cout (value).newline; + + array.checkImplementation(); + } +}