DIRECTORY Basics USING [Comparison], WaterlilyParticularTable USING [Node, NodeRecord, Key, GetKey, CompareKeyToNode]; WaterlilyOrderedSymbolTable: CEDAR DEFINITIONS IMPORTS WaterlilyParticularTable = BEGIN Node: TYPE = WaterlilyParticularTable.Node; NodeRecord: TYPE = WaterlilyParticularTable.NodeRecord; Key: TYPE = WaterlilyParticularTable.Key; GetKey: PRIVATE PROC [n: Node] RETURNS [Key] = INLINE { RETURN [WaterlilyParticularTable.GetKey[n]] }; Compare: PRIVATE PROC [k: Key, n: Node] RETURNS [Basics.Comparison] = INLINE { RETURN [WaterlilyParticularTable.CompareKeyToNode[k, n]] }; Table: TYPE = RECORD [Node]; Error: ERROR [ec: ErrorType]; ErrorType: TYPE = { notInitialized, badTable }; Initialize: PROC [sentinel1, sentinel2: Node]; CreateTable: PROC [header: Node] RETURNS [Table]; DestroyTable: PROC [self: Table]; Insert: PROC [self: Table, nodeToInsert: Node, insertKey: Key]; DuplicateKey: ERROR; Delete: PROC [self: Table, deleteKey: Key] RETURNS [deletedNode: Node]; LookupProc: TYPE = PROC [self: Table, lookupKey: Key] RETURNS [Node]; Lookup: PROC [self: Table, lookupKey: Key] RETURNS [equalNode: Node]; LookupSmallest: PROC [self: Table] RETURNS [smallestNode: Node]; LookupNextLarger: PROC [self: Table, lookupKey: Key] RETURNS [largerNode: Node]; LookupLargest: PROC [self: Table] RETURNS [largestNode: Node]; LookupNextSmaller: PROC [self: Table, lookupKey: Key] RETURNS [smallerNode: Node]; Lookup3: PROC [self: Table, lookupKey: Key] RETURNS [leftNode, equalNode, rightNode: Node]; EnumerateIncreasing: PROC [self: Table, procToApply: PROC [Node] RETURNS [--stop--BOOL]]; CheckTable: PROC [self: Table]; RootNode: PRIVATE PROC [self: Table] RETURNS [rootNode: Node]; END. ªWaterlilyOrderedSymbolTable.mesa Copyright c 1984 by Xerox Corporation. All rights reserved. Russ Atkinson, December 3, 1984 5:42:49 pm PST (cloned from RedBlackTree>OrderedSymbolTable) OrderedSymbolTable 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 from a table of n items takes O(n log n) time. A table stores items of type Node with keys of type Key, where Node and Key are defined in a definitions module that parameterizes the OrderedSymbolTable interface. A user of the package creates a suitable definitions module to parameterize OrderedSymbolTable, then compiles OrderedSymbolTable and RedBlackTreeImpl. The RECORD type constructor allows most procedures below to be invoked using object notation. All procedures below with a self: Table parameter raise Error[badTable] if self appears to be malformed (it might for instance be a normal Node that was passed by mistake.) Procedures This procedure must be called before calling any procedures below. Caller supplies the package instance with two nodes for its internal use. (These nodes are gone forever; we provide no way to reclaim their space.) ! Error[notInitialized] (if Initialize has not been called.) Caller supplies a node to represent a table. The procedure creates an empty table and returns it. Makes table empty, as it was just after CreateTable. ! DuplicateKey (if insertKey already present in table). Caller asserts that Compare[insertKey, nodeToInsert] = equal. Inserts nodeToInsert into table. ERRORs DuplicateKey if Compare[insertKey, x] = equal for some node x already in the table. Removes the (unique) node x in table such that Compare[deleteKey, x] = equal, and returns it, or returns NIL if no such node exists. Procedures Lookup, LookupNextLarger, LookupNextSmaller can all be assigned to a variable of this type. Returns the (unique) node x in table such that Compare[lookupKey, x] = equal, or NIL if no such node exists. Returns the item in table with smallest key, or NIL if t is empty. Returns the node in table with the smallest key strictly larger than lookupKey, or NIL if no such item exists. Returns the item in table with largest key, or NIL if t is empty. Returns the node in table with the largest key strictly smaller than lookupKey, or NIL if no such node exists. This Lookup procedure returns three nodes in table: [LookupNextSmaller[self, lookupKey], Lookup[self, lookupKey], LookupNextLarger[self, lookupKey]]. Note that in a nonempty table, one of the results is guaranteed # NIL. (This procedure was Howard Sturgis' idea.) 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. In particular it cannot examine or modify the table being enumerated. Such enumerations can be implemented using LookupNextLarger or LookupNextSmaller. ERRORs Error[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. Returns the the root of the red-black tree representing the table. Used by package test programs only. Concurrency The implementation of this package is a module monitor. Hence for each instance of this package, at most one table operation may be in progress at a time. Change Log Created by MBrown on March 2, 1982 4:14 pm By editing OrderedSymbolTableRef. Changed by MBrown on March 8, 1982 12:09 pm Defined LookupProc, and removed named results to conform. Added comment about object notation. Changed by MBrown on June 28, 1982 11:11 am Make interface CEDAR. Changed by MBrown on August 26, 1982 10:49 pm Use Environment.Comparison. Changed by MBrown on October 20, 1983 11:35 pm Convert to Cedar 5.0. Changed by Russ Atkinson, December 3, 1984 5:45:15 pm PST Cloned for Waterlily. Ê„– "Cedar" style˜head1šœ ™ Jšœ Ïmœ1™<™.JšœÏc™-—bodyšžØ™ØLšž½™½J™—šÏk ˜ JšœŸœ˜šœŸœ3˜QJ˜——šœŸœŸœŸ˜XJšœŸœ!˜+Jšœ Ÿœ'˜7JšœŸœ ˜)procšÏnœŸœŸœ Ÿœ˜,JšœŸœŸœ(˜9—š œŸœŸœŸœ˜CJšœŸœŸœ5˜F—šœŸœŸœ˜JšžÐckžS™]—JšœŸœ˜šœ Ÿœ ˜/Jšž¬™¬———šž ™ š  œŸœ˜.JšžØ™Ø—š  œŸœŸœ ˜1Jšž<™JšœA™A—š œŸœŸœ˜RJšœn™n—š œŸœŸœ(˜[Jšœ‰™‰J˜—š  œŸœŸœŸœžŸœ˜YJšœ{Ÿœ(™§Jšœç™çJ˜—š  œŸœ˜JšŸœ§™¬J˜—š œŸœŸœŸœ˜>Jšœg™g—JšŸœ˜head2šž ™ Lšžšœ™›——šž ™ ™*Lšž!™!—™+Lšž_™_—™+Lšž™—™-Lšž™—™.Lšž™—™9Lšž™———…—®Ü