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