[Cyan]<Tioga2>Looks>TiogaLooksSupportImpl.mesa!1

TiogaLooksSupportImpl.mesa; written by Bill Paxton, February 1981

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

edited by Bill Paxton, 10-Feb-82 12:58:05

edited by Maxwell, January 5, 1983 3:57 pm

DIRECTORY

Inline,

TiogaLooks,

TiogaLooksOps,

TiogaLooksSupport;

TiogaLooksSupportImpl: CEDAR PROGRAM

IMPORTS Inline, TiogaLooksOps, TiogaLooksSupport

EXPORTS TiogaLooksSupport, TiogaLooksOps

SHARES TiogaLooksOps =

BEGIN OPEN TiogaLooks, TiogaLooksOps, TiogaLooksSupport;

support procedures

equivalent procedures including changed looks

CountRunsAfterChanges: PUBLIC PROC

[ref: Runs, start, len: Offset, limit: Offset ← MaxOffset,

remove, add: Looks, merge: BOOLEAN ← FALSE, firstLooks: Looks ← noLooks]

RETURNS [count: NAT, nonempty: BOOLEAN, lastLooks: Looks] = TRUSTED {

stops counting when exceeds limit

if firstSize is > 0, then tries to merge with first run

ChangedBaseRuns: PROC

[x: BaseRuns, start, len, size: Offset,

remove, add: Looks, limit: Offset ← MaxOffset]

RETURNS [count: NAT, firstLooks, lastLooks: Looks] = TRUSTED INLINE {

find the runs in x in [start..start+len)

modify looks according to remove&add

return count of distinct runs after modify

and looks of first & last runs after modify

first, last: NAT;

IF remove=allLooks THEN RETURN [1, add, add];

[first, last] ← FindBaseRuns[x, start, len];

count ← 1;

firstLooks ← lastLooks ← ModifyLooks[x[first].looks, remove, add];

FOR i: NAT IN (first..last] DO

newLooks: Looks ← ModifyLooks[x[i].looks, remove, add];

IF newLooks # lastLooks THEN {

IF (count ← count+1) > limit THEN RETURN;

lastLooks ← newLooks };

ENDLOOP };

c: NAT;

IF len=0 THEN RETURN [0, merge, firstLooks];

IF remove=allLooks THEN RETURN [

IF merge AND firstLooks=add THEN 0 ELSE 1, TRUE, add];

count ← 0;

nonempty ← merge;

IF len=0 THEN { lastLooks ← firstLooks; RETURN };

IF ref=NIL THEN {

c ← IF merge AND firstLooks=add THEN 0 ELSE 1;

RETURN [count+c, TRUE, add] };

WITH x:ref SELECT FROM

base => {

size: Offset;

firstLks, lastLks: Looks;

len ← MIN[len, CheckLongSub[size←TbaseSize[@x], start]];

[c,firstLks,lastLks] ← ChangedBaseRuns[

@x,start,len,size,remove,add,limit];

now compute count, lastLooks, and lastSize

IF c > limit THEN { count ← count+c; RETURN };

IF merge AND firstLooks=firstLks THEN c ← c-1;

RETURN [count+c, TRUE, lastLks] };

node => WITH x:x SELECT FROM

substr => {

len ← MIN[len, CheckLongSub[x.size, start]];

start ← start + x.start; ref ← x.base; LOOP};

concat => {

xpos: Offset ← x.pos;

len ← MIN[len, CheckLongSub[x.size, start]];

IF start < xpos THEN {

subLen: Offset ← xpos - start;

IF len <= subLen THEN { ref ← x.base; LOOP };

[c, merge, firstLooks] ← CountRunsAfterChanges[

x.base,start,subLen,

limit,remove,add,merge,firstLooks];

count ← count+c; IF c > limit THEN RETURN;

limit ← limit-c;

start ← xpos; len ← len-subLen };

start ← start-xpos; ref ← x.rest; LOOP };

replace => {

xstart: Offset ← x.start;

xnew: Offset ← x.newPos;

len ← MIN[len, CheckLongSub[x.size, start]];

IF start < xstart THEN {

subLen: Offset ← xstart - start;

IF len <= subLen THEN {ref ← x.base; LOOP};

[c, merge, firstLooks] ← CountRunsAfterChanges[

x.base,start,subLen,

limit,remove,add,merge,firstLooks];

count ← count+c; IF c > limit THEN RETURN;

limit ← limit-c; start ← xstart; len ← len-subLen};

IF start < xnew THEN {

st: Offset ← start - xstart;

subLen: Offset ← xnew - start;

IF len <= subLen THEN {

start ← st; ref ← x.replace; LOOP};

[c, merge, firstLooks] ← CountRunsAfterChanges[

x.replace,st,subLen,limit,remove,add,merge,firstLooks];

count ← count+c; IF c > limit THEN RETURN;

limit ← limit-c; start ← xnew; len ← len-subLen};

start ← start - xnew + x.oldPos; ref ← x.base; LOOP};

