Intervals: CEDAR DEFINITIONS = BEGIN Interval: TYPE = RECORD [min, max: INT]; 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]; Insert: PROC [table: Table, value: Value]; Delete: PROC [table: Table, value: Value]; Enumerate: PROC [table: Table, action: PROC [Table, Value] RETURNS [BOOLEAN _ FALSE], interval: Interval _ universe] RETURNS [BOOLEAN]; universe: Interval = [FIRST[INT], LAST[INT]]; empty: Interval = [LAST[INT], FIRST[INT]]; EffectiveRange: PROC [table: Table] RETURNS [Interval]; Union: PROC [interval1, interval2: Interval] RETURNS [Interval]; Overlap: PROC [interval1, interval2: Interval] RETURNS [BOOL]; END. $Intervals.mesa Copyright c 1985 by Xerox Corporation. All rights reversed. Created by Bertrand Serlet, November 16, 1985 7:22:05 pm PST Bertrand Serlet, June 16, 1986 2:30:16 pm PDT 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. Record representing the interval [min .. max]. Note the inclusion of bounds. Creates a new table with a suggested hash size of 2**logHashSize-1. 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. 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. 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. Returns the effective range of all current values. Union of two intervals (trivial function). Overlapping of two intervals (trivial function). ΚΥ– "cedar" style˜codešœ™Kšœ Οmœ1™KšœŸœ™5KšœŸœ@™UKšœ2Ÿœ™JKšœŸœŸ™)——K˜Kš œŸœŸœŸœŸœ˜-Kš œŸœŸœŸœŸœ˜*K˜š‘œŸœŸœ ˜7K™2K™—š‘œŸœ"Ÿœ ˜@K™*—š‘œŸœ"ŸœŸœ˜>K™0—K™KšŸœ˜K˜——…—JC