/*
 * Written by Dawid Kurzyniec and released to the public domain, as explained
 * at http://creativecommons.org/licenses/publicdomain
 */

package edu.emory.mathcs.util.concurrent;

import java.util.*;
import edu.emory.mathcs.backport.java.util.concurrent.*;
import edu.emory.mathcs.backport.java.util.*;

/**
 * This class represents queue of objects. Data is generally stored at the
 * bottom of the queue by <code>put</code> and related operations,
 * and read from the top of the queue by <code>take</code> and related
 * operations. The <code>putAtHead</code> family of operations
 * is also provided to allow storing data at the head of the queue.
 * The underlying implementation uses an array, so no memory allocation occur
 * on queue operations apart from situations where array needs to be resized.
 * The initial and maximum capacity of the queue can be specified at the
 * construction time. The maximum capacity may be also set to "infinity",
 * in which case <code>put</code> operations will never block.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 *
 * @see BlockingQueue
 *
 */
public class DynamicArrayBlockingQueue extends AbstractQueue implements BlockingQueue {
    Object[] buf;
    int beg, end, length;
    int maxcap;

    /**
     * Creates new queue object with initial capacity of 16 and unlimited
     * maximum capacity.
     */
    public DynamicArrayBlockingQueue() {
        this(16);
    }

    /**
     * Creates new queue object with specified initial capacity and unlimited
     * maximum capacity. Initial capacity must be greater than 0, otherwise
     * <code>IllegalArgumentException</code> will be thrown.
     *
     * @param initcap initial capacity of the queue.
     *
     * @throws IllegalArgumentException if initial capacity is not greater
     *         than 0.
     */
    public DynamicArrayBlockingQueue(int initcap) {
        this(initcap, 0);
    }

    /**
     * Creates new queue object with specified initial capacity and specified
     * maximum capacity. Initial capacity must be greater than 0, otherwise
     * <code>IllegalArgumentException</code> will be thrown. Maximum
     * capacity of less than or equal to 0 indicates no limit. Otherwise if
     * the maximum capacity is positive number, it has to be greater than
     * or equal to initial capacity, or <code>IllegalArgumentException</code>
     * will be thrown.
     *
     * @param initcap initial capacity of the queue.
     * @param maxcap maximum capacity of the queue.
     *
     * @throws IllegalArgumentException if initial capacity is not greater
     *         than 0, or maximum capacity is positive number but less than
     *         initial capacity.
     */
    public DynamicArrayBlockingQueue(int initcap, int maxcap) {
        if (initcap <=0) {
            throw new IllegalArgumentException("Invalid initial capacity: " + initcap);
        }
        if (maxcap > 0 && maxcap < initcap) {
            throw new IllegalArgumentException("Invalid max capacity: " + maxcap);
        }
        buf = new Object[initcap];
        beg = end = length = 0;
        this.maxcap = maxcap;
    }

    /**
     * Returns the number of items in this queue.
     */
    public synchronized int size() {
        return length;
    }

    public int remainingCapacity() {
        if (maxcap <= 0) return Integer.MAX_VALUE;
        synchronized (this) {
            return maxcap - length;
        }
    }

    public Iterator iterator() {
        throw new UnsupportedOperationException();
    }

    /**
     * Puts specified object at the bottom of the queue, if possible.
     *
     * @param o object to be put on the bottom of the queue.
     */
    public synchronized boolean offer(Object o) {
        if (beg == end && length > 0) {
            // queue is full
            if (!enlargeForPut()) return false;
        }
        put0(o);
        return true;
    }

