/**
 * Hoofbaby -- http://www.dsource.org/projects/hoofbaby
 * Copyright (C) 2009 Robert Fraser
 * 
 * This program is free software; you can redistribute it andor
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 */

module hoofbaby.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();
	}
}