<> <> <> <> DIRECTORY Basics USING [BITSHIFT], CDBasics, Core, CoreGeometry, SinixD2Intervals, SinixIntervals; SinixD2IntervalsImpl: CEDAR MONITOR LOCKS table USING table: Table IMPORTS Basics, CDBasics, CoreGeometry, SinixIntervals EXPORTS SinixD2Intervals = BEGIN OPEN SinixD2Intervals; Normalize: PROC [table: Table, rect: Rect] RETURNS [buckets, min, max: NAT] = INLINE { width: INT = table.range.x2 + 1 - table.range.x1; buckets _ (table.data.hashSize+1)/2; min _ ((rect.x1 - table.range.x1) * buckets) / width; max _ ((rect.x2 - table.range.x1) * buckets) / width; IF min<0 OR max>=buckets THEN ERROR; -- ERROR probably due to an interval outside the table range }; Hash: PROC [table: Table, instance: CoreGeometry.Instance] RETURNS [hash: NAT _ 0]= { buckets, min, max: NAT; [buckets, min, max] _ Normalize[table, CoreGeometry.InlineBBox[instance]]; 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, logHashSize: NAT _ 2] RETURNS [Table] = { data: REF TableData _ NEW [TableData[Basics.BITSHIFT[value: 1, count: logHashSize]-1]]; RETURN [NEW [TableRec _ [range: range, leafBuckets: 0, data: data]]]; }; ReHash: PROC [table: Table] = { ReInsert: PROC [instance: CoreGeometry.Instance, wire: Core.Wire] = { hash: NAT _ Hash [table, instance]; IF newData[hash]=NIL THEN { newData[hash] _ SinixIntervals.Create[range: [table.range.y1, table.range.y2], logHashSize: 1]; table.leafBuckets _ table.leafBuckets+1; }; SinixIntervals.Insert[newData[hash], instance, wire]; }; 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 SinixIntervals.Enumerate[oldData[i], ReInsert]; ENDLOOP; }; Insert: PUBLIC ENTRY PROC [table: Table, instance: CoreGeometry.Instance, wire: Core.Wire] = { ENABLE UNWIND => NULL; hash: NAT _ Hash[table, instance]; IF table.data[hash]=NIL THEN { table.data[hash] _ SinixIntervals.Create[range: [table.range.y1, table.range.y2], logHashSize: 1]; table.leafBuckets _ table.leafBuckets+1; }; SinixIntervals.Insert[table.data[hash], instance, wire]; IF table.leafBuckets * 2 > table.data.hashSize THEN ReHash[table]; }; Enumerate: PUBLIC PROC [table: Table, action: PROC [CoreGeometry.Instance, Core.Wire], rect: Rect _ universe] = { SubEnumerate: PROC [instance: CoreGeometry.Instance, wire: Core.Wire] = { IF CDBasics.Intersect[CoreGeometry.InlineBBox[instance], clipped] THEN action[instance, wire]; }; data: REF TableData _ table.data; -- stored in the local frame to avoid concurrent inconsistencies buckets, min, max: NAT; hash: NAT _ 0; clipped: Rect _ CDBasics.Intersection[rect, table.range]; IF NOT CDBasics.NonEmpty[clipped] THEN RETURN; -- empty rect [buckets, min, max] _ Normalize[table, clipped]; 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 THEN SinixIntervals.Enumerate[data[i], SubEnumerate, [clipped.y1, clipped.y2]]; ENDLOOP; hash _ hash + buckets; buckets _ buckets / 2; min _ min / 2; max _ max / 2; ENDLOOP; }; DeleteOutside: PUBLIC ENTRY PROC [table: Table, rect: Rect] = { hash: NAT _ 0; buckets, min, max: NAT; clipped: Rect _ CDBasics.Intersection[rect, table.range]; nonEmpty: BOOL _ CDBasics.NonEmpty[clipped]; [buckets, min, max] _ Normalize[table, IF nonEmpty THEN clipped ELSE table.range]; WHILE buckets>0 DO FOR i: NAT IN [hash .. hash+buckets) DO subTable: SinixIntervals.Table = table.data[i]; IF subTable=NIL THEN LOOP; SinixIntervals.DeleteOutside[ subTable, IF nonEmpty AND i>=hash+min AND i<=hash+max THEN [rect.y1, rect.y2] ELSE SinixIntervals.empty ]; ENDLOOP; hash _ hash + buckets; buckets _ buckets / 2; min _ min / 2; max _ max / 2; ENDLOOP; }; Size: PROC [table: Table] RETURNS [size: INT _ 0] = { Count: PROC [CoreGeometry.Instance, Core.Wire] = {size _ size + 1}; Enumerate[table, Count]; }; END.