/* bintree.q: binary search tree data structure (11-07-1993, revised
   03-02-2002 AG) */

/* This file is part of the trees.q sample script. */

include searchtree;

public type BinTree : SearchTree = private const nil, bin X T1 T2;

public mkbintree Xs;

private join T1 T2, init T, last T;

mkbintree Xs:List		= foldl insert nil Xs;

members nil			= [];
members (bin X T1 T2)		= members T1 ++ [X|members T2];

insert nil Y			= bin Y nil nil;
insert (bin X T1 T2) Y		= bin X (insert T1 Y) T2 if X>Y;
				= bin X T1 (insert T2 Y) if X<Y;
				= bin Y T1 T2 if X=Y;

delete nil Y			= nil;
delete (bin X T1 T2) Y		= bin X (delete T1 Y) T2 if X>Y;
				= bin X T1 (delete T2 Y) if X<Y;
				= join T1 T2 if X=Y;

join nil T2			= T2;
join T1 T2			= bin (last T1) (init T1) T2 otherwise;

init (bin X T1 nil)		= T1;
init (bin X T1 T2)		= bin X T1 (init T2) otherwise;

last (bin X T1 nil)		= X;
last (bin X T1 T2)		= last T2 otherwise;

member nil Y			= false;
member (bin X T1 T2) Y		= member T1 Y if X>Y;
				= member T2 Y if X<Y;
				= true if X=Y;