class Comparable<T> {
    compareTo(T y, Int result) {}
}

class Show<T> {
    show(Txt s) {}
}

class Node<T impl. &(Comparable<T:-T>, Show<T:-T>)> {
    T elem;
    Int height;
    Node<T:-T> left;
    Node<T:-T> right;
}

class AVLTreeImp<T impl. &(Comparable<T:-T>, Show<T:-T>)> {
    
    getHeight(Node<T:-T> root, Int height) {
        if ( eqObj(root, null) )
            height := -1;
        else
            height := root.height;
    }
    
    updateHeight(Node<T:-T> root) {
        var Int lh, Int rh;
        
        self.getHeight(root.left, _ : root, height : _, lh);
        self.getHeight(root.right, _ : root, height : _, rh);
        
        if ( gtInt(lh, rh) )
            root.height := add(lh, 1);
        else
            root.height := add(rh, 1);
            
        end lh, rh;
    }

    rotateLeftToRight(Node<T:-T> root) {
        var Node<T:-T> p, Node<T:-T> q;
        
        q := root;
        p := q.left;
        q.left := p.right;
        p.right := q;
        
        self.updateHeight(q : root : _);
        self.updateHeight(p : root : _);
        
        root := p;

        end p, q;
    }

    rotateRightToLeft(Node<T:-T> root) {
        var Node<T:-T> p, Node<T:-T> q;
        
        q := root;
        p := q.right;
        q.right := p.left;
        p.left := q;
        
        self.updateHeight(q : root : _);
        self.updateHeight(p : root : _);
        
        root := p;
        
        end p, q;
    }

    dblRotateLeftToRight(Node<T:-T> root) {
        self.rotateRightToLeft(root.left : root : root.left);
        self.rotateLeftToRight(root : root : root);
    }

    dblRotateRightToLeft(Node<T:-T> root) {
        self.rotateLeftToRight(root.right : root : root.right);
        self.rotateRightToLeft(root : root : root);
    }

    find(Node<T:-T> root, T elem) {
        if ( eqObj(root, null) )
            elem := null;
        else {
            var Int c;
            elem.compareTo(root.elem, _ : y, result : _, c);
            if ( eqInt(c, 0) )      elem := root.elem;
            else if ( ltInt(c, 0) ) self.find(root.left, elem : root, elem : _, elem);
            else                    self.find(root.right, elem : root, elem : _, elem);
            end c;
        }
    }

    insert(Node<T:-T> root, T elem) {
        if ( eqObj(root, null) ) {
            var Node<T:-T> p;
            Node<T:-T>.new(p);
            p.elem := elem;
            p.height := 0;
            p.left := null;
            p.right := null;
            root := p;
            end p;
        } else {
            var Int c;
            elem.compareTo(root.elem, _ : y, result : _, c);
            if ( eqInt(c, 0) ) {
                var T t;
                t := elem;
                elem := root.elem;
                root.elem := t;
                end t;
            } else if ( ltInt(c, 0) ) { 
                self.insert(root.left, elem : root, elem : root.left, elem);
                var Int lh, Int rh;
                self.getHeight(root.left, _ : root, height : _, lh);
                self.getHeight(root.right, _ : root, height : _, rh);
                if ( eqInt(sub(lh, rh), 2) ) {
                    self.getHeight(root.left.left, _ : root, height : _, lh);
                    self.getHeight(root.left.right, _ : root, height : _, rh);
                    if ( gtInt(lh, rh) )
                        self.rotateLeftToRight(root : root : root);
                    else
                        self.dblRotateLeftToRight(root : root : root);
                } else
                    self.updateHeight(root : root : _);
                end lh, rh;
            } else {
                self.insert(root.right, elem : root, elem : root.right, elem);
                var Int lh, Int rh;
                self.getHeight(root.left, _ : root, height : _, lh);
                self.getHeight(root.right, _ : root, height : _, rh);
                if ( eqInt(sub(rh, lh), 2) ) {
                    self.getHeight(root.right.left, _ : root, height : _, lh);
                    self.getHeight(root.right.right, _ : root, height : _, rh);
                    if ( gtInt(rh, lh) )
                        self.rotateRightToLeft(root : root : root);
                    else
                        self.dblRotateRightToLeft(root : root : root);
                } else
                    self.updateHeight(root : root : _);
                end lh, rh;
            }
            end c;
        }
    }

    balanceAfterDelRight(Node<T:-T> root) {
        var Int lh, Int rh;
        self.getHeight(root.left, _ : root, height : _, lh);
        self.getHeight(root.right, _ : root, height : _, rh);
        if ( eqInt(sub(lh, rh), 2) ) {
            self.getHeight(root.left.left, _ : root, height : _, lh);
            self.getHeight(root.left.right, _ : root, height : _, rh);
            if ( not(ltInt(lh, rh)) )
                self.rotateLeftToRight(root : root : root);
            else
                self.dblRotateLeftToRight(root : root : root);
        } else {
            self.updateHeight(root : root : _);
        }
        end lh, rh;
    }

