RoundRobinQueue.java

package gov.usgs.earthquake.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;

/**
 * An abstract base class for round-robin queueing.
 *
 * Sub classes should implement the {@link #getQueueId(Object)} to control how
 * objects are added to queues.
 *
 * @param <T>
 *            type of object being queued.
 */
public class RoundRobinQueue<T> implements Queue<T> {

    /**
     * Map of queues, keyed by queue id (as determined by
     * {@link #getQueueId(Object)}).
     */
    private final HashMap<String, LinkedList<T>> queueMap = new HashMap<String, LinkedList<T>>();

    /**
     * List of queues, same as in map, in round-robin order.
     */
    private final LinkedList<LinkedList<T>> queueList = new LinkedList<LinkedList<T>>();

    /** Default constructor. */
    public RoundRobinQueue() {
    }

    /**
     * This method determines which queue an object uses.
     *
     * @param object
     *            the object being added.
     * @return id of the queue where object should be added.
     */
    protected String getQueueId(T object) {
        return object.toString();
    }

    /** ===================== BLOCKING QUEUE METHODS ======================= **/

    /**
     * Add an item to the queue.
     *
     * @param e
     *            item to add
     * @return true if added.
     */
    @Override
    public boolean add(T e) {
        // find queue
        String queueId = getQueueId(e);
        LinkedList<T> queue = queueMap.get(queueId);
        if (queue == null) {
            // create queue
            queue = new LinkedList<T>();
            queueMap.put(queueId, queue);
            queueList.add(queue);
        }
        // add to queue
        return queue.add(e);
    }

    /**
     * Add an item to the queue, if possible.
     *
     * @param e
     *            item to add
     * @return true if added, false otherwise.
     */
    @Override
    public boolean offer(T e) {
        try {
            // this could in theory throw an unchecked exception
            return this.add(e);
        } catch (Exception ex) {
            return false;
        }
    }

    /**
     * Retrieves and removes the head of this queue.
     *
     * @return first element in queue.
     * @throws NoSuchElementException
     *             if queue is empty.
     */
    @Override
    public T remove() {
        if (queueList.size() == 0) {
            throw new NoSuchElementException();
        }

        T next = null;
        // find queue
        LinkedList<T> nextQueue = queueList.removeFirst();
        // take first item
        next = nextQueue.removeFirst();
        // reschedule queue
        if (nextQueue.size() == 0) {
            // queue is empty, remove
            String queueId = getQueueId(next);
            queueMap.remove(queueId);
        } else {
            // move to end of round robin list
            queueList.add(nextQueue);
        }
        return next;
    }

    /**
     * Retrieves, but does not remove, the head of this queue. This method
     * differs from the {@link #peek()} method only in that it throws an
     * exception if this queue is empty.
     *
     * @return the head of this queue.
     * @throws NoSuchElementException
     *             if this queue is empty.
     */
    @Override
    public T element() {
        if (queueList.size() == 0) {
            throw new NoSuchElementException();
        }
        LinkedList<T> nextQueue = queueList.getFirst();
        return nextQueue.getFirst();
    }

    /**
     * Retrieves and removes the head of this queue.
     *
     * @return the head of this queue, or null if this queue is empty.
     */
    @Override
    public T poll() {
        try {
            return remove();
        } catch (NoSuchElementException nsee) {
            return null;
        }
    }

    /**
     * Retrieves, but does not remove, the head of this queue, returning null if
     * this queue is empty.
     *
     * @return the head of this queue, or null if this queue is empty.
     */
    @Override
    public T peek() {
        try {
            return element();
        } catch (NoSuchElementException nsee) {
            return null;
        }
    }

    /** ======================= COLLECTION METHODS ========================= **/

    @Override
    public boolean addAll(Collection<? extends T> c) {
        Iterator<? extends T> iter = c.iterator();
        boolean added = false;
        while (iter.hasNext()) {
            added = add(iter.next()) || added;
        }
        return added;
    }

    @Override
    public void clear() {
        queueList.clear();
        queueMap.clear();
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        Iterator<?> iter = c.iterator();
        while (iter.hasNext()) {
            if (!contains(iter.next())) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean isEmpty() {
        return queueList.isEmpty();
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        Iterator<?> iter = c.iterator();
        boolean removed = false;
        while (iter.hasNext()) {
            removed = remove(iter.next()) || removed;
        }
        return removed;
    }

    @Override
    public int size() {
        int size = 0;
        Iterator<LinkedList<T>> iter = queueList.iterator();
        while (iter.hasNext()) {
            size = size + iter.next().size();
        }
        return size;
    }

    @Override
    public boolean contains(Object o) {
        try {
            @SuppressWarnings("unchecked")
            String queueId = getQueueId((T) o);
            LinkedList<T> queue = queueMap.get(queueId);
            return queue.contains(o);
        } catch (Exception e) {
            return false;
        }
    }

    @Override
    public boolean remove(Object o) {
        try {
            @SuppressWarnings("unchecked")
            String queueId = getQueueId((T) o);
            LinkedList<T> queue = queueMap.get(queueId);
            boolean removed = queue.remove(o);
            if (queue.isEmpty()) {
                queueMap.remove(queueId);
                queueList.remove(queue);
            }
            return removed;
        } catch (Exception e) {
            return false;
        }
    }

    /** ==================== HORRIBLY INEFFICIENT =========================== */

    /**
     * Deep copy of another RoundRobinQueue.
     *
     * This method is used for semi-destructive iteration methods.
     *
     * NOTE: this assumes {@link #getQueueId(Object)} behaves the same for this
     * and that.
     *
     * @param that a RoundRobinQueue to make a deep copy of
     */
    public RoundRobinQueue(final RoundRobinQueue<T> that) {
        Iterator<LinkedList<T>> iter = that.queueList.iterator();
        while (iter.hasNext()) {
            // copy list
            LinkedList<T> copy = new LinkedList<T>(iter.next());
            // add to round robin list
            this.queueList.add(copy);
            // add to map
            String queueId = that.getQueueId(copy.get(0));
            this.queueMap.put(queueId, copy);
        }
    }

    /**
     * Flatten queue to a list.
     *
     * Creates a copy (see {@link #RoundRobinQueue(RoundRobinQueue)}, then
     * builds list by polling until it is empty.
     *
     * @return list of all items currently in queue.
     */
    public List<T> toList() {
        ArrayList<T> list = new ArrayList<T>(this.size());
        RoundRobinQueue<T> copy = new RoundRobinQueue<T>(this);
        while (true) {
            T next = copy.poll();
            if (next == null) {
                // done
                break;
            }
            list.add(next);
        }
        return list;
    }

    @Override
    public Iterator<T> iterator() {
        return this.toList().iterator();
    }

    @Override
    public Object[] toArray() {
        return this.toList().toArray();
    }

    @Override
    public <T2> T2[] toArray(T2[] array) {
        return this.toList().toArray(array);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        List<T> toremove = this.toList();
        toremove.removeAll(c);
        return this.removeAll(toremove);
    }

}