001package algs13; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005 006/** 007 * The {@code Bag} class represents a bag (or multiset) of 008 * generic items. It supports insertion and iterating over the 009 * items in arbitrary order. 010 * <p> 011 * The <em>add</em>, <em>isEmpty</em>, and <em>size</em> operation 012 * take constant time. Iteration takes time proportional to the number of items. 013 * <p> 014 * For additional documentation, see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of 015 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 016 */ 017public class Bag<T> implements Iterable<T> { 018 private int N; // number of elements in bag 019 private Node<T> first; // beginning of bag 020 021 // helper linked list class 022 private static class Node<T> { 023 public Node() { } 024 public T item; 025 public Node<T> next; 026 } 027 028 /** 029 * Create an empty stack. 030 */ 031 public Bag() { 032 first = null; 033 N = 0; 034 } 035 036 /** 037 * Is the BAG empty? 038 */ 039 public boolean isEmpty() { 040 return first == null; 041 } 042 043 /** 044 * Return the number of items in the bag. 045 */ 046 public int size() { 047 return N; 048 } 049 050 /** 051 * Add the item to the bag. 052 */ 053 public void add(T item) { 054 Node<T> oldfirst = first; 055 first = new Node<>(); 056 first.item = item; 057 first.next = oldfirst; 058 N++; 059 } 060 061 // check internal invariants 062 protected static <T> boolean check(Bag<T> that) { 063 int N = that.N; 064 Bag.Node<T> first = that.first; 065 if (N == 0) { 066 if (first != null) return false; 067 } 068 else if (N == 1) { 069 if (first == null) return false; 070 if (first.next != null) return false; 071 } 072 else { 073 if (first.next == null) return false; 074 } 075 076 // check internal consistency of instance variable N 077 int numberOfNodes = 0; 078 for (Bag.Node<T> x = first; x != null; x = x.next) { 079 numberOfNodes++; 080 } 081 if (numberOfNodes != N) return false; 082 083 return true; 084 } 085 086 087 /** 088 * Return an iterator that iterates over the items in the bag. 089 */ 090 public Iterator<T> iterator() { 091 return new ListIterator(); 092 } 093 094 // an iterator, doesn't implement remove() since it's optional 095 private class ListIterator implements Iterator<T> { 096 private Node<T> current = first; 097 098 public boolean hasNext() { return current != null; } 099 public void remove() { throw new UnsupportedOperationException(); } 100 101 public T next() { 102 if (!hasNext()) throw new NoSuchElementException(); 103 T item = current.item; 104 current = current.next; 105 return item; 106 } 107 } 108 109 /** 110 * A test client. 111 */ 112 public static void main(String[] args) { 113 StdIn.fromString ("to be or not to - be - - that - - - is"); 114 Bag<String> bag = new Bag<>(); 115 while (!StdIn.isEmpty()) { 116 String item = StdIn.readString(); 117 bag.add(item); 118 } 119 120 StdOut.println("size of bag = " + bag.size()); 121 for (String s : bag) { 122 StdOut.println(s); 123 } 124 } 125}