001package algs13; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005 006 007/** 008 * The {@code ResizingArrayBag} class represents a bag (or multiset) of 009 * generic items. It supports insertion and iterating over the 010 * items in arbitrary order. 011 * <p> 012 * This implementation uses a resizing array. 013 * See {@link LinkedBag} for a version that uses a singly linked list. 014 * The <em>add</em> operation takes constant amortized time; the 015 * <em>isEmpty</em>, and <em>size</em> operations 016 * take constant time. Iteration takes time proportional to the number of items. 017 * <p> 018 * For additional documentation, see <a href="https://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of 019 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 020 * 021 * @author Robert Sedgewick 022 * @author Kevin Wayne 023 */ 024public class ResizingArrayBag<Item> implements Iterable<Item> { 025 // initial capacity of underlying resizing array 026 private static final int INIT_CAPACITY = 8; 027 028 private Item[] a; // array of items 029 private int n; // number of elements on bag 030 031 /** 032 * Initializes an empty bag. 033 */ 034 @SuppressWarnings("unchecked") 035 public ResizingArrayBag() { 036 a = (Item[]) new Object[INIT_CAPACITY]; 037 n = 0; 038 } 039 040 /** 041 * Is this bag empty? 042 * @return true if this bag is empty; false otherwise 043 */ 044 public boolean isEmpty() { 045 return n == 0; 046 } 047 048 /** 049 * Returns the number of items in this bag. 050 * @return the number of items in this bag 051 */ 052 public int size() { 053 return n; 054 } 055 056 // resize the underlying array holding the elements 057 @SuppressWarnings("unchecked") 058 private void resize(int capacity) { 059 assert capacity >= n; 060 Item[] copy = (Item[]) new Object[capacity]; 061 for (int i = 0; i < n; i++) 062 copy[i] = a[i]; 063 a = copy; 064 } 065 066 /** 067 * Adds the item to this bag. 068 * @param item the item to add to this bag 069 */ 070 public void add(Item item) { 071 if (n == a.length) resize(2*a.length); // double size of array if necessary 072 a[n++] = item; // add item 073 } 074 075 076 /** 077 * Returns an iterator that iterates over the items in the bag in arbitrary order. 078 * @return an iterator that iterates over the items in the bag in arbitrary order 079 */ 080 public Iterator<Item> iterator() { 081 return new ArrayIterator(); 082 } 083 084 // an iterator, doesn't implement remove() since it's optional 085 private class ArrayIterator implements Iterator<Item> { 086 private int i = 0; 087 public boolean hasNext() { return i < n; } 088 public void remove() { throw new UnsupportedOperationException(); } 089 090 public Item next() { 091 if (!hasNext()) throw new NoSuchElementException(); 092 return a[i++]; 093 } 094 } 095 096 /** 097 * Unit tests the {@code ResizingArrayBag} data type. 098 * 099 * @param args the command-line arguments 100 */ 101 public static void main(String[] args) { 102 ResizingArrayBag<String> bag = new ResizingArrayBag<String>(); 103 bag.add("Hello"); 104 bag.add("World"); 105 bag.add("how"); 106 bag.add("are"); 107 bag.add("you"); 108 109 for (String s : bag) 110 StdOut.println(s); 111 } 112}