OrderedSymbolTableRef.mesa
OrderedSymbolTableRef is a variant of the OrderedSymbolTable package for maintaining symbol tables (key to value maps) with an interesting ordering among keys. The package stores REF ANY items, and accepts an item-comparison procedure as a parameter at the time a table is created, so it does not need to be recompiled to handle different types of items.
Last edited by:
MBrown on October 20, 1983 9:55 pm
DIRECTORY
Basics
USING [Comparison];
OrderedSymbolTableRef:
CEDAR
DEFINITIONS =
BEGIN
Table: TYPE = REF TableObject;
TableObject: TYPE;
Key, Item: TYPE = REF ANY;
Comparison: TYPE = Basics.Comparison;
CompareProc: TYPE = PROC [r1, r2: Item] RETURNS [Comparison];
Procedures
CreateTable:
PROC [compareProc: CompareProc, nodeZone:
ZONE ←
NIL, tableZone:
ZONE ←
NIL]
RETURNS [t: Table];
Returns an empty table that uses the given comparison function. nodeZone will be used to allocate nodes for red-black tree (7 words each), tableZone will be used to allocate header for tree (11 words plus 3 nodes); these both default to the system zone.
DestroyTable:
PROC [t: Table];
Deletes all items from t, then invalidates t.
DeleteAllItems:
PROC [t: Table];
Makes table t empty (t.Size[] = 0).
Size:
PROC [t: Table]
RETURNS [nItems:
INT];
Returns the number of items in t.
Insert:
PROC [t: Table, insertItem: Item];
Inserts item x into table t. ERRORs DuplicateKey (with monitor released) if compareProc[x, y] = equal for some y in the table.
DuplicateKey: ERROR;
Delete:
PROC [t: Table, deleteKey: Item]
RETURNS [deletedItem: Item];
Removes the (unique) item y in t such that compareProc[deleteKey, y] = equal, and returns it, or returns NIL if no such item is present.
Lookup:
PROC [t: Table, lookupKey: Key]
RETURNS [equalItem: Item];
Returns the (unique) item y in t such that compareProc[lookupKey, y] = equal, or NIL if no such item exists.
LookupSmallest:
PROC [t: Table]
RETURNS [smallestItem: Item];
Returns the item in table t with smallest key, or NIL if t is empty.
LookupNextLarger:
PROC [t: Table, lookupKey: Key]
RETURNS [largerItem: Item];
Returns the item in table t with the smallest key strictly larger than lookupKey, or NIL if no such item exists.
LookupLargest:
PROC [t: Table]
RETURNS [largestItem: Item];
Returns the item in table t with largest key, or NIL if t is empty.
LookupNextSmaller:
PROC [t: Table, lookupKey: Key]
RETURNS [smallerItem: Item];
Returns the item in table t with the largest key strictly smaller than lookupKey, or NIL if no such item exists.
Lookup3:
PROC [t: Table, lookupKey: Key]
RETURNS [leftItem, equalItem, rightItem: Item];
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 [t: Table, procToApply:
PROC [Item]
RETURNS [
BOOLEAN]];
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.
The procedure procToApply may make any modifications to the table that it likes; EnumerateIncreasing is implemented to simulate one call on LookupSmallest (to find the first item), and then repeated calls to LookupNextLarger (to find the "next" item), so modifications to the table during the enumeration may be understood in terms of this model.
CheckTable:
PROC [t: 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.
BadTable: ERROR;
RootItem:
PROC [t: Table]
RETURNS [rootItem: Item];
Returns the the root of the red-black tree representing the table. Used by package test programs only.
END.
Ordered Symbol Tables
How to acquire the package
Bringover /a /p <Cedar>Top>RedBlackTreeRef.df to obtain the interface OrderedSymbolTableRef.bcd and the implementation RedBlackTreeRefImpl.bcd. If you bind the implementation into your own configuration, you'll have to import SafeStorage for its use.
Writing CompareProcs
This package tries to be as general as possible, and hence trades some efficiency for flexiblilty. The package stores REF ANY items, and performs comparisons with a user-supplied procedure called a CompareProc.
A CompareProc must be prepared both to compare two items (as in Insert, where it compares insertItem with items already in the table), and to compare a key to an item (as in Lookup, where it compares lookupKey with items already in the table). One way for the client to accomplish this is to make keys and items the same, that is, to embed a key into an item before calling Lookup. This simplifies the CompareProc at the expense of complicating the callers of Lookup. The alternative is to implement a CompareProc that is prepared to see a bare key (such as a REF INT or a ROPE) as its first argument. The second argument to a table's CompareProc is guaranteed to be an item stored in the table.
There is no law that says that all items in a table must have the same type. As you add variability to item types, you add complexity to the CompareProc.
Calling a CompareProc costs one procedure call, plus the cost of two REF ANY discriminations, plus the cost of actually doing the comparison. If the cost of a comparison is high anyway then this overhead is probably acceptable. If comparisons are simple and efficiency is important, you should be using the OrderedSymbolTable package.
Concurrency
The tables maintained by this package are object monitors, so individual calls (except to EnumerateIncreasing) are atomic.
Object notation
Clients of this package may use object notation to call any procedure whose first parameter is "t: Table". For instance, write "table.Insert[node, key]" instead of "OrderedSymbolTable.Insert[table, node, key]".