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}