-- RopeFromEditImpl.Mesa
-- written by Bill Paxton,  February 1981
-- last edit by Bill Paxton, December 22, 1981 9:51 am

DIRECTORY
	RopeFrom,
	RopeEdit,
	RopeEditingAlloc,
	RopeReader,
	Rope,
	RopeInline,
	File;

RopeFromEditImpl: MONITOR
   IMPORTS RopeInline, RopeFrom, RopeEdit, RopeEditingAlloc, RopeReader, Rope
   EXPORTS RopeFrom
   SHARES Rope =
BEGIN
OPEN RopeFrom, RopeInline;

CharsArray: TYPE = RopeReader.CharsArray;
Chars: TYPE = REF CharsArray;
charsPerArray: NAT = RopeReader.charsPerArray;

-- Editing Operations

FlatSubstr: PUBLIC PROC
	[rope: ROPE, start: Offset ← 0, len: Offset ← MaxLen] RETURNS [ROPE] = {
	chars: Chars;
	loc, num: NAT;
	base: ROPE;
	substr: BOOLEAN ← FALSE;
	size: Offset ← RopeInline.InlineSize[rope];
	reader: RopeReader.Ref;
	IF len=MaxLen THEN {
		IF start >= size THEN RETURN [NIL];
		len ← MIN[len,size-start] };
	IF len=0 OR rope=NIL THEN RETURN [NIL];
	IF len > charsPerArray THEN { -- split into balanced parts
		half: Offset ← len/2;
		front: ROPE ← FlatSubstr[rope, start, half];
		back: ROPE ← FlatSubstr[rope, start+half, len-half];
		RETURN [qZone.NEW[Tconcat ← [node[concat[len,front,back,half,
			1+MAX[RopeEdit.Depth[front],RopeEdit.Depth[back]]]]]]] };
	WITH x:rope SELECT FROM
	    node => WITH x:x SELECT FROM
	  	substr => substr ← TRUE;
		object => IF x.size=charsPerArray THEN
			WITH x.base SELECT FROM
				z: Chars => -- don't need to move the characters
					RETURN [qZone.NEW[Tsubstr ←
						[node[substr[len,rope,start,1+RopeEdit.Depth[rope]]]]]];
				ENDCASE;
		ENDCASE; ENDCASE;
	[chars,loc,base] ← RopeEditingAlloc.AllocChars[num ← Short[len]];
	reader ← RopeReader.GetRopeReader[];
	RopeReader.SetPosition[reader, rope, start];
	IF RopeReader.GetChars[reader, chars, num, loc] # num THEN ERROR;
	RopeReader.FreeRopeReader[reader];
	IF substr AND start=0 AND len=size THEN -- just flattening an existing substr
	  WITH x:rope SELECT FROM
	     node => WITH x:x SELECT FROM
	  	substr => { x.base ← base; x.start ← loc; RETURN [@x] };
	     ENDCASE; ENDCASE;
	RETURN [qZone.NEW[Tsubstr ←
		[node[substr[len,base,loc,1+RopeEdit.Depth[base]]]]]]};

FlatConcat: PUBLIC PROC
	[base, rest: ROPE, baseSize, restSize: Offset ← MaxLen, tryAppend: BOOLEAN ← TRUE]
	RETURNS [new: ROPE] = {
	chars: Chars;
	loc, baseNum, restNum: NAT;
	reader: RopeReader.Ref;
	charsRope: ROPE;
	size: Offset;
	IF baseSize=MaxLen THEN baseSize ← RopeInline.InlineSize[base];
	IF restSize=MaxLen THEN restSize ← RopeInline.InlineSize[rest];
	IF (size ← baseSize+restSize) > charsPerArray THEN -- treat separately
		RETURN [qZone.NEW[Tconcat ← [node[concat[size,base,rest,baseSize,
			1+MAX[RopeEdit.Depth[base],RopeEdit.Depth[rest]]]]]]];
	IF size=0 THEN RETURN[NIL];
	IF tryAppend AND (new ← TryAppendConcat[base, rest, baseSize, restSize]) # NIL
		THEN RETURN;
	baseNum ← Short[baseSize];
	restNum ← Short[restSize];
	[chars, loc, charsRope] ← RopeEditingAlloc.AllocChars[Short[size]];
	reader ← RopeReader.GetRopeReader[];
	RopeReader.SetPosition[reader, base];
	IF RopeReader.GetChars[reader, chars, baseNum, loc] # baseNum THEN ERROR;
	RopeReader.SetPosition[reader, rest];
	IF RopeReader.GetChars[reader, chars, restNum, loc+baseNum] # restNum THEN ERROR;
	RopeReader.FreeRopeReader[reader];
	RETURN [qZone.NEW[Tsubstr ← [node[substr[size,charsRope,loc,1+RopeEdit.Depth[charsRope]]]]]]};

