Go to Package Implementation

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;