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