
    <<RedBlackTreeExtrasImpl.Mesa>>
        <<Spreitzer, September 26, 1985 2:50:05 pm PDT>>

    DIRECTORY Basics, RedBlackTree, RedBlackTreeExtras, Rope;

    RedBlackTreeExtrasImpl: CEDAR PROGRAM
        IMPORTS RedBlackTree, Rope
        EXPORTS RedBlackTreeExtras

         = {OPEN RedBlackTree;

        ROPE: TYPE = Rope.ROPE;

        GetIDKey: PUBLIC PROC [data: UserData] RETURNS [key: Key] =
            {key _ data};

        CompareAddresses: PROC [k: Key, data: UserData] RETURNS [Basics.Comparison] = {
            k1: INT = LOOPHOLE[k];
            k2: INT = LOOPHOLE[data];
            RETURN [SELECT k1 FROM
                <k2 => less,
                =k2 => equal,
                >k2 => greater,
                ENDCASE => ERROR];
            };

        CompareRopes: PROC [k: Key, data: UserData] RETURNS [Basics.Comparison] = {
            k1: ROPE = NARROW[k];
            k2: ROPE = NARROW[data];
            RETURN [k1.Compare[k2]];
            };

        CompareRopesOhneCase: PROC [k: Key, data: UserData] RETURNS [Basics.Comparison] = {
            k1: ROPE = NARROW[k];
            k2: ROPE = NARROW[data];
            RETURN [k1.Compare[k2, FALSE]];
            };

        NewRefTable: PUBLIC PROC RETURNS [Table] =
            {RETURN [Create[GetIDKey, CompareAddresses]]};

        NewRopeTable: PUBLIC PROC [case: BOOL _ TRUE] RETURNS [Table] =
            {RETURN [Create[GetIDKey, IF case THEN CompareRopes ELSE CompareRopesOhneCase]]};

        StatelessEnumerateIncreasing: PUBLIC PROC [self: Table, procToApply: EachNode, getKey: GetKey] = {
            key: Key _ NIL;
            FOR data: UserData _ self.LookupSmallest[], self.LookupNextLarger[key] WHILE data # NIL DO
                key _ getKey[data];
                IF procToApply[data] THEN EXIT;
                ENDLOOP;
            };

        DeleteData: PUBLIC PROC [self: Table, deleteKey: Key] RETURNS [deletedData: UserData] = {
            deletedNode: Node _ self.Delete[deleteKey];
            RETURN [IF deletedNode # NIL THEN deletedNode.data ELSE NIL];
            };

        }.