Implement slicing for the vector

1 files changed, 495 insertions, 186 deletions

diff --git a/source/tanya/container/vector.d b/source/tanya/container/vector.d
index 44295f8..2648363 100644
--- a/source/tanya/container/vector.d
+++ b/source/tanya/container/vector.d
@@ -10,22 +10,12 @@
  */  
 module tanya.container.vector;
 
+import std.algorithm.comparison;
+import std.traits;
 import tanya.memory;
 
 /**
- * One dimensional array. It allocates automatically if needed.
- *
- * If you assign a value:
- * ---
- * auto v = make!(Vector!int)(theAllocator);
- * int value = 5;
- *
- * v[1000] = value;
- *
- * dispose(theAllocator, v);
- * ---
- * it will allocate not only for one, but for 1000 elements. So this
- * implementation is more suitable for sequential data with random access.
+ * One dimensional array.
  *
  * Params:
  * 	T = Content type.
@@ -33,27 +23,218 @@ import tanya.memory;
 class Vector(T)
 {
 	/**
-	 * Creates a new $(D_PSYMBOL Vector).
+	 * Defines the container's primary range.
+	 */
+	struct Range(V)
+	{
+		private V[1] data;
+
+		private @property ref inout(V) outer() inout
+		{
+			return data[0];
+		}
+
+		private size_t start, end;
+
+		invariant
+		{
+			assert(start <= end);
+		}
+
+		private alias ElementType = typeof(data[0].vector[0]);
+
+		private this(V data, in size_t a, in size_t b)
+		{
+			this.data = data;
+			start = a;
+			end = b;
+		}
+
+		@property Range save()
+		{
+			return this;
+		}
+
+		@property bool empty() const
+		{
+			return start >= end;
+		}
+
+		@property size_t length() const
+		{
+			return end - start;
+		}
+
+		alias opDollar = length;
+
+		@property ref inout(ElementType) front() inout
+		in
+		{
+			assert(!empty);
+		}
+		body
+		{
+			return outer[start];
+		}
+
+		@property ref inout(ElementType) back() inout
+		in
+		{
+			assert(!empty);
+		}
+		body
+		{
+			return outer[end - 1];
+		}
+
+		void popFront()
+		in
+		{
+			assert(!empty);
+		}
+		body
+		{
+			++start;
+		}
+
+		void popBack()
+		in
+		{
+			assert(!empty);
+		}
+		body
+		{
+			--end;
+		}
+
+		ref inout(ElementType) opIndex(in size_t i) inout
+		in
+		{
+			assert(start + i < end);
+		}
+		body
+		{
+			return outer[start + i];
+		}
+
+		Range opIndex()
+		{
+			return typeof(return)(outer, start, end);
+		}
+
+		Range opSlice(in size_t i, in size_t j)
+		in
+		{
+			assert(i <= j);
+			assert(start + j <= end);
+		}
+		body
+		{
+			return typeof(return)(outer, start + i, start + j);
+		}
+
+		Range!(const(V)) opIndex() const
+		{
+			return typeof(return)(outer, start, end);
+		}
+
+		Range!(const(V)) opSlice(in size_t i, in size_t j) const
+		in
+		{
+			assert(i <= j);
+			assert(start + j <= end);
+		}
+		body
+		{
+			return typeof(return)(outer, start + i, start + j);
+		}
+
+		static if (isMutable!V)
+		{
+			Range opIndexAssign(in ElementType value)
+			in
+			{
+				assert(end <= outer.length);
+			}
+			body
+			{
+				return outer[start .. end] = value;
+			}
+
+			Range opSliceAssign(in ElementType value, in size_t i, in size_t j)
+			in
+			{
+				assert(start + j <= end);
+			}
+			body
+			{
+				return outer[start + i .. start + j] = value;
+			}
+
+			Range opSliceAssign(in Range!Vector value, in size_t i, in size_t j)
+			in
+			{
+				assert(length == value.length);
+			}
+			body
+			{
+				return outer[start + i .. start + j] = value;
+			}
+
+			Range opSliceAssign(in T[] value, in size_t i, in size_t j)
+			in
+			{
+				assert(j - i == value.length);
+			}
+			body
+			{
+				return outer[start + i .. start + j] = value;
+			}
+		}
+	}
+
+	/**
+	 * Creates an empty $(D_PSYMBOL Vector).
 	 *
 	 * Params:
-	 * 	length    = Initial length.
 	 * 	allocator = The allocator should be used for the element
 	 * 	            allocations.
 	 */
