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 ]");
	}
}