Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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 ]");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement