Bag Algorithm

bag_queue_stackHave 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

Leave a Reply

Your email address will not be published. Required fields are marked *