-	this(size_t length, IAllocator allocator = theAllocator)
+	this(IAllocator allocator = theAllocator)
 	{
 		this.allocator = allocator;
-		vector = makeArray!T(allocator, length);
 	}
 
-	/// Ditto.
-	this(IAllocator allocator = theAllocator)
+	/**
+	 * Creates a new $(D_PSYMBOL Vector).
+	 *
+	 * Params:
+	 *  U      = Variadic template for the constructor parameters.
+	 * 	params = Values to initialize the array with. The last parameter can
+	 * 	         be an allocator, if not, $(D_PSYMBOL theAllocator) is used.
+	 */
+	this(U...)(U params)
 	{
-		this(0, allocator);
+		static if (isImplicitlyConvertible!(typeof(params[$ - 1]), IAllocator))
+		{
+			allocator = params[$ - 1];
+			auto values = params[0 .. $ - 1];
+		}
+		else
+		{
+			allocator = theAllocator;
+			alias values = params;
+		}
+
+		resizeArray!T(allocator, vector, values.length);
+		foreach (i, v; values)
+		{
+			vector[i] = v;
+		}
 	}
 
 	/**
-	 * Removes all elements from the vector.
+	 * Destroys this $(D_PSYMBOL Vector).
 	 */
 	~this()
 	{
@@ -61,6 +242,23 @@ class Vector(T)
 	}
 
 	/**
+	 * Removes all elements.
+	 */
+	void clear()
+	{
+		resizeArray!T(allocator, vector, 0);
+	}
+
+	///
+	unittest
+	{
+		auto v = theAllocator.make!(Vector!int)(18, 20, 15);
+
+		v.clear();
+		assert(v.length == 0);
+	}
+
+	/**
 	 * Returns: Vector length.
 	 */
 	@property size_t length() const
@@ -68,95 +266,134 @@ class Vector(T)
 		return vector.length;
 	}
 
+	/// Ditto.
+	size_t opDollar() const
+	{
+		return length;
+	}
+
 	/**
-	 * Expans/shrinks the vector.
+	 * Expands/shrinks the vector.
 	 *
 	 * Params:
 	 * 	length = New length.
 	 */
-	@property void length(size_t length)
+	@property void length(in size_t length)
 	{
 		resizeArray!T(allocator, vector, length);
 	}
 
-    ///
-    unittest
-    {
-        auto v = make!(Vector!int)(theAllocator);
-
-        v.length = 5;
-        assert(v.length == 5);
+	///
+	unittest
+	{
+		auto v = theAllocator.make!(Vector!int);
 
-        v.length = 7;
-        assert(v.length == 7);
+		v.length = 5;
+		assert(v.length == 5);
 
-        v.length = 0;
-        assert(v.length == 0);
+		v.length = 7;
+		assert(v.length == 7);
 
-        dispose(theAllocator, v);
-    }
+		v.length = 0;
+		assert(v.length == 0);
+	}
 
 	/**
 	 * Returns: $(D_KEYWORD true) if the vector is empty.
 	 */
 	@property bool empty() const
 	{
-		return length == 0;
+		return vector.length == 0;
 	}
 
-	static if (isFinalizable!T)
+	/**
+	 * Removes $(D_PARAM howMany) elements from the vector.
+	 *
+	 * This method doesn't fail if it could not remove $(D_PARAM howMany)
+	 * elements. Instead, if $(D_PARAM howMany) is greater than the vector
+	 * length, all elements are removed.
+	 *
+	 * Params:
+	 * 	howMany = How many elements should be removed.
+	 *
+	 * Returns: The number of elements removed
+	 */
+	size_t removeBack(in size_t howMany)
 	{
-		/**
-		 * Removes an elements from the vector.
-		 *
-		 * Params:
-		 * 	pos = Element index.
-		 */
-		void remove(size_t pos)
+		immutable toRemove = min(howMany, length);
+
+		static if (hasElaborateDestructor!T)
 		{
-			auto el = vector[pos];
-			dispose(allocator, el);
+			foreach (ref e; vector[$ - toRemove ..$])
+			{
+				allocator.dispose(e);
+			}
 		}
+		length = length - toRemove;
+
+		return toRemove;
+	}
+
+	///
+	unittest
+	{
+		auto v = theAllocator.make!(Vector!int)(5, 18, 17);
+
+		assert(v.removeBack(0) == 0);
+		assert(v.removeBack(2) == 2);
+		assert(v.removeBack(3) == 1);
+		assert(v.removeBack(3) == 0);
+
+		theAllocator.dispose(v);
 	}
 
 	/**
-	 * Assigns a value. Allocates if needed.
+	 * Assigns a value to the element with the index $(D_PARAM pos).
 	 *
 	 * Params:
 	 * 	value = Value.
 	 *
 	 * Returns: Assigned value.
+	 *
+	 * Precondition: $(D_INLINECODE length > pos)
 	 */
