package ifs.util;

import java.util.*;

/** Queue.
 *
 * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomas Muller</a>
 * @version 1.0
 */
public class Queue {
    private Object iElementData[];
    private int iMaxSize, iFirst, iLast;
    private HashSet iHashedElementData;
    
    /** Constructor
     * @param maxSize maximal size of the queue
     */
    public Queue(int maxSize) {
        iMaxSize = maxSize+2;
        iFirst = iLast = 0;
        iElementData = new Object[iMaxSize];
        iHashedElementData = new HashSet(2*iMaxSize,0.5f);
    }
    
    /** Constructor
     * @param maxSize maximal size of the queue
     * @param initials initial content
     */
    public Queue(int maxSize, Collection initials) {
        this(maxSize);
        for (Iterator i=initials.iterator();i.hasNext();)
            put(i.next());
    }

    /** Puts object at the end of the queue */
    public void put(Object object) throws ArrayIndexOutOfBoundsException {
        iElementData[iLast]=object;
        iHashedElementData.add(object);
        iLast = (iLast + 1) % iMaxSize;
        if (iFirst==iLast) throw new ArrayIndexOutOfBoundsException("Queue is full.");
    }
    
    /** Returns true if queue contains the given object */
    public boolean contains(Object object) {
        return iHashedElementData.contains(object);
    }
    
    /** Gets first element of the queue */
    public Object get() {
        if (iLast==iFirst) return null;
        Object ret = iElementData[iFirst];
        iFirst = (iFirst + 1) % iMaxSize;
        iHashedElementData.remove(ret);
        return ret;
    }
    
    /** Returns size of the queue */
    public int size() {
        return (iLast>=iFirst?iLast-iFirst:iMaxSize+iLast-iFirst);
    }
    
    /** Returns true if the queue is empty */
    public boolean isEmpty() {
        return iFirst==iLast;
    }
}
