-- LSSplineImpl.mesa
--last edited by Michael Plass  August 4, 1982 10:19 am

DIRECTORY Complex, Cubic, LSPiece, Seq, Vector, LSSpline;

LSSplineImpl: PROGRAM IMPORTS LSPiece EXPORTS LSSpline =
BEGIN

Handle: TYPE = LSSpline.Handle;
Rec: TYPE = LSSpline.Rec; 

Create: PUBLIC PROCEDURE [lengthHint: NAT ← 10] RETURNS [handle: Handle] = {
	handle ← NEW[Rec];
	handle.z ← NEW[Seq.ComplexSequenceRec[lengthHint]];
	handle.tan ← NEW[Seq.ComplexSequenceRec[lengthHint]];
	handle.t ← NEW[Seq.RealSequenceRec[lengthHint]];
	handle.length ← 0;
	};

Reset: PUBLIC PROCEDURE [handle: Handle] = {handle.length ← 0};

Sample: PUBLIC PROCEDURE [handle: Handle, samplePoint, tangent: Complex.Vec ← [0,0]] = {
	WHILE handle.length >= handle.z.length DO
		temp: Handle ← Create[handle.length + handle.length/2 + 1];
		FOR i:NAT IN [0..handle.length) DO
			Sample[temp, handle.z[i], handle.tan[i]];
			ENDLOOP;
		handle↑ ← temp↑;
		ENDLOOP;
	handle.z[handle.length] ← samplePoint;
	handle.tan[handle.length] ← tangent;
	handle.length ← handle.length + 1;
	}; 

CubicProc: TYPE = PROCEDURE [Cubic.Bezier];

Subdivide: PUBLIC PROCEDURE [handle: Handle, cubicProc: CubicProc, tolerance: REAL, from: NAT ← 0, thru: NAT ← LAST[NAT]] = {
	b: Cubic.Bezier;
	err: REAL;
	iterations: NAT;
	maxDev: REAL;
	IF handle.length = 0 THEN RETURN;
	thru ← MIN[thru, handle.length - 1];
	IF from >= thru THEN RETURN;
	IF thru = from+1 THEN {
		b0: Vector.Vec ← handle.z[from];
		b3: Vector.Vec ← handle.z[thru];
		cubicProc[[b0, b0, b3, b3]];
		RETURN;
		};
	[b, err, iterations, maxDev] ← LSPiece.FitPiece[
		z: handle.z,
		t: handle.t,
		from: from,
		thru: thru,
		maxd: tolerance,
		maxit: firstTryIterationLimit,
		initTangent: handle.tan[from],
		finalTangent: handle.tan[thru]
		];
	stats.firstTryCount ← stats.firstTryCount + 1;
	stats.firstTryIterations ← stats.firstTryIterations + iterations;
	IF maxDev <= tolerance*firstTryToleranceFactor THEN {
		[b, err, iterations, maxDev] ← LSPiece.FitPiece[
			z: handle.z,
			t: handle.t,
			from: from,
			thru: thru,
			maxd: tolerance/secondTryOptimistFactor,
			maxit: secondTryIterationLimit,
			initTangent: handle.tan[from],
			finalTangent: handle.tan[thru],
			useOldTValues: TRUE
			];
		stats.secondTryCount ← stats.secondTryCount + 1;
		stats.secondTryIterations ← stats.secondTryIterations + iterations;
		};
	IF maxDev <= tolerance THEN cubicProc[b]
	ELSE {
		mid: NAT ← (from+thru)/2;
		Subdivide[handle, cubicProc, tolerance, from, mid];
		Subdivide[handle, cubicProc, tolerance, mid, thru];
		}; 
	};

firstTryIterationLimit: NAT ← 3;
firstTryToleranceFactor: REAL ← 3.0;
secondTryIterationLimit: NAT ← 20;
secondTryOptimistFactor: REAL ← 2.0;

stats: RECORD [
	firstTryCount: INT ← 0,
	firstTryIterations: INT ← 0,
	secondTryCount: INT ← 0,
	secondTryIterations: INT ← 0
	];

END.