-- Test3Impl.mesa
-- written by Bill Paxton, April 1981
-- last edit by Bill Paxton, 28-Jul-81 10:12:47

DIRECTORY
EditTest,
EditSpan,
UndoEvent,
TextNode,
RandomLongInt,
TreeCheck;

Test3Impl: PROGRAM
	IMPORTS EditTest, EditSpan, TreeCheck, TextNode, 
	RandomLongInt, UndoEvent
	EXPORTS EditTest =
BEGIN
OPEN
	EditTest,
	spanI:EditSpan,
	randLI:RandomLongInt,
	undoI:UndoEvent,
	nodeI:TextNode;

Span: TYPE = nodeI.Span;

-- ***** Node Edit operations

PickNodeDest: PROC [tree: Ref]
	RETURNS [dest: Location, start, loc, size: Offset, where: Place,
		after, before: Ref] = {
	[dest, loc, size] ← PickNodeLoc[tree];
	IF size=0 THEN { dest ← nodeI.MakeNodeLoc[tree]; loc ← -1; where ← child }
	ELSE where ← PickPlace[];
	IF where#before THEN {
		after ← nodeI.StepForward[before ← dest.node];
		start ← loc+1 }
	ELSE {	before ← nodeI.StepBackward[after ← dest.node];
		start ← loc }};

