EXTERNAL CLASS AVL;

AVL
BEGIN

    KEY CLASS INTEGERKEY(I); INTEGER I;
    BEGIN
        BOOLEAN PROCEDURE LESS (K); REF(KEY) K; LESS  := I < K QUA INTEGERKEY.I;
        BOOLEAN PROCEDURE EQUAL(K); REF(KEY) K; EQUAL := I = K QUA INTEGERKEY.I;
    END INTEGERKEY;

    PROCEDURE DUMP(ROOT); REF(NODE) ROOT;
    BEGIN
        IF ROOT =/= NONE THEN
        BEGIN
            DUMP(ROOT.LINK(0));
            OUTINT(ROOT.DATA QUA INTEGERKEY.I, 0); OUTTEXT(" ");
            DUMP(ROOT.LINK(1));
        END
    END DUMP;

    INTEGER I;
    REF(NODE) TREE;
    OUTTEXT("Empty tree: "); DUMP(TREE); OUTIMAGE;

    FOR I := 3, 1, 4, 1, 5 DO
    BEGIN OUTTEXT("Insert "); OUTINT(I, 0); OUTTEXT(": ");
          INSERT(TREE, NEW INTEGERKEY(I)); DUMP(TREE); OUTIMAGE;
    END;

    FOR I := 3, 1 DO
    BEGIN OUTTEXT("Remove "); OUTINT(I, 0); OUTTEXT(": ");
          REMOVE(TREE, NEW INTEGERKEY(I)); DUMP(TREE); OUTIMAGE;
    END;

END.