DIRECTORY
RunReader,
TiogaLooks,
TiogaLooksOps,
TiogaLooksSupport;

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
IF current >= (afterRuns _ x[lastRun-1].after) THEN {
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 = {
[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] = {
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] };


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.


èRunReaderImpl.mesa; written by Bill Paxton,  March 1981
edited by McGregor, February 8, 1983 11:38 am
edited by Maxwell, January 5, 1983 1:08 pm
edited by Bill Paxton, July 8, 1983 2:19 pm
know lastRun>0 since lastRun>firstRun
current is in the lastRun.  must special case it.
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
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
***** Shared readers
�Ê
˜Jš
œ7™7Jš
œ-™-Jš
œ*™*Jš
œ+™+J˜š
Ïk	˜	J˜
J˜J˜J˜J˜—šœ�
˜Jš�œ,˜3Jš�œ
˜Jš�œ˜—Jš�œ
�œ*˜4J˜JšÏnœ�œ
�œ
�œ�œ�œ
˜;J˜šžœ�œ
�œ�œ˜?J˜J˜Jš�œ�œ
�œ˜<J˜šœ	�œ�œ˜<Jš�œ9˜=—Jš�œ˜!J˜—Jšœ�œ
�œ�œ
˜ J˜šžœ�œ
�œ˜.Jš�œ"˜)J˜J˜*J˜)J˜J˜Jšžœ�œ,˜9šžœ�œ�œ˜>J˜/J˜+—Jšž
œ�œ�œ˜1šžœ�œ˜J˜)Jšœ&�œ˜9—šžœ�œ�œ�œ˜4Jš�œ5˜;—šž	œ�œ˜J˜š�œ�˜J˜0J˜J˜8J˜)Jš�œ�œ˜J˜——Jš�œ�œ
�œ
�œ�œ
�œ˜,š�œ�œ
Ïc(˜9˜Jš�œ�œ
�œ�œ˜<Jšœ
�œ
˜—Jš�œ�œ
˜—Jš�œ�œ
�œ˜*š�œ�œ
�˜š�
œ�œ
�˜ ˜	J˜Jšœ%�œŸ˜>J˜'J˜Eš�œ�œŸ˜3Jšœ�œ&˜7—š�œ
�œ
�˜Jšœ�œ�œ˜A—š�œ
Ÿ!˜&š�œ,�˜2JšœŸ˜1—š�œŸ6˜=š�œ�œŸ˜:J˜)—Jš�œ8˜<š�œ�˜˜J˜š�œ�œ˜J˜2J˜1—Jš�œ*˜.—˜	J˜J˜ —˜J˜J˜&—˜J˜J˜ —Jš�œ�œ
˜—Jš�œ&˜,——š�œ�œŸ˜;J˜)—š�œŸ ˜'Jš
œ%™%š�œ-�œ˜5Jš
œ1™1š�œ�˜˜J˜J˜&—˜	J˜J˜ —˜J˜š�œ�œ˜J˜.J˜%—Jš�œ*˜.—˜J˜J˜ —Jš�œ�œ
˜—Jš�œ%˜+—J˜—J˜CJšœ�œ
�œ�œ˜5š�œ�˜˜J˜ J˜.J˜2—˜	J˜ š�œ�œ˜J˜,J˜1—Jš�œ$˜(—šœŸ+˜:J˜J˜,J˜4—˜J˜š�œ�œ˜%J˜.J˜3—Jš�œ$˜(—Jš�œ�œ
˜—Jš�œ#˜)—šœ�œ�œ
�˜šœ�œ�œ˜%J˜J˜'J˜0Jšœ�œ˜—šœ�œ�œ˜%J˜
š�œ�œ˜#J˜0Jšœ�œ�œ�œ˜3Jšœ�œ˜—Jš�œ�œ˜"Jšœ�œ˜—šœ�œ�œ˜%J˜J˜š�œ�œ˜Jš�œ�œ˜&Jšœ�œ˜—š�œ�œ˜'J˜Jšœ�œ˜$Jšœ�œ�œ�œ˜4Jšœ�œ˜—J˜1J˜ Jšœ�œ�œ�œ˜DJšœ�œ˜—˜J˜J˜
š�œ�œ˜Jšœ�œ �œ˜2—š�œ!�œ˜)Jšœ�œ�œ˜5J˜JJš�œ�œ�œ˜DJšœ�œ˜—Jšœ�œ�œ˜/—Jš�œ�œ
˜—Jš�œ�œ
˜Jš�œ
˜—Jš�œ
˜—Jš�œ
˜J˜—šœ�œ˜ Jš
œ$™$š
œ4™4š
œ/™/Jš
œ:™:Jš
œ8™8Jš
œ2™2——J˜š�œ�œ�˜:J˜J˜Jšœ2�œ˜8Jš�œ�œ
�œ
˜J˜J˜Jš�œ˜
J˜——šž	œ�œ
�œ9˜OJš�œ�œ˜Jš
œF™FJš
œ?™?šžœ�œ)�œ�œ˜KJ˜
J˜J˜%Jš	œ�œ�œ�œ
�œ˜6J˜J˜Jš
�œ�œ�œ
�œ�œ˜7Jš�œ�œ˜—J˜Jš�œ�œ
�œ
�œ˜š�œ�œ
�œ˜Jš
�œ�œ
�œ
�œ�œ˜Jš�œ!˜'—Jš�œ�œ
�œ
�œ˜4J˜J˜Jš�œ�œ	�œ�œ%�œ
�œ�œ˜WJš
�œ
�œ�œ
�œ�œ
˜.Jš
�œ
�œ�œ
�œ�œ˜/J˜J˜š�œ
Ÿ+˜.J˜J˜J˜#J˜#Jš�œ�œ
�œ�œ˜'Jš�œ�œ�œ�œ
�œ�œ�œ˜FJš�œ�œ
�œ�œ˜)J˜Jš�œ
˜—Jš�œ�œ˜J˜—Jš
œ™J˜Jšœ Ÿ˜5J˜š
žœ�œ
�œ
�œ
�œ˜9Jš�œ
�œ�œ
˜Jš�œ�œ
�œ�œ˜9Jš
�œ
�œ�œ
�œ�œ˜>Jš
�œ
�œ�œ
�œ�œ˜>Jš�œ˜J˜—šž
œ�œ
�œ
�œ˜2Jš�œ
�œ�œ
˜Jšœ�œ˜Jš
�œ�œ�œ�œ
�œ
˜GJš�œ�œ
�œ˜&Jš�œ
�œ�œ
�œ˜+Jš�œ
�œ�œ
�œ˜.J˜—Jš�œ
˜J˜J˜—…—"*/