CheckSpan: PROC
	[span: Span, spanStart, spanLen, treeSize: Offset, beforeSpan, afterSpan: Ref] = {
	start, len, size: Offset;
	before, after: Ref;
	[start, len, size] ← LocateSpan[span];
	IF size # treeSize OR start # spanStart OR len # spanLen THEN ERROR;
	IF (before ← nodeI.StepForward[beforeSpan]) # span.start.node THEN ERROR;
	IF afterSpan # (after ← nodeI.StepForward[span.end.node]) THEN ERROR };

ReplaceNodes: PUBLIC PROC = {
	CheckReplace: PROC = {
		TreeCheck.Verify[destTree];
		TreeCheck.Verify[nodeI.Root[dest.start.node]];
		CheckSpan[result, destStart, sourceLen, resultSize,
			beforeDest, afterDest] };
	
	sourceTree, destTree: Ref;
	source, dest, result: Span;
	beforeDest, afterDest: Ref;
	destStart, destLen, destSize, sourceStart, sourceLen, sourceSize: Offset;
	resultSize: Offset;
	[sourceTree, destTree] ← PickTrees[];
	[source, sourceStart, sourceLen, sourceSize] ← PickNodeSpan[sourceTree];
	[dest, destStart, destLen, destSize] ← PickNodeSpan[destTree];
	beforeDest ← nodeI.StepBackward[dest.start.node];
	afterDest ← nodeI.StepForward[dest.end.node];
	undoI.Reset[event];
	result ← spanI.Replace[dest, source, FALSE, event];
	resultSize ← destSize+sourceLen-destLen;
	CheckReplace;
	undoI.Reset[undoEvent];
	undoI.Undo[event, undoEvent];
	TreeCheck.Verify[destTree];
	TreeCheck.Verify[nodeI.Root[result.start.node]];
	CheckSpan[dest, destStart, destLen, destSize, beforeDest, afterDest];
	undoI.Undo[undoEvent]; -- undo the previous undo
	CheckReplace;
	AdjustTree[destTree, resultSize] };

DeleteFromTree: PUBLIC PROC [tree: Ref, size, num: Offset] RETURNS [newsize: Offset] = {
	newsize ← size;
	WHILE num > 0 DO
		start: Location;
		last, before, after: Ref;
		len, destLoc, destSize: Offset;
		[start, destLoc, destSize] ← PickNodeLoc[tree];
		IF (len ← MIN[num,destSize-destLoc])=0 THEN ERROR;
		last ← FindLastNode[start.node, len];
		after ← nodeI.StepForward[last];
		before ← nodeI.StepBackward[start.node];
		[] ← spanI.Delete[[start,nodeI.MakeNodeLoc[last]]];
		newsize ← newsize-len; num ← num-len;
		CheckDelete[tree, before, after, start.node, newsize];
		ENDLOOP };

CheckDelete: PROC [destTree, beforeDest, afterDest, inDest: Ref,
	resultSize: Offset] = {
	size: Offset;
	next: Ref;
	TreeCheck.Verify[destTree];
	TreeCheck.Verify[nodeI.Root[inDest]];
	IF (size ← TreeSize[destTree]) # resultSize THEN ERROR;
	IF (next ← nodeI.StepForward[beforeDest]) # afterDest THEN ERROR };

DeleteNodes: PUBLIC PROC = {
	destTree: Ref;
	dest: Span;
	beforeDest, afterDest: Ref;
	destStart, destLen, destSize: Offset;
	resultSize: Offset;
	destTree ← PickTree[];
	[dest, destStart, destLen, destSize] ← PickNodeSpan[destTree];
	beforeDest ← nodeI.StepBackward[dest.start.node];
	afterDest ← nodeI.StepForward[dest.end.node];
	undoI.Reset[event];
	spanI.Delete[dest, event];
	resultSize ← destSize-destLen;
	CheckDelete[destTree, beforeDest, afterDest, dest.start.node, resultSize];
	undoI.Reset[undoEvent];
	undoI.Undo[event, undoEvent]; -- undo the delete
	TreeCheck.Verify[destTree];
	CheckSpan[dest, destStart, destLen, destSize, beforeDest, afterDest];
	undoI.Undo[undoEvent]; -- undo the previous undo
	CheckDelete[destTree, beforeDest, afterDest, dest.start.node, resultSize];
	AdjustTree[destTree, resultSize] };

InsertInTree: PUBLIC PROC [tree: Ref, size, num: Offset] RETURNS [newsize: Offset] = {
	newsize ← size;
	WHILE num > 0 DO newsize ← InsertOne[tree]; num ← num-1; ENDLOOP };

InsertNode: PUBLIC PROC = {
	tree: Ref ← PickTree[];
	size: Offset ← InsertOne[tree];
	AdjustTree[tree, size] };

InsertOne: PROC [tree: Ref] RETURNS [size: Offset] = {
	dest: Location;
	destStart, destLoc, destSize: Offset;
	new, afterDest, beforeDest: Ref;
	where: Place;
	[dest,destStart,destLoc,destSize,where,afterDest,beforeDest] ← PickNodeDest[tree];
	new ← spanI.Insert[dest.node, where];
	TreeCheck.Verify[tree];
	CheckSpan[nodeI.MakeNodeSpan[new,new], destStart, 1,
		destSize+1, beforeDest, afterDest];	
	RETURN [destSize+1] };

CopyNodes: PUBLIC PROC = {
	sourceTree, destTree: Ref;
	source, result: Span;
	dest: Location;
	beforeDest, afterDest: Ref;
	destStart, destLoc, destSize, sourceStart, sourceLen, sourceSize: Offset;
	undoLoc, undoSize, resultSize: Offset;
	where: Place;
	[sourceTree, destTree] ← PickTrees[];
	[source, sourceStart, sourceLen, sourceSize] ← PickNodeSpan[sourceTree];
	[dest,destStart,destLoc,destSize,where,afterDest,beforeDest] ← PickNodeDest[destTree];
	undoI.Reset[event];
	result ← spanI.Copy[dest, source, FALSE, where, 0, event];
	TreeCheck.Verify[destTree];
	CheckSpan[result, destStart, sourceLen, resultSize ← destSize+sourceLen,
		beforeDest, afterDest];
	undoI.Reset[undoEvent];
	undoI.Undo[event, undoEvent]; -- undo the copy
	TreeCheck.Verify[destTree];
	[undoLoc, undoSize] ← LocateNode[dest.node];
	IF undoSize # destSize OR undoLoc # destLoc THEN ERROR;
	undoI.Undo[undoEvent]; -- undo the previous undo
	TreeCheck.Verify[destTree];
	CheckSpan[result, destStart, sourceLen, resultSize, beforeDest, afterDest];
	AdjustTree[destTree, resultSize] };

MoveNodes: PUBLIC PROC = {
	CheckMove: PROC = {
		next: Ref;
		size: Offset;
		TreeCheck.Verify[destTree];
		IF result # source THEN ERROR;
		IF (next ← nodeI.StepForward[beforeSource]) # afterSource THEN ERROR;
		IF sourceTree=destTree THEN {
			resultSize ← sourceSize;
			resultStart ← IF destStart > sourceStart THEN destStart-sourceLen ELSE destStart }
		ELSE {	TreeCheck.Verify[sourceTree];
			IF (size ← TreeSize[sourceTree]) # sourceSize-sourceLen THEN ERROR;
			resultSize ← destSize+sourceLen; resultStart ← destStart };
		CheckSpan[result, resultStart, sourceLen, resultSize, beforeDest, afterDest] };

	sourceTree, destTree, beforeDest, afterDest, beforeSource, afterSource: Ref;
	moveToEnd: BOOLEAN;
	source, result: Span;
	dest: Location;
	sourceStart, sourceLen, sourceSize, destStart, destLoc, destSize: Offset;
	where: Place;
	undoLoc, undoSize, resultStart, resultSize: Offset;
	[sourceTree, destTree] ← PickTrees[];
	[source, sourceStart, sourceLen, sourceSize] ← PickNodeSpan[sourceTree];
	IF sourceTree=destTree THEN { 
		destSize ← sourceSize;
		IF moveToEnd←RandomBoolean[] THEN { -- move toward end
			sourceEnd: Offset ← sourceStart+sourceLen;
			IF sourceSize=sourceEnd THEN RETURN; -- cannot move toward end
			where ← IF RandomBoolean[] THEN after ELSE child;
			destLoc ← randLI.Choose[sourceEnd,sourceSize-1] }
		ELSE { -- move toward front
			IF sourceStart=0 THEN RETURN; -- cannot move toward front
			where ← before; destLoc ← randLI.Choose[0,sourceStart-1] };
		dest ← [FindTreeNode[destTree,destLoc],nodeI.NodeItself];
		IF where#before THEN {
			afterDest ← nodeI.StepForward[beforeDest ← dest.node];
			destStart ← destLoc+1 }
		ELSE {	beforeDest ← nodeI.StepBackward[afterDest ← dest.node];
			destStart ← destLoc }}
	ELSE [dest,destStart,destLoc,destSize,where,afterDest,beforeDest] ←
		PickNodeDest[destTree];
	afterSource ← nodeI.StepForward[source.end.node];
	beforeSource ← nodeI.StepBackward[source.start.node];
	undoI.Reset[event];
	result ← spanI.Move[dest, source, FALSE, where, 0, event];
	CheckMove;
	undoI.Reset[undoEvent]; undoI.Undo[event, undoEvent]; -- undo the move
	TreeCheck.Verify[destTree];
	IF sourceTree#destTree THEN TreeCheck.Verify[sourceTree];
	[undoLoc, undoSize] ← LocateNode[dest.node];
	IF undoSize # destSize OR undoLoc # destLoc THEN ERROR;
	CheckSpan[source, sourceStart, sourceLen, sourceSize, beforeSource, afterSource];
	undoI.Undo[undoEvent]; -- undo the previous undo
	CheckMove;
	IF sourceTree#destTree THEN {
		AdjustTree[destTree, destSize+sourceLen];
		AdjustTree[sourceTree, sourceSize-sourceLen] }};

