You need to find out how many times an object occurs within a Collection, and you need a Collection that lets you manipulate the cardinality of objects it contains.

Use a Bag. A Bag can store the same object multiple times while keeping track of how many copies it contains. For example, a Bag object can contain 20 copies of object “A” and 50 copies of object “B,” and it can be queried to see how many copies of an object it contains. You can also add or remove multiple copies of an object—add 10 copies of “A” or remove 4 copies of “B.” The following example creates a Bag and adds multiple copies of two String objects:

import org.apache.commons.collections.Bag;
import org.apache.commons.collections.bag.HashBag;

Bag bag = new HashBag( );

bag.add( "TEST1", 100 );
bag.add( "TEST2", 500 );

int test1Count = bag.getCount( "TEST1" );
int test2Count = bag.getCount( "TEST2" );

System.out.println( "Counts: TEST1: " + test1Count + ", TEST2: " + test2Count );

bag.remove( "TEST1", 1 );
bag.remove( "TEST2", 10 );

int test1Count = bag.getCount( "TEST1" );
int test2Count = bag.getCount( "TEST2" );

System.out.println( "Counts: TEST1: " + test1Count + ", TEST2: " + test2Count );

This example put 100 copies of the String “TEST1” and 500 copies of the String “TEST2” into a HashBag. The contents of the Bag are then printed, and 1 instance of “TEST1” and 10 instances of “TEST2” are removed from the Bag:

Counts: TEST1: 100, TEST2: 500
Counts: TEST1: 99, TEST2: 490

Bag has two implementations—HashBag and TreeBag—which use a HashMap and a TreeMap to store the contents of a Bag. The same design considerations apply to Bag that apply to Map. Use HashBag for performance and TreeBag when it is important to maintain the order that each distinct object was added to a Bag. A TreeBag returns unique objects in the order they were introduced to the Bag.

To demonstrate the Bag object, a system to track inventory is created using a Bag as an underlying data structure. An inventory management system must find out how many copies of a product are in stock, and a Bag is appropriate because it allows you to keep track of the cardinality of an object in a Collection. In Example 5-3, a record store tracks an inventory of albums, consisting of 200 Radiohead albums, 100 Kraftwerk albums, 500 Charlie Parker albums, and 900 ABBA albums.

package com.discursive.jccook.collections.bag;

import java.text.NumberFormat;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;

import org.apache.commons.collections.Bag;
import org.apache.commons.collections.bag.HashBag;
import org.apache.commons.lang.StringUtils;

public class BagExample {
    Bag inventoryBag = new HashBag( );
    
    // Define 4 Albums
    Album album1 = new Album( "Radiohead", "OK Computer" );
    Album album2 = new Album( "Kraftwerk", "The Man-Machine" );
    Album album3 = new Album( "Charlie Parker", "Now's the Time" );
    Album album4 = new Album( "ABBA", "ABBA - Gold: Greatest Hits" );

    public static void main(String[] args) {
        BagExample example = new BagExample( );
        example.start( );
    }
    
    private void start( ) {
        // Read our inventory into a Bag
        populateInventory( );

        System.out.println( "Inventory before Transactions" );
        printAlbums( inventoryBag );
        printSeparator( );

        // A Customer wants to purchase 500 ABBA, 2 Radiohead, and 150 Parker
        Bag shoppingCart1 = new HashBag( );
        shoppingCart1.add( album4, 500 );
        shoppingCart1.add( album3, 150 );
        shoppingCart1.add( album1, 2 );
        checkout( shoppingCart1, "Customer 1" );
        
        // Another Customer wants to purchase 600 copies of ABBA 
        Bag shoppingCart2 = new HashBag( );
        shoppingCart2.add( album4, 600 );
        checkout( shoppingCart2, "Customer 2" );

        // Another Customer wants to purchase 3 copies of Kraftwerk
        Bag shoppingCart3 = new HashBag( );
        shoppingCart3.add( album2, 3 );
        checkout( shoppingCart3, "Customer 3" );

        System.out.println( "Inventory after Transactions" );
        printAlbums( inventoryBag );
        
    }
    
