
    <<RedBlackTreeExtrasImpl.Mesa>>
        <<Spreitzer, October 23, 1985 5:22:46 pm PDT>>

    DIRECTORY Basics, RedBlackTree, RedBlackTreeExtras, Rope;

    RedBlackTreeExtrasImpl: CEDAR PROGRAM
        IMPORTS RedBlackTree, Rope
        EXPORTS RedBlackTreeExtras

         = {OPEN RedBlackTreeExtras, 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;
            };

        StatelessEnumerateDecreasing: PUBLIC PROC [self: Table, procToApply: EachNode, getKey: GetKey] = {
            key: Key _ NIL;
            FOR data: UserData _ self.LookupLargest[], self.LookupNextSmaller[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];
            };

        GetRPKey: PUBLIC PROC [data: UserData] RETURNS [key: Key] =
            {rp: REFPair = NARROW[data]; key _ rp.key};

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

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

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

        NewRefMap: PUBLIC PROC RETURNS [Table] =
            {RETURN [Create[GetRPKey, CompareKeyAddresses]]};

        NewRopeMap: PUBLIC PROC [case: BOOL _ TRUE] RETURNS [Table] =
            {RETURN [Create[GetRPKey, IF case THEN CompareKeyRopes ELSE CompareKeyRopesOhneCase]]};

        Fetch: PUBLIC PROC [table: Table, key: REF ANY] RETURNS [found: BOOLEAN, value: REF ANY] = {
            rp: REFPair = NARROW[table.Lookup[key]];
            IF rp = NIL THEN RETURN [FALSE, NIL];
            RETURN [TRUE, rp.value];
            };

        Store: PUBLIC PROC [table: Table, key, value: REF ANY] RETURNS [new: BOOLEAN] = {
            rp: REFPair = NARROW[table.Lookup[key]];
            IF new _ rp = NIL
                THEN table.Insert[NEW [REFPairPrivate _ [key, value]], key]
                ELSE rp.value _ value;
            };

        }.