mentor/src/searchtree/BSTAlg.i3


 Copyright (C) 1992, Digital Equipment Corporation                         
 All rights reserved.                                                      
 See the file COPYRIGHT for a full description.                            
                                                                           
 Last modified on Wed Jun 15 11:10:33 PDT 1994 by heydon                   
      modified on Tue May  3 13:29:58 PDT 1994 by najork                   

INTERFACE BSTAlg;
Interface to types/procedures common to all binary search tree algorithms.

IMPORT Random, SearchTreeAlgClass, VBT;

TYPE
  PanelData = OBJECT
    nodeCnt: INTEGER;			 (* number of nodes to add *)
    inputType: TEXT;			 (* input data type choice *)
    deleteType: TEXT;			 (* deletion data type choice *)
    rand: Random.T;			 (* random number generator *)
  END;

  Key = CARDINAL;			 (* key value *)
  Keys = REF ARRAY OF Key;		 (* node key array *)

  Node = OBJECT
    key: Key;
    index: INTEGER;			 (* for use by MG *)
    parent, left, right: Node := NIL
  END;

  Tree = OBJECT
    root: Node := NIL;
    nil:  Node := NIL;
  END;

  T = SearchTreeAlgClass.T BRANDED OBJECT
    tree: Tree := NIL;
  END;

  Side = {Left, Right};

VAR
  OtherSide := ARRAY Side OF Side{Side.Right, Side.Left};

PROCEDURE GetPanelData(panel: VBT.T): PanelData;
Returns a new PanelData with field read from the panel panel.

PROCEDURE NewKeys(data: PanelData; input := TRUE): Keys;
Return an array of data.nodeCnt new keys containing some permutation of the key values [1..data.nodeCnt]. If data.inputType = rand, then the permutation is a random one; the seed for the random number generator is data.seed if data.useSeed = TRUE, or a random seed otherwise. If data.inputType = inc, then the permutation contains the keys in increasing order. If data.inputType = dec, then the permutation contains the keys in decreasing order. IF input is false, then the string data.deleteType is used to determine how to build the resulting key array instead of data.inputType.

PROCEDURE NewIndex(): INTEGER;
Returns a new, distinct node index.

PROCEDURE GetChild(node: Node; side: Side): Node;
Returns node.left if side = Side.Left; returns node.right if side = Side.Right.

PROCEDURE SetChild(node: Node; side: Side; val: Node);
Sets node.left to val if side = Side.Left; sets node.right to val if side = Side.Right.

PROCEDURE Rotate(t: Tree; parent: Node; side: Side);
Rotates the parent node about it's side child, and updates the parent of parent (which may be t.root) to point to the new parent.

END BSTAlg.