    private void populateInventory( ) {
        // Adds items to a Bag
        inventoryBag.add( album1, 200 );
        inventoryBag.add( album2, 100 );
        inventoryBag.add( album3, 500 );
        inventoryBag.add( album4, 900 );
    }
    
    private void printAlbums( Bag albumBag ) {
        Set albums = albumBag.uniqueSet( );
        Iterator albumIterator = albums.iterator( );
        while( albumIterator.hasNext( ) ) {
            Album album = (Album) albumIterator.next( );
            NumberFormat format = NumberFormat.getInstance( );
            format.setMinimumIntegerDigits( 3 );
            format.setMaximumFractionDigits( 0 );
            System.out.println( "	" +  
                format.format( albumBag.getCount( album ) ) + 
                " - " + album.getBand( )  );
        }
    }
    
    private void checkout( Bag shoppingCart, String customer ) {
        // Check to see if we have the inventory to cover this purchase
        if( inventoryBag.containsAll( (Collection) shoppingCart ) ) {
            // Remove these items from our inventory
            inventoryBag.removeAll( (Collection) shoppingCart );
            System.out.println( customer + " purchased the following items:" );
            printAlbums( shoppingCart );
        } else {
            System.out.println( customer + ", I'm sorry " +
                                "but we are unable to fill your order." );
        }
        printSeparator( );
    }
    
    private void printSeparator( ) {
        System.out.println( StringUtils.repeat( "*", 65 ) );
    }
}

Albums are stored in the inventoryBag variable, which is populated by a call to populateInventory() method. The printAlbums() method demonstrates how a Bag’s iterator will iterate through all of the distinct objects stored in a Bag, printing out the count for each album by calling getCount( ) on the inventoryBag. After populating and printing the store’s inventory, the start( ) method models the behavior of three customers. Each customer creates a Bag instance, shoppingBag, which holds the Album objects she wishes to purchase.

When a customer checks out of the store, the containsAll() method is called to make sure that the inventoryBag contains adequate inventory to fulfill a customer’s order. If a customer attempts to buy 40 copies of an album, we create a Bag with 40 instances of the Album object, and containsAll( ) will only return true if the inventoryBag contains at least 40 matching albums. Certain that the order can be fulfilled, removeAll( ) reduces the number of albums in the inventoryBag by 40 and the customer’s transaction is considered complete.

Each customer transaction is modeled by a Bag that is subtracted from the inventoryBag using the removeAll( ) method. Example 5-3 prints the inventory before and after the three customer transactions, summarizing the result of each:

Inventory before Transactions
    200 - Radiohead
    100 - Kraftwerk
    900 - ABBA
    500 - Charlie Parker
*****************************************************************
Customer 1 purchased the following items:
    002 - Radiohead
    500 - ABBA
    150 - Charlie Parker
*****************************************************************
Customer 2, I'm sorry but we are unable to fill your order.
*****************************************************************
Customer 3 purchased the following items:
    003 - Kraftwerk
*****************************************************************
Inventory after Transactions
    198 - Radiohead
    097 - Kraftwerk
    400 - ABBA
    350 - Charlie Parker

Technically speaking, Bag is not a real Collection implementation. The removeAll( ), containsAll( ), add(), remove( ), and retainAll( ) methods do not strictly follow the contract defined by the Collection interface. Adhering to a strict interpretation of the Collection interface, removeAll( ) should remove all traces of an object from a collection, and containsAll( ) should not pay attention to the cardinality of an object in a collection. Calling removeAll( ) with a single Album object should clear the Bag of any references to the specified Album object, and containsAll( ) should return true if a collection contains even one instance of a specified object. In Bag, a call to removeAll( ) with three Album objects will remove only the specified number of each Album object. In Example 5-3, the checkout( ) method uses removeAll( ) to remove albums from the inventory. A call to containsAll( ) will only return true if a Bag contains a number greater than or equal to the cardinality specified in the Collection. In Example 5-3, the checkout( ) method uses containsAll( ) to see if there is sufficient inventory to satisfy an order. These violations should not keep you from using Bag, but keep these exceptions to the collection interface in mind if you are going to expose a Bag as a collection in a widely used API.

For more information about the bag data structure, look at a definition from the National Institute of Standards and Technology (NIST) at http://www.nist.gov/dads/HTML/bag.html.