CSC 207 Grinnell College Spring, 2012
 
Algorithms and Object-Oriented Design
 

Sets and Multisets

Summary

This laboratory provides practice working with sets and multisets in the context of a simple problem.

Reference

Several parts of this lab make use of the Java 6 API.

Introduction

Consider the problem of paying for an item at a store and then making change.

For the purposes, we will consider the following currency. (For convenience, all amounts will be in pennies, so all currency amounts can be an int type.)

Currency
Name
Amount   Currency
Name
Amount
twentyNote 2000   quarter 25
tenNote 1000   dime 10
fiveNote 500   nickel 5
oneNote 100   penny 1

When paying a bill or when receiving change for a purchase, a monetary amount typically involves some combination of currency items. For example, $14.96 might be obtained as one tenNote, four oneNotes, three quarters, two dimes, and one penny. This lab considers how such amounts might be modeled within Java.

Currency Denominations

Each currency denomination has two basic properties: a name and an amount, as indicated in the above table. This can be modeled as the following base class within a new package currency:

package currency;

/** Base class to specify a single item of currency, such as
 *  a ten-dollar note or a dime
 *  Each item of currency has a name and an amount
 * @author walker
 *
 */
public class CurrencyItem {
	
	private String name;
	private int amount;
	
	public CurrencyItem (String label, int value)
	{
		name = label;
		amount = value;
	}

	/** the currency name and amount can be retrieved,
	 *  but neither the name nor the amount can be changed
	 */
	public String getName() {
		return name;
	}

	/** the face value of the currency (in cents), such as 10 for a dime
	 */
	public int getAmount() {
		return amount;
	}
	
	/** the public name/amount for this currency item
	 */
	public String toString() {
		return (name + " (" + amount + ")" );
	}
}

Subclasses of CurrencyItem can provide details for each denomination of currency, such as the following definition of a Penny class:

package currency;

/** Subclass for a 10-cent currency denomination 
 * 
 * @author walker
 *
 */
public class Dime extends CurrencyItem {
	
	public Dime ()
	{
		super ("Dime", 10);
	}
}

Additional classes for the various currency denominations are available at the following currency directory

  1. In reviewing class CurrencyItem, why do you think fields name and amount are declared as private (rather than protected), and why does CurrencyItem have getters but no setters?

Often it is worthwhile to be able to place currency items in descending value order. That is, a TwentyNote would be considered to come before a TenNote; a TenNote would come before a FiveNote; etc. Generally, ordering could be determined by comparing the amount of two objects.

  1. Modify the CurrencyItem class, so that it implements the Comparable interface to reflect the ordering of currency objects in descending order.

A Collection of Currency Denominations

With the basic denominations of currency determined, the payment of money involves a collection of currency items. Basically, this might be done in at least three ways:

CurrencyCollection

  1. Write a class CurrencyCollection that extends class ArrayList:

    public class CurrencyCollection extends ArrayList<CurrencyItem>
    

    In addition to the inherited ArrayList methods, a CurrencyCollection should have:

A Currency MultiSet

In computing, a bag or multiset behaves much like a set, except that duplicate items are allowed. One way to implement a multiset involves adding a field to an object that keeps track of how many times an item appears in the set.

  1. Extend CurrencyItem to yield a class CurrencyDenomination that includes a counter of how many times an item should be counted.

  2. Write new subclasses of CurrencyDenomination for each type of currency in the table near the top of this lab

  3. Write a class CurrencyMultiSet that extends Set for CurrencyDenominations to provide similar capabilities as CurrencyCollection in Step 1. Pragmatically, you may want to use an implementation of Set as a starting point.

A Currency Map

One commentary on multisets in Java states,

3. Why isn't there a core interface for "bags" (AKA multisets)?

The Collection interface provides this functionality. We are not providing any public implementations of this interface, as we think that it wouldn't be used frequently enough to "pull its weight." We occasionally return such Collections, which are implemented easily atop AbstractCollection (for example, the Collection returned by Map.values).

[from http://docs.oracle.com/javase/1.4.2/docs/guide/collections/designfaq.html#3]

  1. Examine the definition of the Map interface in Java (with one of its implementations, such as a HashMap or Hashtable) and write an implementation of a multiset for currency items. (To the extent possible, use the CurrencyItem class and its subclasses from the beginning of this lab as items to be stored as part of this map.)

  2. Write a class NewCurrencyMultiSet that uses this Map approach to provide similar capabilities as CurrencyCollection in Step 1.


This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/207.sp012/labs/lab-sets-multisets.shtml

created 5 March 2012
last revised 6 March 2012
Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.