/*******************************************************************************
 * Copyright (c) 2008-2009 Robert Fraser
 * 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *******************************************************************************/

module candy.util.array;

import tango.core.BitManip : bsr;
import tango.core.Traits : isReferenceType;
import tango.core.Memory : GC;
import tango.stdc.string : memcpy, memset;


public struct Array(T, size_t START_SIZE = 16, bool doScan = isReferenceType!(T),
                    alias Realloc = GC.realloc, alias Free = GC.free)
{
	T* arr = null;
	size_t len = 0;
	size_t cap = 0;
	
	public void opCatAssign(T v)
	{
		len++;
		if(len >= cap)
			grow(cap ? cap * 2 : START_SIZE);
		arr[len - 1] = v;
	}
	
	public void opCatAssign(T[] v)
	{
		int newlen = len + v.length;
		if(newlen > cap)
		{
			if(newlen < START_SIZE)
				grow(START_SIZE);
			else
				grow(2 << bsr(newlen + 1)); // Next power of 2
		}
		memcpy(arr + len, v.ptr, (newlen - len) * T.sizeof);
		len = newlen;
	}
	
	public void opCatAssign(Array!(T) v)
	{
		opCatAssign(v.toArray());
	}
	
	public T[] toArray()
	{
		return arr[0 .. len];
	}
	
	public size_t length()
	{
		return len;
	}
	
	public T opIndex(size_t n)
	{
		assert(n < len);
		return arr[n];
	}

	public void opIndexAssign(T v, size_t n)
	{
		assert(n < len);
		arr[n] = v;
	}
	
	public T[] opSlice()
	{
		return toArray();
	}
	
	public T[] opSlice(size_t low, size_t high)
	{
		assert(low <= high);
		assert(high < len);
		return arr[low .. high];
	}
	
	public void opSliceAssign(T v)
	{
		arr[0 .. len] = v;
	}
	
	public void opSliceAssign(T v, size_t low, size_t high)
	{
		assert(low <= high);
		assert(high < len);
		arr[low .. high] = v;
	}
	
	public void opSliceAssign(T[] v, size_t low, size_t high)
	{
		assert(low <= high);
		assert(high < len);
		assert(v.length == high - low);
		memcpy(arr + low, v.ptr, v.length * T.sizeof);
	}
	
	public void opSliceAssign(Array!(T) v, size_t low, size_t high)
	{
		opSliceAssign(v.toArray(), low, high);
	}
	
	public bool isEmpty()
	{
		return len == 0;
	}
	
	public void clear()
	{
		len = 0;
	}
	
	public void free()
	{
		if(arr)
		{
			Free(arr);
			arr = null;
		}
		len = 0;
	}
	
	public void zero()
	{
		if(arr)
		{
			memset(arr, 0, cap * T.sizeof);
			Free(arr);
			arr = null;
		}
		len = 0;
	}
	
	public void addNull()
	{
		len++;
		if(len >= cap)
			grow(cap ? cap * 2 : START_SIZE);
	}
	
	public bool contains(T elem)
	{
		for(int i = 0; i < len; i++)
			if(arr[i] == elem)
				return true;
		return false;
	}
	
	static if(doScan)
		private static const BlkAttr = 0;
	else
		private static const BlkAttr = GC.BlkAttr.NO_SCAN;
	
	private void grow(size_t sz)
	{
		arr = cast(T*) Realloc(arr, sz * T.sizeof, BlkAttr);
		static if(doScan)
		{
			memset(arr + cap, 0, (sz - cap) * T.sizeof); 
		}
		cap = sz;
	}
}

public struct Stack(T, size_t START_SIZE = 16, bool doScan = true, bool zeroOnPop = false,
                    alias ArrayType = Array, ArrayArgs...)
{
	private ArrayType!(T, START_SIZE, doScan, ArrayArgs) arr;
	
	public void pushNull()
	{
		arr.addNull();
	}
	
	public void push(T v)
	{
		arr ~= v;
	}

	public T pop()
	{
		assert(arr.len > 0);
		T ret = arr.arr[arr.len - 1];
		static if(zeroOnPop)
			arr.arr[arr.len - 1] = T.init;
		arr.len--;
		return ret;
	}
	
	public T peek()
	{
		assert(arr.len > 0);
		return arr.arr[arr.len - 1];
	}
	
	public bool isEmpty()
	{
		return arr.isEmpty();
	}
	
	public void clear()
	{
		static if(zeroOnPop)
			arr.zero();
		else
			arr.clear();
	}
	
	public bool contains(T elem)
	{
		return arr.contains(elem);
	}
	
	public T[] toArray()
	{
		return arr.toArray();
	}
}