GENERIC

  TYPE Element IS PRIVATE;     -- assignment and equality predefined
  TYPE KeyType IS PRIVATE;     -- here too

  -- These generic parameters specify how to
  -- retrieve the key from an element, compare elements
  WITH FUNCTION KeyOf (Item: Element) RETURN KeyType IS <>;
  WITH FUNCTION "<"   (Key1, Key2: KeyType) RETURN Boolean IS <>;

PACKAGE Binary_Search_Trees_Generic IS
------------------------------------------------------------------------
--| Specification for Generic Binary Search Tree Package
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: January 1996                                     
------------------------------------------------------------------------

  TYPE Tree IS LIMITED PRIVATE;

  NotFound: EXCEPTION;
  
  PROCEDURE Initialize (T: IN OUT Tree);
  -- Pre:  none
  -- Post: T is an empty tree
  
  PROCEDURE Insert (T : IN OUT Tree; E : Element);
  -- Pre:   T and E are defined
  -- Post:  T is returned with E stored in a node in
  --        its proper place in T. If E is already in the tree,
  --        Insert has no effect.
  
  FUNCTION Search (T: Tree; K : KeyType) RETURN Tree;
  -- Pre:    T and K are defined
  -- Post:   if T has an node with an element E that contains K, 
  --         returns a pointer to E's location;
  -- Raises: NotFound if no such E is in T
  
  FUNCTION Retrieve (T: Tree) RETURN Element;             
  -- Pre:    T is defined
  -- Post:   returns the element stored at the node designated by T
  -- Raises: NotFound if T is NULL
  
  PROCEDURE Delete (T : IN OUT Tree; K : IN KeyType);     
  -- Pre:    T and K are defined
  -- Post:   If T has a node that contains K, T is returned 
  --         with that node deleted
  -- Raises: NotFound if E is not in the tree.
  
  GENERIC
    WITH PROCEDURE Visit (E : Element);
  PROCEDURE Traverse_LNR (T : Tree);
  -- Pre:  T is defined
  -- Post: T is traversed in left-node-right order

PRIVATE

  TYPE BinaryTreeNode;
  TYPE Tree IS ACCESS BinaryTreeNode;
  TYPE BinaryTreeNode IS RECORD
    Info  : Element;
    Left  : Tree := NULL;
    Right : Tree := NULL;
  END RECORD;

END Binary_Search_Trees_Generic;