Bag Implementations That Use Arrays - Data Structures and Abstractions with Java - page 43

assumes that the search for the entry is done already, so we can ignore the first step of the
pseudocode. The rest of the pseudocode, however, gives the basic logic for removing an entry.
We can revise the pseudocode as follows:
// Removes and returns the entry at a given index within the arraybag.
// If no such entry exists, returns null.
if ( the bag is not empty and the given index is not negative )
{

result = bag[givenIndex]
Decrement the counter numberOfEntries
bag[givenIndex] = bag[numberOfEntries]
bag[numberOfEntries] = null
return result

}
else
return null

The definition of the method remove given in the previous segment passes the integer returned by
getIndexOf to removeEntry . Since getIndexOf can return -1, removeEntry must watch for such an
argument. Thus, if the bag is not empty —that is, if numberOfEntries is greater than zero—and
givenIndex is greater than or equal to zero, removeEntry removes the array entry at givenIndex by
replacing it with the last entry and decrementing numberOfEntries . The method then returns the
removed entry. If, however, the bag is empty, the method returns null .
The code for the method is
// Removes and returns the entry at a given index within the arraybag.
// If no such entry exists, returns null.
private T removeEntry( int givenIndex)
{

T result = null ;
if (!isEmpty() && (givenIndex >= 0))
{

result = bag[givenIndex]; // entry to remove

numberOfEntries--;
bag[givenIndex] = bag[numberOfEntries]; // replace entry with last entry

bag[numberOfEntries] = null ; // remove last entry

} // end if
return result;
} // end removeEntry

2.27

Locating the entry to remove. We now need to think about locating the entry to remove from the
bag so we can pass its index to removeEntry . The method contains performs the same search that
we will use to locate anEntry within the definition of remove . Unfortunately, contains returns true
or false; it does not return the index of the entry it locates in the array. Thus, we cannot simply call
that method within our method definition.

Design Decision: Should the method contains return the index of a located entry?
Should we change the definition of contains so that it returns an index instead of a boolean value?
No. As a public method, contains should not provide a client with such implementation details. The
client should have no expectation that a bag's entries are in an array, since they are in no particular
order. Instead of changing the specifications for contains , we will follow our original plan to define a
private method to search for an entry and return its index.