Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

Draymire Java Help Code

By: a guest on Oct 3rd, 2012  |  syntax: Java  |  size: 4.85 KB  |  hits: 8  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. package comp2402a2;
  2.  
  3. import java.util.AbstractQueue;
  4. import java.util.ArrayList;
  5. import java.util.Iterator;
  6. import java.util.List;
  7. import java.util.Random;
  8. import java.util.NoSuchElementException;
  9.  
  10. /**
  11.  * An implementation of a RandomQueue.  This is like a standard queue,
  12.  * except that when we remove an element, we get a random element.
  13.  *
  14.  * TODO: This implementation requires Theta(size) time on average for
  15.  * poll() operation.  Improve this so that it takes constant time.
  16.  * @author morin
  17.  *
  18.  * @param <T> the type of elements stored in the queue
  19.  */
  20. public class RandomQueue<T> extends AbstractQueue<T> {
  21.         /**
  22.          * The list that stores our queue elements
  23.          */
  24.         List<T> l;
  25.        
  26.         /**
  27.          * A source of random numbers
  28.          */
  29.         Random r;
  30.        
  31.         /**
  32.          * The index of the next element we will return
  33.          */
  34.         int next;
  35.         int j=0;//index start
  36.         int k=0;//size of the list
  37.  
  38.         public RandomQueue() {
  39.                 l = new ArrayList<T>();
  40.                 r = new Random();
  41.         }
  42.  
  43.         /**
  44.          * Return an iterator for the elements in the queue
  45.          * Note: this iterator does not necessarily enumerate the elements
  46.          * in random order
  47.          */
  48.         public Iterator<T> iterator() {
  49.                 return l.iterator();
  50.         }
  51.  
  52.         public int size() {
  53.                 return k;
  54.         }
  55.  
  56.        
  57.         public boolean add(T x) {
  58.                 if(k==0) {
  59.                         l.add(x);
  60.                         k++;
  61.                         return true;
  62.                 }
  63.                 if(k+1 > l.size()) resize();
  64.                 l.set((j+k)%l.size(), x);
  65.                 k++;
  66.                 return true;
  67.         }
  68.  
  69.         void resize() {//make the ArrayList bigger (not sure if needed or not
  70.                 List<T> b = new ArrayList<T>(k*2);
  71.                 for(int i=0; i<k; i++){
  72.                         b.add(l.get((j+i)%l.size()));
  73.                 }
  74.                 l = b;
  75.                 j=0;
  76.         }
  77.  
  78.         public boolean offer(T x) {
  79.                 l.add(x);
  80.                 next = r.nextInt(l.size());
  81.                 return true;
  82.         }
  83.  
  84.         public T remove1(int z) throws NoSuchElementException{//remove a random object from the list
  85.                 if (k==0) throw new NoSuchElementException();
  86.                 T x = l.get(z);
  87.                 if (z<=l.size()){ //shift right
  88.                         for(int i=z; i>0; i--){
  89.                                 l.set(i, l.get(i-1));
  90.                         }
  91.                         j++;
  92.                         k--;
  93.                 } else { //shift left
  94.                         for(int i=z; i<l.size();i++){
  95.                                 l.set(i, l.get(i+1));
  96.                         }
  97.                         k--;
  98.                 }
  99.  
  100.                 return x;
  101.         }
  102.  
  103.         /**
  104.          * Return at the next element that will be returned by poll()/remove()
  105.          * without actually removing it
  106.          */
  107.         public T peek() {
  108.                 if (l.size() == 0)
  109.                         return null;
  110.                 assert(next >= 0 && next <= l.size()-1);
  111.                 return l.get(next);
  112.         }
  113.  
  114.         /**
  115.          * Remove and return a random element from the queue
  116.          */
  117.         public T poll() {
  118.                 peek();
  119.                 T x = remove1(next);
  120.                 next = (l.size() > 0) ? r.nextInt(l.size()) : -1;
  121.                 return x;
  122.         }
  123.  
  124.        
  125.  
  126.         public T remove(){
  127.                 return poll();
  128.         }
  129.  
  130.         /**
  131.          * A stupid method to help with tests
  132.          * @param b
  133.          * @throws AssertionError
  134.          */
  135.         protected static void myassert(boolean b) throws AssertionError {
  136.                 if (!b) {
  137.                         throw new AssertionError();
  138.                 }
  139.         }
  140.  
  141.         /**
  142.          * Some test code
  143.          * @param args ignored
  144.          */
  145.         public static void main(String[] args) {
  146.                 RandomQueue<Integer> q = new RandomQueue<Integer>();
  147.                
  148.                 // some simple tests and output to check for randomness
  149.                 int n = 16;
  150.                 for (int j = 0; j < 5; j++) {
  151.                         for (int i = 0; i < n; i++) {
  152.                                 q.add(i);
  153.                         }
  154.                         boolean[] checked = new boolean[n];
  155.                         for (int i = 0; i < n; i++) {
  156.                                 myassert(q.size() == n-i);
  157.                                 Integer k = q.remove();//this would most likely be the offending line
  158.                                 myassert(checked[k] == false);//due to this being the error producing line
  159.                                 checked[k] = true;
  160.                                 System.out.print(k);
  161.                                 if (q.isEmpty()) {
  162.                                         System.out.println();
  163.                                 } else {
  164.                                         System.out.print(",");
  165.                                 }
  166.                         }
  167.                         myassert(q.isEmpty());
  168.                 }
  169.                 // heavier-duty tests to check for randomness
  170.                 n = 10000;
  171.                 for (int i = 0; i < n; i++) {
  172.                         q.add((i % 2 == 0) ? i : n+i);
  173.                 }
  174.                 boolean[] checked = new boolean[n];
  175.                 Integer max = -1;
  176.                 int records = 0;
  177.                 for (int i = 0; i < n; i++) {
  178.                         myassert(q.size() == n-i);
  179.                         Integer k = q.remove();
  180.                         k = (k > n) ? k - n : k;
  181.                         if (k > max) {
  182.                                 max = k;
  183.                                 records++;
  184.                         }
  185.                         myassert(checked[k] == false);
  186.                         checked[k] = true;
  187.                 }
  188.                 myassert(q.isEmpty());
  189.                 System.out.println("# records = " + records
  190.                                 + " (expected " + Math.log(n) + ")");
  191.                
  192.                 // some performance tests
  193.                 n = 100000;
  194.                 System.out.print("Adding " + n + " elements...");
  195.                 long start = System.nanoTime();
  196.                 for (int i = 0; i < n; i++) {
  197.                         q.add(i);
  198.                 }
  199.                 long stop = System.nanoTime();
  200.                 double elapsed = 1e-9*(stop-start);
  201.                 System.out.println("done (" + elapsed + "s) [ "
  202.                                 + (int)(((double)n)/elapsed) + " ops/sec ]");
  203.                 Random r = new Random();
  204.                 System.out.print("Performing " + 5*n + " queue operations...");
  205.                 start = System.nanoTime();
  206.                 for (int i = n; i < 5*n; i++) {
  207.                         if (r.nextBoolean() == false) {
  208.                                 q.remove();
  209.                         } else {
  210.                                 q.add(i);
  211.                         }
  212.                 }
  213.                 stop = System.nanoTime();
  214.                 elapsed = 1e-9*(stop-start);
  215.                 System.out.println("done (" + elapsed + "s) [ "
  216.                                 + (int)(((double)n)/elapsed) + " ops/sec ]");
  217.         }
  218. }