DIRECTORY
Basics,
PrincOpsUtils,
TextLooks,
TextLooksSupport;

TextLooksBasicImpl: CEDAR PROGRAM
IMPORTS Basics, PrincOpsUtils, TextLooks, TextLooksSupport
EXPORTS TextLooks, TextLooksSupport
SHARES TextLooks
= BEGIN OPEN TextLooks, TextLooksSupport;

ReplaceByRun: PUBLIC PROC
[dest: Runs, start, len, runLen, destSize: Offset, inherit: BOOL, looks: Looks]
RETURNS [Runs] = {
merge: BOOL _ FALSE;
mergeLooks: Looks;
split, numruns: NAT;
flat: BaseRuns;
c, numRuns, oldPos, size: Offset;
Count: PROC [start,len: Offset] RETURNS [Offset] = {
IF len=0 THEN RETURN[numRuns];
[c,merge,mergeLooks] _
CountRuns[dest,start,len,FlatMax-numRuns,merge,mergeLooks];
RETURN [numRuns_numRuns+c]};
AddIt: PROC RETURNS [Offset] = {
c _ IF merge AND mergeLooks=looks THEN 0 ELSE 1;
merge _ TRUE; mergeLooks _ looks;
RETURN [numRuns_numRuns+c]};
Extract: PROC [start,len: Offset] = {
IF len > 0 THEN split _ ExtractRuns[flat,dest,start,len,split] };
TryFlatAppendRun: PROC [base: Runs] RETURNS [Runs] = {
flat: BaseRuns;
size: Offset;
[numRuns,merge,mergeLooks] _ CountRuns[base,0,size_Size[base],FlatMax];
IF numRuns > FlatMax OR AddIt[] > FlatMax THEN RETURN [NIL];
flat _ NewBase[numruns_Short[numRuns]];
split _ ExtractRuns[flat,base,0,size,0];
split _ InsertRun[flat,runLen,looks,split];
IF split # numruns THEN ERROR;
IF flat[numruns-1].after # size+runLen THEN ERROR;
RETURN [flat] };
IF runLen=0 THEN RETURN [Delete[dest,start,len,destSize]];
IF inherit THEN -- get looks from destination
IF destSize = 0 THEN NULL -- take from arg list
ELSE looks _ FetchLooks[dest,
IF start > 0 THEN start-1 -- take from before replacement
ELSE IF len=destSize THEN 0 -- replacing everything
ELSE len]; -- take from after replacement
IF dest=NIL AND looks=noLooks THEN RETURN[NIL];
numRuns _ 0; oldPos _ start+len; size _ destSize-len+runLen;
IF	Count[0,start] > FlatMax OR
AddIt[] > FlatMax OR
Count[oldPos,destSize-oldPos] > FlatMax THEN {
newPos: Offset _ start+runLen;
replace, new: Runs;
WHILE dest # NIL DO
TRUSTED {WITH x:dest SELECT FROM node => WITH x:x SELECT FROM
replace => {
xnewPos: Offset _ x.newPos;
xstart: Offset _ x.start;
IF start <= xstart AND oldPos >= xnewPos THEN {
oldPos _ x.oldPos+(oldPos-xnewPos); dest _ x.base; LOOP}
ELSE IF start = xnewPos -- appending to the replacement
AND (new _ TryFlatAppendRun[x.replace])#NIL THEN {
start _ xstart; oldPos _ x.oldPos+len;
dest _ x.base; replace _ new}};
concat => { -- try to append to first part of the concat
xpos: Offset _ x.pos;
IF start=xpos AND len=0 AND 
(new _ TryFlatAppendRun[x.base])#NIL THEN RETURN [
qZone.NEW[Tconcat _ [node[concat
[size, new, x.rest, xpos+runLen]]]]]};
ENDCASE; ENDCASE};
EXIT;
ENDLOOP;
IF replace=NIL AND (replace _ CreateRun[runLen,looks])=NIL THEN
replace _ MakeRun[runLen];
IF dest=NIL THEN dest _ MakeRun[destSize];
RETURN [qZone.NEW[Treplace _ [node[replace
[size,dest,replace,start,oldPos,newPos]]]]]};
IF numRuns=0 THEN RETURN[NIL];
flat _ NewBase[numruns_Short[numRuns]]; split _ 0;
Extract[0,start];
split _ InsertRun[flat,runLen,looks,split];
Extract[oldPos,destSize-oldPos];
IF split # numruns THEN ERROR;
IF flat[numruns-1].after # size THEN ERROR;
RETURN [flat] };