    /**
     * Puts specified object at the bottom of the queue with specified timeout
     * and returns true if operation succeeded, false otherwise.
     * If the length of the queue is equal to its maximum capacity, this method
     * will block until either the length decreases (in which case it proceeds
     * with put and returns true) or timeout expires (in which case it returns
     * false), whichever comes first. If the timeout is a positive
     * number, it indicates a number of milliseconds to wait for available
     * space. If the timeout is equal to 0 and the queue is full, the method
     * will immediately return false. If the timeout is negative, the method
     * will never timeout.
     *
     * @param o object to be put on the bottom of the queue.
     * @param timeout number of milliseconds to wait for available space.
     * @return true if operation succeeded, false if it was abandoned due
     *         to the timeout.
     *
     * @throws InterruptedException if operation is interrupted by other thread
     */
    public synchronized boolean offer(Object o, long timeout, TimeUnit granularity)
        throws InterruptedException
    {
        if (full()) {
            // queue is full
            if (!enlargeForPut()) {
                if (timeout == 0) return false;
                // must wait
                long msecs = granularity.convert(timeout, TimeUnit.MILLISECONDS);
                long startTime = msecs >= 0 ? System.currentTimeMillis(): 0;
                long waitTime = msecs;
                while (length >= maxcap) {
                    if (startTime > 0) {
                        // wait until timeout, or return false if expired
                        if (waitTime <= 0) return false;
                        wait(waitTime);
                        waitTime = msecs - (System.currentTimeMillis() - startTime);
                    }
                    else {
                        wait();
                    }
                }
            }

        }
        put0(o);
        return true;
    }

    public synchronized void put(Object o) throws InterruptedException {
        if (full()) {
            if (!enlargeForPut()) {
                while (length >= maxcap) {
                    wait();
                }
            }

        }
        put0(o);
    }

    /**
     * Inserts specified object at the top of the queue, so the next call
     * to <code>get()<code> would return this object.
     *
     * @param o object to be inserted on the top of the queue.
     * @throws InterruptedException if operation is interrupted by other thread.
     */
    public synchronized boolean offerAtHead(Object o) {
        if (full()) {
            if (!enlargeForPutAtHead()) return false;
        }
        putAtHead0(o);
        return true;
    }

    /**
     * Inserts specified object at the top of the queue, so the next call
     * to <code>poll()<code> or <code>take()</code> would return this object.
     * If the length of the queue is equal to its maximum capacity, this method
     * will block until the length decreases so that the operation can proceed.
     *
     * @param o object to be put at the head of the queue.
     * @throws InterruptedException if operation is interrupted by other thread.
     */
    public synchronized void putAtHead(Object o) throws InterruptedException {
        if (full()) {
            if (!enlargeForPutAtHead()) {
                // must wait
                while (length >= maxcap) {
                    wait();
                }
            }
        }
        putAtHead0(o);
    }

    /**
     * Inserts specified object at the top of the queue, so the next call
     * to <code>get()<code> would return this object, with specified timeout
     * and returns true if operation succeeded, false otherwise.
     * If the length of the queue is equal to its maximum capacity, this method
     * will block until either the length decreases (in which case it proceeds
     * with insert and returns true) or timeout expires (in which case it returns
     * false), whichever comes first. If the timeout is a positive
     * number, it indicates a number of milliseconds to wait for available
     * space. If the timeout is equal to 0 and the queue is full, the method
     * will immediately return false. If the timeout is negative, the method
     * will never timeout.
     *
     * @param o object to be inserted on the top of the queue.
     * @param timeout number of milliseconds to wait for available space.
     * @return true if operation succeeded, false if it was abandoned due
     *         to the timeout.
     * @throws InterruptedException if operation is interrupted by other thread.
     */
    public synchronized boolean offerAtHead(Object o, int timeout, TimeUnit granularity)
        throws InterruptedException
    {
        if (full()) {
            if (!enlargeForPutAtHead()) {
                // must wait
                if (timeout == 0) return false;
                long msecs = granularity.convert(timeout, TimeUnit.MILLISECONDS);
                long startTime = msecs >= 0 ? System.currentTimeMillis(): 0;
                long waitTime = msecs;
                while (length >= maxcap) {
                    if (startTime > 0) {
                        // wait until timeout, or return false if expired
                        if (waitTime <= 0) return false;
                        wait(waitTime);
                        waitTime = msecs - (System.currentTimeMillis() - startTime);
                    }
                    else {
                        wait();
                    }
                }
            }
        }
        putAtHead0(o);
        return true;
    }

    /**
     * Retrieve and remove the first element from the queue, waiting
     * if no objects are present on the queue.
     * @return the object
     * @throws InterruptedException if interrupted while waiting.
     */
    public synchronized Object take() throws InterruptedException {
        while (length <= 0) {
            wait();
        }
        return take0();
    }