-	T opIndexAssign(T value, size_t pos)
+	T opIndexAssign(in T value, in size_t pos)
+	in
+	{
+		assert(length > pos);
+	}
+	body
 	{
-		if (pos >= length)
-		{
-			resizeArray!T(allocator, vector, pos + 1);
-		}
 		return vector[pos] = value;
 	}
 
+	/// Ditto.
+	Range!Vector opIndexAssign(in T value)
+	{
+		vector[0..$] = value;
+		return opIndex();
+	}
+
 	///
 	unittest
 	{
-        auto v = make!(Vector!int)(theAllocator);
-        int[2] values = [5, 15];
+		auto v1 = theAllocator.make!(Vector!int)(12, 1, 7);
 
-		assert(v.length == 0);
-		v[1] = values[0];
-		assert(v.length == 2);
-		v[3] = values[0];
-		assert(v.length == 4);
-		v[4] = values[1];
-		assert(v.length == 5);
+		v1[] = 3;
+		assert(v1[0] == 3);
+		assert(v1[1] == 3);
+		assert(v1[2] == 3);
 
-        dispose(theAllocator, v);
+		theAllocator.dispose(v1);
 	}
 
+
 	/**
 	 * Returns: The value on index $(D_PARAM pos).
+	 *
+	 * Precondition: $(D_INLINECODE length > pos)
 	 */
