Randomized Queue

From Princeton_Algorithms_I

A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random among items in data structure. Create a generic data type RandomizedQueue that implements the following API:

x
public class RandomizedQueue<T> implements Iterable<T> {
    // Construct an empty randomized queue
    public RandomizedQueue();
    // Is the randomzied queue empty
    public boolean isEmpty();
    // return the number of items on the randomzied queue
    public int size();
    // add the item
    public void enqueue(T item);
    // remove and return a random item
    public T dequeue();
    // return a random item (but not remove it)
    public T sample();
    // return and independant iterator over items in random order
    public Iterator<T> iterator();
    //unit testing (required)
    public static void main(String[] args);
};
​

Performance requirement: Randomized queue must support each randomized queue operation (besides creating an iterator) in constant amortized time. That is, any intermixed sequence of m randomized queue operations (starting from an empty queue) must take cm steps in the worst case, for some constant c. A amortized queue containing n items must use $48n + 192$ bytes of memory.

Client: Write a client program Permutation.java that takes an integer k as a command line argument; reads a sequence of string from a standard input using Stdin.readString(); and prints exactly k of them, uniformly at random. Print each item from the sequence at most once. you may assume that $0 \le k\le n$, where $n$ is the number of string on standard input. Note that you are not given $n$.

Solution

x
import java.util.Iterator;
import java.util.NoSuchElementException;
​
import edu.princeton.cs.algs4.StdRandom;
​
public class RandomizedQueue<Item> implements Iterable<Item> {
​
    private static final int INITIAL_CAPACITY = 16;
    private int size;
    private Item[] container;
​
    //Constructs an empty randomized queue
    public RandomizedQueue() {
        container = (Item[]) new Object[INITIAL_CAPACITY];
        size = 0;
    }
​
    // is the randomized queue empty ?
    public boolean isEmpty() {
        return size == 0;
    }
​
    // return the number of items on the randomzied queue
    public int size() {
        return size;
    }
​
    // add the item
    public void enqueue(Item item) {
        if (item == null) throw new IllegalArgumentException();
        if (size == container.length) resizeContainer(2 * container.length);
        container[size++] = item;
    }
​
    private void resizeContainer(int newCap) {
        Item[] resizedContainer = (Item[]) new Object[newCap];
        for (int i = 0; i < size; i++) {
            resizedContainer[i] = container[i];
        }
        container = resizedContainer;
    }
    
    // remove and return item a random item
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException();
        if (size == 1) {
            Item item = container[0];
            container[0] =  null;
            size--;
            return item;
        }
        int randomIndex = StdRandom.uniform(size);
        Item item = container[randomIndex];
        container[randomIndex] = null;
        // This is simply brilliant.
        /*discussion forum: https://www.coursera.org/learn/algorithms-part1/discussions/weeks/2/threads/h5VOQ6owEeagRwptN6JMvA
        */
        container[randomIndex] = container[size - 1];
        size--;
        if (size > 0 && size == this.container.length/4) resizeContainer(container.length/2);
        return item;
    } 
​
    // return a random item (but do not remove it)
    public Item sample() {
        if (isEmpty()) throw new NoSuchElementException();
        if (size == 1) {
            Item item = container[0];
            return item;
        }
        int randomIndex = StdRandom.uniform(size);
        Item item = container[randomIndex];
        return item;
    }
​
    // return an independant iterator over items in random order
    @Override
    public Iterator<Item> iterator() {
        return new RandomizedQueueIterator();
    }
    private final class RandomizedQueueIterator implements Iterator<Item> {
        private int copySize;
        private Item[] copyContainer;
​
        public RandomizedQueueIterator() {
            copySize = size;
            copyContainer = (Item[]) new Object[copySize];
            System.arraycopy(container, 0, copyContainer, 0, copySize);
        }
​
        @Override
        public boolean hasNext() {
            return copySize > 0;
        }
​
        @Override
        public Item next() {
            if (hasNext()) {
                int randomIndex  = StdRandom.uniform(copySize);
                Item item = copyContainer[randomIndex];
                copyContainer[randomIndex] = null;
                copyContainer[randomIndex] = copyContainer[copySize - 1];
                if (copySize > 0 && copySize == copyContainer.length/4){
                    resizeCopyContainer(copyContainer.length/2);
                }
                copySize--;
                return item;
            }
            throw new NoSuchElementException();
        }
​
        private void resizeCopyContainer(int n) {
            Item[] resizedContainer = (Item[])new Object[n];
            for (int i = 0; i < copySize; i++) {
                resizedContainer[i] = copyContainer[i];
            }
            copyContainer = resizedContainer;
        }
​
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
​
    public static void main(String[] args) {
        int n = 5;
        RandomizedQueue<Integer> randomizedQueue = new RandomizedQueue<>();
        for (int i = 0; i < n; i++) {
            randomizedQueue.enqueue(i);
        }
​
        for(int a: randomizedQueue) {
            for (int b: randomizedQueue) {
                System.out.print(a + "-" +  b + " ");
            }
            System.out.println();
        }
    }
}

Client Program

xxxxxxxxxx
import edu.princeton.cs.algs4.StdIn;
//Client program 
public class Permutation {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        RandomizedQueue<String> randomizedQueue = new RandomizedQueue<>();
        while (!StdIn.isEmpty()) {
            String s = StdIn.readString();
            randomizedQueue.enqueue(s);
        }
        for (int i = 0; i < n; i++) {
            System.out.println(randomizedQueue.dequeue());
        }
    }
}