-- File: Intervals.mesa
-- Written by MN/DF March 1981
-- Last edited: March 24, 1981 5:07 PM

DIRECTORY

InlineDefs: FROM "InlineDefs" USING [LowHalf],
IntervalsDefs: FROM "IntervalsDefs" USING [GetHandle, Node, NodeRecord,
Interval, IntervalRecord, BranchingFactor],
MiscDefs: FROM "MiscDefs" USING [CallDebugger],
XFSPDefs: FROM "XFSPDefs" USING [XAllocateHeapNode];

Intervals: PROGRAM
IMPORTS InlineDefs, MiscDefs, XFSPDefs
EXPORTS IntervalsDefs =
BEGIN
OPEN InlineDefs, IntervalsDefs, MiscDefs, XFSPDefs;

InitIntervals: PUBLIC PROCEDURE[left,right: LONG INTEGER] RETURNS[Node] =
BEGIN
range: LONG INTEGER ← right-left-1;
newRange: LONG INTEGER ← 1;
root: Node;
WHILE range>0 DO
range ← range/BranchingFactor;
newRange ← newRange*BranchingFactor;
ENDLOOP;
root ← AllocateNode[NIL, 0, left, newRange];
RETURN[root];
END;

FreeIntervals: PUBLIC PROCEDURE[root: Node,
freeData: PROCEDURE[LONG UNSPECIFIED]] =
BEGIN
int,nextint: Interval;
FOR i:CARDINAL IN [0..BranchingFactor) DO
IF root.sons[i]#NIL THEN FreeIntervals[root.sons[i], freeData];
ENDLOOP;
FOR int ← root.residue, nextint UNTIL int=NIL DO
nextint ← int.next;
freeData[int.hook];
FreeInterval[int];
ENDLOOP;
FreeNode[root];
END;

NullFreeData: PUBLIC PROCEDURE[data: LONG UNSPECIFIED] =
BEGIN
END;

Insert: PUBLIC PROCEDURE[root: Node, left,right: LONG INTEGER,
data: LONG UNSPECIFIED] =
BEGIN
leftSon,rightSon: CARDINAL;
IF left>right THEN {t: LONG INTEGER ← left; left ← right; right ← t;};
IF right<root.left THEN CallDebugger["right<root.left in Insert"];
IF left>root.right THEN CallDebugger["left>root.right in Insert"];
leftSon ← LowHalf[(left-root.left)/root.sonWidth];
rightSon ← LowHalf[(right-root.left-1)/root.sonWidth];
IF leftSon=rightSon AND root.sonWidth>0 THEN
{IF root.sons[leftSon]=NIL THEN
root.sons[leftSon] ←
AllocateNode[root, leftSon, root.left+leftSon*root.sonWidth,
root.sonWidth];
Insert[root.sons[leftSon],left,right,data]
}
ELSE root.residue ← AllocateInterval[root.residue,left,right,data];
END;

GetFirst: PUBLIC PROCEDURE[root: Node, left,right: LONG INTEGER,
getHandle: GetHandle]
RETURNS[LONG POINTER TO UNSPECIFIED] =
BEGIN
node: Node ← root;
getHandle↑ ← [
left: left,
right: right,
node: root,
interval: root.residue
];
RETURN[GetNext[getHandle]];
END;

GetNext: PUBLIC PROCEDURE[getHandle: GetHandle]
RETURNS[LONG POINTER TO UNSPECIFIED] =
BEGIN
IF getHandle.node=NIL THEN CallDebugger["NIL getHandle.node"];
FOR int:Interval ← getHandle.interval, int.next UNTIL int=NIL DO
IF int.left<=getHandle.right AND getHandle.left<=int.right THEN
{data: LONG POINTER TO UNSPECIFIED ← int.hook;
getHandle.interval ← int.next;
RETURN[data];
};
ENDLOOP;
getHandle.node ← NextNode[getHandle, getHandle.node];
IF getHandle.node=NIL THEN RETURN[NIL];
getHandle.interval ← getHandle.node.residue;
RETURN[GetNext[getHandle]];
END;

NextNode: PROCEDURE[getHandle: GetHandle, node: Node] RETURNS[Node] =
BEGIN
nextNode: Node;
--search for first existing son
FOR son:CARDINAL IN [0..BranchingFactor) DO
nextNode ← node.sons[son];
IF nextNode#NIL AND --filter out non-overlapping sons
nextNode.left<=getHandle.right AND getHandle.left<=nextNode.right THEN
RETURN[nextNode];
ENDLOOP;
--no sons, so try brother to the right
RETURN[NextRelative[getHandle, node]];
END;

NextRelative: PROCEDURE[getHandle: GetHandle, node: Node] RETURNS[Node] =
--return next brother, if exists, else next brother of father, etc.
BEGIN
brother: Node;
IF node.father=NIL THEN RETURN[NIL]; --Adam
--search for next existing brother
FOR i:CARDINAL IN (node.index..BranchingFactor) DO
brother ← node.father.sons[i];
IF brother#NIL AND --filter out non-overlapping brothers
brother.left<=getHandle.right AND getHandle.left<=brother.right THEN
RETURN[brother];
ENDLOOP;
--get next uncle
RETURN[NextRelative[getHandle, node.father]];
END;


--Allocation

NodesFree: Node ← NIL; --uses .father field as link
IntervalsFree: Interval ← NIL; --uses .next field as link

AllocateNode: PROCEDURE[father: Node, index: CARDINAL,
left,range: LONG INTEGER] RETURNS[Node] =
BEGIN
node: Node;
IF NodesFree=NIL THEN node ← XAllocateHeapNode[SIZE[NodeRecord]]
ELSE
{node ← NodesFree;
NodesFree ← NodesFree.father;
};
node↑ ← [
sons: ALL[NIL],
father: father,
index: index,
residue: NIL,
left: left,
right: left+range,
sonWidth: range/BranchingFactor
];
RETURN[node];
END;

FreeNode: PROCEDURE[node: Node] = INLINE
BEGIN
node.father ← NodesFree;
NodesFree ← node;
END;

AllocateInterval: PROCEDURE[next: Interval, left,right: LONG INTEGER, data:LONG POINTER TO UNSPECIFIED] RETURNS[Interval] =
BEGIN
interval: Interval;
IF IntervalsFree=NIL THEN
interval ← XAllocateHeapNode[SIZE[IntervalRecord]]
ELSE
{interval ← IntervalsFree;
IntervalsFree ← IntervalsFree.next;
};
interval↑ ← [
next: next,
left:left,
right: right,
hook:data
];
RETURN[interval];
END;

FreeInterval: PROCEDURE[interval: Interval] = INLINE
BEGIN
interval.next ← IntervalsFree;
IntervalsFree ← interval;
END;



END.