Keyed—random access to data by key.
Sorted—sequential access to data sorted by key.

The Keyed entity is also parent to a KeyedHash class that implements random access by key using a hashing algorithm. KeyedHash does not provide sorted access. The Sorted entity is also parent to a class that implements a general sorting algorithm for non-indexed data. The data produced by the sorting class can only be accessed sequentially, not randomly.

The KeyedIndex class requires multiple inheritance, inheriting from both parents—Keyed and Sorted. When we built the KeyedIndex class in Java, we needed to model at least one parent as an interface. We decided to create the KeyedIndex class by modeling the Keyed entity as an abstract class and the Sorted entity as an interface:

public abstract class Keyed
{
   ...
}

public interface Sorted
{
   ...
}

public class KeyedIndex extends Keyed
   implements Sorted
{
   ...
}

We chose this design for the following reasons:

• Random access by key is the primary use of KeyedIndex, sorted access by key is secondary.
• The Keyed entity is more complex and has more methods than the Sorted entity.
• The Keyed entity has common code shared by derived classes. The Sorted entity has nocommon code.
• The Keyed entity utilizes field variables. The Sorted entity has no variables.

—L.F.