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.