001package algs13;
002import stdlib.*;
003
004public class XResizingArrayQueueofStrings {
005        private String[] q;      // queue elements
006        private int N;           // number of elements on queue
007        private int first;       // index of first element of queue
008        private int last;        // index of next available slot
009        // Invariant (after the constructor):
010        //   a[(first + 0) % q.length]..a[(first + N-1) % q.length] are non null
011        //   a[(first + N) % q.length]..a[(first + a.length-1) % q.length] are null
012        public XResizingArrayQueueofStrings() {
013                this.q = new String[2];
014                this.N = 0;
015                this.first = 0;
016                this.last = 0;
017        }
018
019        public boolean isEmpty() { return N == 0;    }
020        public int size()        { return N;         }
021
022        private void resize(int capacity) {
023                if (capacity <= N) throw new IllegalArgumentException ();
024                String[] temp = new String[capacity];
025                for (int i = 0; i < N; i++) { 
026                        temp[i] = q[(first + i) % q.length];
027                }
028                q = temp;
029                first = 0;
030                last  = N;
031        }
032
033        public void enqueue(String item) {
034                if (N == q.length) resize(2*q.length);  // double size of array if necessary
035                q[last] = item;
036                last = (last + 1) % q.length;
037                N++;
038        }
039
040        // remove the least recently added item
041        public String dequeue() {
042                if (isEmpty()) throw new Error("Queue underflow");
043                String item = q[first];
044                q[first] = null;                         // to avoid loitering
045                N--;
046                first = (first + 1) % q.length;
047                if (N > 0 && N == q.length/4) resize(q.length/2); // shrink size of array if necessary
048                return item;
049        }
050
051        public String toString () {
052                if (isEmpty()) return "[]";
053                StringBuilder sb = new StringBuilder ("[");
054                sb.append (q[first % q.length]);
055                int i = 1;
056                while (i < N) {
057                        sb.append (" ");
058                        sb.append (q[(first + i) % q.length]);
059                        i++;
060                }
061                sb.append ("]");
062                return sb.toString ();
063        }
064        private void check (String expected) {
065                if (N<0 || N>q.length) throw new Error ();
066                if (N==0 && q.length!=2) throw new Error ("Expected length 2, got " + q.length);
067                if (N!=0 && N<q.length/4) throw new Error ();
068                if (((first + N) % q.length) != last) throw new Error ();
069                for (int i=0; i<N; i++) {
070                        if (q[(first + i) % q.length] == null) throw new Error ();
071                }
072                for (int i=N; i<q.length; i++) {
073                        if (q[(first + i) % q.length] != null) throw new Error ();
074                }
075                if (expected != null) {
076                        if (!expected.equals(this.toString ())) throw new Error ("Expected \"" + expected + "\", got \"" + this + "\"");
077                }
078                StdOut.println (this);
079        }
080        private void check (String iExpected, String iActual, String expected) {
081                if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\"");
082                check (expected);
083        }
084        public static void mainX (String args[]) {
085                String k;
086                var d1 = new XResizingArrayQueueofStrings ();
087                d1.enqueue ("11"); d1.check ("[11]");
088                d1.enqueue ("12"); d1.check ("[11 12]");
089                k = d1.dequeue(); d1.check ("11", k, "[12]");
090                k = d1.dequeue(); d1.check ("12", k, "[]");
091
092                d1 = new XResizingArrayQueueofStrings ();
093                for (int i = 10; i < 20; i++)
094                        d1.enqueue (Integer.toString(i));
095                d1.check ("[10 11 12 13 14 15 16 17 18 19]");
096
097                for (int i = 10; i < 20; i++) {
098                        d1.dequeue (); d1.check (null);
099                }
100                try { d1.dequeue (); throw new Error ("Expected exception"); } catch (Error e) {}
101        }
102
103        // A test client
104        public static void main (String[] args) {
105                StdIn.fromString ("to be or not to - be - - that - - - is");
106
107                var q = new XResizingArrayQueueofStrings();
108                while (!StdIn.isEmpty()) {
109                        String item = StdIn.readString();
110                        if (!item.equals("-")) q.enqueue(item);
111                        else StdOut.print(q.dequeue() + " ");
112                }
113                StdOut.println("(" + q.size() + " left on queue)");
114        }
115}