001package algs13;
002import stdlib.*;
003import java.util.ConcurrentModificationException;
004import java.util.Iterator;
005import java.util.NoSuchElementException;
006/* ***********************************************************************
007 *  Compilation:  javac ResizingArray.java
008 *  Execution:    java ResizingArray < input.txt
009 *************************************************************************/
010
011public class ResizingArray<T> implements Iterable<T> {
012        private T[] a;
013        private int N;
014        private long opcount;
015
016        @SuppressWarnings("unchecked")
017        public ResizingArray(int initialCapacity) {
018                this.N = 0;
019                this.a = (T[]) new Object[initialCapacity];
020        }
021        public ResizingArray()                       { this (4); }
022        public ResizingArray(Iterable<T> collection) { this (); addAll (collection); }
023        public ResizingArray(T[] array)              { this (); addAll (array); }
024
025        public int size() { return N;  }
026
027        @SuppressWarnings("unchecked")
028        public void ensureCapacity(int minCapacity) {
029                opcount++;
030                if (minCapacity > a.length) {
031                        int newCapacity = Math.max (minCapacity, a.length*2);
032                        T[] temp = (T[]) new Object[newCapacity];
033                        for (int i = a.length - 1; i >= 0; i--) temp[i] = a[i];
034                        a = temp;
035                }
036        }
037
038        public void set(int index, T item) {
039                if (index >= N) throw new Error ();
040                opcount++;
041                a[index] = item;
042        }
043        public void add(T item) {
044                ensureCapacity(N+1);
045                a[N++] = item;
046        }
047        public void addAll(Iterable<T> collection) {
048                for (T item : collection) {
049                        ensureCapacity(N+1);
050                        a[N] = item;
051                        N++;
052                }
053        }
054        public void addAll(T[] array) {
055                int newSize = N + array.length;
056                ensureCapacity(newSize);
057                for (int i = 0; i < array.length ; i++) {
058                        a[i+N] = array[i];
059                }
060                N = newSize;
061        }
062
063
064
065        public Iterator<T> iterator()  { return new ArrayIterator(); }
066        private class ArrayIterator implements Iterator<T> {
067                private int index = 0;
068                private long oc = opcount;
069
070                public boolean hasNext()  { return index < N; }
071                public void remove()      { throw new UnsupportedOperationException();  }
072                public T next() {
073                        if (opcount != oc) throw new ConcurrentModificationException ();
074                        if (!hasNext()) throw new NoSuchElementException();
075                        T item = a[index];
076                        index++;
077                        return item;
078                }
079        }
080
081        public String toString () {
082                if (N == 0) return "[]";
083                StringBuilder sb = new StringBuilder ("[");
084                sb.append (N + "/" + a.length + ":");
085                sb.append (a[0]);
086                for (int i = 1; i < N; i++) {
087                        sb.append (" ");
088                        sb.append (a[i]);
089                }
090                sb.append ("]");
091                return sb.toString ();
092        }
093
094        public static void main(String[] args) {
095                ResizingArray<Integer> a = new ResizingArray<>();
096                for (int i=0; i<10; i++) {
097                        a.add (StdRandom.uniform(100));
098                        StdOut.println (a);
099                }
100                a.set (1, 5);
101                StdOut.println (a);
102                a.addAll (new Integer[] { 1, 2, 3, 4, 5 });
103                StdOut.println (a);
104                Queue<Integer> q = new Queue<>();
105                for (int i = 1; i < 6; i++)
106                        q.enqueue (i);
107                a.addAll (q);
108                StdOut.println (a);
109        }
110}