A Second ADT: SortedList

In Chapter 3 we built a SortedArray: a structure that keeps its elements in sorted order so that it can find them quickly with binary search. It has this public interface:

public class SortedArray<T extends Comparable<T>> {
  public void add(T element) { ... }
  public T get(int index) { ... }
  public boolean remove(T element) { ... }
  public boolean contains(T element) { ... }
  public int indexOf(T element) { ... }
  public int size() { ... }
}

This comes close to the List interface, but it does not have set. A SortedArray cannot support set, because that would allow a caller to put an element at an index that does not match its sorted position and break the sorted order.

If we wanted to make SortedArray a List, we would have to implement set in some way. One strategy is to have set throw an exception:

@Override
public void set(int index, T element) {
  throw new UnsupportedOperationException("a sorted list has no set");
}

Java’s standard library does something similar. I think it is a bad idea. When we throw an exception for set, we are violating the List contract. A caller could pass a SortedArray to any code that expects a List, and that code would call set. The program would compile, but it would fail at run time.

Given how we defined List, a sorted array is not a List. A sorted array is a kind of list, but a different one with its own contract.

Let’s define a SortedList ADT that is similar to List, but without set.

/**
 * A SortedList keeps its non-null elements in ascending order at all times. The
 * position of an element is determined by its value, not by the caller, so there
 * is no way to place a value at a chosen index.
 *
 * @param <T> the element type; must be Comparable so elements can be ordered.
 */
public interface SortedList<T extends Comparable<T>> {

  /**
   * Insert a value into the position that keeps this list sorted.
   *
   * @param element the non-null value to insert.
   * @throws NullPointerException if element is null.
   */
  void add(T element);

  /**
   * Return the element at the given index, where index 0 is the smallest value.
   *
   * @param index a position from 0 to size() - 1.
   * @return the element at that position.
   * @throws IndexOutOfBoundsException if index < 0 or index >= size().
   */
  T get(int index);

  /**
   * Remove the first occurrence of a value.
   *
   * @param element the value to remove.
   * @return true if a value was removed, false if it was not found.
   */
  boolean remove(T element);

  /**
   * Report whether a value is present in this list.
   *
   * @param element the value to look for.
   * @return true if present, false otherwise.
   */
  boolean contains(T element);

  /**
   * Find the index of the first occurrence of a value.
   *
   * @param element the value to look for.
   * @return the index of the first occurrence, or -1 if not present.
   */
  int indexOf(T element);

  /**
   * Report how many elements are in this list.
   *
   * @return the number of elements; never negative.
   */
  int size();
}

A SortedList does not have the set method, and it needs comparable (and non-null) elements so it can keep them in order.