-- 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.
(635)\95b10B214f1 8f0 8f1 8f0 31b9B40f1 8f0 73f1 8f0 3b13B315b13B381b12B59b6B757b8B275b7B579b8B440b12B677b12B410b8B92b16B396b12B