/**
 * Collections that support the key operations for binary search.
 *
 * @author Samuel A. Rebelsky
 * @version 1.1 of May 2004.
 */
public interface BinarySearchable 
  extends Collection
{
  /** 
   * Get the ``middle'' value in the collection. 
   * Preconditions: 
   *   (1) The collection is nonempty.
   * Postconditions: 
   *   (2) Returns some designated element in the collection.  That element
   *       should be less than approximately half the elements and greater 
   *       than approximately half the elements.
   */
  public Object middle();

  /** 
   * Get elements in the collection that are smaller than the
   * middle element.
   * Preconditions: 
   *   (1) The collection is nonempty.
   * Postconditions: 
   *   (1) Each element in the returned collection is smaller than or equal
   *       to the value returned by middle.
   *   (2) Any element in the original collection that is smaller than or
   *       equal to the value returned by middle is in the returned collection.
   */
  public BinarySearchable smaller();

  /** 
   * Get elements in the collection that are larger than the
   * middle element.
   * Preconditions: 
   *   (1) The collection is nonempty.
   * Postconditions: 
   *   (1) Each element in the returned collection is greater than or equal
   *       to the value returned by middle.
   *   (2) Any element in the original collection that is greater than or
   *       equal to the value returned by middle is in the returned collection.
   */
  public BinarySearchable larger();

  /**
   * Determine if the collection is empty.
   */
  public boolean isEmpty();
} // BinarySearchable