-- TreeEditImpl.mesa
-- written by Bill Paxton, May 1981
-- last edit by Bill Paxton, 29-Jun-81  8:46:02

DIRECTORY
TreeEdit,
EditNotify,
NodeProps,
TextEdit,
OtherNode,
TextNode;

TreeEditImpl: PROGRAM
	IMPORTS nodeI:TextNode, editI:TextEdit, TreeEdit, EditNotify,
		propsI:NodeProps, otherI:OtherNode
	EXPORTS TreeEdit =
BEGIN
OPEN TreeEdit, EditNotify;

-- **** Editing Operations for tree structure ****
	
ReplaceNodes: PUBLIC PROC [destFirst, destLast, sourceFirst, sourceLast: Ref] = {
	notify: REF ReplacingNodes Change;
	first,last,destParent,destPrev,destAfter: Ref;
	[first,last] ← CopySpan[sourceFirst,sourceLast];
	notify ← NEW[ReplacingNodes Change ←
			[ReplacingNodes[destFirst, destLast, sourceFirst, sourceLast]]];
	[destParent,destPrev,destAfter] ← Relatives[destFirst,destLast];
	Notify[destParent,NIL,notify,before];
	IF first=NIL THEN Del[destParent,destPrev,destAfter]
	ELSE Rep[destParent,destPrev,destAfter,first,last];
	Notify[destParent,NIL,notify,after] };

CopyNodes: PUBLIC PROC [dest, sourceFirst, sourceLast: Ref, child: BOOLEAN ← TRUE] = {
	first, last, parent: Ref;
	notify: REF CopyingNodes Change;
	IF dest=NIL THEN RETURN;
	notify ← NEW [CopyingNodes Change ←
			[CopyingNodes[dest, sourceFirst, sourceLast, child]]];
	parent ← IF child THEN dest ELSE nodeI.Parent[dest];
	Notify[parent,NIL,notify,before];
	[first,last] ← CopySpan[sourceFirst,sourceLast];
	InsertSpan[dest,first,last,child];
	Notify[parent,NIL,notify,after] };

BadMove: PUBLIC ERROR = CODE;
MoveNodesOnto: PUBLIC PROC [destFirst, destLast, moveFirst, moveLast: Ref] = {
	-- dest cannot be within source
	notify: REF MovingNodesOnto Change;
	moveParent, movePrev, moveAfter: Ref;
	destParent, destPrev, destAfter: Ref;
	IF moveFirst=NIL THEN { DeleteNodes[destFirst,destLast]; RETURN };
	[moveParent,movePrev,moveAfter] ← Relatives[moveFirst,moveLast];
	[destParent,destPrev,destAfter] ← Relatives[destFirst,destLast];
	IF moveParent=destParent THEN { -- check overlapping or adjacent
		IF InsideSiblings[moveFirst,destFirst,destLast] THEN {
			IF InsideSiblings[moveLast,destFirst,destLast] AND
				moveLast # destLast THEN DeleteNodes[moveAfter,destLast];
			IF moveFirst # destFirst THEN DeleteNodes[destFirst,movePrev];
			RETURN };
		IF InsideSiblings[moveLast,destFirst,destLast] THEN {
			IF moveLast # destLast THEN DeleteNodes[moveAfter,destLast];
			RETURN };
		IF InsideSiblings[destFirst,moveFirst,moveLast] THEN RETURN;
		IF moveAfter=destFirst OR destAfter=moveFirst THEN {
			DeleteNodes[destFirst,destLast]; RETURN }};
	IF InsideSiblings[destFirst,moveFirst,moveLast] THEN ERROR BadMove; -- dest inside source
	notify ← NEW [MovingNodesOnto Change ←
			[MovingNodesOnto[destFirst, destLast, moveFirst, moveLast]]];
	Notify[destParent,moveParent,notify,before];
	Del[moveParent,movePrev,moveAfter];
	Rep[destParent,destPrev,destAfter,moveFirst,moveLast];
	Notify[destParent,moveParent,notify,after] };

MoveNodes: PUBLIC PROC [dest, moveFirst, moveLast: Ref, child: BOOLEAN ← TRUE] = {
	-- dest cannot be within source
	notify: REF MovingNodes Change;
	newParent, moveParent, movePrev, moveAfter: Ref;
	IF InsideSpan[dest,moveFirst,moveLast] THEN ERROR BadMove;
	[moveParent,movePrev,moveAfter] ← Relatives[moveFirst,moveLast];
	notify ← NEW [MovingNodes Change ←
			[MovingNodes[dest, moveFirst, moveLast, child]]];
	newParent ← IF child THEN dest ELSE nodeI.Parent[dest];
	Notify[newParent,moveParent,notify,before];
	Del[moveParent,movePrev,moveAfter];
	InsertSpan[dest,moveFirst,moveLast,child];
	Notify[newParent,moveParent,notify,after] };