change => {

xstart: Offset ← x.start;

xend, subLen: Offset;

len ← MIN[len, CheckLongSub[x.size, start]];

IF start < xstart THEN {

IF len <= (subLen ← xstart-start) THEN {ref ← x.base; LOOP};

[c, merge, firstLooks] ← CountRunsAfterChanges[

x.base,start,subLen,limit,remove,add,merge,firstLooks];

count ← count+c; IF c > limit THEN RETURN;

limit ← limit-c; start ← xstart; len ← len-subLen};

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

newRemove, newAdd: Looks;

[newRemove, newAdd] ←

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

subLen ← MIN[xend-start,len];

[c, merge, firstLooks] ← CountRunsAfterChanges[

x.base,start,subLen,

limit,newRemove,newAdd,merge,firstLooks];

count ← count+c; IF c > limit THEN RETURN;

limit ← limit-c; start ← xend; len ← len-subLen};

ref ← x.base; LOOP};

ENDCASE => ERROR;

ENDLOOP};

ExtractRunsAfterChanges: PUBLIC PROC

[base: BaseRuns, ref: Runs, remove, add: Looks,

start: Offset, len: Offset, index: NAT ← 0]

RETURNS [NAT] = TRUSTED { -- value is next index

IF len>0 AND remove=allLooks THEN

RETURN [InsertRun[base, len, add, index]];

IF len=0 THEN RETURN [index];

IF ref=NIL THEN -- treat as noLooks

RETURN [InsertRun[base, len, add, index]];

WITH x:ref SELECT FROM

base => {

first, last: NAT;

firstLen, lastLen, xloc, next, loc, size: Offset;

newLooks, oldLooks: Looks;

len ← IF (size←TbaseSize[@x]) < start THEN 0 ELSE MIN[len,size-start];

[first, last] ← FindBaseRuns[@x, start, len];

[firstLen, lastLen] ← BaseRunLengths[@x,start,len,first,last];

oldLooks ← ModifyLooks[x[first].looks, remove, add];

IF index=0 THEN { -- this is the first run to be extracted

loc ← firstLen; base[0] ← [loc, oldLooks]; index ← 1 }

ELSE {

loc ← base[index-1].after + firstLen;

IF base[index-1].looks=oldLooks -- merge runs

THEN base[index-1].after ← loc

ELSE { base[index] ← [loc, oldLooks]; index ← index+1 }};

xloc ← x[first].after;

FOR i: NAT IN (first..last] DO

newLooks ← ModifyLooks[x[i].looks, remove, add];

next ← IF i=last THEN xloc+lastLen ELSE x[i].after;

loc ← loc+next-xloc; xloc ← next;

IF newLooks # oldLooks THEN {

base[index] ← [loc, newLooks];

oldLooks ← newLooks; index ← index+1 }

ELSE base[index-1].after ← loc;

ENDLOOP;

RETURN [index] };

node => WITH x:x SELECT FROM

substr => {

len ← MIN[len, CheckLongSub[x.size, start]];

start ← start + x.start; ref ← x.base; LOOP};

concat => {

xpos: Offset ← x.pos;

len ← MIN[len, CheckLongSub[x.size, start]];

IF start < xpos THEN {

subLen: Offset ← xpos - start;

IF len <= subLen THEN { ref ← x.base; LOOP };

index ← ExtractRunsAfterChanges[

base,x.base,remove,add,start,subLen,index];

start ← xpos; len ← len-subLen };

start ← start-xpos; ref ← x.rest; LOOP };

replace => {

xstart: Offset ← x.start;

xnew: Offset ← x.newPos;

len ← MIN[len, CheckLongSub[x.size, start]];

IF start < xstart THEN {

subLen: Offset ← xstart - start;

IF len <= subLen THEN {ref ← x.base; LOOP};

index ← ExtractRunsAfterChanges[

base,x.base,remove,add,start,subLen,index];

start ← xstart; len ← len-subLen};

IF start < xnew THEN {

st: Offset ← start - xstart;

subLen: Offset ← xnew - start;

IF len <= subLen THEN {

start ← st; ref ← x.replace; LOOP};

index ← ExtractRunsAfterChanges[

base,x.replace,remove,add,st,subLen,index];

start ← xnew; len ← len-subLen};

start ← start - xnew + x.oldPos; ref ← x.base; LOOP};

