DIRECTORY
EditSpan,
EditSpanSupport,
TextEdit,
RopeEdit,
TiogaItemClass,
TiogaBasicClass,
TiogaNode,
TiogaNodeOps,
TiogaTreeOps,
TreeSlice;

EditSpanSupportImpl: CEDAR MONITOR 
IMPORTS EditSpan, TiogaNodeOps, TiogaTreeOps, TreeSlice
EXPORTS EditSpanSupport
SHARES TiogaNode =
BEGIN
OPEN EditSpanSupport, TreeSlice, EditSpan;

NeedNestingChange: PUBLIC PROC [before, after, top, bottom: Slice, nesting: INTEGER, depth: NAT]
RETURNS [NeededNestingChange] = {
bandStart, afterOver: INTEGER;
topLen, botLen: NAT;
nesting _ MIN[1,nesting];
topLen _ top.length; botLen _ bottom.length;
bandStart _ before.length+nesting-(topLen-depth);
IF bandStart <= 0 THEN RETURN [needNest]; -- must be at least 1
afterOver _ after.length-(botLen-depth+bandStart);
IF afterOver > 1 THEN RETURN [needUnNest];
RETURN [ok] };

Splice: PUBLIC PROC [before, after: Slice, beforeStart, afterStart: NAT _ 0] = {
a, b: Ref;
beforeLen, afterLen: NAT;
beforeLen _ before.length - beforeStart;
afterLen _ after.length - afterStart;
IF before.kind # before OR after.kind # after THEN ERROR;
IF afterLen > beforeLen+1 THEN ERROR; -- cannot have gaps in tree
b _ TreeSlice.LastOfSlice[before];
IF afterLen = beforeLen+1 THEN { -- adopt children
a _ TreeSlice.LastOfSlice[after];
IF a # NIL AND beforeLen > 0 THEN TiogaTreeOps.LastSibling[a].next _ b }
ELSE a _ NIL;
WITH b SELECT FROM
br: RefBranchNode => {
brchild: RefBranchNode = TiogaNodeOps.NarrowToBranchNode[a];
IF a # NIL AND brchild=NIL THEN ERROR;
br.child _ brchild };
ls: TiogaNode.RefListNode => ls.contents _ a;
bx: TiogaNode.RefBoxNode => bx.contents _ a;
ENDCASE => ERROR;
IF beforeLen=0 THEN RETURN;
FOR i: NAT _ beforeLen-1, i-1 DO -- do successors
a, b: Ref;
b _ before[beforeStart+i];
IF i >= afterLen OR (a_after[afterStart+i])=NIL THEN { -- no successor
IF i > 0 THEN { b.next _ before[beforeStart+i-1]; b.last _ TRUE }}
ELSE { -- has successor
IF a=b THEN RETURN;
IF i > 0 THEN TiogaTreeOps.LastSibling[a].next _ before[beforeStart+i-1];
b.next _ a; b.last _ FALSE };
IF i=0 THEN RETURN;
ENDLOOP };

ReplaceBand: PUBLIC PROC [before, after, top, bottom: Slice, nesting: INTEGER, event: Event] = {
depth: NAT;
fullBottom: Slice;
nesting _ MIN[1,nesting];
IF top.length >= before.length+nesting THEN ERROR;
depth _ MAX[1,before.length+nesting-top.length];
fullBottom _ TreeSlice.InsertPrefix[before,bottom,depth];
Splice[fullBottom,after];
Splice[before,top,depth];
FreeSlice[fullBottom] };

BadBand: PUBLIC ERROR = CODE;

DescribeBand: PUBLIC PROC [first, last: RefBranchNode]
RETURNS [before, after, top, bottom: Slice, nesting: INTEGER, depth: NAT] = {
BadBandError: PROC = {
ERROR BadBand [! UNWIND => {
FreeSlice[before]; FreeSlice[after];
FreeSlice[top]; FreeSlice[bottom] } ] };
pred: RefBranchNode _ TiogaTreeOps.Backward[first].back;
minDepth: NAT;
IF pred=NIL THEN ERROR BadBand; -- first is root node
IF pred=last THEN ERROR BadBand; -- this actually happened during testing!
[before,top] _ TreeSlice.MakeSlices[pred];
nesting _ top.length-before.length;
[bottom,after] _ TreeSlice.MakeSlices[last];
minDepth _ MIN[before.length,bottom.length];
FOR depth _ 0, depth+1 UNTIL depth >= minDepth DO
IF before[depth] # bottom[depth] THEN { -- check for legality
bot: Ref _ bottom[depth];
FOR node: Ref _ before[depth], TiogaTreeOps.Next[node] DO
SELECT node FROM
bot => EXIT;
NIL => BadBandError[]; -- last must come before first
ENDCASE;
ENDLOOP;
EXIT };
ENDLOOP;
IF depth=0 THEN BadBandError[]; -- different root nodes for first and last
IF TreeSlice.LastOfSlice[top] # first THEN ERROR;
IF before[before.length+nesting-2] # TiogaTreeOps.Parent[first] THEN ERROR;
IF TreeSlice.LastOfSlice[bottom] # last THEN ERROR };

DestSlices: PUBLIC PROC [dest: RefBranchNode, where: Place]
RETURNS [before, after: Slice, nesting: INTEGER] = {
SELECT where FROM
after => { [before,after] _ TreeSlice.MakeSlices[dest]; nesting _ 0 };
child => { [before,after] _ TreeSlice.MakeSlices[dest]; nesting _ 1 };
before => {
pred: RefBranchNode _ TiogaTreeOps.Backward[dest].back;
[before,after] _ TreeSlice.MakeSlices[pred];
nesting _ after.length-before.length };
ENDCASE => ERROR };

CreateDest: PUBLIC PROC [depth: NAT] RETURNS [dest: BranchLoc] = {
node: RefBranchNode;
UNTIL depth = 0 DO 
child: RefBranchNode _ TiogaNodeOps.NewBranchNode[];
IF node # NIL THEN { node.child _ child; child.next _ node };
node _ child; depth _ depth-1; ENDLOOP;
RETURN [[node,TiogaNode.NodeItself]] };

CopySpan: PUBLIC PROC [span: TreeSpan] RETURNS [result: TreeSpan] = {
node, sourceFirst, sourceLast, child, new, prev, parent, first: Ref;
firstLoc, lastLoc: Offset;
br: RefBranchNode;
sourceFirst _ span.start.node; firstLoc _ span.start.where;
sourceLast _ span.end.node; lastLoc _ span.end.where;
IF (node _ sourceFirst)=NIL OR sourceLast=NIL THEN RETURN [TiogaTreeOps.nullSpan];
parent _ -- parent for the copied span
IF TiogaNodeOps.IsBasic[node] THEN
TiogaNodeOps.NewListNode[TiogaNode.invalidItemClassID]
ELSE TiogaNodeOps.NewBranchNode[];
DO -- create new node each time through the loop
WITH node SELECT FROM --  create new node of same kind as old node
br: RefBranchNode => {
newBr: RefBranchNode;
new _ newBr _ TiogaNodeOps.NewBranchNode[] };
tx: TiogaNode.RefTextNode => {
newTx: TiogaNode.RefTextNode;
new _ newTx _ TiogaNodeOps.NewTextNode[tx.class];
newTx.rope _ tx.rope; newTx.runs _ tx.runs };
bx: TiogaNode.RefBoxNode => {
newBx: TiogaNode.RefBoxNode;
new _ newBx _ TiogaNodeOps.NewBoxNode[bx.class];
IF bx.data # NIL THEN { -- copy the data
itemClass: TiogaItemClass.ItemClass _ TiogaNodeOps.FetchItemClass[bx.class];
IF itemClass.copy#NIL THEN itemClass.copy[bx, newBx] }};
ls: TiogaNode.RefListNode => {
newLs: TiogaNode.RefListNode;
new _ newLs _ TiogaNodeOps.NewListNode[ls.class];
IF ls.data # NIL THEN { -- copy the data
itemClass: TiogaItemClass.ItemClass _ TiogaNodeOps.FetchItemClass[ls.class];
IF itemClass.copy#NIL THEN itemClass.copy[ls, newLs] }};
bs: TiogaNode.RefBasicNode => {
newBs: TiogaNode.RefBasicNode;
new _ newBs _ TiogaNodeOps.NewBasicNode[bs.class];
IF bs.data # NIL THEN { -- copy the data
basicClass: TiogaBasicClass.BasicClass _ TiogaNodeOps.FetchBasicClass[bs.class];
IF basicClass.copy#NIL THEN basicClass.copy[bs, newBs] }};
ENDCASE => ERROR;
Inherit[node,new,TRUE]; -- inherit properties from node
IF prev#NIL THEN { prev.last _ FALSE; prev.next _ new } -- insert new into tree as next sibling of prev
ELSE WITH parent SELECT FROM -- insert new into tree as first child/contents of parent
br: RefBranchNode => WITH new SELECT FROM
newItem: TiogaNode.RefItemNode => br.contents _ newItem;
newBr: RefBranchNode => br.child _ newBr;
ENDCASE => ERROR;
bx: TiogaNode.RefBoxNode => bx.contents _ new;
ls: TiogaNode.RefListNode => ls.contents _ new;
ENDCASE => ERROR;
new.new _ new.last _ TRUE; new.next _ parent; prev _ new;
IF node=sourceFirst THEN first _ new;
IF node=sourceLast THEN RETURN [[[first,firstLoc],[new,lastLoc]]];
IF (child _ TiogaTreeOps.Contents[node])=NIL AND
(br _ TiogaNodeOps.NarrowToBranchNode[node])#NIL THEN
child _ TiogaTreeOps.BranchChild[br]; -- use Contents and BranchChild to get internal rep's created
IF child#NIL THEN { node _ child; parent _ new; prev _ NIL } -- descend in the tree
ELSE DO -- move to next node, sibling or up* then sibling
isBranch: BOOL;
IF ~node.last THEN { node _ TiogaTreeOps.Next[node]; EXIT }; -- use Next to get internal rep created
prev _ parent;
IF (parent _ parent.next) = NIL THEN { -- need a new parent
parentBr: RefBranchNode _ TiogaNodeOps.NewBranchNode[];
parent _ parentBr;
WITH prev SELECT FROM
br: RefBranchNode => parentBr.child _ br;
it: TiogaNode.RefItemNode => parentBr.contents _ it;
bs: TiogaNode.RefBasicNode => ERROR; -- cannot happen since prev comes from previous parent
ENDCASE => ERROR;
prev.next _ parent };
isBranch _ TiogaNodeOps.IsBranch[node];
IF (node _ node.next -- the parent --) = NIL THEN ERROR; -- bad arg span; failed to find sourceLast
new _ new.next; -- move new to its parent also
IF ~isBranch THEN WITH node SELECT FROM
br: RefBranchNode => IF br.child # NIL THEN {
node _ TiogaTreeOps.BranchChild[br]; -- use BranchChild to get internal rep created
parent _ new; prev _ NIL; EXIT };
ENDCASE;
ENDLOOP;
ENDLOOP };

DoSplits: PUBLIC PROC [alpha, beta: TreeSpan, event: Event]
RETURNS [newalpha, newbeta: BranchSpan] = {

Break: PROC [root: RefBranchNode, node: Ref, before: BOOL] RETURNS [newLoc: BranchLoc] = {
newLoc.node _ BreakStatement[alphaRoot, node, before, event];
newLoc.where _ IF newLoc.node=node THEN NodeItself ELSE 0 };

MakeTextSplit: PROC [root: RefBranchNode, node: Ref, offset: Offset] = {

FixLoc: PROC [old: TreeLoc] RETURNS [newLoc: TreeLoc] = {
where: Offset;
IF old.node # node THEN RETURN [old];
SELECT where _ old.where FROM
= NodeItself => ERROR;
< offset => RETURN [[node,where]];
ENDCASE => RETURN [[new,where-offset]] };

new: Ref;
IF node=NIL OR offset=NodeItself OR ~TiogaNodeOps.IsText[node] THEN RETURN;
new _ BreakTextNode[root, [node, offset], event];
alpha.start _ FixLoc[alpha.start];
alpha.end _ FixLoc[alpha.end];
beta.start _ FixLoc[beta.start];
beta.end _ FixLoc[beta.end] };

alphaRoot, betaRoot: RefBranchNode;
alphaRoot _ TiogaTreeOps.Root[alpha.start.node];
betaRoot _ TiogaTreeOps.Root[beta.start.node];
MakeTextSplit[alphaRoot, alpha.start.node, alpha.start.where];
MakeTextSplit[betaRoot, beta.start.node, beta.start.where];
MakeTextSplit[alphaRoot, alpha.end.node, alpha.end.where+1];
MakeTextSplit[betaRoot, beta.end.node, beta.end.where+1];
newalpha.start _ Break[alphaRoot, alpha.start.node, TRUE];
newalpha.end _ Break[alphaRoot, alpha.end.node, FALSE];
newbeta.start _ Break[betaRoot, beta.start.node, TRUE];
newbeta.end _ Break[betaRoot, beta.end.node, FALSE] };

DoSplitsForMove: PUBLIC PROC [dest: TreeLoc, source: TreeSpan, where: Place, event: Event]
RETURNS [newdest: BranchLoc, newsource: BranchSpan] = {
destSpan: TreeSpan;
desBranchSpan: BranchSpan;
SELECT where FROM
before => destSpan _ [dest, TiogaTreeOps.nullLoc];
after => destSpan _ [TiogaTreeOps.nullLoc, dest];
ENDCASE => ERROR;
[desBranchSpan, newsource] _ DoSplits[destSpan, source, event];
newdest _ IF where=before THEN desBranchSpan.start ELSE desBranchSpan.end };

ReMerge: PUBLIC PROC [
alpha, beta: BranchSpan, merge: RefBranchNode, event: Event, tail: BOOL _ FALSE]
RETURNS [newalpha, newbeta: BranchSpan] = {
FixNode: PROC [old: RefBranchNode] RETURNS [RefBranchNode] = INLINE {
RETURN [IF old=merge THEN breakStatement ELSE old] };
break: Ref;
breakStatement: RefBranchNode;
IF tail THEN merge _ TiogaTreeOps.Forward[merge].nx;
break _ JoinStatements[TiogaTreeOps.Root[merge], merge, event].node;
WHILE (breakStatement _ TiogaNodeOps.NarrowToBranchNode[break])=NIL DO
break _ TiogaTreeOps.Parent[break]; ENDLOOP;
newalpha.start _ [FixNode[alpha.start.node], alpha.start.where];
newalpha.end _ [FixNode[alpha.end.node], alpha.end.where];
newbeta.start _ [FixNode[beta.start.node], beta.start.where];
newbeta.end _ [FixNode[beta.end.node], beta.end.where] };

UndoSplits: PUBLIC PROC [alpha, beta: BranchSpan, event: Event] = {
IF alpha.start.where # NodeItself THEN
[alpha,beta] _ ReMerge[alpha,beta,alpha.start.node,event];
IF beta.start.where # NodeItself THEN
[alpha,beta] _ ReMerge[alpha,beta,beta.start.node,event];
IF alpha.end.where # NodeItself THEN
[alpha,beta] _ ReMerge[alpha,beta,alpha.end.node,event,TRUE];
IF beta.end.where # NodeItself THEN
[alpha,beta] _ ReMerge[alpha,beta,beta.end.node,event,TRUE];
};

UndoSplitsForMove: PUBLIC PROC [dest: BranchLoc, source: BranchSpan, where: Place, event: Event] = {
destSpan: BranchSpan;
SELECT where FROM
before => destSpan _ [dest, TiogaTreeOps.nullBranchLoc];
after => destSpan _ [TiogaTreeOps.nullBranchLoc, dest];
ENDCASE => ERROR;
UndoSplits[destSpan,source,event] };

END.


lEditSpanSupportImpl.mesa; written by Bill Paxton, June 1981
edited by McGregor, February 14, 1983 1:59 pm
edited by Bill Paxton, August 10, 1983 4:25 pm
edited by Maxwell, January 5, 1983 12:47 pm
join slices
make after[afterStart+i] be successor of before[beforeStart+i]
if more after's than before's, adopt as children of last before
do Splices to insert (top-bottom) between (before-after)
nesting tells how to offset last of before vs. last of top
before[before.length-1+nesting] will be predecessor of top[top.length-1]

top[top.length-1] = first
before[before.length-1+nesting] = predecessor of first 
bottom[bottom.length-1] = last
raises BadBand error if last doesn't follow first in tree structure
or if first or last is root node

check assertions

where = after means insert starting as sibling after dest
where = child means insert starting as child of dest
where = before means insert starting as sibling before dest

create tree of parents
check if done
go to next node
take care of parent
check if have just finished the contents of a branch and now need to do children
split off head or tail sections of spans so have spans of complete branches	
Use newLoc.where to encode whether or not broke the statement.
This should really be changed so that it will use the info saved on the undo log.  This doesn't currently take care of break from way down in the contents.
�Ê(˜Jš
œ;™;Jš
œ-™-Jš
œ.™.Jš
œ+™+J˜Jš
Ïk	˜	J˜	J˜J˜	J˜	J˜J˜J˜
J˜
J˜
J˜
J˜šœ�
œ
˜#Jš�œ0˜7Jš�œ˜Jš�œ˜—Jš
�˜Jš�œ&˜*J˜š
Ïnœ�œ
�œ.�œ	�œ
˜`Jš�œ˜!Jšœ�œ
˜Jšœ�œ
˜Jšœ
�œ˜J˜,J˜1Jš�œ�œ
�œ
Ïc˜?J˜2Jš�œ�œ
�œ˜*Jš�œ˜J˜—šžœ�œ
�œ1�œ	˜PJš
œ™Jš
œ>™>Jš
œ?™?Jš
œ
˜
Jšœ�œ
˜J˜(J˜%Jš�œ�œ�œ
�œ
˜9Jš�œ�œ
�œŸ˜AJ˜"š�œ�œŸ˜2J˜!Jš�œ�œ
�œ�œ'˜H—Jš�œ�œ
˜
š�œ�œ
�˜˜J˜<Jš�œ�œ
�œ	�œ
�œ
�œ
˜&Jš
œ˜—J˜-J˜,Jš�œ�œ
˜—Jš�œ
�œ
�œ
˜š�œ�œ�œ
Ÿ˜1Jš
œ
˜
J˜š	�œ�œ�œ
�œŸ˜FJš�œ�œ.�œ˜B—š�œŸ˜Jš�œ�œ
�œ
˜Jš�œ�œ<˜IJšœ�œ˜—Jš�œ�œ
�œ
˜Jš�œ˜
J˜——šžœ�œ
�œ.�œ˜`Jš
œ8™8Jš
œ:™:Jš
œH™HJšœ�œ
˜J˜Jšœ
�œ˜Jš�œ%�œ
�œ
˜2Jšœ�œ%˜0J˜9J˜J˜J˜J˜—Jšœ	�œ
�œ�œ
˜J˜šžœ�œ
�œ˜6Jš�œ.�œ	�œ˜MJ™Jš
œ™Jš
œ7™7Jš
œ™Jš
œC™CJš
œ ™ J™šžœ�œ˜š�œ�œ˜J˜$J˜(——Jš
œ8˜8Jšœ
�œ
˜Jš	�œ�œ
�œ
�œ
Ÿ˜5Jš�œ�œ
�œ
Ÿ)˜JJ˜*J˜#J˜,Jšœ�œ˜,š�œ�œ�˜1š�œ�œŸ˜=Jš
œ˜š�œ4�˜9š�œ�˜Jšœ�œ
˜Jš�œŸ˜5Jš�œ
˜—Jš�œ
˜—Jš�œ˜—Jš�œ
˜—Jš�œ	�œŸ*˜JJš
œ™Jš�œ$�œ
�œ
˜1Jš�œ>�œ
�œ
˜KJš�œ&�œ
�œ˜5J˜—šž
œ�œ
�œ$˜;Jš�œ!�œ˜4J™Jš
œ9™9Jš
œ4™4Jš
œ;™;J™Jš�œ�˜J˜FJ˜F˜Jš
œ7˜7J˜,J˜'—Jš�œ�œ˜J˜—š
ž
œ�œ
�œ	�œ�œ˜BJš
œ™Jš
œ˜š�œ�œ
˜Jš
œ4˜4Jš�œ�œ
�œ+˜=Jšœ�œ
˜'—Jš�œ!˜'J˜—šžœ�œ
�œ�œ˜EJš
œD˜DJ˜J˜Jš
œ;˜;Jš
œ5˜5Jš�œ�œ
�œ�œ
�œ
�œ˜Ršœ	Ÿ˜&š�œ�˜"Jš
œ6˜6—Jš�œ˜"—š�œ
Ÿ-˜0š�œ�œ
�œ
Ÿ,˜B˜J˜J˜-—˜J˜Jš
œ1˜1J˜-—˜J˜Jš
œ0˜0š�œ�œ
�œŸ˜(J˜LJš�œ�œ
�œ˜8——˜J˜Jš
œ1˜1š�œ�œ
�œŸ˜(Jš
œL˜LJš�œ�œ
�œ˜8——˜J˜Jš
œ2˜2š�œ�œ
�œŸ˜(Jš
œP˜PJš�œ�œ
�œ˜:——Jš�œ�œ
˜—Jšœ�œŸ˜7Jš	�œ�œ
�œ�œŸ/˜gš	�œ
�œ�œ
�œ
Ÿ9˜Všœ�œ�œ
�˜)J˜8J˜)Jš�œ�œ
˜—J˜.J˜/Jš�œ�œ
˜—Jšœ�œ ˜9J™
Jš�œ�œ
˜%Jš�œ�œ
�œ$˜BJ™š�œ'�œ
�˜0Jšœ-�œ
�˜5Jšœ&Ÿ=˜c—Jš	�œ�œ
�œ&�œŸ˜Sš�œ
�œ
Ÿ1˜9Jšœ
�œ
˜Jš�œ�œ#�œŸ'˜dJ™J˜š�œ�œ
�œŸ˜;Jš
œ7˜7Jš
œ˜š�œ�œ
�˜Jš
œ)˜)Jš
œ4˜4Jšœ�œŸ6˜[Jš�œ�œ
˜—J˜—J™PJ˜'Jš�œŸœ�œ
�œ
�œŸ*˜cJšœŸ˜.š	�œ�œ
�œ�œ
�˜'šœ�œ�œ
�œ˜-Jšœ%Ÿ.˜SJšœ�œ�œ˜!—Jš�œ
˜—Jš�œ
˜—Jš�œ˜
J˜——šžœ�œ
�œ&˜;Jš�œ$˜+Jš
œL™LJ˜šžœ�œ*�œ�œ˜ZJš
œ=˜=Jš
œ>™>Jšœ�œ�œ�œ˜<—J˜Jšž
œ�œ5˜H˜šžœ�œ�œ˜9J˜Jš�œ�œ
�œ˜%š�œ�˜Jšœ�œ
˜Jšœ�œ˜"Jš�œ�œ˜)J˜——Jš
œ	˜	Jš�œ�œ
�œ�œ�œ
�œ
˜KJš
œ1˜1J˜"J˜J˜ J˜J˜—Jš
œ#˜#Jš
œ0˜0Jš
œ.˜.Jš
œ>˜>Jš
œ;˜;Jš
œ<˜<Jš
œ9˜9Jšœ4�œ˜:Jšœ0�œ˜7Jšœ1�œ˜7Jšœ-�œ˜6J˜—šžœ�œ
�œ>˜ZJš�œ0˜7Jš
œ˜Jš
œ˜š�œ�˜J˜2J˜1Jš�œ�œ
˜—Jš
œ?˜?Jšœ
�œ�œ�œ˜LJ˜—šžœ�œ
�œ˜JšœC�œ�œ
˜PJš�œ$˜+šžœ�œ�œ�œ˜EJš�œ�œ�œ�œ˜5—Jš
œ˜Jš
œ˜Jš�œ�œ(˜4Jš
œD˜Dš�œ;�œ
�˜FJšœ$�œ
˜,—Jš
œ@˜@Jš
œ:˜:Jš
œ=˜=Jš
œ9˜9J˜—šž
œ�œ
�œ,˜CJš
Ïb›
™›
š�œ �˜&J˜:—š�œ�˜%J˜9—š�œ�˜$Jšœ7�œ˜=—š�œ�˜#Jšœ6�œ˜<—Jš
œ˜J˜—šžœ�œ
�œF˜dJš
œ˜š�œ�˜J˜8J˜7Jš�œ�œ
˜—J˜$J˜—Jš�œ
˜J˜J˜—…—-Ð?d