tango.util.collection.ArraySeq

class ArraySeq(T) : SeqCollection!(T), Sortable!(T) ¶#

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

For an introduction to this package see Overview .

int minCapacity [public, static] ¶#

The minimum capacity of any non-empty buffer

T array[] array [package] ¶#

The elements, or null if no buffer yet allocated.

this() [public] ¶#

Make a new empty ArraySeq.

this(Predicate screener) [public] ¶#

Make an empty ArraySeq with given element screener

this(Predicate s, T[] b, int c) [package] ¶#

Special version of constructor needed by clone()

ArraySeq!(T) duplicate() [public, final] ¶#

Make an independent copy. The elements themselves are not cloned

int capacity() [public, final] ¶#

return the current internal buffer capacity (zero if no buffer allocated).

Returns:

capacity (always greater than or equal to size())

void capacity(int newCap) [public, final] ¶#

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:

 capacity() >= size() &&
 version() != PREV(this).version() == (capacity() != PREV(this).capacity())
 

bool contains(T element) [public, final] ¶#

Implements tango.util.collection.impl.Collection.Collection.contains Time complexity: O(n).

See Also:

tango.util.collection.impl.Collection.Collection.contains

uint instances(T element) [public, final] ¶#

Implements tango.util.collection.impl.Collection.Collection.instances Time complexity: O(n).

See Also:

tango.util.collection.impl.Collection.Collection.instances

GuardIterator!(T) elements() [public, final] ¶#

Implements tango.util.collection.impl.Collection.Collection.elements Time complexity: O(1).

See Also:

tango.util.collection.impl.Collection.Collection.elements

int opApply(int delegate (inout T value) dg) ¶#

Implements tango.util.collection.model.View.View.opApply Time complexity: O(n).

See Also:

tango.util.collection.model.View.View.opApply

T head() [public, final] ¶#

Implements tango.util.collection.model.Seq.Seq.head. Time complexity: O(1).

See Also:

tango.util.collection.model.Seq.Seq.head

T tail() [public, final] ¶#

Implements tango.util.collection.model.Seq.Seq.tail. Time complexity: O(1).

See Also:

tango.util.collection.model.Seq.Seq.tail

T get(int index) [public, final] ¶#

Implements tango.util.collection.model.Seq.Seq.get. Time complexity: O(1).

See Also:

tango.util.collection.model.Seq.Seq.get

int first(T element, int startingIndex = 0) [public, final] ¶#

Implements tango.util.collection.model.Seq.Seq.first. Time complexity: O(n).

See Also:

tango.util.collection.model.Seq.Seq.first

int last(T element, int startingIndex = 0) [public, final] ¶#

Implements tango.util.collection.model.Seq.Seq.last. Time complexity: O(n).

See Also:

tango.util.collection.model.Seq.Seq.last

ArraySeq subset(int from, int _length) [public, final] ¶#

Implements tango.util.collection.model.Seq.Seq.subseq. Time complexity: O(length).

See Also:

tango.util.collection.model.Seq.Seq.subseq

void clear() [public, final] ¶#

Implements tango.util.collection.impl.Collection.Collection.clear. Time complexity: O(1).

See Also:

tango.util.collection.impl.Collection.Collection.clear

void remove(T element) [public, final] ¶#

Implements tango.util.collection.impl.Collection.Collection.removeOneOf. Time complexity: O(n).

See Also:

tango.util.collection.impl.Collection.Collection.removeOneOf

void replace(T oldElement, T newElement) [public, final] ¶#

Implements tango.util.collection.impl.Collection.Collection.replaceOneOf Time complexity: O(n).

See Also:

tango.util.collection.impl.Collection.Collection.replaceOneOf

void replaceAll(T oldElement, T newElement) [public, final] ¶#

Implements tango.util.collection.impl.Collection.Collection.replaceAllOf. Time complexity: O(n * number of replacements).

See Also:

tango.util.collection.impl.Collection.Collection.replaceAllOf

void removeAll(T element) [public, final] ¶#

Implements tango.util.collection.impl.Collection.Collection.exclude. Time complexity: O(n * instances(element)).

See Also:

tango.util.collection.impl.Collection.Collection.exclude

T take() [public, final] ¶#

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

void sort(Comparator!(T) cmp) [public] ¶#

Implements tango.util.collection.SortableCollection.sort. Time complexity: O(n log n). Uses a quicksort-based algorithm.

See Also:

tango.util.collection.SortableCollection.sort

void prepend(T element) [public, final] ¶#

Implements tango.util.collection.impl.SeqCollection.SeqCollection.prepend. Time complexity: O(n)

See Also:

tango.util.collection.impl.SeqCollection.SeqCollection.prepend

void replaceHead(T element) [public, final] ¶#

Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceHead. Time complexity: O(1).

See Also:

tango.util.collection.impl.SeqCollection.SeqCollection.replaceHead

void removeHead() [public, final] ¶#

Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeHead. Time complexity: O(n).

See Also:

tango.util.collection.impl.SeqCollection.SeqCollection.removeHead

void append(T element) [public, final] ¶#

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

void replaceTail(T element) [public, final] ¶#

Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceTail. Time complexity: O(1).

See Also:

tango.util.collection.impl.SeqCollection.SeqCollection.replaceTail

void removeTail() [public, final] ¶#

Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeTail. Time complexity: O(1).

See Also:

tango.util.collection.impl.SeqCollection.SeqCollection.removeTail

void addAt(int index, T element) [public, final] ¶#

Implements tango.util.collection.impl.SeqCollection.SeqCollection.addAt. Time complexity: O(n).

See Also:

tango.util.collection.impl.SeqCollection.SeqCollection.addAt

void removeAt(int index) [public, final] ¶#

Implements tango.util.collection.impl.SeqCollection.SeqCollection.remove. Time complexity: O(n).

See Also:

tango.util.collection.impl.SeqCollection.SeqCollection.removeAt

void replaceAt(int index, T element) [public, final] ¶#

Implements tango.util.collection.impl.SeqCollection.SeqCollection.replaceAt. Time complexity: O(1).

See Also:

tango.util.collection.impl.SeqCollection.SeqCollection.replaceAt

void prepend(Iterator!(T) e) [public, final] ¶#

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

void append(Iterator!(T) e) [public, final] ¶#

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

void addAt(int index, Iterator!(T) e) [public, final] ¶#

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

void removeRange(int fromIndex, int toIndex) [public, final] ¶#

Implements tango.util.collection.impl.SeqCollection.SeqCollection.removeFromTo. Time complexity: O(n).

See Also:

tango.util.collection.impl.SeqCollection.SeqCollection.removeFromTo

void quickSort(T s[] s, int lo, int hi, Comparator!(T) cmp) [public, static, final] ¶#

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

T[] toArray() [public, override] ¶#

expose collection content as an array

void growBy_(int inc) [private, final] ¶#

Main method to control buffer sizing. The heuristic used for growth is:

 if out of space:
   if need less than minCapacity, grow to minCapacity
   else grow by average of requested size and minCapacity.
 

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.

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.

void insert_(int index, Iterator!(T) e) [private, final] ¶#

Utility to splice in enumerations

void checkImplementation() [public, override] ¶#

Implements tango.util.collection.model.View.View.checkImplementation.

See Also:

tango.util.collection.model.View.View.checkImplementation

class ArrayIterator(T) : AbstractIterator!(T) ¶#

opApply() has migrated here to mitigate the virtual call on method get()