/* vim: set expandtab tabstop=4 shiftwidth=4 : */

import java.util.Iterator;

public class RandomizedQueue<Item> implements Iterable<Item>
{
    private int n;
    private Item[] items;

    // construct an empty randomized queue
    public RandomizedQueue()
    {
        n = 0;
        items = (Item[]) new Object[1];
    }

    // is the queue empty?
    public boolean isEmpty() { return n == 0; }

    // return the number of items on the queue
    public int size() { return n; }

    // add the item
    public void enqueue(Item item)
    {
        if (item == null) throw new java.lang.NullPointerException();
        if (n == items.length)
        {
            Item[] copy = (Item[]) new Object[n*2];
            for (int i = 0; i < n; i++)
                copy[i] = items[i];
            items = copy;
        }
        items[n++] = item;
    }

    // delete and return a random item
    public Item dequeue()
    {
        if (n == 0) throw new java.util.NoSuchElementException();
        int r = StdRandom.uniform(n);
        Item item = items[r];
        items[r] = items[--n];
        items[n] = null;
        if (n > 0 && n == items.length/4)
        {
            Item[] copy = (Item[]) new Object[items.length/2];
            for (int i = 0; i < n; i++)
                copy[i] = items[i];
            items = copy;
        }
        return item;
    }

    // return (but do not delete) a random item
    public Item sample()
    {
        if (n == 0) throw new java.util.NoSuchElementException();
        return items[StdRandom.uniform(n)];
    }

    // return an independent iterator over items in random order
    public Iterator<Item> iterator() { return new RandomizedQueueIterator(); }

    private class RandomizedQueueIterator implements Iterator<Item>
    {
        // must be random !!!!
        private int idx;
        private int[] random;

        public RandomizedQueueIterator()
        {
            idx = 0;
            random = new int[n];
            for (int i = 0; i < n; i++)
                random[i] = i;
            for (int i = 0; i < n; i++)
            {
                int r = StdRandom.uniform(i + 1);
                int tmp = random[i];
                random[i] = random[r];
                random[r] = tmp;
            }
        }

        public boolean hasNext()
        { return idx < n; }
        public void remove()
        { throw new java.lang.UnsupportedOperationException(); }
        public Item next()
        {
            if (idx >= n) throw new java.util.NoSuchElementException();
            Item item = items[random[idx++]];
            return item;
        }
    }
}