change => {

xstart: Offset ← x.start;

xend, subLen: Offset;

len ← MIN[len, CheckLongSub[x.size, start]];

IF start < xstart THEN {

IF len <= (subLen ← xstart-start) THEN {ref ← x.base; LOOP};

index ← ExtractRunsAfterChanges[

base,x.base,remove,add,start,subLen,index];

start ← xstart; len ← len-subLen};

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

newRemove, newAdd: Looks;

[newRemove,newAdd] ←

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

subLen ← MIN[xend-start,len];

index ← ExtractRunsAfterChanges[

base,x.base,newRemove,newAdd,start,subLen,index];

start ← xend; len ← len-subLen};

ref ← x.base; LOOP};

ENDCASE => ERROR;

ENDLOOP};

LooksStats: PUBLIC PROC [base: Runs, start: Offset ← 0, len: Offset ← MaxOffset]

RETURNS [size, pieces, depth: Offset] = TRUSTED {

rem, altDepth, subSize, subDepth, subPieces: Offset;

size ← 0;

rem ← Size[base] - start;

altDepth ← 0;

IF len > rem THEN len ← rem;

pieces ← depth ← 0;

WHILE len > 0 DO

x: Runs ← base;

WITH x: x SELECT FROM

base => {

first, last: NAT;

[first,last] ← FindBaseRuns[@x,start,len];

RETURN [size+last-first+1,pieces+1,MAX[depth,altDepth]] };

node => {

depth ← depth+1;

WITH x: x SELECT FROM

substr =>

{base ← x.base; start ← start + x.start; LOOP};

concat =>

{subLen: Offset ← x.pos - start;

IF subLen > 0 THEN

{IF len <= subLen THEN {base ← x.base; LOOP};

[subSize,subPieces,subDepth] ← LooksStats[x.base, start, subLen];

pieces ← pieces+subPieces;

size ← size+subSize;

altDepth ← MAX[altDepth,depth+subDepth];

len ← len - subLen; start ← 0}

ELSE start ← -subLen;

base ← x.rest; LOOP};

replace =>

three pieces to consider (first, middle, last)

{xstart: Offset ← x.start;

len1: Offset ← xstart - start;

base ← x.base;

IF len1 > 0 THEN

{-- a piece in first section

IF len1 >= len THEN LOOP; -- only in first section

[subSize,subPieces,subDepth] ← LooksStats[base, start, len1];

pieces ← pieces+subPieces;

size ← size+subSize;

altDepth ← MAX[altDepth,depth+subDepth];

start ← xstart; len ← len - len1; len1 ← 0};

{xpos: Offset ← x.newPos;

len2: Offset ← xpos - start;

IF len2 <= 0 THEN

{-- no piece in middle section

start ← x.oldPos - len2; LOOP};

a piece in middle section of replace node

base ← x.replace; start ← -len1;

IF len2 >= len THEN LOOP; -- only in middle section

[subSize,subPieces,subDepth] ← LooksStats[base, start, len2];

pieces ← pieces+subPieces;

size ← size+subSize;

altDepth ← MAX[altDepth,depth+subDepth];

base ← x.base; start ← x.oldPos; len ← len - len2;

}};

change => {base ← x.base; LOOP};

ENDCASE => ERROR };

ENDCASE => ERROR;

ENDLOOP;

RETURN [0,0,0];

};

Lks: TYPE = ARRAY [0..1] OF UNSPECIFIED;

LooksAND: PUBLIC PROC [looks1, looks2: Looks] RETURNS [Looks] = TRUSTED {

compute looks1 & looks2

OPEN Inline;

lks1: Lks ← LOOPHOLE[looks1];

lks2: Lks ← LOOPHOLE[looks2];

lks: Lks;

lks[0] ← BITAND[lks1[0],lks2[0]];

lks[1] ← BITAND[lks1[1],lks2[1]];

RETURN [LOOPHOLE[lks]] };

LooksOR: PUBLIC PROC [looks1, looks2: Looks] RETURNS [Looks] = TRUSTED {

compute looks1 v looks2

OPEN Inline;

lks1: Lks ← LOOPHOLE[looks1];

lks2: Lks ← LOOPHOLE[looks2];

lks: Lks;

lks[0] ← BITOR[lks1[0],lks2[0]];

lks[1] ← BITOR[lks1[1],lks2[1]];

RETURN [LOOPHOLE[lks]] };

LooksNOT: PUBLIC PROC [looks: Looks] RETURNS [Looks] = TRUSTED {

compute ~looks

OPEN Inline;

lks: Lks ← LOOPHOLE[looks];

lks[0] ← BITNOT[lks[0]]; lks[1] ← BITNOT[lks[1]];

RETURN [LOOPHOLE[lks]] };

END.