<> <> <> <> <<>> <> <<>> DIRECTORY Basics USING [Comparison]; RedBlackTree: CEDAR DEFINITIONS = BEGIN <> Node: TYPE = REF NodeRep; NodeRep: TYPE = RECORD[ rbLLink, rbRLink: Node _ NIL, rbColor: BOOL _ FALSE, data: UserData]; Key: TYPE = REF; UserData: TYPE = REF; Table: TYPE = REF TableRep; TableRep: PRIVATE TYPE = MONITORED RECORD [root: Node, private: REF]; <> BadTable: ERROR; <> GetKey: TYPE = PROC [data: UserData] RETURNS [Key]; <> <<>> Compare: TYPE = PROC [k: Key, data: UserData] RETURNS [Basics.Comparison]; <> <<>> EachNode: TYPE = PROC [data: UserData] RETURNS [stop: BOOL _ FALSE]; <> <<>> LookupProc: TYPE = PROC [self: Table, lookupKey: Key] RETURNS [data: UserData]; <> <<>> <> <<>> Create: PROC [getKey: GetKey, compare: Compare] RETURNS [Table]; <> <<>> DestroyTable: PROC [self: Table]; <> Size: PROC [self: Table] RETURNS [INT]; <> Insert: PROC [self: Table, dataToInsert: UserData, insertKey: Key]; <> <> <<>> InsertNode: PROC [self: Table, nodeToInsert: Node, insertKey: Key]; <> <> <<>> DuplicateKey: ERROR; Delete: PROC [self: Table, deleteKey: Key] RETURNS [deletedNode: Node]; <> LookupNode: PROC [self: Table, lookupKey: Key] RETURNS [node: Node]; <> <<>> Lookup: LookupProc; <> <<>> LookupNextLarger: LookupProc; <> <<>> LookupNextSmaller: LookupProc; <> <<>> LookupSmallest: PROC [self: Table] RETURNS [data: UserData]; <> <<>> LookupLargest: PROC [self: Table] RETURNS [data: UserData]; <> <<>> Lookup3: PROC [self: Table, lookupKey: Key] RETURNS [leftData, equalData, rightData: UserData]; <> <> <> <> EnumerateIncreasing: PROC [self: Table, procToApply: EachNode]; <> <> EnumerateDecreasing: PROC [self: Table, procToApply: EachNode]; <> <> CheckTable: PROC [self: Table]; <> END.