Another way to store a collection of items is called a keyed bag. In this type of bag, whenever an item is added, the programmer using the bag also provides an integer called the key. Each item added to the keyed bag must have a unique key; two items cannot have the same key. For this project, implement a keyed bag in which the items to be stored are strings (perhaps people’s names) and the keys are numbers (perhaps Social Security or other identification numbers). So, the insertion method has this specification: 

public void insert
(String entry, int key);
// Precondition: size( ) < CAPACITY, and the
// bag does not yet contain any item
// with the given key.
// Postcondition: A new copy of entry has
// been added to the bag, with the given key.

When the programmer wants to remove or retrieve an item from a keyed bag, the key of the item must be specified rather than the item itself. The keyed bag should also have a boolean method that can be used to determine whether the bag has an item with a specified key.

A keyed bag differs from the bag with receipts (in the previous project). In a keyed bag, the programmer using the class specifies a particular key when an item is inserted. In contrast, for a bag with receipts, the insert method returns a receipt, and the programmer using the class has no control over what that receipt might be.

Here’s an implementation idea: A keyed bag can have two private arrays, one that holds the string data and one that holds the corresponding keys. The data at location data[i] has a key that is stored in key[i].

Data from Previous Project

In this project, you will implement a new class called a bag with receipts. This new class is similar to an ordinary bag, but the data consists of strings, and the way that the strings are added and removed is different. Each time a string is added to a bag with receipts, the insert method returns a unique integer called the receipt. Later, when you want to remove a string, you must provide a copy of the receipt as a parameter to the remove method. The remove method removes the item whose receipt has been presented and also returns that item through its return value. You may also have a method that returns a copy of the string without removing it.

Here’s an implementation idea: A bag with receipts can have a private array, like this:

private String[ ] data;

Some locations in this array may contain null, which means that that location is unused. When a new string is added, we will find the first spot that is currently unused and store the new string there. The receipt for the string is the index of the location where the string is stored.