package comp2402a2;

import java.util.AbstractQueue;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.NoSuchElementException;

/**
 * An implementation of a RandomQueue.  This is like a standard queue,
 * except that when we remove an element, we get a random element.
 *
 * TODO: This implementation requires Theta(size) time on average for
 * poll() operation.  Improve this so that it takes constant time.
 * @author morin
 *
 * @param <T> the type of elements stored in the queue
 */
public class RandomQueue<T> extends AbstractQueue<T> {
    /**
     * The list that stores our queue elements
     */
    List<T> l;

    /**
     * A source of random numbers
     */
    Random r;

    /**
     * The index of the next element we will return
     */
    int next;
    int j=0;//index start
    int k=0;//size of the list

    public RandomQueue() {
        l = new ArrayList<T>();
        r = new Random();
    }

    /**
     * Return an iterator for the elements in the queue
     * Note: this iterator does not necessarily enumerate the elements
     * in random order
     */
    public Iterator<T> iterator() {
        return l.iterator();
    }

    public int size() {
        return k;
    }


    public boolean add(T x) {
        if(k==0) {
            l.add(x);
            k++;
            return true;
        }
        if(k+1 > l.size()) resize();
        l.set((j+k)%l.size(), x);
        k++;
        return true;
    }

    void resize() {//make the ArrayList bigger (not sure if needed or not
        List<T> b = new ArrayList<T>(k*2);
        for(int i=0; i<k; i++){
            b.add(l.get((j+i)%l.size()));
        }
        l = b;
        j=0;
    }

    public boolean offer(T x) {
        l.add(x);
        next = r.nextInt(l.size());
        return true;
    }

    public T remove1(int z) throws NoSuchElementException{//remove a random object from the list
        if (k==0) throw new NoSuchElementException();
        T x = l.get(z);
        if (z<=l.size()){ //shift right
            for(int i=z; i>0; i--){
                l.set(i, l.get(i-1));
            }
            j++;
            k--;
        } else { //shift left
            for(int i=z; i<l.size();i++){
                l.set(i, l.get(i+1));
            }
            k--;
        }

        return x;
    }

    /**
     * Return at the next element that will be returned by poll()/remove()
     * without actually removing it
     */
    public T peek() {
        if (l.size() == 0)
            return null;
        assert(next >= 0 && next <= l.size()-1);
        return l.get(next);
    }

    /**
     * Remove and return a random element from the queue
     */
    public T poll() {
        peek();
        T x = remove1(next);
        next = (l.size() > 0) ? r.nextInt(l.size()) : -1;
        return x;
    }



    public T remove(){
        return poll();
    }

    /**
     * A stupid method to help with tests
     * @param b
     * @throws AssertionError
     */
    protected static void myassert(boolean b) throws AssertionError {
        if (!b) {
            throw new AssertionError();
        }
    }

    /**
     * Some test code
     * @param args ignored
     */
    public static void main(String[] args) {
        RandomQueue<Integer> q = new RandomQueue<Integer>();

        // some simple tests and output to check for randomness
        int n = 16;
        for (int j = 0; j < 5; j++) {
            for (int i = 0; i < n; i++) {
                q.add(i);
            }
            boolean[] checked = new boolean[n];
            for (int i = 0; i < n; i++) {
                myassert(q.size() == n-i);
                Integer k = q.remove();//this would most likely be the offending line
                myassert(checked[k] == false);//due to this being the error producing line
                checked[k] = true;
                System.out.print(k);
                if (q.isEmpty()) {
                    System.out.println();
                } else {
                    System.out.print(",");
                }
            }
            myassert(q.isEmpty());
        }
        // heavier-duty tests to check for randomness
        n = 10000;
        for (int i = 0; i < n; i++) {
            q.add((i % 2 == 0) ? i : n+i);
        }
        boolean[] checked = new boolean[n];
        Integer max = -1;
        int records = 0;
        for (int i = 0; i < n; i++) {
            myassert(q.size() == n-i);
            Integer k = q.remove();
            k = (k > n) ? k - n : k;
            if (k > max) {
                max = k;
                records++;
            }
            myassert(checked[k] == false);
            checked[k] = true;
        }
        myassert(q.isEmpty());
        System.out.println("# records = " + records
                + " (expected " + Math.log(n) + ")");

        // some performance tests
        n = 100000;
        System.out.print("Adding " + n + " elements...");
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            q.add(i);
        }
        long stop = System.nanoTime();
        double elapsed = 1e-9*(stop-start);
        System.out.println("done (" + elapsed + "s) [ "
                + (int)(((double)n)/elapsed) + " ops/sec ]");
        Random r = new Random();
        System.out.print("Performing " + 5*n + " queue operations...");
        start = System.nanoTime();
        for (int i = n; i < 5*n; i++) {
            if (r.nextBoolean() == false) {
                q.remove();
            } else {
                q.add(i);
            }
        }
        stop = System.nanoTime();
        elapsed = 1e-9*(stop-start);
        System.out.println("done (" + elapsed + "s) [ "
                + (int)(((double)n)/elapsed) + " ops/sec ]");
    }
}