Intervals.mesa
Copyright © 1985 by Xerox Corporation. All rights reversed.
Created by Bertrand Serlet, November 16, 1985 7:22:05 pm PST
Bertrand Serlet, March 13, 1986 1:48:02 pm PST
Definitions for handling tables of values, with each value corresponding to a one dimension interval. Enumeration of all values that overlap a given interval is a fast operation. The range of all intervals must be known at the creation of the table. Tables are implemented by hashing, and grow when the number of elements in table is too large. All operations except enumeration are monitored.
Intervals: CEDAR DEFINITIONS = BEGIN
Interval: TYPE = RECORD [min, max: INT];
Record representing the interval [min .. max].
Note the inclusion of bounds.
Table: TYPE = REF TableRec;
TableRec: TYPE = MONITORED RECORD [
range: Interval,   -- given at creation time, it retains the range of all intervals. Clients should not change this field.
size: NAT,    -- maintained by all operations. Clients should not change this field.
valueInterval: ValueIntervalProc, -- user-given function to access the interval corresponding to a value. Should be fast to compute. Clients should not change this field.
userData: REF,  -- user field.
effectiveRange: PRIVATE Interval, -- effective range of current values. Use EffectiveRange to read that field (that may not be correct)
leafBuckets: PRIVATE NAT,  -- private field to detect when ReHashing is necessary.
data: PRIVATE REF TableData
];
TableData: PRIVATE TYPE = RECORD [c: SEQUENCE hashSize: NAT OF LIST OF Value];
Value: TYPE = REF;
ValueIntervalProc: TYPE = PROC [Table, Value] RETURNS [Interval];
Create: PROC [range: Interval, valueInterval: ValueIntervalProc, userData: REF ← NIL, logHashSize: NAT ← 2] RETURNS [Table];
Creates a new table with a suggested hash size of 2**logHashSize-1.
Insert: PROC [table: Table, value: Value];
Adds a new value in the table.
The corresponding interval must lie in the creation range, otherwise an ERROR might occur.
This operation is monitored.
Does NOT check if value was already member of the table.
Delete: PROC [table: Table, value: Value];
Deletes all occurences of value in the table.
The corresponding interval must lie in the creation range, otherwise an ERROR might occur.
This operation is monitored.
Enumerate: PROC [table: Table, action: PROC [Table, Value] RETURNS [BOOLEAN ← FALSE], interval: Interval ← universe] RETURNS [BOOLEAN];
Enumerates all values of the table that overlap a given range.
The interval might be OUTSIDE the range of the table.
This operation is NOT monitored, and concurrent Insert/Delete may or may not be seen.
Applies action to each value until action returns TRUE or no more value.
Returns TRUE if some action returns TRUE.
universe: Interval = [FIRST[INT], LAST[INT]];
empty: Interval = [LAST[INT], FIRST[INT]];
EffectiveRange: PROC [table: Table] RETURNS [Interval];
Returns the effective range of all current values.
Union: PROC [interval1, interval2: Interval] RETURNS [Interval];
Union of two intervals (trivial function).
Overlap: PROC [interval1, interval2: Interval] RETURNS [BOOL];
Overlapping of two intervals (trivial function).
END.