-- 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.