-- RopeEditReplaceImpl.mesa
-- written by Bill Paxton, February 1981
-- last edit by Bill Paxton, December 22, 1981 10:23 am

DIRECTORY
RopeEdit,
RopeFrom,
Rope,
RopeInline;

RopeEditReplaceImpl: PROGRAM
	IMPORTS RopeEdit, RopeInline, RopeFrom
	EXPORTS RopeEdit
	SHARES Rope =
BEGIN
OPEN RopeEdit, RopeInline;
	
FlatMax: Offset = 30; -- if shorter, copy to flat rope


-- Edit 

ReplaceByChar: PUBLIC PROC [
	base: ROPE, char: CHAR,
	start: Offset ← 0, len, baseSize: Offset ← MaxLen]
	RETURNS [new: ROPE] = {
	oldPos, newPos, size, xsize: Offset;
	replace: ROPE;
	IF baseSize=MaxLen THEN baseSize ← RopeInline.InlineSize[base];
	IF start > baseSize THEN start ← baseSize;
	len ← MIN[len,baseSize-start];
	IF (new ← RopeFrom.TryAppendReplaceByChar[base,char,start,len,baseSize]) # NIL
		THEN RETURN;
	IF (size ← baseSize+1-len) <= FlatMax THEN RETURN [
		RopeFrom.FlatReplaceByChar[base,char,start,len,baseSize,FALSE]];
	oldPos ← start+len;
	newPos ← start+1;
	IF base # NIL THEN WITH x:base SELECT FROM
	  node => WITH x:x SELECT FROM
		 replace => {
			xnewPos: Offset ← x.newPos;
			xstart: Offset ← x.start;
			xsize ← xnewPos-xstart;
			IF start = xnewPos THEN { -- appending to the replacement
				ok: BOOLEAN ← FALSE;
				IF (new ← RopeFrom.TryFlatAppendChar[x.replace, char, xsize]) # NIL
					THEN { replace ← new; ok ← TRUE }
				ELSE IF xsize < FlatMax THEN {
					replace ← RopeFrom.FlatAppendChar[x.replace, char, xsize, FALSE];
					ok ← TRUE };
				IF ok THEN {
					start ← xstart; oldPos ← x.oldPos+len;
					newPos ← start+xsize+1;
					base ← x.base }}};
		 concat => {
			xpos: Offset ← x.pos;
			IF start=xpos AND len=0 THEN {
				ok: BOOLEAN ← FALSE;
				IF (new ← RopeFrom.TryFlatAppendChar[x.base, char, xpos]) # NIL THEN
					ok ← TRUE
				ELSE IF xpos < FlatMax THEN {
					new ← RopeFrom.FlatAppendChar[x.base, char, xpos, FALSE];
					ok ← TRUE };
				IF ok THEN RETURN [
					RopeFrom.qZone.NEW[Tconcat ← [node[concat[size,new,x.rest,xpos+1,
						1+MAX[Depth[new],Depth[x.rest]]]]]]] }};
		 ENDCASE;
	  ENDCASE;
	IF replace=NIL THEN replace ← RopeFrom.Character[char];
	new ← RopeFrom.qZone.NEW[Treplace ← [node[replace[size,base,replace,start,oldPos,newPos,
		1+MAX[Depth[base],Depth[replace]]]]]]};

ReplaceByString: PUBLIC PROC [
	base: ROPE, string: REF READONLY TEXT,
	stringStart: NAT ← 0, stringNum: NAT ← MaxNat,
	start: Offset ← 0, len, baseSize: Offset ← MaxLen]
	RETURNS [new: ROPE] = {
	oldPos, newPos, size, xsize: Offset;
	replace: ROPE;
	IF baseSize=MaxLen THEN baseSize ← RopeInline.InlineSize[base];
	IF start > baseSize THEN start ← baseSize;
	len ← MIN[len,baseSize-start];
	IF stringNum=MaxNat THEN {
		stringSize: NAT ← IF string=NIL THEN 0 ELSE string.length;
		IF stringStart >= stringSize THEN
			RETURN [Delete[base,start,len,baseSize]];
		stringNum ← stringSize-stringStart };
	IF (new ← RopeFrom.TryAppendReplaceByString[
		base,string,stringStart,stringNum,start,len,baseSize]) # NIL
		THEN RETURN [new];
	IF (size ← baseSize+stringNum-len) <= FlatMax THEN RETURN [
		RopeFrom.FlatReplaceByString[
			base,string,stringStart,stringNum,start,len,baseSize,FALSE]];
	oldPos ← start+len;
	newPos ← start+stringNum;
	IF base # NIL THEN WITH x:base SELECT FROM
	  node => WITH x:x SELECT FROM
		replace => {
			xnewPos: Offset ← x.newPos;
			xstart: Offset ← x.start;
			IF start = xnewPos THEN { -- appending to the replacement
				ok: BOOLEAN ← FALSE;
				xsize ← xnewPos-xstart;
				IF (new ← RopeFrom.TryFlatAppendString[x.replace,
					string,stringStart,stringNum,xsize]) # NIL THEN {
					replace ← new; ok ← TRUE}	
				ELSE IF xsize+stringNum <= FlatMax THEN {
					replace ← RopeFrom.FlatAppendString[x.replace,
						string,stringStart,stringNum,xsize];
					ok ← TRUE };
				IF ok THEN {
					start ← xstart; oldPos ← x.oldPos+len;
					newPos ← start+xsize+stringNum;
					base ← x.base}}};
		concat => {
			xpos: Offset ← x.pos;
			IF start=xpos AND len=0 THEN {
				ok: BOOLEAN ← FALSE;
				IF (new ← RopeFrom.TryFlatAppendString[x.base, 
					string,stringStart,stringNum,xpos]) # NIL THEN ok ← TRUE
				ELSE IF xpos+stringNum <= FlatMax THEN {
					new ← RopeFrom.FlatAppendString[x.base, 
						string,stringStart,stringNum,xpos,FALSE];
					ok ← TRUE };
				IF ok THEN RETURN [
					RopeFrom.qZone.NEW[Tconcat ← [node[concat[size,new,x.rest,xpos+stringNum,
						1+MAX[Depth[new],Depth[x.rest]]]]]]] }};
		ENDCASE;
	  ENDCASE;
	IF replace=NIL THEN
		replace ← RopeFrom.String[string,stringStart,stringNum];
	new ← RopeFrom.qZone.NEW[Treplace ← [node[replace[size,base,replace,start,oldPos,newPos,
		1+MAX[Depth[base],Depth[replace]]]]]]};

