Vector.v3

// Copyright 2010 Google Inc. All rights reserved.
// See LICENSE for details of Apache 2.0 license.

// A utility class which represents an efficient, growable, appendable array
class Vector<T> {
	var array: Array<T>;
	var length: int;

	// Get the element at {index}.
	def [index: int] -> T {
		return array[index];
	}
	// Update the element at {index} to be {e}.
	def [index: int] = e: T {
		array[index] = e;
	}
	// Get the element at {index}, returning the default value for <T> if out of bounds.
	def get(index: int) -> T {
		return if(index >= 0 && index < length, array[index]);
	}
	// Set the element at {index} to {e}, growing if necessary.
	def set(index: int, e: T) -> this {
		if (index < 0) return;
		grow(index + 1);
		array[index] = e;
		if (index >= length) length = index + 1;
	}
	// Add the element {e} to the end of this vector.
	def put(e: T) -> this {
		var a = array, s = length;
		if (a == null) array = a = Array<T>.new(s + 10);
		else if (s >= a.length) array = a = Arrays.grow(a, a.length + 10 + s);
		a[s] = e;
		length = s + 1;
	}
	// Add all the elements in {array} to the end of this vector.
	def puta(array: Array<T>) -> this {
		if (array != null) putk(array, 0, array.length);
	}
	// Add the elements from the given range in the array to the end of this vector.
	// #deprecated: use {Vector.putr} instead
	def putk(a: Array<T>, start: int, end: int) -> this {
		putr(a[start ... end]);
	}
	// Add the elements from the range {r} to the end of this vector.
	def putr(r: Range<T>) -> this {
		var curlen = length, rlen = r.length, newlen = curlen + rlen;
		if (array == null) array = Array<T>.new(newlen);
		else if (newlen > array.length) grow(curlen + newlen);

		var v = array[curlen ..+ rlen];
		for (i < rlen) v[i] = r[i];
		length = newlen;
	}
	// Add {v} {n} times to this vector.
	def putn(v: T, n: int) -> this {
		var max = length + n;
		grow(max);
		for (i = length; i < max; i++) array[i] = v;
		length += n;
	}
	// Add all of the elements from {v} to the end of this vector.
	def putv(v: Vector<T>) -> this {
		if (v.array != null) putk(v.array, 0, v.length);
	}
	// Apply the function {f} to each element in this vector.
	def apply(f: T -> void) {
		var a = array;
		if (a != null) {
			var max = length, len = a.length;
			for (i < len) {
				if (i >= max) return;
				f(a[i]);
			}
		}
	}
	// Reverse the elements of this vector in-place.
	def reverse() -> this {
		if (array == null) return;
		Ranges.reverse(array[0 ... length]);
	}
	// Grow the internal storage of this vector to the new length {nlength}.
	def grow(nlength: int) -> this {
		if (array == null) array = Array<T>.new(nlength);
		else if (nlength > array.length) array = Arrays.grow(array, nlength);
	}
	// Copy this vector into a new, appropriately-sized array.
	def copy() -> Array<T> {
		if (array == null) return [];
		return Arrays.copy(array, Array<T>.new(length));
	}
	// Extract all elements from this vector, leaving it empty.
	// Note this is more efficient than copy() if the array is sized exactly.
	def extract() -> Array<T> {
		if (array == null) return [];
		var result = array;
		if (length != result.length) result = Arrays.copy(result, Array<T>.new(length));
		array = null;
		length = 0;
		return result;
	}
	// Send the elements of this vector to function {f}, avoiding an intermediate copy.
	// Note that it is implementation dependent if {f} is called multiple times, e.g. if
	// the internal storage is fragmented.
	def send<R>(f: Range<T> -> R) -> R {
		return if(array != null, f(array[0 ... length]));
	}
	// Clear all elements to default value and set length to {0}.
	def clear() -> this {
		length = 0;
		if (array == null) return;
		var x = array, d: T;
		for (i < x.length) x[i] = d;
	}
	// Resize this vector to be {nlength} elements.
	def resize(nlength: int) -> this {
		if (nlength > length) grow(nlength);
		length = nlength;
	}
}

// Utility methods for vectors.
component Vectors {
	// Construct a single-element vector which contains {e}.
	def of1<T>(e: T) -> Vector<T> {
		var v = Vector<T>.new();
		v.array = [e];
		v.length = 1;
		return v;
	}
	// Construction a new vector that shares the same storage as {array}.
	def ofN<T>(array: Array<T>) -> Vector<T> {
		var v = Vector<T>.new();
		v.array = array;
		v.length = array.length;
		return v;
	}
	// Use a vector as a queue and drain all elements, applying {f} to each element,
	// which may add more elements to the vector.
	def drain<T>(v: Vector<T>, pos: int, f: T -> void) -> int {
		while (pos < v.length) f(v.array[pos++]);
		return pos;
	}
	// Reset a vector to instead contain the elements in {array}, releasing any existing
	// storage in the vector.
	def overwrite<T>(v: Vector<T>, array: Array<T>) -> Vector<T> {
		v.length = array.length;
		v.array = array;
		return v;
	}
}