    /**
     * Gets the object from the top of the queue.
     * If the queue is empty, this method
     * will block until either the length increases (in which case it proceeds
     * with get) or timeout expires (in which case it returns null),
     * whichever comes first. If the timeout is a positive
     * number, it indicates a number of milliseconds to wait.
     * If the timeout is equal to 0 and the queue is empty, the method
     * will immediately return null. If the timeout is negative, the method
     * will never timeout.
     *
     * @param timeout number of milliseconds to wait for available space.
     * @return object from the top of the queue or null on timeout.
     * @throws InterruptedException if operation is interrupted by other thread.
     */
    public synchronized Object poll(long timeout, TimeUnit granularity)
        throws InterruptedException
    {
        if (length <= 0) {
            if (timeout == 0) return null;
            long msecs = granularity.convert(timeout, TimeUnit.MILLISECONDS);
            long startTime = msecs >= 0 ? System.currentTimeMillis(): 0;
            long waitTime = msecs;

            do {
                if (startTime > 0) {
                    // wait until timeout, or return null if expired
                    if (waitTime <= 0) return null;
                    wait(waitTime);
                    waitTime = msecs - (System.currentTimeMillis() - startTime);
                }
                else {
                    wait();
                }
            }
            while (length <= 0);
        }
        return take0();
    }

    public Object peek() {
        if (length <= 0) return null;
        return peek0();
    }

    /**
     * Remove and return an element from the queue if one is available.
     *
     * @return an element previously on the queue, or <tt>null</tt> if the
     *         queue is empty.
     */
    public synchronized Object poll() {
        if (length <= 0) return null;
        return take0();
    }

    private Object take0() {
        Object ret = buf[beg];
        buf[beg] = null;
        beg++;
        if (beg >= buf.length)
            beg = 0;
        length--;
        notifyAll();
        return ret;
    }

    private Object peek0() {
        return buf[beg];
    }

    private void put0(Object o) {
        buf[end++] = o;
        if (end >= buf.length) end = 0;
        length++;
        notifyAll();
    }

    private void putAtHead0(Object o) {
        beg--;
        if (beg < 0) beg = buf.length - 1;
        buf[beg] = o;
        length++;
        notifyAll();
    }

    private boolean enlargeForPut() {
        if (maxcap <= 0 || length < maxcap) {
            int newcap = maxcap <= 0 ? length * 2 : Math.min(maxcap, length * 2);
            Object[] newbuf = new Object[newcap];
            System.arraycopy(buf, beg, newbuf, 0, length - beg);
            System.arraycopy(buf, 0, newbuf, length - beg, end);
            buf = newbuf;
            beg = 0;
            end = length;
            return true;
        }
        return false;
    }

    private boolean enlargeForPutAtHead() {
        if (maxcap <= 0 || length < maxcap) {
            // can resize
            int newcap = maxcap <= 0 ? length * 2 : Math.min(maxcap, length * 2);
            Object[] newbuf = new Object[newcap];
            System.arraycopy(buf, beg, newbuf, 1, length - beg);
            System.arraycopy(buf, 0, newbuf, beg + 1, end);
            buf = newbuf;
            beg = 1;
            end = length + 1;
            return true;
        }
        return false;
    }

    private boolean full() {
       return (beg == end && length > 0);
    }

    public int drainTo(Collection c) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        int drained = 0;
        synchronized (this) {
            while (length > 0) {
                c.add(take0());
                drained++;
            }
        }
        return drained;
    }

    public int drainTo(Collection c, int maxElements) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        int drained = 0;
        synchronized (this) {
            while (drained < maxElements && length > 0) {
                c.add(take0());
                drained++;
            }
        }
        return drained;
    }



//    /**
//     * Returns the string representation of this queue.
//     */
//    public String toString() {
//        String s = "(cap=" + buf.length + ", len=" + length +
//            ", beg=" + beg + ", end=" + end + ": |";
//        for (int i=0; i<buf.length; i++) {
//            if (buf[i] == null) s += "."; else s += "*";
//        }
//        s+="|)";
//        return s;
//    }

}
