01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package algs13;
import stdlib.*;
import java.util.Iterator;
import java.util.NoSuchElementException;
/* ***********************************************************************
 *  Compilation:  javac ResizingArrayBag.java
 *  Execution:    java ResizingArrayBag
 *
 *  Bag implementation with a resizing array.
 *
 *************************************************************************/

public class XResizingArrayBag<T> implements Iterable<T> {
  private T[] a;         // array of items
  private int N = 0;        // number of elements on stack

  // create an empty bag
  @SuppressWarnings("unchecked")
  public XResizingArrayBag() {
    a = (T[]) new Object[2];
  }

  public boolean isEmpty() { return N == 0; }
  public int size()        { return N;      }

  // resize the underlying array holding the elements
  private void resize(int capacity) {
    if (capacity <= N) throw new IllegalArgumentException ();
    @SuppressWarnings("unchecked")
    T[] temp = (T[]) new Object[capacity];
    for (int i = 0; i < N; i++)
      temp[i] = a[i];
    a = temp;
  }

  // add a new item to the bag
  public void add(T item) {
    if (N == a.length) resize(2*a.length);    // double size of array if necessary
    a[N++] = item;                            // add item
  }

  public Iterator<T> iterator()  { return new ArrayIterator();  }

  // an iterator, doesn't implement remove() since it's optional
  private class ArrayIterator implements Iterator<T> {
    private int i = 0;
    public boolean hasNext()  { return i < N;                               }
    public void remove()      { throw new UnsupportedOperationException();  }

    public T next() {
      if (!hasNext()) throw new NoSuchElementException();
      return a[i++];
    }
  }



  /* *********************************************************************
   * Test routine.
   **********************************************************************/
  public static void main(String[] args) {
    XResizingArrayBag<String> bag = new XResizingArrayBag<>();
    bag.add("Hello");
    bag.add("World");
    bag.add("how");
    bag.add("are");
    bag.add("you");

    for (String s : bag)
      StdOut.println(s);
  }

}