WaterlilyOrderedSymbolTable.mesa
Copyright © 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.
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];
The RECORD type constructor allows most procedures below to be invoked using object notation.
Error: ERROR [ec: ErrorType];
ErrorType:
TYPE = { notInitialized, badTable };
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
Initialize:
PROC [sentinel1, sentinel2: Node];
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.)
CreateTable:
PROC [header: Node]
RETURNS [Table];
! 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.
DestroyTable:
PROC [self: Table];
Makes table empty, as it was just after CreateTable.
Insert:
PROC [self: Table, nodeToInsert: Node, insertKey: Key];
! 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.
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.
LookupProc:
TYPE =
PROC [self: Table, lookupKey: Key]
RETURNS [Node];
Procedures Lookup, LookupNextLarger, LookupNextSmaller can all be assigned to a variable of this type.
Lookup:
PROC [self: Table, lookupKey: Key]
RETURNS [equalNode: Node];
Returns the (unique) node x in table such that Compare[lookupKey, x] = equal, or NIL if no such node exists.
LookupSmallest:
PROC [self: Table]
RETURNS [smallestNode: Node];
Returns the item in table with smallest key, or NIL if t is empty.
LookupNextLarger:
PROC [self: Table, lookupKey: Key]
RETURNS [largerNode: Node];
Returns the node in table with the smallest key strictly larger than lookupKey, or NIL if no such item exists.
LookupLargest:
PROC [self: Table]
RETURNS [largestNode: Node];
Returns the item in table with largest key, or NIL if t is empty.
LookupNextSmaller:
PROC [self: Table, lookupKey: Key]
RETURNS [smallerNode: Node];
Returns the node in table with the largest key strictly smaller than lookupKey, or NIL if no such node exists.
Lookup3:
PROC [self: Table, lookupKey: Key]
RETURNS [leftNode, equalNode, rightNode: Node];
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.)
EnumerateIncreasing:
PROC [self: Table, procToApply:
PROC [Node]
RETURNS [
--stop--
BOOL]];
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.
CheckTable:
PROC [self: Table];
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.
RootNode:
PRIVATE
PROC [self: Table]
RETURNS [rootNode: Node];
Returns the the root of the red-black tree representing the table. Used by package test programs only.
END.
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.