-	ref T opIndex(in size_t pos)
+	ref inout(T) opIndex(in size_t pos) inout
 	in
 	{
 		assert(length > pos);
@@ -169,19 +406,55 @@ class Vector(T)
 	///
 	unittest
 	{
-        auto v = make!(Vector!int)(theAllocator);
-        int[2] values = [5, 15];
+		auto v = theAllocator.make!(Vector!int)(6, 123, 34, 5);
+
+		assert(v[0] == 6);
+		assert(v[1] == 123);
+		assert(v[2] == 34);
+		assert(v[3] == 5);
+
+		theAllocator.dispose(v);
+	}
+
+	/**
+	 * Comparison for equality.
+	 *
+	 * Params:
+	 * 	o = The vector to compare with.
+	 *
+	 * Returns: $(D_KEYWORD true) if the vectors are equal, $(D_KEYWORD false)
+	 *          otherwise.
+	 */
+	override bool opEquals(Object o)
+	{
+		auto v = cast(Vector) o;
+
+		return v is null ? super.opEquals(o) : vector == v.vector;
+	}
+
+	///
+	unittest
+	{
+		auto v1 = theAllocator.make!(Vector!int);
+		auto v2 = theAllocator.make!(Vector!int);
+
+		assert(v1 == v2);
+
+		v1.length = 1;
+		v2.length = 2;
+		assert(v1 != v2);
+
+		v1.length = 2;
+		v1[0] = v2[0] = 2;
+		v1[1] = 3;
+		v2[1] = 4;
+		assert(v1 != v2);
 
-		v[1] = values[0];
-		assert(v[1] is values[0]);
-		v[3] = values[0];
-		assert(v[3] is values[0]);
-		v[4] = values[1];
-		assert(v[4] is values[1]);
-		v[0] = values[1];
-		assert(v[0] is values[1]);
+		v2[1] = 3;
+		assert(v1 == v2);
 
-        dispose(theAllocator, v);
+		theAllocator.dispose(v1);
+		theAllocator.dispose(v2);
 	}
 
 	/**
@@ -190,7 +463,7 @@ class Vector(T)
 	 * Params:
 	 * 	dg = $(D_KEYWORD foreach) body.
 	 */
-	int opApply(int delegate(ref T) dg)
+	int opApply(scope int delegate(ref T) dg)
 	{
 		int result;
 
@@ -207,7 +480,7 @@ class Vector(T)
 	}
 
 	/// Ditto.
-	int opApply(int delegate(ref size_t i, ref T) dg)
+	int opApply(scope int delegate(ref size_t i, ref T) dg)
 	{
 		int result;
 
@@ -226,183 +499,217 @@ class Vector(T)
 	///
 	unittest
 	{
-        auto v = make!(Vector!int)(theAllocator, 1);
-        int[3] values = [5, 15, 8];
+		auto v = theAllocator.make!(Vector!int)(5, 15, 8);
 
-        v[0] = values[0];
-        v[1] = values[1];
-        v[2] = values[2];
-
-		int i;
-		foreach (e; v)
+		size_t i;
+		foreach (j, ref e; v)
 		{
-			assert(i != 0 || e is values[0]);
-			assert(i != 1 || e is values[1]);
-			assert(i != 2 || e is values[2]);
-			++i;
+			i = j;
 		}
+		assert(i == 2);
 
 		foreach (j, e; v)
 		{
-			assert(j != 0 || e is values[0]);
-			assert(j != 1 || e is values[1]);
-			assert(j != 2 || e is values[2]);
+			assert(j != 0 || e == 5);
+			assert(j != 1 || e == 15);
+			assert(j != 2 || e == 8);
 		}
-
-        dispose(theAllocator, v);
-	}
-
-	/**
-	 * Sets the first element. Allocates if the vector is empty.
-     *
-     * Params:
-     *  x = New element.
-     */
-	@property void front(ref T x)
-	{
-		this[0] = x;
+		theAllocator.dispose(v);
 	}
 
 	/**
 	 * Returns: The first element.
-     */
+	 *
+	 * Precondition: $(D_INLINECODE length > 0)
+	 */
 	@property ref inout(T) front() inout
-    in
+	in
 	{
-		assert(!empty);
+		assert(vector.length > 0);
 	}
 	body
 	{
 		return vector[0];
 	}
 
-    ///
-    unittest
-    {
-        auto v = make!(Vector!int)(theAllocator, 1);
-        int[2] values = [5, 15];
+	///
+	unittest
+	{
+		auto v = theAllocator.make!(Vector!int)(5);
 
-        v.front = values[0];
-        assert(v.front == 5);
+		assert(v.front == 5);
 
-        v.front = values[1];
-        assert(v.front == 15);
+		v.length = 2;
+		v[1] = 15;
+		assert(v.front == 5);
 
-        dispose(theAllocator, v);
-    }
+		theAllocator.dispose(v);
+	}
 
 	/**
-	 * Move position to the next element.
+	 * Returns: The last element.
 	 *
-	 * Returns: $(D_KEYWORD this).
+	 * Precondition: $(D_INLINECODE length > 0)
 	 */
-	typeof(this) popFront()
+	@property ref inout(T) back() inout
 	in
 	{
-		assert(!empty);
+		assert(vector.length > 0);
 	}
 	body
 	{
-		vector[0 .. $ - 1] = vector[1..$];
-		resizeArray(allocator, vector, length - 1);
-		return this;
+		return vector[$ - 1];
 	}
 
 	///
 	unittest
 	{
-        auto v = make!(Vector!int)(theAllocator, 1);
-        int[2] values = [5, 15];
+		auto v = theAllocator.make!(Vector!int)(5);
 
-        v[0] = values[0];
-        v[1] = values[1];
-        assert(v.front is values[0]);
-        assert(v.length == 2);
-		v.popFront();
-        assert(v.front is values[1]);
-        assert(v.length == 1);
-		v.popFront();
-        assert(v.empty);
+		assert(v.back == 5);
 
-        dispose(theAllocator, v);
+		v.length = 2;
+		v[1] = 15;
+		assert(v.back == 15);
+
+		theAllocator.dispose(v);
 	}
 
 	/**
-	 * Sets the last element. Allocates if the vector is empty.
-     *
-     * Params:
-     *  x = New element.
-     */
-	@property void back(ref T x)
+	 * Returns: A range that iterates over elements of the container, in
+	 *          forward order.
+	 */
+	Range!Vector opIndex()
+	{
+		return typeof(return)(this, 0, length);
+	}
+
+	/// Ditto.
+	Range!(const Vector) opIndex() const
+	{
+		return typeof(return)(this, 0, length);
+	}
+
+	/// Ditto.
+	Range!(immutable Vector) opIndex() immutable
 	{
-		vector[empty ? 0 : $ - 1] = x;
+		return typeof(return)(this, 0, length);
 	}
 
 	/**
-	 * Returns: The last element.
-     */
-	@property ref inout(T) back() inout
-    in
+	 * Params:
+	 * 	i = Slice start.
+	 * 	j = Slice end.
+	 *
+	 * Returns: A range that iterates over elements of the container from
+	 *          index $(D_PARAM i) up to (excluding) index $(D_PARAM j).
+	 *
+	 * Precondition: $(D_INLINECODE i <= j && j <= length)
+	 */
+	Range!Vector opSlice(in size_t i, in size_t j)
+	in
 	{
-		assert(!empty);
+		assert(i <= j);
+		assert(j <= length);
 	}
 	body
 	{
-		return vector[$ - 1];
+		return typeof(return)(this, i, j);
 	}
 
-    ///
-    unittest
-    {
-        auto v = make!(Vector!int)(theAllocator, 1);
-        int[2] values = [5, 15];
-
-        v.back = values[0];
-        assert(v.back == 5);
-
-        v.back = values[1];
-        assert(v.back == 15);
+	/// Ditto.
+	Range!(const Vector) opSlice(in size_t i, in size_t j) const
+	in
+	{
+		assert(i <= j);
+		assert(j <= length);
+	}
+	body
+	{
+		return typeof(return)(this, i, j);
+	}
 
-        dispose(theAllocator, v);
-    }
+	/// Ditto.
+	Range!(immutable Vector) opSlice(in size_t i, in size_t j) immutable
+	in
+	{
+		assert(i <= j);
+		assert(j <= length);
+	}
+	body
+	{
+		return typeof(return)(this, i, j);
+	}
 
 	/**
-	 * Move position to the previous element.
+	 * Slicing assignment.
+	 *
+	 * Params:
+	 * 	value = New value.
+	 * 	i     = Slice start.
+	 * 	j     = Slice end.
 	 *
-	 * Returns: $(D_KEYWORD this).
+	 * Returns: Assigned value.
+	 *
+	 * Precondition: $(D_INLINECODE i <= j && j <= length);
+	 *               The lenghts of the ranges and slices match.
 	 */
-	typeof(this) popBack()
+	Range!Vector opSliceAssign(in T value, in size_t i, in size_t j)
 	in
 	{
-		assert(!empty);
+		assert(i <= j);
+		assert(j <= length);
 	}
 	body
 	{
-		resizeArray(allocator, vector, length - 1);
-		return this;
+		vector[i .. j] = value;
+		return opSlice(i, j);
+	}
+
+	/// Ditto.
+	Range!Vector opSliceAssign(in Range!Vector value, in size_t i, in size_t j)
+	in
+	{
+		assert(j - i == value.length);
+	}
+	body
+	{
+		vector[i .. j] = value.outer.vector[value.start .. value.end];
+		return opSlice(i, j);
+	}
+
+	/// Ditto.
+	Range!Vector opSliceAssign(in T[] value, in size_t i, in size_t j)
+	in
+	{
+		assert(j - i == value.length);
+	}
+	body
+	{
+		vector[i .. j] = value;
+		return opSlice(i, j);
 	}
 
 	///
 	unittest
 	{
-        auto v = make!(Vector!int)(theAllocator, 1);
-        int[2] values = [5, 15];
+		auto v1 = theAllocator.make!(Vector!int)(3, 3, 3);
+		auto v2 = theAllocator.make!(Vector!int)(1, 2);
+
+		v1[0..2] = 286;
+		assert(v1[0] == 286);
+		assert(v1[1] == 286);
+		assert(v1[2] == 3);
 
-        v[0] = values[0];
-        v[1] = values[1];
-        assert(v.back is values[1]);
-        assert(v.length == 2);
-		v.popBack();
-        assert(v.back is values[0]);
-        assert(v.length == 1);
-		v.popBack();
-        assert(v.empty);
+		v2[0..$] = v1[1..3];
+		assert(v2[0] == 286);
+		assert(v2[1] == 3);
 
-        dispose(theAllocator, v);
+		theAllocator.dispose(v2);
+		theAllocator.dispose(v1);
 	}
 
-	/// Container.
-	protected T[] vector;
+	private T[] vector;
 
 	private IAllocator allocator;
 }
@@ -410,7 +717,9 @@ class Vector(T)
 ///
 unittest
 {
-	auto v = make!(Vector!int)(theAllocator);
+	auto v = theAllocator.make!(Vector!int)(5, 15, 8);
 
-	dispose(theAllocator, v);
+	assert(v.front == 5);
+	assert(v[1] == 15);
+	assert(v.back == 8);
 }