TextLooksSupportImpl.mesa
Copyright © 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
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;
-- support procedures
-- equivalent procedures including changed looks
CountRunsAfterChanges: PUBLIC PROC
[ref: Runs, start, len: INT, limit: INT ← MaxLen,
remove, add: Looks, merge: BOOLFALSE, firstLooks: Looks ← noLooks]
RETURNS [count: NAT, nonempty: BOOL, lastLooks: Looks] = {
-- stops counting when exceeds limit
-- if firstSize is > 0, then tries to merge with first run
ChangedBaseRuns: PROC
[x: BaseRuns, start, len, size: INT,
remove, add: Looks, limit: INT ← MaxLen]
RETURNS [count: NAT, firstLooks, lastLooks: Looks] = {
-- 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;
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];
-- 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] };
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 =>
-- three pieces to consider (first, middle, last)
{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};
-- 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;
}};
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.