001// Exercise 4.3.36
002package algs13;
003import stdlib.*;
004import java.util.Iterator;
005public class MyRandomQueue<T> implements Iterable<T> {
006
007        /** Create an empty random queue. */
008        public MyRandomQueue () {}
009
010        /** Is it empty? */
011        public boolean isEmpty () {
012                return true;
013        }
014
015        /** Return the number of elements. */
016        public int size () {
017                return 0;
018        }
019
020        /** Add an item. */
021        public void enqueue (T item) {}
022
023        /** Return (but do not remove) a random item. */
024        public T sample () {
025                return null;
026        }
027
028        /** Remove and return a random item. */
029        public T dequeue () {
030                return null;
031        }
032
033        /** Return an iterator over the items in random order. */
034        public Iterator<T> iterator () {
035                return new QueueIterator ();
036        }
037
038        // an iterator, doesn't implement remove() since it's optional
039        private class QueueIterator implements Iterator<T> {
040                public boolean hasNext () { return false; }
041                public T next () { return null; }
042                public void remove () {}
043        }
044
045        // Test code from https://blog.itu.dk/BADS-F2011/2011/02/10/programming-exercise-3-randomqueue/
046        public static void main (String args[]) {
047                int NUMROLLS = 10000;
048                // Build a queue containing the Integers 1,2,...,6:
049                MyRandomQueue<Integer> q1 = new MyRandomQueue<> ();
050                for (int i = 1; i < 7; ++i)
051                        q1.enqueue (i); // autoboxing! cool!
052
053                // Print 30 die rolls to standard output
054                StdOut.print ("Some die rolls: ");
055                for (int i = 1; i < 30; ++i)
056                        StdOut.print (q1.sample () + " ");
057                StdOut.println ();
058
059                // Let's be more serious: do they really behave like die rolls?
060                int[] rolls = new int[NUMROLLS];
061                for (int i = 0; i < NUMROLLS; ++i)
062                        rolls[i] = q1.sample (); // autounboxing! Also cool!
063                StdOut.format ("Mean (should be around 3.5): %5.4f\n", StdStats.mean (rolls));
064                StdOut.format ("Standard deviation (should be around 1.7): %5.4f\n", StdStats.stddev (rolls));
065
066                // Let's look at the iterator. First, we make a queue of colours:
067                MyRandomQueue<String> q2 = new MyRandomQueue<> ();
068                q2.enqueue ("red");
069                q2.enqueue ("blue");
070                q2.enqueue ("green");
071                q2.enqueue ("yellow"); //q2.print ();
072                q2.dequeue (); //q2.print ();
073                q2.dequeue (); //q2.print ();
074                q2.enqueue ("purple"); //q2.print ();
075                q2.enqueue ("orange"); //q2.print ();
076
077                Iterator<String> it1 = q2.iterator ();
078                Iterator<String> it2 = q2.iterator ();
079
080                StdOut.print ("Two colours from first shuffle: ");
081                StdOut.print (it1.next () + " ");
082                StdOut.print (it1.next () + " ");
083
084                StdOut.print ("\nEntire second shuffle: ");
085                while (it2.hasNext ())
086                        StdOut.print (it2.next () + " ");
087
088                StdOut.print ("\nRemaining two colours from first shuffle: ");
089                StdOut.print (it1.next () + " ");
090                StdOut.println (it1.next ());
091
092                Stopwatch s = new Stopwatch ();
093                int[][] irolls = new int[6][NUMROLLS];
094                for (int i = 0; i < NUMROLLS; ++i) {
095                        Iterator<Integer> it3 = q1.iterator ();
096                        for (int j = 0; j < 6; j++)
097                                irolls[j][i] = it3.next ();
098                }
099                StdOut.format ("Elapsed time: %5.4f\n", s.elapsedTime ());
100                for (int j = 0; j < 6; j++) {
101                        StdOut.format ("Mean (should be around 3.5): %5.4f\n", StdStats.mean (irolls[j]));
102                        StdOut.format ("Standard deviation (should be around 1.7): %5.4f\n", StdStats.stddev (irolls[j]));
103                }
104        }
105
106}