/**
 * Append-only linear-access data structure containing integers. Designed for
 * high efficiency and lots of data. (Backed by an array of arrays.)
 * 
 * Not natively thread-safe.
 * 
 * @author timmc
 */
public class IntegerStack {
	private final int chunkSize;

	private int[][] data = new int[0][];
	
	private int count = 0;
	
	/**
	 * Create an integer stack with the given chunkSize.
	 * @param chunkSize  Length of int arrays.
	 */
	public IntegerStack(int chunkSize) {
		this.chunkSize = chunkSize;
		extend();
	}
	
	/**
	 * Create an integer stack with the default chunk size (just under
	 * 32 kibi-ints).
	 */
	public IntegerStack() {
		this(1024*32-10);
	}
	
	/**
	 * Grow the major array by one. (Use only when no room left in last minor.)
	 */
	private void extend() {
		int[][] longer = new int[data.length+1][];
		System.arraycopy(data, 0, longer, 0, data.length);
		longer[longer.length-1] = new int[chunkSize];
		data = longer;
	}
	
	/**
	 * Add an integer to the end of the list.
	 */
	public void add(int val) {
		if(count % chunkSize == 0) {
			extend();
		}
		data[count / chunkSize][count % chunkSize] = val;
		count++;
	}
	
	/**
	 * Create an iterator over this data structure. 
	 * @return Fresh iterator.
	 */
	public Iterator iterator() {
		return new Iterator();
	}
	
	/**
	 * Test functionality.
	 */
	public static void main(String[] args) {
		IntegerStack subject = new IntegerStack(3);
		int count = 10000;
		for(int i=0; i<count; i++) {
			subject.add(i);
		}
		Iterator iter = subject.iterator();
		for(int i=0; i<count; i++) {
			assertTrue(iter.hasNext(), "iterZ has next");
			int val = iter.next();
			if(i != val) {
				assertTrue(false, "iterZ.next() match");
			}
		}
		assertTrue(!iter.hasNext(), "iterZ done");
	}
	
	/**
	 * Throw {@link AssertionError} with given text if test is false.
	 */
	private static void assertTrue(boolean test, String name) {
		if(!test)
			throw new AssertionError(name);
	}
	
	/**
	 * Iterator for an IntegerStack. Mutation of underlying IntegerStack will
	 * be reflected in iterator.
	 * 
	 * @author timmc
	 */
	public class Iterator {
		private int cursor;
		
		/**
		 * Create a fresh iterator.
		 */
		public Iterator() {
			cursor = 0;
		}
		
		/**
		 * Returns true if {@link #next()} can be called at least once more.
		 */
		public boolean hasNext() {
			return cursor < count;
		}
		
		/**
		 * Return the current value (and advance the cursor.)
		 */
		public int next() {
			int val = data[cursor / chunkSize][cursor % chunkSize];
			cursor++;
			return val;
		}
	}
}