[Cyan]<Tioga2>Text>RunReaderImpl.mesa!1

RunReaderImpl.mesa; written by Bill Paxton, March 1981

edited by McGregor, February 8, 1983 11:38 am

edited by Bill Paxton, June 1, 1983 2:52 pm

edited by Maxwell, January 5, 1983 1:08 pm

DIRECTORY

RunReader,

TiogaLooks,

TiogaLooksOps,

TiogaLooksSupport,

TiogaNodeOps;

RunReaderImpl: CEDAR MONITOR

IMPORTS TiogaLooksSupport, TiogaLooksOps, RunReader

EXPORTS RunReader

SHARES RunReader, TiogaLooks =

BEGIN OPEN RunReader, TiogaLooks, TiogaLooksSupport;

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

GetIndex: PUBLIC PROC [reader: Ref] RETURNS [index: Offset] = {

base: Base;

offset: Offset;

IF reader.after = reader.current THEN RETURN [reader.index];

base ← reader.base;

offset ← IF reader.current=0 THEN base[reader.after-1].after

ELSE base[reader.after-1].after-base[reader.current-1].after;

RETURN [reader.index - offset] };

NoMoreRuns: PUBLIC ERROR = CODE;

ReadRun: PUBLIC PROC [reader: Ref, mode: Mode]

