Have to admit it, after a few (will not say how many) years studying Computer Science, architecting and developing systems in multiple programming languages and platforms I had missed the Bag algorithm :o( Gladly I am spending time reading and performing several (do not have time to work on all) exercises and examples in the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne.
The Bag algorithm is used to implement an object that stores in no particular order items added to it. There is an Application Programming Interface (API) to get the size of the bag and to determine if it is empty. If an Iterator is implemented, then a client is able to iterate in no particular order through the items in a bag.
From the console of the Eclipse IDE:
main >>> enter item (2exit): Hello
main >>> enter item (2exit): world
main >>> enter item (2exit): this
main >>> enter item (2exit): is
main >>> enter item (2exit): a
main >>> enter item (2exit): test
main >>> enter item (2exit): 2exit
main <<< 6 items in the bag
main <<< b: test a is this world Hello
The code for this implementation is an edited version of the Bag algorithm in the book on page 155:
package edu.princeton.cs.algs4;
import java.util.Iterator;
public class Bag<Item> implements Iterable<Item>{
private Node first;
private int N;
private class Node {
Item item;
Node next;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
public synchronized void add(Item item) {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
N++;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
public void remove() {}
}
// **** test code ****
public static void main(String[] args) {
Bag<String> b = new Bag<String>();
// **** ****
String item = “”;
do {
StdOut.print(“main >>> enter item (2exit): “);
item = StdIn.readString();
// **** add item to the bag (if needed) ****
if (!item.equals(“2exit”)) {
b.add(item);
}
} while (!item.equals(“2exit”));
// **** ****
StdOut.println(“main <<< ” + b.size() + ” items in the bag”);
// **** iterate through the bag ****
StdOut.print(“main <<< b: “);
for (String s : b) {
StdOut.print(s + ” “);
}
StdOut.println();
}
}
The algorithm for the Bag is quite similar to a Stack or Queue. The names of the methods are similar (i.e., isEmpty() and size()) or are missing (e.g., push(), pop(), enqueue(), dequeue()).
Not sure if an errata in the add() method was already reported. In my copy of the book, fourth printing, September 2013, the N++; statement was missing. I submitted an errata entry.
Not sure if I will spend the time generating entries for the Stack and Queue algorithms. They are quite similar to the Bag. My suggestion is to try them to make sure you get the concept of implementing an Iterator.
If you have comments or questions please let me know.
John
John.canessa@gmail.com