BadTranspose: PUBLIC ERROR = CODE;
TransposeNodes: PUBLIC PROC [alphaFirst, alphaLast, betaFirst, betaLast: Ref] = {
	-- alpha and beta must not overlap
	alphaParent, alphaPrev, alphaAfter, betaParent, betaPrev, betaAfter: Ref;
	notify: REF TransposingNodes Change;
	IF OverlappingSpans[alphaFirst,alphaLast,betaFirst,betaLast] THEN ERROR BadTranspose;
	[alphaParent,alphaPrev,alphaAfter] ← Relatives[alphaFirst,alphaLast];
	[betaParent,betaPrev,betaAfter] ← Relatives[betaFirst,betaLast];
	notify ← NEW [TransposingNodes Change ←
			[TransposingNodes[alphaFirst, alphaLast, betaFirst, betaLast]]];
	Notify[alphaParent,betaParent,notify,before];
	IF alphaAfter=betaFirst THEN { -- move alpha after beta
		Del[alphaParent,alphaPrev,alphaAfter];
		InsertSpan[betaLast,alphaFirst,alphaLast,FALSE] }
	ELSE IF betaAfter=alphaFirst THEN { -- move beta after alpha
		Del[betaParent,betaPrev,betaAfter];
		InsertSpan[alphaLast,betaFirst,betaLast,FALSE] }
	ELSE { -- move both
		Del[alphaParent,alphaPrev,alphaAfter];
		Del[betaParent,betaPrev,betaAfter];
		IF alphaPrev # NIL THEN InsertSpan[alphaPrev,betaFirst,betaLast,FALSE]
		ELSE InsertSpan[alphaParent,betaFirst,betaLast,TRUE];
		IF betaPrev # NIL THEN InsertSpan[betaPrev,alphaFirst,alphaLast,FALSE]
		ELSE InsertSpan[betaParent,alphaFirst,alphaLast,TRUE] };
	Notify[alphaParent,betaParent,notify,after] };

InsertTextNode: PUBLIC PROC [dest: Ref, inherit, child: BOOLEAN ← TRUE]
	RETURNS [new: RefTextNode] = {
	newParent: Ref;
	notify: REF InsertingTextNode Change;
	new ← CreateTextNode[];
	IF inherit THEN Inherit[dest,new];
	notify ← NEW [InsertingTextNode Change ←
			[InsertingTextNode[dest, inherit, child, new]]];
	newParent ← IF child THEN dest ELSE nodeI.Parent[dest];
	Notify[newParent,NIL,notify,before];
	InsertSpan[dest,new,new,child];
	Notify[newParent,NIL,notify,after] };

InsertOtherNode: PUBLIC PROC [dest: Ref, inherit, child: BOOLEAN ← TRUE]
	RETURNS [new: RefOtherNode] = {
	newParent: Ref;
	notify: REF InsertingOtherNode Change;
	new ← CreateOtherNode[];
	IF inherit THEN Inherit[dest,new];
	notify ← NEW [InsertingOtherNode Change ←
			[InsertingOtherNode[dest, inherit, child, new]]];
	newParent ← IF child THEN dest ELSE nodeI.Parent[dest];
	Notify[newParent,NIL,notify,before];
	InsertSpan[dest,new,new,child];
	Notify[newParent,NIL,notify,after] };

SplitNode: PUBLIC PROC [node: RefTextNode, textLoc: Offset, inherit, child: BOOLEAN ← TRUE] = {
	new: RefTextNode ← InsertTextNode[node,inherit,child];
	[] ← editI.MoveText[new,0,node,textLoc] };

MergeNodes: PUBLIC PROC [node: RefTextNode] = {
	-- merge node and its next sibling
	-- sibling must also be a text node
	-- node must be terminal
	-- copies text of node to start of sibling, then deletes node
	sibling: Ref;
	merge: RefTextNode;
	IF node.child # NIL THEN RETURN;
	IF (sibling ← nodeI.Next[node])=NIL THEN RETURN;
	IF (merge ← nodeI.NarrowToTextNode[sibling])=NIL THEN RETURN;
	[] ← editI.CopyText[merge,0,node];
	DeleteNode[node] };
	
-- **** Support routines for editing operations

