The Big Programming Thread - Page 816

import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.function.Function;

public class Q<E> implements Iterable<E> {
	
	public static final Function<Integer, Integer> DEFAULT_RESIZE_STRATEGY =
			length -> Math.min(length * 2, length + 1024);
	
	protected Function<Integer, Integer> resizeStrat = DEFAULT_RESIZE_STRATEGY;
	protected Object[] buffer;
	protected int head;
	protected int tail;
	protected long modCount;
	
	public Q(int capacity) {
		if (capacity <= 0) {
			throw new IllegalArgumentException("capacity <= 0; capacity="+capacity);
		}
		buffer = new Object[capacity];
	}
	
	public void setResizingStrategy(Function<Integer, Integer> strategy) {
		if (strategy == null) {
			throw new IllegalArgumentException("strategy == null");
		}
		resizeStrat = strategy;
	}
	
	public Function<Integer, Integer> getResizingStrategy() {
		return resizeStrat;
	}
	
	public int size() {
		if (tail > head) {
			return tail - head;
		}
		return head - tail;
	}
	
	public void pushAtHead(E value) {
		resizeIfNeeded();
		buffer[calculateIndex(--head)] = value;
		modCount++;
	}
	
	@SuppressWarnings("unchecked")
	public E peekAtHead() {
		throwExceptionIfEmpty();
		return (E) buffer[calculateIndex(head)];
	}
	
	@SuppressWarnings("unchecked")
	public E popAtHead() {
		throwExceptionIfEmpty();
		modCount++;
		return (E) buffer[calculateIndex(head++)];
	}
	
	public void pushAtTail(E value) {
		resizeIfNeeded();
		buffer[calculateIndex(tail++)] = value;
		modCount++;
	}
	
	@SuppressWarnings("unchecked")
	public E peekAtTail() {
		throwExceptionIfEmpty();
		return (E) buffer[calculateIndex(tail - 1)];
	}
	
	@SuppressWarnings("unchecked")
	public E popAtTail() {
		throwExceptionIfEmpty();
		modCount++;
		return (E) buffer[calculateIndex(--tail)];
	}
	
	@Override
	public Iterator<E> iterator() {
		final long modCountAtStart = modCount;
		return new Iterator<E>() {
			int current = head;
			@Override
			@SuppressWarnings("unchecked")
			public E next() {
				if (!hasNext()) {
					throw new NoSuchElementException();
				}
				if (modCountAtStart != modCount) {
					throw new ConcurrentModificationException();
				}
				return (E) buffer[calculateIndex(current++)];
			}
			@Override
			public boolean hasNext() {
				return current != tail;
			}
		};
	}
	
	protected int calculateIndex(int position) {
		int index = position % buffer.length;
		if (index < 0) {
			index += buffer.length;
		}
		return index;
	}
	
	protected void resizeIfNeeded() {
		if (size() != buffer.length) {
			return;
		}
		
		int newLength = getResizingStrategy().apply(buffer.length);
		Object[] newBuffer = new Object[newLength];
		
		if (head < 0) {
			int headIndex = calculateIndex(head);
			int headLength = buffer.length - headIndex;
			System.arraycopy(buffer, headIndex, newBuffer, 0, headLength);
			int tailIndex = calculateIndex(tail);
			System.arraycopy(buffer, 0, newBuffer, headLength, tailIndex);
		} else {
			int headLength = buffer.length - head;
			System.arraycopy(buffer, head, newBuffer, 0, headLength);
			System.arraycopy(buffer, calculateIndex(tail-1), newBuffer, headLength, head);
		}
		
		head = 0;
		tail = buffer.length;
		buffer = newBuffer;
	}
	
	protected void throwExceptionIfEmpty() {
		if (size() == 0) {
			throw new IllegalStateException("size() == 0");
		}
	}
	
	public String toDebugString() {
		StringBuilder builder = new StringBuilder();
		builder.append("[buffer=");
		builder.append(Arrays.toString(buffer));
		builder.append(", head=");
		builder.append(head);
		builder.append(", tail=");
		builder.append(tail);
		builder.append(", size=");
		builder.append(size());
		builder.append("]");
		return builder.toString();
	}
	
	@Override
	public String toString() {
		int size = size();
		if (size == 0) {
			return "[]";
		}
		if (size == 1) {
			return "["+peekAtHead()+"]";
		}
		StringBuilder sb = new StringBuilder(2 + 3 * size);
		sb.append('[');
		for (E value : this) {
			sb.append(value);
			sb.append(", ");
		}
		sb.delete(sb.length() - 2, sb.length());
		sb.append(']');
		return sb.toString();
	}
	
}

public class ThreadSafeQueue<T> {

	ArrayList<T> backingList = new ArrayList<T>()

	public synchronized T enqueue(T t) {
		backingList.add(t);
		return t;
	}
	
	public synchronized T dequeue() {
		if(backingList.isEmpty) {
			//throw some exception or return null
		}
		
		return backingList.remove(0);
	}
}