001// Exercise 1.3.14 (Solution published at http://algs4.cs.princeton.edu/)
002package algs13;
003import stdlib.*;
004import java.util.Iterator;
005import java.util.NoSuchElementException;
006/* ***********************************************************************
007 *  Compilation:  javac ResizingArrayQueue.java
008 *  Execution:    java ResizingArrayQueue < input.txt
009 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt
010 *
011 *  Queue implementation with a resizing array.
012 *
013 *  % java ResizingArrayQueue < tobe.txt
014 *  to be or not to be (2 left on queue)
015 *
016 *************************************************************************/
017
018public class ResizingArrayQueue<T> implements Iterable<T> {
019        private T[] q;           // queue elements
020        private int N;           // number of elements on queue
021        private int first;       // index of first element of queue
022        private int last;        // index of next available slot
023
024        // cast needed since no generic array creation in Java
025        @SuppressWarnings("unchecked")
026        public ResizingArrayQueue() {
027                this.q = (T[]) new Object[2];
028                this.N = 0;
029                this.first = 0;
030                this.last = 0;
031        }
032
033        public boolean isEmpty() { return N == 0;    }
034        public int size()        { return N;         }
035
036        @SuppressWarnings("unchecked")
037        private void resize(int capacity) {
038                if (capacity <= N) throw new IllegalArgumentException ();
039                T[] temp = (T[]) new Object[capacity];
040                for (int i = 0; i < N; i++) temp[i] = q[(first + i) % q.length];
041                q = temp;
042                first = 0;
043                last  = N;
044        }
045
046        public void enqueue(T item) {
047                if (N == q.length) resize(2*q.length);   // double size of array if necessary
048                q[last] = item;                          // add item
049                last = (last + 1) % q.length;
050                N++;
051        }
052
053        // remove the least recently added item
054        public T dequeue() {
055                if (isEmpty()) throw new Error("Queue underflow");
056                T item = q[first];
057                q[first] = null;                         // to avoid loitering
058                N--;
059                first = (first + 1) % q.length;
060                if (N > 0 && N == q.length/4) resize(q.length/2); // shrink size of array if necessary
061                return item;
062        }
063
064        public Iterator<T> iterator() { return new ArrayIterator(); }
065        private class ArrayIterator implements Iterator<T> {
066                private int i = 0;
067                public boolean hasNext()  { return i < N;                               }
068                public void remove()      { throw new UnsupportedOperationException();  }
069
070                public T next() {
071                        if (!hasNext()) throw new NoSuchElementException();
072                        T item = q[(first + i) % q.length];
073                        i++;
074                        return item;
075                }
076        }
077
078        public String toString () {
079                if (isEmpty()) return "[]";
080                StringBuilder sb = new StringBuilder ("[");
081                Iterator<T> i = iterator();
082                sb.append (i.next ());
083                while (i.hasNext ()) {
084                        sb.append (" ");
085                        sb.append (i.next ());
086                }
087                sb.append ("]");
088                return sb.toString ();
089        }
090        private void check (String expected) {
091                if (N<0 || N>q.length) throw new Error ();
092                if (N==0 && q.length!=2) throw new Error ("Expected length 2, got " + q.length);
093                if (N!=0 && N<q.length/4) throw new Error ();
094                if (((first + N) % q.length) != last) throw new Error ();
095                for (int i=0; i<N; i++) {
096                        if (q[(first + i) % q.length] == null) throw new Error ();
097                }
098                for (int i=N; i<q.length; i++) {
099                        if (q[(first + i) % q.length] != null) throw new Error ();
100                }
101                if (expected != null) {
102                        if (!expected.equals(this.toString ())) throw new Error ("Expected \"" + expected + "\", got \"" + this + "\"");
103                }
104                StdOut.println (this);
105        }
106        private void check (T iExpected, T iActual, String expected) {
107                if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\"");
108                check (expected);
109        }
110        public static void mainx (String args[]) {
111                ResizingArrayQueue<Integer> d1;
112                Integer k;
113                d1 = new ResizingArrayQueue<> ();
114                d1.enqueue (11); d1.check ("[11]");
115                d1.enqueue (12); d1.check ("[11 12]");
116                k = d1.dequeue(); d1.check (11, k, "[12]");
117                k = d1.dequeue(); d1.check (12, k, "[]");
118
119                d1 = new ResizingArrayQueue<> ();
120                for (int i = 10; i < 20; i++)
121                        d1.enqueue (i);
122                d1.check ("[10 11 12 13 14 15 16 17 18 19]");
123
124                for (int i = 0; i < 10; i++) {
125                        d1.dequeue (); d1.check (null);
126                }
127                try { d1.dequeue (); throw new Error ("Expected exception"); } catch (Error e) {}
128        }
129
130        // A test client
131        public static void main (String[] args) {
132                StdIn.fromString ("to be or not to - be - - that - - - is");
133
134                ResizingArrayQueue<String> q = new ResizingArrayQueue<>();
135                while (!StdIn.isEmpty()) {
136                        String item = StdIn.readString();
137                        if (!item.equals("-")) q.enqueue(item);
138                        else StdOut.print(q.dequeue() + " ");
139                }
140                StdOut.println("(" + q.size() + " left on queue)");
141        }
142}