Inherit: PROC [old, new: Ref] = INLINE {
	CopyProp: PROC [name: ATOM, value: REF] RETURNS [BOOLEAN] = {
		newvalue: REF;
		IF (newvalue ← propsI.CopyInfo[name,value]) # NIL THEN
			propsI.PutProp[new,name,newvalue];
		RETURN [FALSE] };
	new.typename ← old.typename;
	new.hasstyle ← old.hasstyle;
	IF old.props # NIL THEN [] ← propsI.MapProps[old,CopyProp] };

InsertSpan: PROC [dest, first, last: Ref, child: BOOLEAN] = {
	IF first=NIL THEN RETURN;
	IF child THEN { -- insert as first children of dest
		IF dest.child # NIL THEN { last.next ← dest.child; last.last ← FALSE }
		ELSE { last.next ← dest; last.last ← TRUE };
		dest.child ← first }
	ELSE { -- insert as next sibling of dest
		last.next ← dest.next; last.last ← dest.last;
		dest.last ← FALSE; dest.next ← first }};	

CopySpan: PUBLIC PROC [sourceFirst, sourceLast: Ref] RETURNS [first, last: Ref] = {
	node, topnode, child, new, prev, parent: Ref;
	IF (topnode ← node ← sourceFirst)=NIL THEN RETURN;
	DO	-- create new node each time through the loop
		WITH n:node SELECT FROM
			text => { 
				txt: RefTextNode;
				new ← txt ← nodeI.qZone.NEW[nodeI.TextBody];
				txt.rope ← n.rope; txt.runs ← n.runs };
			other => {
				othr: RefOtherNode;
				new ← othr ← nodeI.qZone.NEW[nodeI.OtherBody];
				othr.variety ← n.variety;
				othr.info ← otherI.CopyInfo[@n] };
			ENDCASE => ERROR;
		Inherit[node,new];
		-- insert new
		IF prev#NIL THEN prev.next ← new
		ELSE IF parent#NIL THEN parent.child ← new;
		-- go to next one
		IF (child ← node.child) # NIL THEN { -- descend in the tree
			node ← child; new.next ← parent; parent ← new; prev ← NIL }
		ELSE DO -- move to next node, sibling or up* then sibling
			IF node=topnode THEN {
				IF first=NIL THEN first ← new;
				IF topnode=sourceLast THEN { last ← new; RETURN };
				topnode ← node ← topnode.next; prev ← new; EXIT }; 
			IF ~node.last THEN { node ← node.next; prev ← new; EXIT };
			new.last ← TRUE; prev ← parent; parent ← parent.next;
			node ← node.next;
			ENDLOOP;
		ENDLOOP };

Relatives: PUBLIC PROC [destFirst, destLast:Ref] RETURNS [destParent, destPrev, destAfter:Ref] = {
	OPEN nodeI;
	nx: Ref;
	destAfter ← Next[destLast];
	destParent ← Parent[destAfter];
	IF (destPrev ← FirstChild[destParent])=destFirst THEN destPrev ← NIL
	ELSE DO IF (nx←destPrev.next)=destFirst THEN RETURN; destPrev ← nx; ENDLOOP };

InsideSpan: PUBLIC PROC [node,first,last: Ref] RETURNS [inside: BOOLEAN] = {
	-- returns true if node is inside the span of branches [first..last]
	spanParent: Ref ← nodeI.Parent[first];
	nodeParent: Ref;
	DO	IF node=NIL THEN RETURN [FALSE];
		IF (nodeParent ← nodeI.Parent[node]) = spanParent THEN
			RETURN [InsideSiblings[node,first,last]];
		node ← nodeParent;
		ENDLOOP };

InsideSiblings: PUBLIC PROC [node,first,last: Ref] RETURNS [inside: BOOLEAN] = {
	FOR n:Ref ← first, n.next DO
		SELECT n FROM
			node => RETURN [TRUE];
			last => EXIT;
			ENDCASE;
		ENDLOOP;
	RETURN [FALSE] };

OverlappingSpans: PUBLIC PROC [alphaFirst, alphaLast, betaFirst, betaLast: Ref]
	RETURNS [overlap: BOOLEAN] = {
	-- returns true if branches [alphaFirst..alphaLast] overlap [betaFirst..betaLast]
	RETURN [
	IF nodeI.Parent[alphaFirst] = nodeI.Parent[betaFirst] THEN
		InsideSiblings[alphaFirst,betaFirst,betaLast] OR
			InsideSiblings[betaFirst,alphaFirst,alphaLast]
	ELSE InsideSpan[alphaFirst,betaFirst,betaLast] OR
		InsideSpan[betaFirst,alphaFirst,alphaLast]] };

Rep: PROC [destParent,destPrev,destAfter,first,last:Ref] = {
	IF destPrev # NIL THEN { destPrev.last ← FALSE; destPrev.next ← first }
	ELSE destParent.child ← first;
	IF destAfter # NIL THEN { last.last ← FALSE; last.next ← destAfter }
	ELSE { last.last ← TRUE; last.next ← destParent }};

Del: PROC [destParent,destPrev,destAfter:Ref] = {
	IF destPrev # NIL THEN
		IF destAfter # NIL THEN destPrev.next ← destAfter
		ELSE { destPrev.last ← TRUE; destPrev.next ← destParent }
	ELSE destParent.child ← destAfter };

	
-- **** Operations for creating nodes ****

CreateTextNode: PUBLIC PROC RETURNS [RefTextNode] = { RETURN [nodeI.qZone.NEW[nodeI.TextBody]] };
	
CreateOtherNode: PUBLIC PROC RETURNS [RefOtherNode] = { RETURN [nodeI.qZone.NEW[nodeI.OtherBody]] };


-- ***** Initialization

Start: PUBLIC PROC = { -- for initialization only
	};

END.