CountRuns: PUBLIC PROC
[runs: Runs, start, len: Offset, limit: Offset _ MaxOffset,
merge: BOOL _ FALSE, firstLooks: Looks _ noLooks]
RETURNS [count: Offset, nonempty: BOOL, lastLooks: Looks] = {
c: Offset;
count _ 0;
DO	nonempty _ merge;
IF len=0 THEN { lastLooks _ firstLooks; RETURN };
IF runs=NIL THEN {
c _ IF merge AND firstLooks=noLooks THEN 0 ELSE 1;
RETURN [count+c, TRUE, noLooks] };
TRUSTED {WITH x:runs SELECT FROM
base => {
first, last: NAT;
len _ MIN[len, CheckLongSub[TbaseSize[@x], start]];
[first, last] _ FindBaseRuns[@x, start, len];
c _ last-first+1;
IF merge AND firstLooks=x[first].looks THEN c _ c-1;
RETURN [count+c, TRUE, x[last].looks]};
node => WITH x:x SELECT FROM
substr => {
len _ MIN[len, CheckLongSub[x.size, start]];
start _ start + x.start; runs _ 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 { runs _ x.base; LOOP };
[c, merge, firstLooks] _ CountRuns[
x.base, start, subLen, limit, merge, firstLooks]; 
count _ count+c; IF c > limit THEN RETURN;
limit _ limit-c; start _ xpos; len _ len-subLen }; 
start _ start-xpos; runs _ 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 {runs _ x.base; LOOP};
[c, merge, firstLooks] _ CountRuns[
x.base, start, subLen, limit, 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; runs _ x.replace; LOOP};
[c, merge, firstLooks] _ CountRuns[
x.replace, st, subLen, limit, merge, firstLooks]; 
count _ count+c; IF c > limit THEN RETURN;
limit _ limit-c; start _ xnew; len _ len-subLen};
start _ start - xnew + x.oldPos; runs _ 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 {runs _ x.base; LOOP};
[c, merge, firstLooks] _ CountRuns[
x.base, start, subLen, limit, 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 {
subLen _ MIN[xend-start,len];
[c, merge, firstLooks] _ CountRunsAfterChanges[
x.base, start, subLen, limit,
x.remove, x.add, merge, firstLooks]; 
count _ count+c; IF c > limit THEN RETURN;
limit _ limit-c; start _ xend; len _ len-subLen};
runs _ x.base; LOOP};
ENDCASE => ERROR;
ENDCASE => ERROR};
ENDLOOP};

