import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;

public final class FastBlockingQueue<T> {
	@SuppressWarnings("rawtypes")
	private static final AtomicIntegerFieldUpdater<FastBlockingQueue> countUpdater
			= AtomicIntegerFieldUpdater.newUpdater(FastBlockingQueue.class, "count");
	private volatile int count;
	private final Object[] buffer;
	private final int idxMask;
	private int takeIndex;
	private int putIndex;

	public FastBlockingQueue(int bufSize) {
		if (bufSize < 2 || Integer.highestOneBit(bufSize) != bufSize)
			throw new IllegalArgumentException();
		buffer = new Object[bufSize];
		idxMask = bufSize - 1;
	}

	public boolean isEmpty() {
		return count == 0;
	}

	public int size() {
		return count;
	}

	public boolean tryPut(T p) {
		int newCount;
		Object[] buf = buffer;
		int cap = buf.length;
		synchronized (buf) {
			if (count == cap)
				return false;
			int idx = putIndex;
			buf[idx] = p;
			putIndex = idx + 1 & idxMask;
			newCount = countUpdater.incrementAndGet(this);
			if (newCount < cap)
				buf.notify();
		}
		if (newCount == 1) {
			synchronized (this) {
				notify();
			}
		}
		return true;
	}

	public void put(T p) throws InterruptedException {
		int newCount;
		Object[] buf = buffer;
		int cap = buf.length;
		synchronized (buf) {
			while (count == cap)
				buf.wait();
			int idx = putIndex;
			buf[idx] = p;
			putIndex = idx + 1 & idxMask;
			newCount = countUpdater.incrementAndGet(this);
			if (newCount < cap)
				buf.notify();
		}
		if (newCount == 1) {
			synchronized (this) {
				notify();
			}
		}
	}

	public T fastTake() throws InterruptedException {
		if (count == 0) {
			synchronized (this) {
				while (count == 0)
					wait();
			}
		}
		Object[] buf = buffer;
		int idx = takeIndex;
		@SuppressWarnings("unchecked")
		T p = (T)buf[idx];
		buf[idx] = null;
		takeIndex = idx + 1 & idxMask;
		if (countUpdater.getAndDecrement(this) == buf.length) {
			synchronized (buf) {
				buf.notify();
			}
		}
		return p;
	}

	public T tryFastTake() {
		if (count == 0)
			return null;
		Object[] buf = buffer;
		int idx = takeIndex;
		@SuppressWarnings("unchecked")
		T p = (T)buf[idx];
		buf[idx] = null;
		takeIndex = idx + 1 & idxMask;
		if (countUpdater.getAndDecrement(this) == buf.length) {
			synchronized (buf) {
				buf.notify();
			}
		}
		return p;
	}

	@SuppressWarnings("unchecked")
	public T take() throws InterruptedException {
		T p;
		int oldCount;
		synchronized (this) {
			while (count == 0)
				wait();
			int idx = takeIndex;
			p = (T)buffer[idx];
			buffer[idx] = null;
			takeIndex = idx + 1 & idxMask;
			oldCount = countUpdater.getAndDecrement(this);
			if (oldCount > 1)
				notify();
		}
		if (oldCount == buffer.length) {
			synchronized (buffer) {
				buffer.notify();
			}
		}
		return p;
	}
}