Sorted Lists - Data Structures and Abstractions with Java - page 410

16.3

The first two methods are straightforward, but getPosition deserves some comment. Given an
entry in the sorted list, the method getPosition returns the entry's position number within the list,
as you would expect. We number the entries beginning with 1, just as we do for the ADT list. But
what if the given entry is not in the sorted list? In this case, getPosition returns the position num-
ber where the entry belongs in the list. The returned number is negative, however, to signal that the
entry is not in the list. For example, if missingObject is not in the sorted list sList but belongs at
position 3, sList.getPosition(missingObject) would return - 3.
The sorted list also has some, but not all, of the operations of an ADT list. We have already
mentioned that adding an entry at a given position is not possible, because otherwise the client
could destroy the order of the sorted list. For the same reason, the list's replace method is not
available to a sorted list. The other operations of the ADT list, however, are useful for a sorted list
as well, including the ones that retrieve or remove the entry at a given position. The methods
getEntry and remove each have a position number as a parameter, but they will not alter the rela-
tive order of the entries in the sorted list.
Although the list's remove method returns the object removed from the list, it is not necessary
for the sorted list's remove method to do so. The client already has at least a copy of this entry to
enable it to invoke sorted list's remove .

16.4

The Java interface in Listing 16-1 specifies these operations in more detail. The notation ? super T ,
which Segment 8.2 introduced, means any superclass of the generic type T .

LISTING 16-1

The interface SortedListInterface

/** An interface for the ADT sorted list.
Entries in the list have positions that begin with 1.

*/
public interface SortedListInterface<T extends Comparable<? super T>>
{

/** Adds a new entry to this sorted list in its proper order.
@param newEntry the object to be added as a new entry */
public void add(T newEntry);

/** Removes a specified entry from this sorted list.
@param anEntry the object to be removed
@return true if anEntry was located and removed */
public boolean remove(T anEntry);

/** Gets the position of an entry in this sorted list.
@param anEntry the object to be found
@return the position of the first or only occurrence of anEntry
if it occurs in the list; otherwise returns the position
where anEntry would occur in the list, but as a negative
integer */
public int getPosition(T anEntry);

// The following methods are described in Segment 12.7 of Chapter 12
// as part of the ADT list:

public T getEntry( int givenPosition);