Replace: PUBLIC PROC [
	base: ROPE, start: Offset ← 0, len: Offset ← MaxLen, replace: ROPE ← NIL,
	baseSize, repSize: Offset ← MaxLen]
	RETURNS [new: ROPE] = {
	size, oldPos, newPos, xsize: Offset;
	IF baseSize=MaxLen THEN baseSize ← RopeInline.InlineSize[base];
	IF start >= baseSize THEN
		RETURN [Concat[base,replace,baseSize,repSize]];
	IF len=MaxLen THEN len ← MIN[len,baseSize-start];
	IF len=0 AND replace=NIL THEN RETURN[base];
	IF repSize=MaxLen THEN repSize ← RopeInline.InlineSize[replace];
	size ← baseSize-len+repSize;
	IF size <= FlatMax THEN RETURN [
		RopeFrom.FlatReplace[base,start,len,replace,size,baseSize,repSize]];
	oldPos ← start+len;
	newPos ← start+repSize;
	WHILE base # NIL DO WITH x:base SELECT FROM
	  node => WITH x:x SELECT FROM
		replace => {
			xnewPos: Offset ← x.newPos;
			xstart: Offset ← x.start;
			IF start <= xstart AND oldPos >= xnewPos THEN {
				-- replacing the replacement
				oldPos ← x.oldPos+(oldPos-xnewPos); len ← oldPos-start;
				base ← x.base; LOOP}
			ELSE IF repSize = 0 AND start > xstart AND oldPos = xnewPos
				-- deleting replacement end
				AND (xsize←start-xstart) <= FlatMax THEN {
				replace ← RopeFrom.FlatSubstr[x.replace,0,xsize];
				newPos ← start; oldPos ← x.oldPos;
				start ← xstart; base ← x.base}
			ELSE IF repSize = 0 AND start = xstart AND oldPos < xnewPos
				-- deleting start
				AND (xsize←xnewPos-oldPos) <= FlatMax THEN {
				replace ← RopeFrom.FlatSubstr[x.replace,len,xsize];
				newPos ← start+xsize; oldPos ← x.oldPos; base ← x.base}
			ELSE IF start = xnewPos THEN {
				ok: BOOLEAN ← FALSE;
				xsize ← xnewPos-xstart;
				IF repSize <= FlatMax AND
					(new ← RopeFrom.TryAppendConcat[x.replace,replace,xsize,repSize]) # NIL
					THEN ok ← TRUE
				ELSE IF xsize+repSize <= FlatMax THEN {
					new ← RopeFrom.FlatConcat[x.replace,replace,xsize,repSize,FALSE];
					ok ← TRUE };
				IF ok THEN {
					replace ← new; new ← NIL;
					start ← xstart; len ← len+x.oldPos-xstart;
					oldPos ← start+len;
					repSize ← xsize+repSize; newPos ← start+repSize;
					base ← x.base; LOOP }}
			ELSE IF start+len = xstart AND (xsize←xnewPos-xstart)+repSize <= FlatMax THEN {
				-- replacing just before	
				replace ← RopeFrom.FlatConcat[replace,x.replace,repSize,xsize];
				len ← len+x.oldPos-xstart; oldPos ← start+len;
				repSize ← xsize+repSize; newPos ← start+repSize;
				base ← x.base; LOOP }};
		concat => {
			xpos: Offset ← x.pos;
			IF start=xpos AND len=0 THEN { -- insert between base&rest
				partSize: Offset;
				ok: BOOLEAN ← FALSE;
				-- first try flat concat of x.base&replacement
				IF repSize <= FlatMax AND
					(new ← RopeFrom.TryAppendConcat[x.base,replace,xpos,repSize]) # NIL
					THEN ok ← TRUE
				ELSE IF (partSize←xpos+repSize) <= FlatMax THEN {
					new ← RopeFrom.FlatConcat[x.base,replace,xpos,repSize,FALSE];
					ok ← TRUE };
				IF ok THEN RETURN [
					RopeFrom.qZone.NEW[Tconcat ← [node[concat[size,new,x.rest,partSize,
						1+MAX[Depth[new],Depth[x.rest]]]]]]];
				-- otherwise try concat of replacement&x.rest
				IF (partSize←x.size-xpos+repSize) <= FlatMax THEN {
					new ← RopeFrom.FlatConcat[replace,x.rest,repSize,x.size-xpos];
					RETURN [RopeFrom.qZone.NEW[Tconcat ← [node[concat[size,x.base,
						new,xpos,1+MAX[Depth[new],Depth[x.rest]]]]]]]};
				}};
		ENDCASE;
	  ENDCASE;
	  EXIT;
	  ENDLOOP;
	IF base=NIL THEN RETURN [replace];
	new ← RopeFrom.qZone.NEW[Treplace ← [node[replace[size,base,replace,start,oldPos,newPos,
		1+MAX[Depth[base],Depth[replace]]]]]]};
  
END.