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;