RedBlackTreeExtras:
CEDAR
DEFINITIONS = {
OPEN RedBlackTree;
GetIDKey: GetKey;
Simply returns its argument.
NewRefTable:
PROC
RETURNS [Table];
Any REF is a suitable entry. The REF is the key as well as the data. Ordered by loopholing the REF into a number.
NewRopeTable:
PROC [case:
BOOL ←
TRUE]
RETURNS [Table];
Entries are ROPEs. The ROPE is the key, as well as the data. Ordered by Rope.Compare[case: case].
StatelessEnumerateIncreasing: PROC [self: Table, procToApply: EachNode, getKey: GetKey];
StatelessEnumerateDecreasing:
PROC [self: Table, procToApply: EachNode, getKey: GetKey];
`procToApply' is relatively unrestricted: it only needs to refrain from trashing the key of its `data'. In particular, it is NOT prohibited from doing other RedBlackTree operations on `self'.
DeleteData:
PROC [self: Table, deleteKey: Key]
RETURNS [deletedData: UserData];
Removes the (unique) node x in table such that Compare[deleteKey, x] = equal, and returns its data, or returns NIL if no such node exists.
REFPair: TYPE = REF REFPairPrivate;
REFPairPrivate:
TYPE =
RECORD [
key, value: REF ANY];
GetRPKey: GetKey;
Returns the key of a REFPair.
NewRefMap:
PROC
RETURNS [Table];
Entries are REFPairs, with each key being a REF ANY. Ordered by loopholing the key into a number.
NewRopeMap:
PROC [case:
BOOL ←
TRUE]
RETURNS [Table];
Entries are REFPairs, with each key being a ROPE. Ordered by Rope.Compare[case: case].
Fetch:
PROC [table: Table, key:
REF
ANY]
RETURNS [found:
BOOLEAN, value:
REF
ANY];
value will be NIL when NOT found.
Store:
PROC [table: Table, key, value:
REF
ANY]
RETURNS [new:
BOOLEAN];
returns TRUE after inserting new pair
returns FALSE after overwriting old value for existing key-value pair
}.