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}