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;
};
}.