001package algs13; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005/* *********************************************************************** 006 * Compilation: javac ResizingArrayBag.java 007 * Execution: java ResizingArrayBag 008 * 009 * Bag implementation with a resizing array. 010 * 011 *************************************************************************/ 012 013public class XResizingArrayBag<T> implements Iterable<T> { 014 private T[] a; // array of items 015 private int N = 0; // number of elements on stack 016 017 // create an empty bag 018 @SuppressWarnings("unchecked") 019 public XResizingArrayBag() { 020 a = (T[]) new Object[2]; 021 } 022 023 public boolean isEmpty() { return N == 0; } 024 public int size() { return N; } 025 026 // resize the underlying array holding the elements 027 private void resize(int capacity) { 028 if (capacity <= N) throw new IllegalArgumentException (); 029 @SuppressWarnings("unchecked") 030 T[] temp = (T[]) new Object[capacity]; 031 for (int i = 0; i < N; i++) 032 temp[i] = a[i]; 033 a = temp; 034 } 035 036 // add a new item to the bag 037 public void add(T item) { 038 if (N == a.length) resize(2*a.length); // double size of array if necessary 039 a[N++] = item; // add item 040 } 041 042 public Iterator<T> iterator() { return new ArrayIterator(); } 043 044 // an iterator, doesn't implement remove() since it's optional 045 private class ArrayIterator implements Iterator<T> { 046 private int i = 0; 047 public boolean hasNext() { return i < N; } 048 public void remove() { throw new UnsupportedOperationException(); } 049 050 public T next() { 051 if (!hasNext()) throw new NoSuchElementException(); 052 return a[i++]; 053 } 054 } 055 056 057 058 /* ********************************************************************* 059 * Test routine. 060 **********************************************************************/ 061 public static void main(String[] args) { 062 XResizingArrayBag<String> bag = new XResizingArrayBag<>(); 063 bag.add("Hello"); 064 bag.add("World"); 065 bag.add("how"); 066 bag.add("are"); 067 bag.add("you"); 068 069 for (String s : bag) 070 StdOut.println(s); 071 } 072 073}