    001    package ifs.util;
    002
    003    import java.util.*;
    004
    005    /** Queue.
    006     *
    007     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    008     * @version 1.0
    009     */
    010    public class Queue {
    011        private Object iElementData[];
    012        private int iMaxSize, iFirst, iLast;
    013        private HashSet iHashedElementData;
    014
    015        /** Constructor
    016         * @param maxSize maximal size of the queue
    017         */
    018        public Queue(int maxSize) {
    019            iMaxSize = maxSize+2;
    020            iFirst = iLast = 0;
    021            iElementData = new Object[iMaxSize];
    022            iHashedElementData = new HashSet(2*iMaxSize,0.5f);
    023        }
    024
    025        /** Constructor
    026         * @param maxSize maximal size of the queue
    027         * @param initials initial content
    028         */
    029        public Queue(int maxSize, Collection initials) {
    030            this(maxSize);
    031            for (Iterator i=initials.iterator();i.hasNext();)
    032                put(i.next());
    033        }
    034
    035        /** Puts object at the end of the queue */
    036        public void put(Object object) throws ArrayIndexOutOfBoundsException {
    037            iElementData[iLast]=object;
    038            iHashedElementData.add(object);
    039            iLast = (iLast + 1) % iMaxSize;
    040            if (iFirst==iLast) throw new ArrayIndexOutOfBoundsException("Queue is full.");
    041        }
    042
    043        /** Returns true if queue contains the given object */
    044        public boolean contains(Object object) {
    045            return iHashedElementData.contains(object);
    046        }
    047
    048        /** Gets first element of the queue */
    049        public Object get() {
    050            if (iLast==iFirst) return null;
    051            Object ret = iElementData[iFirst];
    052            iFirst = (iFirst + 1) % iMaxSize;
    053            iHashedElementData.remove(ret);
    054            return ret;
    055        }
    056
    057        /** Returns size of the queue */
    058        public int size() {
    059            return (iLast>=iFirst?iLast-iFirst:iMaxSize+iLast-iFirst);
    060        }
    061
    062        /** Returns true if the queue is empty */
    063        public boolean isEmpty() {
    064            return iFirst==iLast;
    065        }
    066    }