MoveNodesOnto: PUBLIC PROC = {

	CheckMoveOnto: PROC = {
		IF result # source THEN ERROR;
		TreeCheck.Verify[destTree];
		IF sourceTree = destTree THEN { -- check for overlap or adjacent
			IF destEnd=sourceStart THEN CheckSpan[result, destStart, sourceLen,
				sourceSize-destLen, beforeDest, afterSource]
			ELSE IF sourceEnd=destStart THEN CheckSpan[result, sourceStart, sourceLen,
				sourceSize-destLen, beforeSource, afterDest]
			ELSE IF sourceStart IN [destStart..destEnd) THEN
				IF sourceEnd IN [destStart..destEnd] THEN
					CheckSpan[result, destStart, sourceLen,
						sourceSize+sourceLen-destLen,
						beforeDest, afterDest]
				ELSE CheckSpan[result, destStart, sourceLen,
					sourceSize+destStart-sourceStart, beforeDest, afterSource]
			ELSE IF sourceEnd IN [destStart..destEnd) THEN
				CheckSpan[result, sourceStart, sourceLen,
					sourceSize+sourceEnd-destEnd, beforeSource, afterDest]
			ELSE IF sourceStart < destStart THEN
				IF sourceEnd >= destEnd THEN 
					CheckSpan[result, sourceStart, sourceLen, sourceSize,
						beforeSource, afterSource]
				ELSE CheckSpan[result, destStart-sourceLen, sourceLen,
					sourceSize-destLen, beforeDest, afterDest]
			ELSE CheckSpan[result, destStart, sourceLen,
				sourceSize-destLen, beforeDest, afterDest] }
		ELSE {	size: Offset;
			next: Ref;
			TreeCheck.Verify[sourceTree];
			IF (size ← TreeSize[sourceTree]) # sourceSize-sourceLen THEN ERROR;
			IF (next ← nodeI.StepForward[beforeSource]) # afterSource THEN ERROR;
			CheckSpan[result, destStart, sourceLen, destSize+sourceLen-destLen,
				beforeDest, afterDest] }};
		
	sourceTree, destTree: Ref;
	source, dest, result: Span;
	beforeDest, afterDest, beforeSource, afterSource: Ref;
	destStart, destLen, destSize, sourceStart, sourceLen, sourceSize: Offset;
	destEnd, sourceEnd: Offset;
	[sourceTree, destTree] ← PickTrees[];
	[source, sourceStart, sourceLen, sourceSize] ← PickNodeSpan[sourceTree];
	sourceEnd ← sourceStart+sourceLen;
	[dest, destStart, destLen, destSize] ← PickNodeSpan[destTree];
	destEnd ← destStart+destLen;
	beforeDest ← nodeI.StepBackward[dest.start.node];
	afterDest ← nodeI.StepForward[dest.end.node];
	beforeSource ← nodeI.StepBackward[source.start.node];
	afterSource ← nodeI.StepForward[source.end.node];
	undoI.Reset[event];
	result ← spanI.MoveOnto[dest, source, FALSE, event];
	CheckMoveOnto;
	undoI.Reset[undoEvent]; undoI.Undo[event, undoEvent]; -- undo the move
	TreeCheck.Verify[destTree];
	IF sourceTree # destTree THEN TreeCheck.Verify[sourceTree];
	CheckSpan[dest, destStart, destLen, destSize, beforeDest, afterDest];
	CheckSpan[source, sourceStart, sourceLen, sourceSize, beforeSource, afterSource];
	undoI.Undo[undoEvent]; -- undo the previous undo
	CheckMoveOnto;
	IF sourceTree # destTree THEN {
		AdjustTree[destTree, destSize+sourceLen-destLen];
		AdjustTree[sourceTree, sourceSize-sourceLen] }
	ELSE AdjustTree[destTree, TreeSize[destTree]] };
	

