INTERFACE BSTAlg;

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.