-- RopeReaderMiscImpl.mesa
-- written by Bill Paxton,  January 1981
-- last edit by Bill Paxton, December 22, 1981 9:41 am

DIRECTORY
	RopeReader,
	RopeFrom,
	Rope,
	RopeInline,
	Space,
	Process,
	RTTypesBasic;

RopeReaderMiscImpl: MONITOR
   IMPORTS RopeReader, Rope, RopeInline, RopeFrom,
		Space, RTTypesBasic, Process
   EXPORTS RopeReader
   SHARES RopeReader, Rope =
   
BEGIN OPEN RopeReader, RopeInline;

EqSubstrs: PUBLIC PROC [r1,r2: ROPE, start1,start2,len: Offset, rdr1,rdr2: Ref ← NIL]
	RETURNS [eq: BOOLEAN] = {
	-- uses readers rdr1 and rdr2 to read ropes r1 and r2 to test for equality
	-- returns TRUE if r1 is same as len chars of r2 starting at start
	free1, free2: BOOLEAN ← FALSE;
	size1: Offset ← InlineSize[r1];
	size2: Offset ← InlineSize[r2];
	start1 ← MIN[start1,size1];
	start2 ← MIN[start2,size2];
	IF len=MaxLen THEN { IF (len ← size1-start1) # size2-start2 THEN RETURN [FALSE] }
	ELSE IF start1+len > size1 THEN RETURN [FALSE]
	ELSE IF start2+len > size2 THEN RETURN [FALSE];
	IF rdr1 = NIL THEN { rdr1 ← GetRopeReader[]; free1 ← TRUE };
	IF rdr2 = NIL THEN { rdr2 ← GetRopeReader[]; free2 ← TRUE };
	SetPosition[rdr1,r1,start1];
	SetPosition[rdr2,r2,start2];
	eq ← TRUE;
	WHILE len > 0 DO
		num: NAT ← Short[MIN[len,LAST[NAT]]]; -- loop on NAT instead of Offset
		len ← len-num;
		THROUGH [0..num) DO
			IF Get[rdr1]#Get[rdr2] THEN { eq ← FALSE; GOTO Finis };
			ENDLOOP;
		REPEAT Finis => NULL;
		ENDLOOP;
	IF free1 THEN FreeRopeReader[rdr1];
	IF free2 THEN FreeRopeReader[rdr2] };

CompareSubstrs: PUBLIC PROC [
	r1, r2: ROPE, start1, len1, start2, len2: Offset,
	rdr1, rdr2: Ref ← NIL, case: BOOLEAN ← TRUE]
	RETURNS [result:INTEGER] = {
	-- uses readers rdr1 and rdr2 to compare ropes r1 and r2
	-- returns -1 for r1 < r2; 0 for r1 = r2; and +1 for r1 > r2
	-- if ~case then all characters forced lowercase for comparison
	Lower: PROC [c: CHARACTER] RETURNS [CHARACTER] = INLINE {
		RETURN [IF c ~IN ['A..'Z] THEN c ELSE
			LOOPHOLE[LOOPHOLE[c,CARDINAL]+40B,CHARACTER]] };
	size1: Offset ← InlineSize[r1];
	size2: Offset ← InlineSize[r2];
	rem, rem1, rem2: Offset;
	free1, free2: BOOLEAN ← FALSE;
	rem1 ← IF start1 > size1 THEN 0 ELSE size1-start1;
	rem2 ← IF start2 > size2 THEN 0 ELSE size2-start2;
	IF rdr1 = NIL THEN { rdr1 ← GetRopeReader[]; free1 ← TRUE };
	IF rdr2 = NIL THEN { rdr2 ← GetRopeReader[]; free2 ← TRUE };
	len1 ← MIN[len1,rem1]; len2 ← MIN[len2,rem2]; rem ← MIN[len1,len2];
	SetPosition[rdr1,r1,start1];
	SetPosition[rdr2,r2,start2];
	result ← 0;
	WHILE rem > 0 DO
		num: NAT ← Short[MIN[rem,LAST[NAT]]];
		rem ← rem-num;
		THROUGH [0..num) DO
			c1: CHARACTER ← Get[rdr1];
			c2: CHARACTER ← Get[rdr2];
			IF ~case THEN { c1 ← Lower[c1]; c2 ← Lower[c2] };
			SELECT c1 FROM
				< c2 => { result ← -1; GOTO Finis };
				> c2 => { result ← 1; GOTO Finis };
				ENDCASE;
			ENDLOOP;
		REPEAT Finis => NULL;
		ENDLOOP;
	IF free1 THEN FreeRopeReader[rdr1];
	IF free2 THEN FreeRopeReader[rdr2];
	RETURN [
	IF result # 0 THEN result ELSE SELECT TRUE FROM
		len1 < len2 => -1,
		len1 > len2 => 1,
		ENDCASE => 0] };

-- implementation of ropes using character arrays

CList: TYPE = REF CListBody;
CListBody: TYPE = RECORD [chars: Chars, space: Space.Handle, next: CList];
charsList: CList ← NIL;

CharsRope: PUBLIC ENTRY PROC [
	chars: Chars, space: Space.Handle ← Space.nullHandle]
	RETURNS [ROPE] = {
	FOR lst:CList ← charsList, lst.next UNTIL lst=NIL DO
		IF lst.chars = chars THEN {
			IF lst.space = Space.nullHandle THEN lst.space ← space
			ELSE IF space # Space.nullHandle THEN ERROR;
			EXIT };
		REPEAT FINISHED => charsList ← RopeFrom.pZone.NEW[CListBody ← [chars,space,charsList]];
		ENDLOOP;
	RETURN [RopeFrom.qZone.NEW[Tobject ← [node[object[
			charsPerArray,LOOPHOLE[chars],CharsFetch,CharsMap,NIL]]]]] };

CharsFinalizer: PROC [charsFQ: RTTypesBasic.FinalizationQueue] = {
	DO	chars: REF CharsArray = NARROW[RTTypesBasic.FQNext[charsFQ]];
		space: Space.Handle = RemoveFromCList[chars];
		IF space # Space.nullHandle THEN {
			Space.Unmap[space]; Space.Map[space, Space.defaultWindow] };
		ENDLOOP };