RETURNS [count: Offset, looks: Looks] = {

runs: Runs ← reader.runs;

index, current: Offset ← GetIndex[reader];

after: Offset ← TiogaLooksOps.Size[runs];

first: Offset ← 0;

remove, add: Looks ← noLooks;

SetIndx: PROC [index: Offset] = { reader.index ← index };

SetBaseInfo: PROC [current, first, after: NAT, base: Base] = {

reader.current ← current; reader.first ← first;

reader.after ← after; reader.base ← base };

ClearBaseInfo: PROC = { SetBaseInfo[0,0,0,NIL] };

SetLooksInfo: PROC = {

reader.remove ← remove; reader.add ← add;

reader.changeLooks ← remove # noLooks OR add # noLooks };

Modify: PROC [lks: Looks] RETURNS [Looks] = INLINE {

RETURN [TiogaLooksSupport.ModifyLooks[lks, remove, add]] };

SingleRun: PROC = {

ClearBaseInfo;

SELECT mode FROM

get => SetIndx[index + (count ← after-current)];

peek => count ← after-current;

backwards => SetIndx[index - (count ← current-first+1)];

peekbackwards => count ← current-first+1;

ENDCASE => ERROR};

IF runs=NIL THEN RETURN [LAST[NAT],noLooks];

SELECT mode FROM -- adjust current depending on direction

backwards, peekbackwards =>

IF current=0 THEN ERROR NoMoreRuns ELSE current ← current-1;

get, peek => NULL;

ENDCASE => ERROR;

IF current >= after THEN ERROR NoMoreRuns;

WHILE runs # NIL DO

TRUSTED {WITH x:runs SELECT FROM

base => {

len: Offset ← after-first;

firstRun, lastRun, afterRun, curRun: NAT; -- indexes into runs

startRuns, afterRuns, startCur: Offset;

[firstRun, lastRun] ← TiogaLooksSupport.FindBaseRuns[@x, first, len];

IF firstRun=lastRun THEN { -- treat as special case

SingleRun; RETURN [count, Modify[x[firstRun].looks]] };

IF (firstRun=0 AND first=0) OR

(firstRun>0 AND x[firstRun-1].after=first) THEN startRuns ← first

ELSE -- only included part of firstRun

IF current >= (startRuns ← x[firstRun].after) THEN

firstRun ← firstRun+1 -- current not in first run

ELSE { -- current is in the first run. must special case it.

IF x[lastRun].after=after THEN { -- include all of lastRun

afterRuns ← after; afterRun ← lastRun+1 }

ELSE { afterRuns ← x[lastRun-1].after; afterRun ← lastRun };

SELECT mode FROM

get => {

count ← startRuns-current;

IF afterRun > firstRun THEN {

SetBaseInfo[firstRun+1, firstRun+1, afterRun, @x];

SetIndx[index+afterRuns-current]; SetLooksInfo; }

ELSE { ClearBaseInfo; SetIndx[index+count] }};

peek => {

count ← startRuns-current;

ClearBaseInfo; SetIndx[index] };

backwards => {

count ← current-first+1;

ClearBaseInfo; SetIndx[index-count] };

peekbackwards => {

count ← current-first+1;

ClearBaseInfo; SetIndx[index] };

ENDCASE => ERROR;

RETURN [count, Modify[x[firstRun].looks]] };

IF x[lastRun].after=after THEN { -- included all of lastRun

afterRuns ← after; afterRun ← lastRun+1 }

ELSE { -- only included part of lastRun

know lastRun>0 since lastRun>firstRun

IF current >= (afterRuns ← x[lastRun-1].after) THEN {

current is in the lastRun. must special case it.

SELECT mode FROM

get => {

count ← after-current;

ClearBaseInfo; SetIndx[index+count] };

peek => {

count ← after-current;

ClearBaseInfo; SetIndx[index] };

backwards => {

count ← current-afterRuns+1;

IF lastRun > firstRun THEN {

SetBaseInfo[lastRun-1, firstRun, lastRun, @x];

SetIndx[index-count]; SetLooksInfo; }

ELSE { ClearBaseInfo; SetIndx[index-count] }};

peekbackwards => {

count ← current-afterRuns+1;

ClearBaseInfo; SetIndx[index] };

ENDCASE => ERROR;

RETURN [count, Modify[x[lastRun].looks]] };

afterRun ← lastRun };

curRun ← TiogaLooksSupport.BaseRun[@x, current, firstRun, lastRun];

startCur ← IF curRun=0 THEN 0 ELSE x[curRun-1].after;

SELECT mode FROM

get => {

count ← x[curRun].after-current;

SetBaseInfo[curRun+1, firstRun, afterRun, @x];

SetIndx[index+afterRuns-current]; SetLooksInfo; };

peek => {

count ← x[curRun].after-current;

IF current = startCur THEN {

SetBaseInfo[curRun, firstRun, afterRun, @x];

SetIndx[index+afterRuns-current]; SetLooksInfo; }

ELSE { ClearBaseInfo; SetIndx[index] }};

backwards => { -- recall that current has been decremented

count ← current-startCur+1;

SetBaseInfo[curRun, firstRun, afterRun, @x];

SetIndx[index+afterRuns-current-1]; SetLooksInfo; };

peekbackwards => {

count ← current-startCur+1;

IF current = x[curRun].after-1 THEN {

SetBaseInfo[curRun+1, firstRun, afterRun, @x];

SetIndx[index+afterRuns-current-1]; SetLooksInfo; }

ELSE { ClearBaseInfo; SetIndx[index] }};

ENDCASE => ERROR;

RETURN [count, Modify[x[curRun].looks]]};

node => WITH x:x SELECT FROM

substr => IF current < x.size THEN {

offset: Offset;

current ← current + (offset ← x.start);

first ← first + offset; after ← after + offset;

runs ← x.base; LOOP };

concat => IF current < x.size THEN {

xpos: Offset;

IF current >= (xpos ← x.pos) THEN {

current ← current - xpos; after ← after - xpos;

first ← IF first <= xpos THEN 0 ELSE first - xpos;

runs ← x.rest; LOOP };

IF after > xpos THEN after ← xpos;

runs ← x.base; LOOP };

replace => IF current < x.size THEN {

xstart: Offset ← x.start;

newPos, oldPos: Offset;

IF current < xstart THEN {

IF after > xstart THEN after ← xstart;

runs ← x.base; LOOP };

IF current < (newPos ← x.newPos) THEN {

current ← current - xstart;

after ← MIN[after, newPos] - xstart;

first ← IF first <= xstart THEN 0 ELSE first-xstart;

runs ← x.replace; LOOP };

current ← current - newPos + (oldPos ← x.oldPos);

after ← after - newPos + oldPos;

first ← IF first >= newPos THEN first - newPos + oldPos ELSE oldPos;

runs ← x.base; LOOP };

change => {

xstart: Offset ← x.start;

xend: Offset;

IF current < xstart THEN {

after ← MIN[after, xstart]; runs ← x.base; LOOP };

IF current < (xend ← xstart+x.len) THEN {

after ← MIN[after, xend]; first ← MAX[first, xstart];

[remove, add] ← TiogaLooksSupport.MergeChanges[x.remove,x.add,remove,add];

IF remove=TiogaLooks.allLooks THEN { SingleRun; RETURN[count,add] };

runs ← x.base; LOOP };

first ← MAX[first,xend]; runs ← x.base; LOOP };

ENDCASE => ERROR;

ENDCASE => ERROR};

EXIT;

ENDLOOP;

ERROR NoMoreRuns};

MergedGet: PUBLIC ReaderProc = {

merges adjacent runs with same looks

regular Get may give same looks on successive calls

e.g., if Concat[A,B] produces in a concat-node

and the last run in A has the same looks as the first in B

Get will first return last run from A, then first from B

MergedGet will combine these into a single result1

[count,looks] ← Get[reader];

WHILE reader.current=reader.after OR reader.changeLooks DO

nxtCount: Offset;

nxtLooks: Looks;

[nxtCount,nxtLooks] ← Peek[reader ! NoMoreRuns => EXIT];

IF nxtLooks#looks THEN RETURN;

count ← count+nxtCount;

[,] ← Get[reader];

ENDLOOP };

EqSubstrs: PUBLIC PROC [r1,r2: Runs, start1,start2,len: Offset, rdr1,rdr2: Ref]

RETURNS [BOOLEAN] = {

uses readers rdr1 and rdr2 to read runs r1 and r2 to test for equality

returns TRUE if r1 is same as len looks of r2 starting at start

NoLooks: PROC [r: Runs, start, len: Offset, rdr: Ref] RETURNS [BOOLEAN] = {

looks: Looks;

runLen: Offset;

size: Offset ← TiogaLooksOps.Size[r];

len ← IF start > size THEN 0 ELSE MIN[len,size-start];

SetPosition[rdr,r,start];

[runLen,looks] ← Get[rdr];

IF looks # noLooks OR runLen < len THEN RETURN [FALSE];

RETURN [TRUE] };

size1, size2: Offset;

IF len=0 THEN RETURN[TRUE];

IF r1=NIL THEN {

IF r2=NIL THEN RETURN [TRUE];

RETURN [NoLooks[r2,start2,len,rdr2]] };

IF r2=NIL THEN RETURN [NoLooks[r1,start1,len,rdr1]];

size1 ← TiogaLooksOps.Size[r1];

size2 ← TiogaLooksOps.Size[r2];

IF len=LAST[Offset] 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];

SetPosition[rdr1, r1, start1];

SetPosition[rdr2, r2, start2];

DO -- check the runs in the specified sections

looks1,looks2: Looks;

runLen1,runLen2: Offset;

[runLen1,looks1] ← MergedGet[rdr1];

[runLen2,looks2] ← MergedGet[rdr2];

IF looks1 # looks2 THEN RETURN [FALSE];

IF runLen1 >= len THEN { IF runLen2 < len THEN RETURN [FALSE]; EXIT };

IF runLen2 # runLen1 THEN RETURN [FALSE];

len ← len-runLen1;

ENDLOOP;

RETURN [TRUE] };

***** Shared readers

runrdr1, runrdr2, runrdr3: Ref; -- shared run readers

GetRunReader: PUBLIC ENTRY PROC RETURNS [reader: Ref] = {

ENABLE UNWIND => NULL;

IF runrdr3 # NIL THEN { reader ← runrdr3; runrdr3 ← NIL }

ELSE IF runrdr2 # NIL THEN { reader ← runrdr2; runrdr2 ← NIL }

ELSE IF runrdr1 # NIL THEN { reader ← runrdr1; runrdr1 ← NIL }

ELSE reader ← Create[] };

FreeRunReader: PUBLIC ENTRY PROC [reader: Ref] = {

ENABLE UNWIND => NULL;

SetPosition[reader, NIL];

IF runrdr3 = reader OR runrdr2 = reader OR runrdr1 = reader THEN ERROR;

IF runrdr3 = NIL THEN runrdr3 ← reader

ELSE IF runrdr2 = NIL THEN runrdr2 ← reader

ELSE IF runrdr1 = NIL THEN runrdr1 ← reader };

END.