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.
Example 5-3. Using a Bag to track inventory
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.
18.118.208.97