// An array-based list of Character objects.
public class MyArrayList
{
	public final int DEFAULT_SIZE = 10;
	private int size;
	private Character[] array;
	
	
	public MyArrayList()
	{
		array = new Character[DEFAULT_SIZE];
		size = 0;
	}
	
	
	public int getSize()
	{
		return size;
	}
	
	
	public void set(int index, Character c)
	{
		array[index] = c;
	}
	
	
	public String toString()
	{
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		toString(0, sb);
		sb.append("]");
		return sb.toString();
	}
	
	
	private void toString(int index, StringBuilder sb)
	{
		if (index < getSize() - 1)
		{
			sb.append(array[index] + ", ");
			toString(index + 1, sb);
		}
		else if (index < getSize())
		{
			sb.append(array[index]);
		}
	}
	
	
	/*public void add(int index, Character c)
	{
		if (index < 0 || index > getSize())
		{
			throw new IndexOutOfBoundsException();
		}
		
		// Assumes available space in array.
		if (getSize() == 0  || getSize() == index)
		{
			array[index] = c;
		}
		else
		{
			shiftTowardsEnd(index, getSize() - 1);
			array[index] = c;
		}
		size++;
	}
	*/
	
	public void add(int index, Character c)
	{
		if (index < 0 || index > getSize())
		{
			throw new IndexOutOfBoundsException();
		}

		Character[] newArray = new Character[2 * array.length];
		copyArray(array, newArray, 0);
		array = newArray;
		
		if (getSize() == 0  || getSize() == index)
		{
			array[index] = c;
		}
		else
		{
			shiftTowardsEnd(index, getSize() - 1);
			array[index] = c;
		}
		size++;
	}
	
	
	
	// Shift elements by one towards the end of the array
	// Assumes available space in array.
	private void shiftTowardsEnd(int index, int current)
	{
		if (current >= index)
		{
			array[current + 1] = array[current];
			shiftTowardsEnd(index, current - 1);
		}
	}
	
	
	private void copyArray(Character[] from, Character[] to, int index)
	{
		if (index < getSize())
		{
			to[index] = from[index];
			copyArray(from, to, index + 1);
		}
	}
	
	
	public Character remove(int index)
	{
		Character result = array[index];
		shiftTowardsStart(index + 1);
		size--;
		return result;
	}


	// Shift elements by one towards the start of the array
	private void shiftTowardsStart(int current)
	{
		array[current - 1] = array[current];
		if (current == getSize() - 1)
		{
			array[current] = null;
		}
		else
		{
			shiftTowardsStart(current + 1);
		}
	}
	
	
	public static void main(String[] args)
	{
		MyArrayList ma = new MyArrayList();
		
		System.out.println("Empty array:");
		System.out.println(ma);
		
		System.out.println("Consecutive characters:");
		ma.add(0, 'a');
		ma.add(1, new Character('b'));
		ma.add(2, 'd');
		ma.add(2, 'c');
		ma.add(4, new Character('e'));
		ma.add(5, 'f');
		System.out.println(ma);
		
		System.out.println("Remove d:");
		ma.remove(3);
		System.out.println(ma);
		
		System.out.println("Copy array:");
		ma.add(2, 's');
		ma.add(2, 's');
		ma.add(2, 's');
		ma.add(2, 's');
		ma.add(2, 's');
		ma.add(2, 's');
		ma.add(2, 's');
		ma.add(2, 's');
		ma.add(2, 's');
		ma.add(2, 's');
		System.out.println(ma);		
	}
	
}