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}