WITH Lists_Generic;
PACKAGE BODY Trees_Xref_Generic IS
------------------------------------------------------------------------
--| Body of GenericXrefTrees, cross-reference version
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: January 1996                                     
------------------------------------------------------------------------

  PACKAGE XrefLists IS 
    NEW Lists_Generic (ElementType => NonKeyInfoType);
  USE XrefLists;
    
  TYPE BinaryTreeNode IS RECORD
    Key   : KeyType;
    Refs  : List;
    Left  : Tree;
    Right : Tree;
  END RECORD;

  -- procedure definitions, not exported

  FUNCTION MakeNode (K : IN KeyType;
                     V : IN NonKeyInfoType) RETURN Tree IS
  -- Pre:  K and V are defined
  -- Post: returns a pointer to a tree node, with K in
  --   the key field and V in the first node of a reference list

    Result : Tree;
  BEGIN
    Result     := NEW BinaryTreeNode;
    Result.Key := K;
    AddToRear(Result.Refs, V);
    RETURN Result;
  END MakeNode;

  PROCEDURE ConnectLeft (T : IN OUT tree;
                         K : KeyType;
                         V : NonKeyInfoType) IS
  -- Pre:  T, K, and V are defined; T.Left is NULL
  -- Post: creates a tree node using MakeNode, then attaches
  --   this new node to the left subtree of T
  BEGIN
    T.Left := MakeNode (K, V);
  END ConnectLeft;

  PROCEDURE ConnectRight (T : IN OUT tree;
                          K : KeyType;
                          V : NonKeyInfoType) IS
  -- Pre:  T, K, and V are defined; T.Right is NULL
  -- Post: creates a tree node using MakeNode, then attaches
  --   this new node to the right subtree of T
  BEGIN
    T.Right := MakeNode (K, V);
  END ConnectRight;

  PROCEDURE ProcessDuplicate (T : IN OUT tree;
                              K : IN KeyType;
                              V : IN NonKeyInfoType) IS
  -- Pre:  T, K, and V are defined
  -- Post: attaches V to the end of the reference list headed at T
  BEGIN
    AddToRear (T.Refs, V);
  END ProcessDuplicate;

  PROCEDURE Insert (T : IN OUT tree;
                    K : KeyType;
                    N : NonKeyInfoType) IS
  BEGIN

    IF T = NULL THEN
      T := MakeNode (K, N);

    ELSIF K < T.key THEN
      IF T.left = NULL THEN
        ConnectLeft (T, K, N);
      ELSE
        Insert (T.left, K, N);
      END IF;

    ELSIF T.Key < K THEN
      IF T.right = NULL THEN
        ConnectRight (T, K, N);
      ELSE
        Insert (T.right, K, N);
      END IF;

    ELSE
      ProcessDuplicate (T, K, N);
    END IF;
  END Insert;

  PROCEDURE VisitTree (T : Tree) IS
  -- Pre:  T is defined
  -- Post: traverses the list of references headed at T
    Current: Position;
  BEGIN
    DisplayKey (T.Key);
    Current := First(T.Refs);
    WHILE NOT IsPastEnd(T.Refs, Current) LOOP
      DisplayRef (Retrieve(T.Refs, Current));
      GoAhead (T.Refs, Current);
    END LOOP;
  END VisitTree;

  PROCEDURE Display (T : tree) IS
  BEGIN
    IF T = NULL THEN
      RETURN;
    ELSE
      Display (T.Left);
      VisitTree (T);
      Display (T.Right);
    END IF;
  END Display;

END Trees_Xref_Generic;