TryAppendConcat: PUBLIC PROC [base, rest: ROPE, baseSize, restSize: Offset ← MaxLen]
	RETURNS [ROPE] = {
	chars: Chars;
	size: Offset;
	IF baseSize=MaxLen THEN baseSize ← RopeInline.InlineSize[base];
	IF restSize=MaxLen THEN restSize ← RopeInline.InlineSize[rest];
	IF (size ← baseSize+restSize) > charsPerArray THEN -- treat separately
		RETURN [qZone.NEW[Tconcat ← [node[concat[size,base,rest,baseSize,
			1+MAX[RopeEdit.Depth[base],RopeEdit.Depth[rest]]]]]]];
	IF size=0 THEN RETURN[NIL];
	IF base#NIL AND rest#NIL THEN WITH--1-- x:base SELECT FROM node => WITH--2-- x:x SELECT FROM
		substr => WITH--3-- z:x.base SELECT FROM node => WITH--4-- z:z SELECT FROM
		   object => IF z.size=charsPerArray THEN WITH--5-- z.base SELECT FROM
		      w: Chars => { -- base is a substr of a charsarray
		         WITH--6-- y:rest SELECT FROM node => WITH--7-- y:y SELECT FROM
			    substr => IF x.base=y.base AND x.start+x.size=y.start THEN
				WITH--8-- z:x.base SELECT FROM node => WITH--9-- z:z SELECT FROM
					object => IF z.size=charsPerArray THEN
						WITH--10-- z.base SELECT FROM
							w: Chars => -- don't need to move the characters
							RETURN [qZone.NEW[Tsubstr ←
								[node[substr[x.size+y.size,x.base,x.start,
									1+RopeEdit.Depth[x.base]]]]]];
							ENDCASE; ENDCASE; ENDCASE; ENDCASE; ENDCASE; --6..10--
		         { -- try to allocate room adjacent to base
			 ok: BOOLEAN;
			 loc: NAT;
			 newbase: ROPE ← x.base;
			 xstart: Offset ← x.start;
			 count: NAT ← Short[restSize];
			 baseNum: NAT ← Short[baseSize];
			 [ok,chars] ← RopeEditingAlloc.TryAllocAdjacent[newbase,
				loc←baseNum+Short[xstart],count];
			 IF ok THEN { -- transfer the chars 
				reader: RopeReader.Ref ← RopeReader.GetRopeReader[];
				RopeReader.SetPosition[reader,rest];
				IF RopeReader.GetChars[reader,chars,count,loc] # count THEN ERROR;
				RopeReader.FreeRopeReader[reader];
				RETURN [qZone.NEW[Tsubstr ←
					[node[substr[size,newbase,xstart,1+RopeEdit.Depth[newbase]]]]]] }}};
			 ENDCASE; ENDCASE; ENDCASE; ENDCASE; ENDCASE; --1..5--
	RETURN [NIL] };
	
