RedBlackTree.mesa
Copyright Ó 1985, 1986, 1991 by Xerox Corporation. All rights reserved.
MBrown on October 20, 1983 11:36 pm
Russ Atkinson (RRA) May 7, 1985 12:11:39 pm PDT
RedBlackTree is a package for maintaining symbol tables (key to value maps) with an ordering among keys. The ordering allows the table to perform searches such as "find the smallest item in the table that is larger than this one," as well as exact-match searches. The package's implementation uses a binary tree representation of 2-3-4 trees, called red-black trees; this means that any search, insertion, or deletion operation from a table of n items takes O(log n) average time.
DIRECTORY
Basics USING [Comparison];
RedBlackTree: CEDAR DEFINITIONS = BEGIN
Types
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];
This is the representation of a RedBlackTree object. The RECORD type constructor allows most procedures below to be invoked using object notation.
BadTable: ERROR;
All procedures below with a self: Table parameter raise BadTable if self appears to be malformed.
GetKey: TYPE = PROC [data: UserData] RETURNS [Key];
Callback proc type: Given the user data in a node, return the key
Compare: TYPE = PROC [k: Key, data: UserData] RETURNS [Basics.Comparison];
Callback proc type: Given a key and the user data in a node, return the comparison of the keys
EachNode: TYPE = PROC [data: UserData] RETURNS [stop: BOOL ¬ FALSE];
Callback proc type: to be called from EnumerateIncreasing & EnumerateDecreasing.
LookupProc: TYPE = PROC [self: Table, lookupKey: Key] RETURNS [data: UserData];
Procedures Lookup, LookupNextLarger, LookupNextSmaller can all be assigned to a variable of this type.
Procedures
Create: PROC [getKey: GetKey, compare: Compare] RETURNS [Table];
This procedure must be called before calling any procedures below. Caller supplies the package instance with the procedures needed to interpret keys and nodes.
DestroyTable: PROC [self: Table];
Makes table empty, as it was just after CreateTable.
Size: PROC [self: Table] RETURNS [INT];
Returns the number of nodes in the table.
Insert: PROC [self: Table, dataToInsert: UserData, insertKey: Key];
! DuplicateKey (if insertKey already present in table).
Caller asserts that Compare[insertKey, dataToInsert] = equal. Inserts nodeToInsert into table. ERRORs DuplicateKey if Compare[insertKey, x] = equal for some node x already in the table.
InsertNode: PROC [self: Table, nodeToInsert: Node, insertKey: Key];
! DuplicateKey (if insertKey already present in table).
Just like Insert, but inserts a node. This is useful if the client desires to reuse nodes instead of creating new nodes.
DuplicateKey: ERROR;
Delete: PROC [self: Table, deleteKey: Key] RETURNS [deletedNode: Node];
Removes the (unique) node x in table such that Compare[deleteKey, x] = equal, and returns it, or returns NIL if no such node exists.
LookupNode: PROC [self: Table, lookupKey: Key] RETURNS [node: Node];
Returns the node associated with the given key, or NIL if no such node exists. If data # NIL, then compare[lookupKey, node.data] = equal. This is useful when one wants to replace the data at a given node without altering the key.
Lookup: LookupProc;
Returns the user data associated with the given key, or NIL if no such node exists. If data # NIL, then compare[lookupKey, data] = equal.
LookupNextLarger: LookupProc;
Returns the user data associated with the smallest key strictly larger than lookupKey, or NIL if no such item exists.
LookupNextSmaller: LookupProc;
Returns the user data associated with the the largest key strictly smaller than lookupKey, or NIL if no such node exists.
LookupSmallest: PROC [self: Table] RETURNS [data: UserData];
Returns the user data associated with the smallest key, or NIL if the table is empty.
LookupLargest: PROC [self: Table] RETURNS [data: UserData];
Returns the user data associated with the largest key, or NIL if the table is empty.
Lookup3: PROC [self: Table, lookupKey: Key] RETURNS [leftData, equalData, rightData: UserData];
Equivalent (but faster than)
leftData ← LookupNextSmaller[self, lookupKey];
equalData ← Lookup[self, lookupKey];
leftData ← LookupNextLarger[self, lookupKey];
EnumerateIncreasing: PROC [self: Table, procToApply: EachNode];
For each item x in the table, in increasing order by key value, executes procToApply[x]. Returns when procToApply returns TRUE or when all items have been enumerated.
procToApply is restricted: it cannot call other procedures in this interface, because the monitor lock is held during this enumeration. In particular it cannot examine or modify the table being enumerated. Stateless enumerations can be implemented using LookupNextLarger or LookupNextSmaller.
EnumerateDecreasing: PROC [self: Table, procToApply: EachNode];
For each item x in the table, in decreasing order by key value, executes procToApply[x]. Returns when procToApply returns TRUE or when all items have been enumerated.
procToApply is restricted: it cannot call other procedures in this interface, because the monitor lock is held during this enumeration. In particular it cannot examine or modify the table being enumerated. Stateless enumerations can be implemented using LookupNextLarger or LookupNextSmaller.
CheckTable: PROC [self: Table];
Raises BadTable if the red-black tree representing the table is not well-formed. Used by package test programs; may be used for client debugging of unsafe programs.
END.