    balanceAfterDelLeft(Node<T:-T> root) {
        var Int lh, Int rh;
        self.getHeight(root.left, _ : root, height : _, lh);
        self.getHeight(root.right, _ : root, height : _, rh);
        if ( eqInt(sub(rh, lh), 2) ) {
            self.getHeight(root.right.left, _ : root, height : _, lh);
            self.getHeight(root.right.right, _ : root, height : _, rh);
            if ( not(ltInt(rh, lh)) )
                self.rotateRightToLeft(root : root : root);
            else
                self.dblRotateRightToLeft(root : root : root);
        } else {
            self.updateHeight(root : root : _);
        }
        end lh, rh;
    }

    delRightmost(Node<T:-T> root, Node<T:-T> deleted) {   
        if ( eqObj(root.right, null) ) {
           deleted := root;
           root := root.left;
        } else {
           self.delRightmost(root.right, _ : root, deleted : root.right, deleted);
           self.balanceAfterDelRight(root : root : root);
        }
     }
    
    delete(Node<T:-T> root, T elem) {
        if ( eqObj(root, null) ) 
            skip;
        else {
            var Int c;
            elem.compareTo(root.elem, _ : y, result : _, c);
            if ( eqInt(c, 0) ) {
                if ( eqObj(root.left, null) ) {
                    elem := root.elem;
                    root := root.right;
                } else if ( eqObj(root.right, null) ) {
                    elem := root.elem;
                    root := root.left;
                } else {
                    var Node<T:-T> rt, Node<T:-T> del;
                    self.delRightmost(root.left, _ : root, deleted : rt, del);
                    del.left := rt;
                    del.right := root.right;
                    root := del;
                    end rt, del;
                }
            } else {
                if ( ltInt(c, 0) ) {
                    self.delete(root.left, elem : root, elem : root.left, elem);
                    self.balanceAfterDelLeft(root : root : root);
                } else {
                    self.delete(root.right, elem : root, elem : root.right, elem);
                    self.balanceAfterDelLeft(root : root : root);
                }
            }
            end c;
        }
    }

    inorder(Node<T:-T> root, Int indent) {
        if ( not(eqObj(root, null)) ) {
            self.inorder(root.left, add(indent, 2) : root, indent : _, _);
            
            var Int i;
            i := indent;
            while ( gtInt(i, 0) ) {
                print " ",;
                i := sub(i, 1);
            }
            end i;
            
            var Txt s;
            root.elem.show(_ : s : s);
            print s;
            end s;
            
            self.inorder(root.right, add(indent, 2) : root, indent : _, _);
        } else
            skip;
    }
}

class AVLTree<T impl. &(Comparable<T:-T>, Show<T:-T>)> {
    priv. Node<T:-T> root;
    priv. AVLTreeImp<T:-T> imp; 

    init() {
        AVLTreeImp<T:-T>.new(self.imp);
        self.root := null;
    }
    
    get(T elem) {
        self.imp.find(self.root, elem : root, elem : _, elem);
    }
    
    put(T elem) {
        self.imp.insert(self.root, elem : root, elem : self.root, elem);
    }
    
    remove(T elem) {
        self.imp.delete(self.root, elem : root, elem : self.root, elem);
    }
    
    pr() {
        self.imp.inorder(self.root, 0 : root, indent : _, _);
    }
}

class Integer {
    priv. Int value;
    
    init(Int value) {
        self.value := value;
    }
    
    show(Txt s) {
        s := toTxtInt(self.value);
    }
    
    compareTo(Integer y, Int result) {
        result := sub(self.value, y.value); 
    }
}

main {
    AVLTree<T:-Integer> tr;
    AVLTree<T:-Integer>.new(tr);
    tr.init();

    var Int i, Integer integer;
    
    i := 10;

    while ( ltInt(i, 90) ) {
        Integer.new(integer);
        integer.init(i : value : _);
        tr.put(integer : elem : _);
        i := add(i, 1);
    }

    tr.pr();

    print "--------";

    i := 80;
    while ( gtInt(i, 30) ) {
        Integer.new(integer);
        integer.init(i : value : _);
        tr.remove(integer : elem : _);
        i := sub(i, 1);
    }
        
    tr.pr();

    print "--------";

    i := 15;
    while ( ltInt(i, 85) ) {
        Integer.new(integer);
        integer.init(i : value : _);
        tr.remove(integer : elem : _);
        i := add(i, 1);
    }
        
    tr.pr();

    end i, integer;
}