D2Intervals.mesa
Copyright © 1985 by Xerox Corporation. All rights reversed.
Created by Bertrand Serlet, March 8, 1986 1:40:51 pm PST
Bertrand Serlet, April 3, 1986 7:23:13 pm PST
Definitions for handling tables of values, with each value corresponding to a two dimension rectangle. Enumeration of all values that overlap a given rectangle is a fast operation. The range of all rectangles must be known at the creation of the table. A value should be associated with the same rectangle during the lifetime 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.
DIRECTORY Intervals USING [empty, Interval, Table, universe];
D2Intervals: CEDAR DEFINITIONS = BEGIN
Interval: TYPE = Intervals.Interval;
Rect: TYPE = RECORD [x, y: Interval];
Record representing the rect [xmin .. xmax]*[ymin .. ymax].
Note the inclusion of bounds.
Table: TYPE = REF TableRec;
TableRec: TYPE = MONITORED RECORD [
range: Rect,    -- given at creation time, it retains the range of all rects. Clients should not change this field.
size: NAT,    -- maintained by all operations. Clients should not change this field.
valueRect: ValueRectProc, -- user-given function to access the rectangle corresponding to a value. Should be fast to compute. Clients should not change this field.
userData: REF,  -- user field.
effectiveRange: PRIVATE Rect, -- 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 Intervals.Table];
Value: TYPE = REF;
ValueRectProc: TYPE = PROC [Table, Value] RETURNS [Rect];
Create: PROC [range: Rect, valueRect: ValueRectProc, 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 rectangle 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 rectangle 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], rect: Rect ← universe] RETURNS [BOOLEAN];
Enumerates all values of the table that overlap a given range.
The rectangle 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.
Erase: PROC [table: Table];
D2Intervals tables are circular (alas)!
This function erases all sub-tables, and resets the Size to 0.
universe: Rect = [Intervals.universe, Intervals.universe];
empty: Rect = [Intervals.empty, Intervals.empty];
EffectiveRange: PROC [table: Table] RETURNS [Rect];
Returns the effective range of all current values.
Union: PROC [rect1, rect2: Rect] RETURNS [Rect];
Union of two rects (trivial function).
Overlap: PROC [rect1, rect2: Rect] RETURNS [BOOL];
Overlapping of two rects (trivial function).
END.