/* avltree.q: AVL 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 AVLTree : SearchTree = private const nil, bin X H T1 T2;

public mkavltree Xs;

private mknode X T1 T2;
private join T1 T2, init T, last T, height T, slope T, rebal T;
private rol T, ror T, shl T, shr T;

mkavltree Xs:List		= foldl insert nil Xs;

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

insert nil Y			= bin 1 Y nil nil;
insert (bin H X T1 T2) Y	= rebal (mknode X (insert T1 Y) T2) if X>Y;
				= rebal (mknode X T1 (insert T2 Y)) if X<Y;
				= bin H Y T1 T2 if X=Y;

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

join nil T2			= T2;
join T1 T2			= rebal (mknode (last T1) (init T1) T2)
					otherwise;

init (bin H X T1 nil)		= T1;
init (bin H X T1 T2)		= rebal (mknode X T1 (init T2)) otherwise;

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

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

/* mknode constructs a tree node, computing the height value */

mknode X T1 T2			= bin (max (height T1) (height T2) +1)
					X T1 T2;

/* height and slope compute the height and slope (difference between heights
   of the left and the right subtree), respectively */

height nil			= 0;
height (bin H X T1 T2)		= H;

slope nil			= 0;
slope (bin H X T1 T2)		= height T1 - height T2;

/* rebal rebalances after single insertions and deletions */

rebal T				= shl T if slope T = -2;
				= shr T if slope T = 2;
				= T otherwise;

/* rotation operations */

rol (bin H X1 T1 (bin H2 X2 T2 T3))
				= mknode X2 (mknode X1 T1 T2) T3;

ror (bin H1 X1 (bin H2 X2 T1 T2) T3)
				= mknode X2 T1 (mknode X1 T2 T3);

shl (bin H X T1 T2)		= rol (mknode X T1 (ror T2)) if slope T2 =1;
				= rol (bin H X T1 T2) otherwise;

shr (bin H X T1 T2)		= ror (mknode X T1 (ror T2)) if slope T2 = -1;
				= ror (bin H X T1 T2) otherwise;