ExtractRuns: PUBLIC PROC
[base: BaseRuns, ref: Runs, start, len: Offset, index: NAT _ 0]
RETURNS [NAT] = TRUSTED { -- value is next index
DO 
IF len=0 THEN RETURN [index];
IF ref=NIL THEN -- treat as noLooks
RETURN [InsertRun[base, len, noLooks, index]];
WITH x:ref SELECT FROM
base => {
firstLen, lastLen, xloc, next, loc: Offset;
first, last: NAT;
len _ MIN[len, CheckLongSub[TbaseSize[@x], start]];
[first, last] _ FindBaseRuns[@x, start, len];
[firstLen, lastLen] _ BaseRunLengths[@x,start,len,first,last];
IF index=0 THEN { -- this is the first run to be extracted
loc _ firstLen; base[0] _ [loc, x[first].looks]; index _ 1 }
ELSE {
loc _ base[index-1].after + firstLen;
IF base[index-1].looks=x[first].looks -- merge runs
THEN base[index-1].after _ loc
ELSE { base[index] _ [loc, x[first].looks]; index _ index+1 }};
IF first=last THEN RETURN [index];
IF (xloc _ x[first].after) = loc THEN { -- can simply copy runs
numRuns: NAT;
IF (numRuns _ last-first-1) > 0 THEN {
CopyRuns[to:base, toLoc:index,
from:@x, fromLoc:first+1, nRuns: numRuns];
index _ index+numRuns; loc _ base[index-1].after }}
ELSE FOR i: NAT IN (first..last) DO
loc _ loc + (next _ x[i].after) - xloc; xloc _ next;
base[index] _ [loc, x[i].looks];
index _ index+1; ENDLOOP;
base[index] _  [loc+lastLen, x[last].looks];
RETURN [index+1] };
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 _ ExtractRuns[base,x.base,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 _ ExtractRuns[base,x.base,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 _ ExtractRuns[base,x.replace,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 _ ExtractRuns[base,x.base,start,subLen,index]; 
start _ xstart; len _ len-subLen};
IF start < (xend _ xstart+x.len) THEN {
subLen _ MIN[xend-start,len];
index _ ExtractRunsAfterChanges[
base,x.base,x.remove,x.add,start,subLen,index]; 
start _ xend; len _ len-subLen};
ref _ x.base; LOOP};
ENDCASE => ERROR;
ENDCASE => ERROR;
ENDLOOP};

NewBase: PUBLIC PROC [runs: NAT] RETURNS [BaseRuns] = {
RETURN [pZone.NEW[base RunsBody[runs]]];
};

BaseRun: PUBLIC PROC
[x: BaseRuns, index: Offset, lower: NAT _ 0, upper: NAT _ LAST[NAT]]
RETURNS [NAT] = {
len: NAT;
size: Offset;
IF index = 0 THEN RETURN [0];
IF (len_x.length) <= 1 THEN RETURN [0];
IF index+1 >= (size_TbaseSize[x]) THEN RETURN[len-1];
IF upper >= len THEN upper _ len-1;
IF lower > 0 AND x[lower-1].after > index THEN lower _ 0;
DO -- always know index is in run between lower and upper inclusive
run: NAT _ (upper+lower)/2;
IF index < x[run].after THEN upper _ run ELSE lower _ run+1;
IF upper=lower THEN RETURN[upper];
ENDLOOP };

CopyRuns: PUBLIC PROC [to, from: BaseRuns, toLoc, fromLoc, nRuns: NAT] = TRUSTED {
RunsOffset: NAT = SIZE[base RunsBody[0]];
nLeft: NAT;
IF nRuns=0 THEN RETURN;
IF fromLoc >= from.length OR toLoc >= to.length THEN ERROR;
nLeft _ nRuns-1;
to[toLoc+nLeft] _ from[fromLoc+nLeft]; -- bounds check
PrincOpsUtils.LongCOPY[
from: LOOPHOLE[from,LONG POINTER]+fromLoc*SIZE[Run]+RunsOffset,
to: LOOPHOLE[to,LONG POINTER]+toLoc*SIZE[Run]+RunsOffset,
nwords: nLeft*SIZE[Run]]};

InsertRun: PUBLIC PROC [base: BaseRuns, len: Offset, looks: Looks, index: NAT]
RETURNS [NAT] = { -- value is next index
IF index=0 THEN { base[0] _ [len,looks]; index _ 1 }
ELSE {
loc: Offset _ base[index-1].after + len;
IF base[index-1].looks=looks -- merge runs
THEN base[index-1].after _ loc
ELSE { base[index] _ [loc,looks]; index _ index+1 }};
RETURN [index]};

FindBaseRuns: PUBLIC PROC [x: BaseRuns, start, len: Offset]
RETURNS [first, last: NAT] = {
first _ BaseRun[x, start];
last _ IF len>1 THEN BaseRun[x, start+len-1, first] ELSE first };

BaseRunLengths: PUBLIC PROC [x: BaseRuns, start, len: Offset, first, last: NAT]
RETURNS [firstLen, lastLen: Offset] = {
IF first=last THEN RETURN[len,len];
RETURN[x[first].after-start, start+len-x[last-1].after] };

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

ModifyLooks: PUBLIC PROC [old, remove, add: Looks] RETURNS [Looks] = TRUSTED {
oldlks: Lks _ LOOPHOLE[old];
addlks: Lks _ LOOPHOLE[add];
remlks: Lks _ LOOPHOLE[remove];
newlks: Lks;
newlks[0] _ Basics.BITOR[addlks[0],Basics.BITAND[Basics.BITNOT[remlks[0]],oldlks[0]]];
newlks[1] _ Basics.BITOR[addlks[1],Basics.BITAND[Basics.BITNOT[remlks[1]],oldlks[1]]];
RETURN [LOOPHOLE[newlks]];
};

MergeChanges: PUBLIC PROC [oldrem, oldadd, rem, add: Looks]
RETURNS [newrem, newadd: Looks] = TRUSTED { 
oldaddlks: Lks _ LOOPHOLE[oldadd];
oldremlks: Lks _ LOOPHOLE[oldrem];
remlks: Lks _ LOOPHOLE[rem];
addlks: Lks _ LOOPHOLE[add];
newremlks, newaddlks: Lks;
newremlks[0] _ Basics.BITOR[oldremlks[0],remlks[0]];
newremlks[1] _ Basics.BITOR[oldremlks[1],remlks[1]];
newaddlks[0] _ Basics.BITOR[addlks[0],Basics.BITAND[Basics.BITNOT[remlks[0]],oldaddlks[0]]];
newaddlks[1] _ Basics.BITOR[addlks[1],Basics.BITAND[Basics.BITNOT[remlks[1]],oldaddlks[1]]];
RETURN [LOOPHOLE[newremlks], LOOPHOLE[newaddlks]];
};

END.

 TextLooksBasicImpl.mesa
written by Bill Paxton, February 1981
Bill Paxton,  7-Dec-81 11:33:25
Maxwell, January 5, 1983 3:55 pm
Russ Atkinson, July 25, 1983 3:41 pm

-- replacing the replacement
-- stops counting when exceeds limit
-- if merge is true, then doesn't count first run if its looks=firstLooks
-- now extract the runs
-- modified looks are == (old & ~remove) v add
--	((lks & ~oldrem) v oldadd) & ~rem) v add ==
--		lks & ~(oldrem v rem)) v ((oldadd & ~rem) v add
--	thus, newrem _ oldrem v rem, newadd _ (oldadd & ~rem) v add
�Ê
…˜š
Ïc™Jš
�%™%Jš
�™J™ J™$J™—š
Ïk	˜	J˜Jš
œ˜J˜
J˜—J˜šœž
˜!Jšžœ3˜:Jšžœ˜#Jšžœ
˜Jšœ
žœ
žœ˜)—J˜šÏnœžœ
ž˜Jšœ<žœ˜OJšžœ˜Jšœžœžœ
˜J˜Jšœžœ
˜J˜J˜!šŸœžœžœ
˜4Jšžœžœ
žœ
˜˜J˜;—Jšžœ˜—šŸœžœ
žœ
˜ Jš	œžœžœžœžœ˜0Jšœžœ˜!Jšžœ˜—šŸœžœ˜%Jšžœ	žœ2˜A—šŸœžœžœ˜6J˜J˜
J˜GJš
žœžœžœ
žœžœ˜<J˜'J˜(J˜+Jšžœžœ
žœ
˜Jšžœ%žœ
žœ
˜2Jšžœ
˜—Jšžœ
žœ
žœ#˜:šžœ	žœ
�˜-Jšžœžœ
žœ
�˜/šžœ˜Jšžœžœ	�˜9Jšžœ
žœžœ�˜3Jšžœ�˜)——Jšžœžœ
žœžœ
žœ
žœ˜/J˜<šžœž˜Jšœž˜Jšœ(žœ˜.J˜J˜šžœžœ
ž˜Jš
žœžœžœ
žœ	žœžœ
ž˜=˜J˜J˜šžœžœžœ˜/Jš
�™Jšœ3žœ
˜8—šžœ
žœ�˜7Jšžœ%žœ
žœ˜2J˜&J˜——šœ�,˜8J˜šžœžœžœ
˜šœ!žœ
žœ
žœ˜2šœžœ˜ J˜&————Jšžœžœ
˜Jšžœ
˜Jšžœ
˜—š	žœ	žœ
žœ%žœ
ž˜?J˜—Jšžœžœ
žœ˜*šžœžœ˜*J˜-——Jšžœžœ
žœ
žœ˜J˜2J˜J˜+J˜ Jšžœžœ
žœ
˜Jšžœžœ
žœ
˜+Jšžœ
˜J˜—šŸ	œžœ
ž˜˜;Jšœžœžœ˜1—Jšžœžœ˜=Jš
�$™$Jš
�I™IJ˜
J˜
šžœ˜Jšžœžœžœ˜1šžœžœ
žœ˜Jš	œžœžœžœžœ˜2Jšžœžœ
˜"—Jšžœžœžœ
ž˜ ˜	Jšœ
žœ
˜Jšœžœ*˜3J˜-J˜Jšžœžœžœ	˜4Jšžœžœ˜'—šœžœžœ
ž˜˜Jšœžœ#˜,Jšœ(žœ˜.—˜J˜Jšœžœ#˜,šžœžœ˜J˜Jšžœžœžœ˜.˜#J˜2—Jšœžœžœ
žœ
˜*J˜3—Jšœ#žœ˜*—˜J˜J˜Jšœžœ#˜,šžœžœ˜J˜ Jšžœžœžœ˜,˜#J˜2—Jšœžœžœ
žœ
˜*J˜J˜"—šžœžœ˜J˜J˜šžœžœ˜Jšœžœ˜$—˜#J˜2—Jšœžœžœ
žœ
˜*J˜1—Jšœ0žœ˜6—˜J˜J˜Jšœžœ#˜,šžœžœ˜Jšžœ žœžœ˜=˜#J˜2—Jšœžœžœ
žœ
˜*J˜J˜"—šžœžœ˜'Jšœ	žœ˜˜/˜J˜%——Jšœžœžœ
žœ
˜*J˜1—Jšœžœ˜—Jšžœžœ
˜—Jšžœžœ˜Jšžœ˜	J˜——šŸœžœ
ž˜Jšœ7žœ˜?Jšžœžœžœ�˜0šžœ
˜Jšžœžœ
žœ	˜šžœžœ
žœ
�˜#Jšžœ(˜.—Jšžœžœ
ž˜˜	J˜+Jšœ
žœ
˜Jšœžœ*˜3J˜-J˜>Jš
�™šžœ	žœ�(˜:J˜<—šžœ˜J˜%šžœ$�
˜3Jšžœ˜—Jšžœ;˜?—Jšžœžœ
žœ	˜"šžœžœ�˜?Jšœ	žœ
˜
šžœžœ˜&˜J˜*—J˜3——š	žœ
žœžœ
žœž˜#J˜4J˜ Jšœžœ
˜—J˜,Jšžœ
˜—šœžœžœ
ž˜˜Jšœžœ#˜,Jšœ'žœ˜-—˜J˜Jšœžœ#˜,šžœžœ˜J˜Jšžœžœžœ˜-J˜4J˜"—Jšœ"žœ˜)—˜J˜J˜Jšœžœ#˜,šžœžœ˜J˜ Jšžœžœžœ˜+J˜5J˜"—šžœžœ˜J˜J˜šžœžœ˜Jšœžœ˜#—J˜5J˜ —Jšœ/žœ˜5—˜J˜J˜Jšœžœ#˜,šžœžœ˜Jšžœ žœžœ˜<J˜5J˜"—šžœžœ˜'Jšœ	žœ˜˜ J˜0—J˜ —Jšœžœ˜—Jšžœžœ
˜—Jšžœžœ
˜Jšžœ˜	J˜——š
Ÿœžœ
žœžœžœ˜7Jšžœžœ˜(Jš
œ˜J˜—šŸœžœ
ž˜Jš	œ$žœ
žœžœ
žœ˜DJšžœžœ˜Jšœžœ
˜	J˜
Jšžœžœ
žœ˜Jšžœžœ
žœ˜'Jšžœ žœ
žœ˜5Jšžœžœ˜#Jšžœžœžœ˜9šžœ
�@˜CJšœžœ˜Jšžœžœ
žœ˜<Jšžœ
žœ
žœ˜"Jšžœ˜
J˜——š
Ÿœžœ
žœ-žœžœ˜RJšœžœžœ˜)Jšœžœ
˜Jšžœ	žœ
žœ
˜Jšžœžœžœ
žœ
˜;J˜Jšœ'�˜6š
œ˜Jš	œžœžœ
žœ
žœ˜?Jš	œžœžœ
žœžœ˜9Jšœžœ˜J˜——šŸ	œžœ
žœ4žœ
˜NJšžœžœ�˜(Jšžœ	žœ%˜4šžœ˜J˜(šžœ�
˜*Jšžœ˜—Jšžœ1˜5—Jšžœ
˜J˜—šŸœžœ
žœ"˜;Jšžœžœ˜J˜Jšœžœžœ žœ	˜AJ˜—šŸœžœ
žœ0žœ
˜OJšžœ ˜'Jšžœžœ
žœ
˜#Jšžœ4˜:J˜—Jš	œžœžœžœ
žœ
˜%J˜š
Ÿœžœ
žœžœžœ˜NJš
�.™.Jšœžœ˜Jšœžœ˜Jšœžœ	˜J˜Jšœžœžœžœ˜VJšœžœžœžœ˜VJšžœžœ
˜Jš
œ˜J˜—šŸœžœ
žœ"˜;Jšžœžœ˜,—Jš
�.™.Jš
�3™3š
�>™>Jšœžœ	˜"Jšœžœ	˜"Jšœžœ˜Jšœžœ˜J˜Jšœžœ˜4Jšœžœ˜4Jšœžœžœžœ˜\Jšœžœžœžœ˜\Jšžœžœ
žœ
˜2Jš
œ˜J˜—Jšžœ
˜J˜—…—-Š=/