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. & 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. Types This is the representation of a RedBlackTree object. The RECORD type constructor allows most procedures below to be invoked using object notation. All procedures below with a self: Table parameter raise BadTable if self appears to be malformed. Callback proc type: Given the user data in a node, return the key Callback proc type: Given a key and the user data in a node, return the comparison of the keys Callback proc type: to be called from EnumerateIncreasing & EnumerateDecreasing. Procedures Lookup, LookupNextLarger, LookupNextSmaller can all be assigned to a variable of this type. Procedures This procedure must be called before calling any procedures below. Caller supplies the package instance with the procedures needed to interpret keys and nodes. Makes table empty, as it was just after CreateTable. Returns the number of nodes in the table. ! 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. ! 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. Removes the (unique) node x in table such that Compare[deleteKey, x] = equal, and returns it, or returns NIL if no such node exists. 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. Returns the user data associated with the given key, or NIL if no such node exists. If data # NIL, then compare[lookupKey, data] = equal. Returns the user data associated with the smallest key strictly larger than lookupKey, or NIL if no such item exists. Returns the user data associated with the the largest key strictly smaller than lookupKey, or NIL if no such node exists. Returns the user data associated with the smallest key, or NIL if the table is empty. Returns the user data associated with the largest key, or NIL if the table is empty. Equivalent (but faster than) leftData _ LookupNextSmaller[self, lookupKey]; equalData _ Lookup[self, lookupKey]; leftData _ LookupNextLarger[self, lookupKey]; 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. 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. 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. Κ •NewlineDelimiter –(cedarcode) style™codešΟc™Kšœ Οeœ=™HKš#™#K™/K™šβ™βK™—šΟk ˜ šœŸœ˜K˜———KšΟn œŸœŸ œŸ˜'K˜™K˜KšœŸœŸœ ˜šœ ŸœŸœ˜KšœŸœ ŸœŸœ˜4Kšœ˜—KšœŸœŸœ˜Kšœ ŸœŸœ˜K˜KšœŸœŸœ ˜š œ ŸœŸœŸ œŸœŸœ˜EKš:ΠckS™“K˜—š œŸœ˜Kš8œ!™a—K˜š œŸœŸœŸœ˜3KšœA™AK™—š œŸœŸœŸœ˜JKšœ^™^K™—š  œŸœŸœŸœŸœŸœ˜DKšœP™PK™—š  œŸœŸœŸœ˜OKšœf™fK™——š ™ K™š œŸœ$Ÿœ ˜@Kš ™ K™—š  œŸœ˜!Kšœ4™4K˜—š œŸœŸœŸœ˜'Kšœ)™)K˜—š œŸœ7˜CKš7™7Kš'œ ˆ™»K™—š  œŸœ3˜CKš7™7Kšœy™yK™—š  œŸœ˜K˜—š œŸœŸœ˜GKšœiŸœ™„K˜—š  œŸœŸœ˜DKšœ3Ÿœ$ŸœŠ™ηK™—š œ ˜Kšœ8Ÿœ$Ÿœ(™ŠK™—š œ ˜KšœZŸœ™uK™—š œ ˜Kšœ^Ÿœ™yK™—š œŸœŸœ˜