RemoveFromCList: ENTRY PROC [chars: Chars] RETURNS [space: Space.Handle] = {
	lst, prev: CList;
	IF (lst←charsList)=NIL THEN RETURN [Space.nullHandle];
	IF lst.chars = chars THEN {
		lst.chars ← NIL; charsList ← lst.next; RETURN [lst.space] };
	DO	prev ← lst;
		IF (lst ← lst.next)=NIL THEN RETURN [Space.nullHandle];
		IF lst.chars = chars THEN {
			lst.chars ← NIL; prev.next ← lst.next; RETURN [lst.space] };
		ENDLOOP };

CharsFetch: PROC [ref: REF, index: Offset] RETURNS [c:CHAR] = {
	WITH ref SELECT FROM
		x: Chars => RETURN[x[Short[index]]];
		ENDCASE => ERROR Rope.NoRope };

CharsMap: PROC
	[base: REF, start,len: Offset, action: PROC [CHAR] RETURNS [BOOLEAN]]
	RETURNS [BOOLEAN] = {
	WITH base SELECT FROM
		x: Chars => {
			st: NAT ← Short[start];
			FOR i: NAT IN [st..st+Short[len]) DO
				IF action[x[i]] THEN RETURN [TRUE];
				ENDLOOP };
		ENDCASE => ERROR Rope.NoRope;
	RETURN [FALSE] };


-- ***** rope reader cache

Create: PUBLIC PROC RETURNS [Ref] = { RETURN[RopeFrom.pZone.NEW[Body]] };

roperdr1, roperdr2, roperdr3: Ref; -- shared rope readers

GetRopeReader: PUBLIC ENTRY PROC RETURNS [reader: Ref] = {
	IF roperdr3 # NIL THEN { reader ← roperdr3; roperdr3 ← NIL }
	ELSE IF roperdr2 # NIL THEN { reader ← roperdr2; roperdr2 ← NIL }
	ELSE IF roperdr1 # NIL THEN { reader ← roperdr1; roperdr1 ← NIL }
	ELSE reader ← Create[] };

FreeRopeReader: PUBLIC ENTRY PROC [reader: Ref] = {
	SetPosition[reader, NIL];
	reader.charForEndOfRope ← FALSE;
	IF roperdr3 = reader OR roperdr2 = reader OR roperdr1 = reader THEN ERROR;
	IF roperdr3 = NIL THEN roperdr3 ← reader
	ELSE IF roperdr2 = NIL THEN roperdr2 ← reader
	ELSE IF roperdr1 = NIL THEN roperdr1 ← reader };


-- ***** Initialization

charsFQ: RTTypesBasic.FinalizationQueue = RTTypesBasic.NewFQ[]; -- for CharsArrays

StartRopeReaderMisc: PUBLIC PROC = {
	RTTypesBasic.EstablishFinalization[CODE[CharsArray],1,charsFQ];
	Process.Detach[FORK CharsFinalizer[charsFQ]]};

END.