TransposeNodes: PUBLIC PROC = {
	
	CheckTranspose: PROC = {
		TreeCheck.Verify[alphaTree];
		IF alphaTree = betaTree THEN {
			IF ~alphaFirst THEN {
				CheckSpan[alpha, betaStart, alphaLen, alphaSize, beforeBeta, afterBeta];
				CheckSpan[beta, alphaStart+alphaLen-betaLen, betaLen, alphaSize,
					beforeAlpha, afterAlpha] }
			ELSE {	CheckSpan[alpha, betaStart-alphaLen+betaLen, alphaLen, alphaSize,
					beforeBeta, afterBeta];
				CheckSpan[beta, alphaStart, betaLen, alphaSize,
					beforeAlpha, afterAlpha] }}
		ELSE {	TreeCheck.Verify[betaTree];
			CheckSpan[alpha, betaStart, alphaLen, betaSize+alphaLen-betaLen,
				beforeBeta, afterBeta];
			CheckSpan[beta, alphaStart, betaLen, alphaSize+betaLen-alphaLen,
				beforeAlpha, afterAlpha] }};
		
	alphaTree, betaTree: Ref;
	alpha, beta, alphaResult, betaResult: Span;
	beforeAlpha, afterAlpha, beforeBeta, afterBeta: Ref;
	alphaStart, alphaLen, alphaSize, betaStart, betaLen, betaSize: Offset;
	alphaEnd, betaEnd: Offset;
	alphaFirst: BOOLEAN;
	
	[alphaTree, betaTree] ← PickTrees[];
	[alpha, alphaStart, alphaLen, alphaSize] ← PickNodeSpan[alphaTree];
	alphaEnd ← alphaStart+alphaLen;
	beforeAlpha ← nodeI.StepBackward[alpha.start.node];
	afterAlpha ← nodeI.StepForward[alpha.end.node];
	
	IF alphaTree = betaTree THEN {
		betaFirst, betaLast: Ref;
		betaSize ← alphaSize;
		IF alphaFirst←RandomBoolean[] THEN {
			IF alphaEnd+1 >= alphaSize THEN RETURN; -- nothing after alpha
			[betaStart,betaEnd] ← ChooseTwo[alphaEnd+1,alphaSize] }
		ELSE { -- pick beta section to left of alpha
			IF alphaStart <= 1 THEN RETURN; -- nothing before alpha
			[betaStart,betaEnd] ← ChooseTwo[0,alphaStart-1] };
		IF (betaLen ← betaEnd-betaStart) = 0 THEN RETURN;
		betaFirst ← FindTreeNode[betaTree, betaStart];
		betaLast ← FindTreeNode[betaTree, betaEnd-1];
		beta ← nodeI.MakeNodeSpan[betaFirst, betaLast] }
	ELSE [beta, betaStart, betaLen, betaSize] ← PickNodeSpan[betaTree];
	beforeBeta ← nodeI.StepBackward[beta.start.node];
	afterBeta ← nodeI.StepForward[beta.end.node];
	undoI.Reset[event];
	[alphaResult,betaResult] ← spanI.Transpose[alpha, beta, FALSE, event];
	IF alpha # alphaResult OR beta # betaResult THEN ERROR;
	CheckTranspose;
	undoI.Reset[undoEvent]; undoI.Undo[event, undoEvent]; -- undo the transpose
	TreeCheck.Verify[alphaTree];
	IF alphaTree # betaTree THEN TreeCheck.Verify[betaTree];
	CheckSpan[alpha, alphaStart, alphaLen, alphaSize, beforeAlpha, afterAlpha];
	CheckSpan[beta, betaStart, betaLen, betaSize, beforeBeta, afterBeta];
	undoI.Undo[undoEvent]; -- undo the previous undo
	CheckTranspose;
	IF alphaTree # betaTree THEN {
		AdjustTree[alphaTree, alphaSize+betaLen-alphaLen];
		AdjustTree[betaTree, betaSize+alphaLen-betaLen] }
	ELSE AdjustTree[alphaTree, alphaSize] };

