DIRECTORY Basics USING [BITSHIFT], D2Intervals, Intervals; D2IntervalsImpl: CEDAR MONITOR LOCKS table USING table: Table IMPORTS Basics, Intervals EXPORTS D2Intervals = BEGIN OPEN D2Intervals; Hash: PROC [table: Table, xRect: Interval] RETURNS [hash: NAT _ 0]= { xRange: Interval _ table.range.x; buckets: NAT _ (table.data.hashSize+1)/2; min: NAT _ ((xRect.min - xRange.min) * buckets) / (xRange.max + 1 - xRange.min); max: NAT _ ((xRect.max - xRange.min) * buckets) / (xRange.max + 1 - xRange.min); IF min<0 OR max>=buckets THEN ERROR; -- ERROR probably due to an rect outside the table range UNTIL min=max DO hash _ hash + buckets; buckets _ buckets / 2; min _ min / 2; max _ max / 2; ENDLOOP; hash _ hash + min; }; Create: PUBLIC PROC [range: Rect, valueRect: ValueRectProc, userData: REF _ NIL, logHashSize: NAT _ 2] RETURNS [Table] = { data: REF TableData _ NEW [TableData[Basics.BITSHIFT[value: 1, count: logHashSize]-1]]; RETURN [NEW [TableRec _ [ range: range, size: 0, valueRect: valueRect, userData: userData, effectiveRange: empty, leafBuckets: 0, data: data ]]]; }; SubValueInterval: PROC [subTable: Intervals.Table, value: Intervals.Value] RETURNS [interval: Interval] = { table: Table _ NARROW [subTable.userData]; interval _ table.valueRect[table, value].y; }; ReHash: PROC [table: Table] = { ReInsert: PROC [subTable: Intervals.Table, value: Intervals.Value] RETURNS [quit: BOOL _ FALSE] = { rect: Rect _ table.valueRect[table, value]; hash: NAT _ Hash [table, rect.x]; IF newData[hash]=NIL THEN { newData[hash] _ Intervals.Create[range: table.range.y, valueInterval: SubValueInterval, userData: table]; table.leafBuckets _ table.leafBuckets+1; }; table.effectiveRange _ Union[rect, table.effectiveRange]; Intervals.Insert[newData[hash], value]; }; oldData: REF TableData _ table.data; newData: REF TableData _ NEW [TableData[oldData.hashSize*2+1]]; table.data _ newData; table.leafBuckets _ 0; FOR i: NAT IN [0 .. oldData.hashSize) DO IF oldData[i]#NIL THEN [] _ Intervals.Enumerate[oldData[i], ReInsert]; ENDLOOP; }; Insert: PUBLIC ENTRY PROC [table: Table, value: Value] = { ENABLE UNWIND => NULL; rect: Rect _ table.valueRect[table, value]; hash: NAT _ Hash [table, rect.x]; table.size _ table.size + 1; IF table.data[hash]=NIL THEN { table.data[hash] _ Intervals.Create[range: table.range.y, valueInterval: SubValueInterval, userData: table]; table.leafBuckets _ table.leafBuckets+1; }; table.effectiveRange _ Union[rect, table.effectiveRange]; Intervals.Insert[table.data[hash], value]; IF table.leafBuckets * 2 > table.data.hashSize THEN ReHash[table]; }; Delete: PUBLIC ENTRY PROC [table: Table, value: Value] = { ENABLE UNWIND => NULL; xRect: Interval _ table.valueRect[table, value].x; hash: NAT _ Hash [table, xRect]; previousSize: NAT; IF table.data[hash]=NIL THEN RETURN; previousSize _ table.data[hash].size; Intervals.Delete[table.data[hash], value]; IF table.data[hash].size=previousSize THEN RETURN; -- no deletion occurred table.effectiveRange _ universe; table.size _ table.size - (previousSize - table.data[hash].size); }; Enumerate: PUBLIC PROC [table: Table, action: PROC [Table, Value] RETURNS [BOOLEAN _ FALSE], rect: Rect _ universe] RETURNS [BOOLEAN] = { SubEnumerate: PROC [subTable: Intervals.Table, value: Intervals.Value] RETURNS [quit: BOOL _ FALSE] = { quit _ Overlap[table.valueRect[table, value], clipped] AND action[table, value]; }; data: REF TableData _ table.data; -- stored in the local frame to avoid concurrent inconsistencies range: Rect _ table.range; -- stored in the local frame to avoid concurrent inconsistencies effectiveRange: Rect _ table.effectiveRange; buckets: NAT _ (data.hashSize+1)/2; hash: NAT _ 0; clipped: Rect _ [[MAX [rect.x.min, range.x.min, effectiveRange.x.min], MIN [rect.x.max, range.x.max, effectiveRange.x.max]], [MAX [rect.y.min, range.y.min, effectiveRange.y.min], MIN [rect.y.max, range.y.max, effectiveRange.y.max]]]; min, max: NAT; IF clipped.x.min>clipped.x.max OR clipped.y.min>clipped.y.max THEN RETURN [FALSE]; -- empty rect min _ ((clipped.x.min - range.x.min) * buckets) / (range.x.max + 1 - range.x.min); max _ ((clipped.x.max - range.x.min) * buckets) / (range.x.max + 1 - range.x.min); IF min<0 OR max>=buckets THEN ERROR; -- bug in the implementation WHILE buckets>0 DO FOR i: NAT IN [hash+min .. hash+max] DO IF data[i]#NIL AND Intervals.Enumerate[data[i], SubEnumerate, clipped.y] THEN RETURN [TRUE]; ENDLOOP; hash _ hash + buckets; buckets _ buckets / 2; min _ min / 2; max _ max / 2; ENDLOOP; RETURN [FALSE]; }; Erase: PUBLIC ENTRY PROC [table: Table] = { FOR i: NAT IN [0 .. table.data.hashSize) DO IF table.data[i]=NIL THEN LOOP; table.data[i].userData _ NIL; table.data[i] _ NIL; ENDLOOP; table.leafBuckets _ 0; table.effectiveRange _ empty; table.size _ 0; }; EffectiveRange: PUBLIC INTERNAL PROC [table: Table] RETURNS [effectiveRange: Rect _ empty] = { ComputeEffectiveRange: PROC [table: Table, value: Value] RETURNS [BOOL _ FALSE] = { effectiveRange _ Union[table.valueRect[table, value], effectiveRange]; }; IF table.effectiveRange#universe THEN RETURN [table.effectiveRange]; [] _ Enumerate[table, ComputeEffectiveRange]; table.effectiveRange _ effectiveRange; }; Union: PUBLIC PROC [rect1, rect2: Rect] RETURNS [Rect] = { RETURN [[Intervals.Union[rect1.x, rect2.x], Intervals.Union[rect1.y, rect2.y]]]; }; Overlap: PUBLIC PROC [rect1, rect2: Rect] RETURNS [BOOL] = { RETURN [Intervals.Overlap[rect1.x, rect2.x] AND Intervals.Overlap[rect1.y, rect2.y]]; }; END. ΐD2IntervalsImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reversed. Created by Bertrand Serlet, March 8, 1986 1:51:29 pm PST Bertrand Serlet, April 3, 1986 7:42:17 pm PST Κ2– "cedar" style˜codešœ™Kšœ Οmœ1™