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 9 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.)

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:

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

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.

2. 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:

• Currency items might be stored separately in a collection (e.g., in an ArrayList).
• The CurrencyItem class might be extended to a CurrencyDenomination class that keeps track of name of a currency denomination (e.g., Dime), the amount of the denomination (e.g, 10), and the number of those items being stored (e.g., 2 Dimes).
• Multiple CurrencyItem objects may be stored in a Map using distinct keys.

CurrencyCollection

3. 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 constructor which has a single int as parameter and creates a collection of CurrencyItem objects that have a total amount equal to the constructor's parameter.
     Hints:
     • Determine the required number of TwentyNotes, TenNotes, ..., Nickels, Pennies in order; use modular arithmetic (i.e., the remainder operator % to determine the number of each currency denomination needed.)
     • Some programmers may find that an array with denomination amounts may aid coding.
     • Some programmers may find a switch statement also may help in constructing specific objects. (Alternatively, use of a builder pattern might be helpful to some.)
   • a new method totalValue that sums the amount of the CurrencyItem items in the ArrayList
   • a revised toString method that returns a listing of the elements in stored in the collection.

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.

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

   • The initial constructor should set the count to 1.
   • A method increment should add 1 to the count.
   • A method decrement should subtract 1 from the count.
   • A method getCount should return the count (but there should be no setter method).
   • A revised toString method should include the count as well as the name and denomination value. (It would be nice if toString gave a grammatically plausible result, such as "1 dime" or "2 dimes".)

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

6. 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/8/docs/technotes/guides/collections/designfaq.html#a3]

7. 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.)

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

created 5 March 2012 revised 6 March 2012 links revised 13 October 2014 very minor editing 31 January 2020
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.