DIRECTORY
TextLooks USING [allLooks, BaseRuns, Looks, MaxLen, noLooks, Runs, RunsBody, Size],
TextLooksSupport USING [BaseRunLengths, CheckLongSub, FindBaseRuns, InsertRun, MergeChanges, ModifyLooks];

TextLooksSupportImpl: CEDAR PROGRAM
IMPORTS TextLooks, TextLooksSupport
EXPORTS TextLooksSupport, TextLooks
SHARES TextLooks
= BEGIN OPEN TextLooksSupport, TextLooks;



CountRunsAfterChanges: PUBLIC PROC
[ref: Runs, start, len: INT, limit: INT _ MaxLen,
remove, add: Looks, merge: BOOL _ FALSE, firstLooks: Looks _ noLooks]
RETURNS [count: NAT, nonempty: BOOL, lastLooks: Looks] = {
ChangedBaseRuns: PROC
[x: BaseRuns, start, len, size: INT,
remove, add: Looks, limit: INT _ MaxLen]
RETURNS [count: NAT, firstLooks, lastLooks: Looks] = {
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;
DO 
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 ref SELECT FROM
x: REF RunsBody.base => {
size: INT;
firstLks, lastLks: Looks;
len _ MIN[len, CheckLongSub[size_TbaseSize[x], start]];
[c,firstLks,lastLks] _ ChangedBaseRuns[
x,start,len,size,remove,add,limit];
IF c > limit THEN { count _ count+c; RETURN };
IF merge AND firstLooks=firstLks THEN c _ c-1;
RETURN [count+c, TRUE, lastLks] };
x: REF RunsBody.node.substr => {
len _ MIN[len, CheckLongSub[x.size, start]];
start _ start + x.start; ref _ x.base; LOOP};
x: REF RunsBody.node.concat => {
xpos: INT _ x.pos;
len _ MIN[len, CheckLongSub[x.size, start]];
IF start < xpos THEN {
subLen: INT _ 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 };
x: REF RunsBody.node.replace => {
xstart: INT _ x.start;
xnew: INT _ x.newPos;
len _ MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
subLen: INT _ 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: INT _ start - xstart;
subLen: INT _ 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};
x: REF RunsBody.node.change => {
xstart: INT _ x.start;
xend, subLen: INT;
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: INT, len: INT, index: NAT _ 0]
RETURNS [NAT] = { -- value is next index
IF len>0 AND remove=allLooks THEN
RETURN [InsertRun[base, len, add, index]];
DO 
IF len=0 THEN RETURN [index];
IF ref=NIL THEN -- treat as noLooks
RETURN [InsertRun[base, len, add, index]];
WITH ref SELECT FROM
x: REF RunsBody.base => {
first, last: NAT;
firstLen, lastLen, xloc, next, loc, size: INT;
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] };
x: REF RunsBody.node.substr => {
len _ MIN[len, CheckLongSub[x.size, start]];
start _ start + x.start; ref _ x.base; LOOP};
x: REF RunsBody.node.concat => {
xpos: INT _ x.pos;
len _ MIN[len, CheckLongSub[x.size, start]];
IF start < xpos THEN {
subLen: INT _ 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 };
x: REF RunsBody.node.replace => {
xstart: INT _ x.start;
xnew: INT _ x.newPos;
len _ MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
subLen: INT _ 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: INT _ start - xstart;
subLen: INT _ 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};
x: REF RunsBody.node.change => {
xstart: INT _ x.start;
xend, subLen: INT;
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: INT _ 0, len: INT _ MaxLen]
RETURNS [size, pieces, depth: INT]  = {
rem, altDepth, subSize, subDepth, subPieces: INT;
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 base SELECT FROM
x: REF RunsBody.base => {
first, last: NAT;
[first,last] _ FindBaseRuns[x,start,len];
RETURN [size+last-first+1,pieces+1,MAX[depth,altDepth]] };
xNode: REF RunsBody.node => {
depth _ depth+1; 
WITH xNode SELECT FROM
x: REF RunsBody.node.substr =>
{base _ x.base; start _ start + x.start; LOOP};
x: REF RunsBody.node.concat  =>
{subLen: INT _ 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};
x: REF RunsBody.node.replace =>
{xstart: INT _ x.start;
len1: INT _ 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: INT _ x.newPos;
len2: INT _ xpos - start;
IF len2 <= 0 THEN
{-- no piece in middle section
start _ x.oldPos - len2; LOOP};
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;
}};
x: REF RunsBody.node.change => {base _ x.base; LOOP};
ENDCASE => ERROR };
ENDCASE => ERROR;
ENDLOOP;
RETURN [0,0,0];
};

TbaseSize: PUBLIC PROC [x: BaseRuns] RETURNS [INT]
= { RETURN [IF x.length=0 THEN 0 ELSE x[x.length-1].after] };

END.
$TextLooksSupportImpl.mesa
Copyright c 1985, 1986 by Xerox Corporation.  All rights reserved.
Bill Paxton, February 1981
Bill Paxton, 10-Feb-82 12:58:05
Maxwell, January 5, 1983 3:57 pm
Russ Atkinson, July 25, 1983 3:44 pm
Michael Plass, March 29, 1985 2:46:22 pm PST
Doug Wyatt, September 3, 1986 1:16:02 pm PDT

-- support procedures
-- equivalent procedures including changed looks
-- stops counting when exceeds limit
-- if firstSize is > 0, then tries to merge with first run
-- 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
-- now compute count, lastLooks, and lastSize
-- three pieces to consider (first, middle, last)
-- a piece in middle section of replace node
Κ
ϊ˜
codeš
œ™Kšœ
Οm
œ7™BKš
œ™Kš
œ™K™ K™$K™,K™,K™—š
Οk	˜	Kšœ
žœD˜SKšœžœT˜j—K˜KšΠblœžœ
ž˜#Kšžœ˜#Kšžœ˜#Kšžœ
˜Kšœžœ
žœ˜)K˜Kš
œ™K˜Kš
œ0™0K˜šΟnœžœ
ž˜"šœžœ	žœ
˜1Kšœžœžœ˜E—Kšžœ	žœžœ˜:Kš
œ$™$Kš
œ:™:š œž˜šœ žœ
˜$Kšœžœ
˜(—Kšžœ	žœ#˜6Kš
œ+™+Kš
œ'™'Kš
œ-™-Kš
œ.™.Kšœ
žœ
˜Kšžœžœ
žœ˜-K˜,K˜
K˜Bšžœžœ
žœž˜K˜7šžœžœ˜Kšžœžœ
žœ
˜)K˜—Kšžœ˜
——Kšœžœ
˜Kšžœžœ
žœ˜,šžœžœ
žœ˜ Kš
žœžœžœžœžœ˜6—K˜
šžœ
˜K˜Kšžœžœžœ˜1šžœžœ
žœ˜Kš	œžœžœžœžœ˜.Kšžœžœ	˜—šžœžœ
ž˜šœžœ˜Kšœžœ
˜
K˜Kšœžœ.˜7˜'K˜#—Kš
œ-™-Kšžœžœžœ˜.Kšžœžœžœ	˜.Kšžœžœ
˜"—šœžœ˜ Kšœžœ#˜,Kšœ'žœ˜-—šœžœ˜ Kšœžœ	˜Kšœžœ#˜,šžœžœ˜Kšœžœ˜Kšžœžœžœ˜-˜/K˜K˜$—Kšœžœžœ
žœ
˜*K˜K˜"—Kšœ"žœ˜)—šœžœ˜!Kšœžœ˜Kšœžœ˜Kšœžœ#˜,šžœžœ˜Kšœžœ˜Kšžœžœžœ˜+˜/K˜K˜$—Kšœžœžœ
žœ
˜*K˜3—šžœžœ˜Kšœžœ˜Kšœžœ˜šžœžœ˜Kšœžœ˜#—˜/K˜8—Kšœžœžœ
žœ
˜*K˜1—Kšœ/žœ˜5—šœžœ˜ Kšœžœ˜Kšœžœ
˜Kšœžœ#˜,šžœžœ˜Kšžœ žœžœ˜<˜/K˜8—Kšœžœžœ
žœ
˜*K˜3—šžœžœ˜'K˜˜K˜+—Kšœ	žœ˜˜/K˜K˜*—Kšœžœžœ
žœ
˜*K˜1—Kšœžœ˜—Kšžœžœ
˜—Kšžœ˜	K˜——š œžœ
ž˜$˜/Kšœžœžœ	žœ˜%—KšžœžœΟc˜(šžœžœž˜!Kšžœ$˜*—šžœ
˜Kšžœžœ
žœ	˜šžœžœ
žœ
‘˜#Kšžœ$˜*—šžœžœ
ž˜šœžœ˜Kšœ
žœ
˜Kšœ*žœ
˜.K˜Kš	œžœžœžœ
žœ˜EK˜,K˜=K˜4šžœ	žœ‘(˜:K˜6—šžœ˜K˜%šžœ‘
˜-Kšžœ˜—Kšžœ5˜9—K˜šžœžœ
žœž˜K˜0Kšœžœžœžœ˜3K˜!šžœžœ˜K˜K˜&—Kšžœ˜Kšžœ
˜—Kšžœ˜—šœžœ˜ Kšœžœ#˜,Kšœ'žœ˜-—šœžœ˜ Kšœžœ	˜Kšœžœ#˜,šžœžœ˜Kšœžœ˜Kšžœžœžœ˜-˜ K˜+—K˜"—Kšœ"žœ˜)—šœžœ˜!Kšœžœ˜Kšœžœ˜Kšœžœ#˜,šžœžœ˜Kšœžœ˜Kšžœžœžœ˜+˜ K˜,—K˜"—šžœžœ˜Kšœžœ˜Kšœžœ˜šžœžœ˜Kšœžœ˜#—˜ K˜,—K˜ —Kšœ/žœ˜5—šœžœ˜ Kšœžœ˜Kšœžœ
˜Kšœžœ#˜,šžœžœ˜Kšžœ žœžœ˜<˜ K˜,—K˜"—šžœžœ˜'K˜˜K˜(—Kšœ	žœ˜˜ K˜2—K˜ —Kšœžœ˜—Kšžœžœ
˜—Kšžœ˜	K˜——š
 
œžœ
žœžœžœ
˜GKšžœžœ˜'Kšœ-žœ
˜1K˜	K˜K˜
Kšžœžœ˜K˜šžœ	ž˜K˜šžœžœ
ž˜šœžœ˜Kšœ
žœ
˜K˜)Kšžœžœ˜:—šœžœ˜K˜šžœžœ
ž˜šœžœ˜Kšœ)žœ˜/—šœžœ˜šœ	žœ˜šžœžœ
˜šœ
žœžœžœ˜-K˜AK˜K˜Kšœžœ˜(K˜—Kšžœ˜—Kšœžœ˜——šœžœ˜Kš
œ1™1šœ	žœ˜Kšœžœ˜K˜šžœ
ž˜šœ
‘˜Kšžœ
žœ
žœ‘˜2K˜=K˜K˜Kšœžœ˜(K˜,——šœžœ˜Kšœžœ˜šžœž˜šœ
‘˜Kšœžœ˜——Kš
œ,™,K˜ Kšžœ
žœ
žœ‘˜3K˜=K˜K˜Kšœžœ˜(K˜2K˜———Kšœžœ)žœ˜5Kšžœžœ˜——Kšžœžœ
˜—Kšžœ
˜—Kšžœ	˜K˜K˜—š
 	œžœ
žœžœžœ
˜2Kš	œžœžœžœžœ˜=K˜—Kšžœ
˜—…—#¨1Ζ