FlatReplace: PUBLIC PROC [
	base: ROPE, start: Offset ← 0, len: Offset ← MaxLen, replace: ROPE ← NIL,
	size, baseSize, repSize: Offset ← MaxLen]
		RETURNS [ROPE] = {
	chars: Chars;
	charsRope: ROPE;
	initloc, loc, strt, oldpos, repsize, tailsize, sze: NAT;
	reader: RopeReader.Ref;
	Get: PROC [r: ROPE, begin,count: NAT] = {
		IF count > 0 THEN {
			RopeReader.SetPosition[reader,r,begin];
			IF RopeReader.GetChars[reader,chars,count,loc] # count THEN ERROR;
			loc ← loc+count}};
	IF baseSize=MaxLen THEN baseSize ← RopeInline.InlineSize[base];
	IF start >= baseSize THEN
		RETURN [FlatConcat[base,replace,baseSize,repSize]];
	IF len=MaxLen THEN len ← MIN[len,baseSize-start];
	IF repSize=MaxLen THEN repSize ← RopeInline.InlineSize[replace];
	IF size=MaxLen THEN size ← baseSize-len+repSize;
	IF size=0 THEN RETURN [NIL];
	IF size > charsPerArray THEN -- treat separately
		RETURN [Rope.Replace[base, start, len, replace]];
	repsize ← Short[repSize];	
	tailsize ← Short[baseSize]-(oldpos←Short[len]+(strt←Short[start]));
	[chars,loc,charsRope] ← RopeEditingAlloc.AllocChars[sze←Short[size]];
	initloc ← loc;
	reader ← RopeReader.GetRopeReader[];
	Get[base,0,strt];
	Get[replace,0,repsize];
	Get[base,oldpos,tailsize];
	RopeReader.FreeRopeReader[reader];
	IF loc-initloc#sze THEN ERROR;
	RETURN [qZone.NEW[Tsubstr ← [node[substr[size,charsRope,initloc,1+RopeEdit.Depth[charsRope]]]]]]};

FlatCopy: PUBLIC PROC [
	dest: ROPE, destLoc: Offset ← 0,
	source: ROPE, start: Offset ← 0, len: Offset ← MaxLen,
	destSize: Offset ← MaxLen]
	RETURNS [ROPE] = {
	chars: Chars;
	charsRope: ROPE;
	size: Offset;
	initloc, loc, dst, sze: NAT;
	reader: RopeReader.Ref;
	Get: PROC [base: ROPE, begin, count: NAT] = {
		IF count > 0 THEN {
			RopeReader.SetPosition[reader,base,begin];
			IF RopeReader.GetChars[reader,chars,count,loc] # count THEN ERROR;
			loc ← loc+count}};
	IF len=MaxLen THEN {
		sourceSize: Offset ← RopeInline.InlineSize[source];
		IF start >= sourceSize THEN RETURN [dest];
		len ← MIN[len,sourceSize-start] };
	IF destSize=MaxLen THEN destSize ← RopeInline.InlineSize[dest];
	IF destLoc > destSize THEN destLoc ← destSize;
	IF (size←destSize+len) > charsPerArray THEN -- treat separately
		RETURN [FlatInsert[dest,destLoc,FlatSubstr[source,start,len],destSize,len]];
	IF size=0 THEN RETURN[NIL];
	[chars, loc, charsRope] ← RopeEditingAlloc.AllocChars[sze ← Short[size]];
	initloc ← loc;
	reader ← RopeReader.GetRopeReader[];
	Get[dest,0,dst←Short[destLoc]];
	Get[source,Short[start],Short[len]];
	Get[dest,dst,Short[destSize]-dst];
	RopeReader.FreeRopeReader[reader];
	IF loc-initloc # sze THEN ERROR;
	RETURN [qZone.NEW[Tsubstr ← [node[substr[size,charsRope,initloc,1+RopeEdit.Depth[charsRope]]]]]]};

