[Cyan]<PreISLCedar>TempTioga>TextLooksBasicImpl.mesa!1

-- TextLooksBasicImpl.mesa

-- written by Bill Paxton, February 1981

-- last edit by Bill Paxton, 7-Dec-81 11:33:25

Last Edited by: Maxwell, January 5, 1983 3:55 pm

DIRECTORY

Inline,

TextLooks,

TextLooksSupport;

TextLooksBasicImpl: CEDAR PROGRAM

IMPORTS TextLooks, TextLooksSupport, Inline

EXPORTS TextLooks, TextLooksSupport

SHARES TextLooks =

BEGIN OPEN TextLooks, TextLooksSupport;

ReplaceByRun: PUBLIC PROC [

dest: Runs, start, len, runLen, destSize: Offset,

inherit: BOOLEAN, looks: Looks]

RETURNS [Runs] = {

merge: BOOLEAN ← 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 {

-- replacing the replacement

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: BOOLEAN ← FALSE, firstLooks: Looks ← noLooks]

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

-- stops counting when exceeds limit

-- if merge is true, then doesn't count first run if its looks=firstLooks

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

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];

-- now extract the runs

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;

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

Inline.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 UNSPECIFIED;

ModifyLooks: PUBLIC PROC [old, remove, add: Looks] RETURNS [Looks] = TRUSTED {

-- modified looks are == (old & ~remove) v add

OPEN Inline;

oldlks: Lks ← LOOPHOLE[old];

addlks: Lks ← LOOPHOLE[add];

remlks: Lks ← LOOPHOLE[remove];

newlks: Lks;

newlks[0] ← BITOR[addlks[0],BITAND[BITNOT[remlks[0]],oldlks[0]]];

newlks[1] ← BITOR[addlks[1],BITAND[BITNOT[remlks[1]],oldlks[1]]];

RETURN [LOOPHOLE[newlks]] };

MergeChanges: PUBLIC PROC [oldrem, oldadd, rem, add: Looks]

RETURNS [newrem, newadd: Looks] = TRUSTED {

-- ((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

OPEN Inline;

oldaddlks: Lks ← LOOPHOLE[oldadd];

oldremlks: Lks ← LOOPHOLE[oldrem];

remlks: Lks ← LOOPHOLE[rem];

addlks: Lks ← LOOPHOLE[add];

newremlks, newaddlks: Lks;

newremlks[0] ← BITOR[oldremlks[0],remlks[0]];

newremlks[1] ← BITOR[oldremlks[1],remlks[1]];

newaddlks[0] ← BITOR[addlks[0],BITAND[BITNOT[remlks[0]],oldaddlks[0]]];

newaddlks[1] ← BITOR[addlks[1],BITAND[BITNOT[remlks[1]],oldaddlks[1]]];

RETURN [LOOPHOLE[newremlks], LOOPHOLE[newaddlks]] };

END.