SplitNode: PUBLIC PROC = {

	CheckSplit: PROC = {
		TreeCheck.Verify[destTree];
		CheckSpan[nodeI.MakeNodeSpan[newNode,newNode], destLoc, 1, destSize+1,
			before, splitNode] };
		
	destTree: Ref ← PickTree[];
	destLoc, destSize, splitLoc: Offset;
	dest: Location;
	splitNode: Node;
	before, after, newNode: Ref;
	
	[dest, destLoc, destSize] ← PickNodeLoc[destTree];
	after ← nodeI.StepForward[dest.node]; before ← nodeI.StepBackward[dest.node];
	splitLoc ← PickOne[splitNode ← nodeI.NarrowToTextNode[dest.node]];
	undoI.Reset[event];
	newNode ← spanI.Split[[splitNode,splitLoc], event];
	CheckSplit;
	undoI.Reset[undoEvent];
	undoI.Undo[event, undoEvent]; -- undo the split
	TreeCheck.Verify[destTree];
	CheckSpan[nodeI.MakeNodeSpan[splitNode,splitNode], destLoc, 1, destSize, before, after];
	undoI.Undo[undoEvent]; -- undo the undo
	CheckSplit;
	AdjustTree[destTree, destSize+1] };

MergeNodes: PUBLIC PROC = {

	CheckMerge: PROC = {
		TreeCheck.Verify[destTree];
		IF mergeNode # before THEN ERROR;
		CheckSpan[nodeI.MakeNodeSpan[mergeNode,mergeNode],
			destLoc-1, 1, destSize-1, nodeI.StepBackward[before], after] };
	
	destTree: Ref ← PickTree[];
	destLoc, destSize: Offset;
	dest: Location;
	before, after, destNode, mergeNode: Ref;
	mergeLoc: Location;
	
	[dest, destLoc, destSize] ← PickNodeLoc[destTree];
	IF destLoc=0 THEN RETURN; -- no predecessor to merge with
	destNode ← dest.node;
	after ← nodeI.StepForward[destNode]; before ← nodeI.StepBackward[destNode];
	undoI.Reset[event];
	mergeLoc ← spanI.Merge[destNode, event];
	mergeNode ← mergeLoc.node;
	CheckMerge;
	undoI.Reset[undoEvent];
	undoI.Undo[event, undoEvent]; -- undo the merge
	TreeCheck.Verify[destTree];
	CheckSpan[nodeI.MakeNodeSpan[destNode,destNode], destLoc, 1, destSize, before, after];
	undoI.Undo[undoEvent]; -- undo the undo
	CheckMerge;
	AdjustTree[destTree, destSize-1] };

NestNodes: PUBLIC PROC = { ChangeNesting[1] };

UnNestNodes: PUBLIC PROC = { ChangeNesting[-1] };

ChangeNesting: PROC [change: INTEGER] = {
	destTree: Ref;
	dest, result: Span;
	before, after: Ref;
	destStart, destLen, destSize: Offset;
	destTree ← PickTree[];
	[dest, destStart, destLen, destSize] ← PickNodeSpan[destTree];
	before ← nodeI.StepBackward[dest.start.node];
	after ← nodeI.StepForward[dest.end.node];
	undoI.Reset[event];
	result ← spanI.ChangeNesting[dest, change, event];
	IF result # dest THEN ERROR;
	CheckSpan[dest, destStart, destLen, destSize, before, after];
	undoI.Reset[undoEvent];
	undoI.Undo[event, undoEvent]; -- undo the change in nesting
	TreeCheck.Verify[destTree];
	CheckSpan[dest, destStart, destLen, destSize, before, after];
	undoI.Undo[undoEvent]; -- undo the previous undo
	CheckSpan[dest, destStart, destLen, destSize, before, after] };

END.