FlatMove: PUBLIC PROC [
	base: ROPE, destLoc, start: Offset ← 0, len, baseSize: Offset ← MaxLen]
	RETURNS [ROPE] = {
	-- no-op if destLoc in [start..start+len]
	chars: Chars;
	charsRope: ROPE;
	initloc, loc, strt, dst, num, end, basesze: NAT;
	reader: RopeReader.Ref;
	Get: PROC [begin,count: NAT] = {
		IF count > 0 THEN {
			RopeReader.SetPosition[reader,base,begin];
			IF RopeReader.GetChars[reader,chars,count,loc] # count THEN ERROR;
			loc ← loc+count}};
	IF baseSize=MaxLen THEN baseSize ← RopeInline.InlineSize[base];
	IF baseSize=0 THEN RETURN[NIL];
	IF start > baseSize THEN start ← baseSize;
	IF len=MaxLen THEN len ← MIN[len,baseSize-start];
	IF destLoc IN [start..start+len] THEN RETURN[base];
	IF baseSize > charsPerArray THEN { -- treat separately
		moving: ROPE ← FlatSubstr[base, start, len];
		newbase: ROPE ← FlatDelete[base, start, len, baseSize];
		IF destLoc > start THEN destLoc ← destLoc-len;
		RETURN [FlatInsert[newbase, destLoc, moving, baseSize-len, len]]};
	dst ← Short[destLoc];
	end ← (strt ← Short[start]) + (num ← Short[len]);
	IF dst < end THEN { -- moving left
		-- same as moving [dst..strt) right to end
		temp: NAT ← dst; dst ← end; end ← strt; strt ← temp; num ← end-strt };
	[chars,loc,charsRope] ← RopeEditingAlloc.AllocChars[basesze←Short[baseSize]];
	initloc ← loc;
	reader ← RopeReader.GetRopeReader[];
	Get[0,strt];
	Get[end,dst-end];
	Get[strt,num];
	Get[dst,basesze-dst];
	RopeReader.FreeRopeReader[reader];
	IF loc-initloc # basesze THEN ERROR;
	RETURN [qZone.NEW[Tsubstr ← [node[substr[baseSize,charsRope,initloc,1+RopeEdit.Depth[charsRope]]]]]]};

FlatTranspose: PUBLIC PROC [
	base: ROPE, astart, alen, bstart, blen: Offset,
	baseSize: Offset ← MaxLen]
	RETURNS [ROPE] = {
	-- [astart..astart+alen) must not intersect [bstart..bstart+blen)
	chars: Chars;
	charsRope: ROPE;
	astrt, anum, bstrt, bnum, aend, bend, initloc, loc, sze: NAT;
	reader: RopeReader.Ref;
	Get: PROC [begin,count: NAT] = {
		IF count > 0 THEN {
			RopeReader.SetPosition[reader,base,begin];
			IF RopeReader.GetChars[reader,chars,count,loc] # count THEN ERROR;
			loc ← loc+count}};
	IF astart > bstart THEN { -- switch them
		start: Offset ← astart;
		len: Offset ← alen;
		astart ← bstart; bstart ← start;
		alen ← blen; blen ← len };
	IF baseSize=MaxLen THEN baseSize ← RopeInline.InlineSize[base];
	IF baseSize=0 THEN RETURN[NIL];
	IF baseSize > charsPerArray THEN { -- treat separately
		newbase: ROPE ← FlatMove[base, baseSize, bstart+blen, astart, alen];
		RETURN [FlatMove[newbase, baseSize, astart, bstart-alen, blen]]};
	aend ← (astrt ← Short[astart])+(anum ← Short[alen]);
	bend ← (bstrt ← Short[bstart])+(bnum ← Short[blen]);
	sze ← Short[baseSize];
	[chars, loc, charsRope] ← RopeEditingAlloc.AllocChars[sze];
	initloc ← loc;
	reader ← RopeReader.GetRopeReader[];
	Get[0,astrt];
	Get[bstrt,bnum];
	Get[aend,bstrt-aend];
	Get[astrt,anum];
	Get[bend,sze-bend];
	RopeReader.FreeRopeReader[reader];
	IF loc-initloc # sze THEN ERROR;
	RETURN [qZone.NEW[Tsubstr ← [node[substr[baseSize,charsRope,initloc,1+RopeEdit.Depth[charsRope]]]]]]};

-- ***** Initialization

StartRopeFromEdit: PUBLIC PROC = {
	};

END.