DIRECTORY
Basics USING [CompareInt, Comparison, NonNegative],
XRope;
XRopeImpl: CEDAR PROGRAM
IMPORTS Basics, XRope
EXPORTS XRope
SHARES  XRope
= BEGIN OPEN XRope;

NonNeg: PROC [INT] RETURNS [INT] ~ Basics.NonNegative;

SingleSize: PROC [base: XROPE] RETURNS [INT, Text] ~ INLINE {
WITH base SELECT FROM text: Text => RETURN[text.size, text];
ENDCASE => RETURN[[(IF base=NIL THEN 0 ELSE base.size), NIL]];
};

CheckLongAdd: PROC [x, y: INT] RETURNS [INT] ~ INLINE {
RETURN[Basics.NonNegative[x+y]];
};

InlineDepth: PROC [base: XROPE] RETURNS [INTEGER] ~ TRUSTED INLINE {
IF base=NIL THEN RETURN[0];
WITH x: base SELECT FROM
substr => RETURN [x.depth];
concat => RETURN [x.depth];
replace => RETURN [x.depth];
ENDCASE => RETURN [1];
};

NoRope: PUBLIC ERROR = CODE;

emptyRope: Text ~ NEW[TextRep[0]];

NewText: PUBLIC PROC [size: INT] RETURNS [text: Text] = TRUSTED {
IF size = 0 THEN RETURN [emptyRope];
text _ NEW[TextRep[size]];
text.size _ size;
};

Substr: PUBLIC PROC [base: XROPE, start: INT _ 0, len: INT _ MaxLen]
RETURNS [new: XROPE] = TRUSTED {
size: INT _ InlineSize[base];
rem: INT _ NonNeg[size - NonNeg[start]];
depth: INTEGER _ 1;
IF len <= 0 THEN RETURN [emptyRope] ELSE IF len > rem THEN len _ rem;
IF start = 0 AND len = rem THEN RETURN [base];
IF len <= FlatMax THEN RETURN [Flatten[base, start, len]];
DO 
WITH x: x SELECT FROM
text => EXIT;
substr => {start _ start + x.start; base _ x.base};
concat => {
rem: INT _ x.pos - start;
IF rem > 0
THEN {IF len > rem THEN {depth _ x.depth; EXIT}; base _ x.base}
ELSE {start _ -rem; base _ x.rest};
};
replace => {
len1: INT _ x.start - start;
IF len1 > 0
THEN {
IF len > len1 THEN {depth _ x.depth; EXIT};
base _ x.base}
ELSE {
xnew: INT _ x.newPos;
len2: INT _ xnew - start;
IF len2 > 0
THEN {
IF len > len2 THEN {depth _ x.depth; EXIT};
start _ -len1;
base _ x.replace}
ELSE {
start _ x.oldPos - len2;
base _ x.base};
};
};
object => {
EXIT};
ENDCASE => ERROR NoRope;
IF start # 0 THEN LOOP;
IF len = InlineSize[base] THEN RETURN [base];
ENDLOOP;
[] _ NonNeg[start];
[] _ NonNeg[len];
new _ NEW[XRopeRep.substr _
[size: len, cases: substr[base: base, start: start, depth: depth + 1]]];
IF depth >= MaxDepth THEN new _ Balance[new];
};

Cat: PUBLIC PROC [r1, r2, r3, r4, r5: XROPE _ NIL] RETURNS [XROPE] ~ {
RETURN [Concat[Concat[r1,r2], Concat[Concat[r3, r4], r5]]]; 
};

Concat: PUBLIC PROC [base,rest: XROPE _ NIL] RETURNS [new: XROPE] ~ {
baseStr, restStr: Text;
baseLen, restLen, size: INT;
depth: INTEGER _ 1;
IF rest = NIL THEN RETURN [base];
[baseLen, baseStr] _ SingleSize[base];
IF baseLen = 0 THEN RETURN [rest];
[restLen, restStr] _ SingleSize[rest];
IF restLen = 0 THEN RETURN [base];
size _ CheckLongAdd[baseLen,restLen];
IF size <= FlatMax THEN {
str: Text ~ NewText[size];
index: NAT _ 0;
AddChar: ActionType ~ { str[index] _ c; index _ index+1 };
IF baseStr = NIL
THEN [] _ Map[base, 0, baseLen, AddChar]
ELSE FOR i: NAT IN [0..baseLen) DO str[index] _ baseStr[i]; index _ index+1 ENDLOOP;
IF restStr = NIL
THEN [] _ Map[rest, 0, restLen, AddChar]
ELSE FOR i: NAT IN [0..restLen) DO str[index] _ restStr[i]; index _ index+1 ENDLOOP;
RETURN [str]};
SELECT TRUE FROM
restLen < FlatMax =>
WITH base SELECT FROM
x: REF XRopeRep.concat =>
IF x.size-x.pos < FlatMax/2 THEN {
baseLen _ x.pos;
rest _ Concat[x.rest, rest];
base _ x.base;
};
ENDCASE;
baseLen < FlatMax =>
WITH base SELECT FROM
x: REF XRopeRep.concat =>
IF x.pos < FlatMax/2 THEN {
rest _ x.rest;
baseLen _ x.pos+baseLen;
base _ Concat[base, x.base];
};
ENDCASE;
ENDCASE;
[] _ NonNeg[size-baseLen];
depth _ MAX[InlineDepth[base], InlineDepth[rest]] + 1;
new _ NEW[XRopeRep.concat _
[size: size, cases: concat[base: base, rest: rest, pos: baseLen, depth: depth]]];
IF depth > MaxDepth THEN new _ Balance[new];
};

Replace: PUBLIC PROC [base: XROPE, start: INT _ 0, len: INT _ MaxLen, with: XROPE _ NIL] RETURNS [new: XROPE] ~ {
baseSize: INT _ InlineSize[base];
repSize:  INT _ InlineSize[with];
rem: INT _ NonNeg[baseSize - NonNeg[start]];
depth: INTEGER _ 0;
oldPos: INT _ start +
(IF len < 0 THEN len _ 0 ELSE IF len > rem THEN len _ rem ELSE len);
newPos: INT _ CheckLongAdd[start, repSize];
size: INT _ CheckLongAdd[baseSize-len, repSize];
IF size = repSize THEN RETURN [with];
IF len = 0 AND repSize = 0 THEN RETURN [base];  -- identity check
IF size <= FlatMax THEN {
str: Text ~ NewText[size];
index: NAT _ 0;
AddChar: ActionType ~ { str[index] _ c; index _ index+1 };
IF start > 0 THEN [] _ Map[base, 0, start, AddChar];
IF repSize > 0 THEN [] _ Map[with, 0, repSize, AddChar];
IF oldPos < baseSize THEN [] _ Map[base, oldPos, baseSize, AddChar];
RETURN [str]};
WITH base SELECT FROM
x: REF XRopeRep.replace => {
xnewPos: INT _ x.newPos;
xstart: INT _ x.start;
SELECT TRUE FROM
start <= xstart AND oldPos >= xnewPos => {
oldPos _ x.oldPos + (oldPos - xnewPos);
base _ x.base;
};
start = xnewPos => {
IF repSize + (xnewPos - xstart) <= FlatMax THEN {
with _ Concat[x.replace, with];
start _ xstart;
oldPos _ x.oldPos + len;
base _ x.base;
};
};
ENDCASE;
};
ENDCASE;
[] _ NonNeg[NonNeg[newPos] - NonNeg[start]];
[] _ NonNeg[NonNeg[oldPos] - start];
[] _ NonNeg[NonNeg[size] - newPos];
depth _ MAX[InlineDepth[base], InlineDepth[with]] + 1;
new _ NEW[XRopeRep.replace _
[size: size, cases: replace[base: base, replace: with, newPos: newPos, oldPos: oldPos, start: start,depth: depth]]];
IF depth > MaxDepth THEN new _ Balance[new];
};

Fetch: PUBLIC PROC [base: XROPE, index: INT _ 0] RETURNS [CHAR] ~ {
WITH base SELECT FROM
text: Text => RETURN[text[index]]; -- quick kill for a flat rope
ENDCASE => {
size: INT ~ IF base=NIL THEN 0 ELSE base.size;
[] _ NonNeg[index];
[] _ NonNeg[size-index-1];
};
DO
WITH base SELECT FROM
x: REF XRopeRep.text => RETURN[x[index]];
x: REF XRopeRep.substr => {index _ index + x.start; base _ x.base};
x: REF XRopeRep.concat  => {
IF index < x.pos THEN {base _ x.base; LOOP};
index _ index - x.pos;
base _ x.rest};
x: REF XRopeRep.replace => {
IF index < x.start THEN {base _ x.base; LOOP};
IF index < x.newPos THEN {
index _ index - x.start;
base _ x.replace;
LOOP};
index _ index - x.newPos + x.oldPos;
base _ x.base};
x: REF XRopeRep.object => RETURN [x.fetch[x.base, index]];
ENDCASE => ERROR NoRope;
ENDLOOP;
};

Map: PUBLIC PROC [base: XROPE, start: INT _ 0, len: INT _ MaxLen, action: ActionType] RETURNS [BOOL]  = TRUSTED {
rem: INT _ NonNeg[InlineSize[base] - NonNeg[start]];
IF len > rem THEN len _ rem;
WHILE len > 0 DO
WITH x: base SELECT FROM
text => {
st: NAT _ QShort[start];
FOR i: CARDINAL IN [st..st+QShort[len]) DO
IF action[QFetch[@x,i]] THEN RETURN [TRUE];
ENDLOOP;
RETURN [FALSE]};
node =>
WITH x: x SELECT FROM
substr => {start _ start + x.start; base _ x.base; LOOP};
concat  => {
xpos: INT _ x.pos;
IF start+len <= xpos THEN {base _ x.base; LOOP};
IF start < xpos THEN  {
subLen: INT _ xpos-start;
IF Map[x.base, start, subLen, action] THEN RETURN [TRUE];
start _ xpos; len _ len - subLen};
start _ start - xpos;
base _ x.rest;
};
replace => {
xstart: INT _ x.start;
xnew: INT _ x.newPos;
IF start < xstart THEN {
subLen: INT _ xstart-start;
IF subLen >= len THEN {base _ x.base; LOOP};
IF Map[x.base, start, subLen, action] THEN RETURN [TRUE];
start _ xstart; len _ len - subLen};
IF start < xnew THEN {
subLen: INT _ xnew-start;
st: INT _ start - xstart;
IF subLen >= len THEN {start _ st; base _ x.replace; LOOP};
IF Map[x.replace, st, subLen, action] THEN RETURN [TRUE];
start _ xnew; len _ len - subLen};
start _ start - xnew + x.oldPos;
base _ x.base};
object => {
map: MapType _ x.map;
data: REF _ x.base;
IF map # NIL THEN RETURN[map[data, start, len, action]];
{fetch: FetchType _ x.fetch;
FOR i: INT IN [start..start+len) DO
IF action[fetch[data, i]] THEN RETURN [TRUE];
ENDLOOP;
RETURN [FALSE]}};
ENDCASE => ERROR NoRope;
ENDCASE => ERROR NoRope;
ENDLOOP;
RETURN [FALSE];
};

Translate: PUBLIC PROC
[base: XROPE, start: INT _ 0, len: INT _ MaxLen, translator: TranslatorType _ NIL]
RETURNS [new: XROPE] = TRUSTED { 
index: INT _ start;
intRem: INT _ NonNeg[InlineSize[base] - NonNeg[start]];
rem: NAT _ intRem;
text: Text _ NIL;
IF len <= 0 OR rem = 0 THEN RETURN [emptyRope];
IF len < rem THEN rem _ len;
WITH base SELECT FROM
t: Text => {
short: CARDINAL _ index;
text _ NewText[rem];
FOR i: NAT IN [0..rem) DO
c: CHAR _ QFetch[t, short];
IF translator # NIL THEN c _ translator[c];
text[i] _ c;
short _ short + 1;
ENDLOOP;
new _ text;
};
ENDCASE => {
each: PROC RETURNS [CHAR] = TRUSTED {
c: CHAR _ InlineFetch[base, index];
index _ index + 1;
IF translator # NIL THEN c _ translator[c];
RETURN [c];
};
RETURN [FromProc[rem, each]];
}; 
};

Flatten: PUBLIC PROC [base: XROPE, start: INT _ 0, len: INT _ MaxLen]
RETURNS [rtn: Text] = TRUSTED {
size: INT _ InlineSize[base];
rem: INT _ NonNeg[size - NonNeg[start]];
IF len > rem THEN len _ rem;
IF start = 0 AND len = rem THEN {
IF base = NIL THEN RETURN [NIL];
IF base.tag = text THEN RETURN [LOOPHOLE[base]];
};
IF len <= 0 THEN RETURN [emptyRope];
rtn _ NewText[Short[len]];
rtn.length _ 0;
[] _ AppendChars[LOOPHOLE[rtn], base, start, len];
};

MakeRope: PUBLIC PROC
[base: REF, size: INT, fetch: FetchType, map: MapType, move: MoveType]
RETURNS [XROPE] = TRUSTED {
IF size = 0 THEN RETURN [emptyRope];
RETURN [NEW[Tobject _
[node[size: size, cases: object[base: base, fetch: fetch, map: map, move: move]]]]];
};

FromProc: PUBLIC PROC [len: INT, p: PROC RETURNS [CHAR], maxPiece: INT _ MaxLen] RETURNS [XROPE] = TRUSTED {
IF len <= 0 THEN RETURN [emptyRope];
IF maxPiece < FlatMax
THEN maxPiece _ FlatMax
ELSE IF maxPiece > LAST[NAT] THEN maxPiece _ LAST[NAT];
IF len <= maxPiece
THEN {
rtn: Text _ NewText[QShort[len]];
FOR i: NAT IN [0..QShort[len]) DO rtn[i] _ p[]; ENDLOOP;
RETURN [rtn]}
ELSE {
left: XROPE _ FromProc[len/2, p, maxPiece];
right: XROPE _ FromProc[(len+1)/2, p, maxPiece];
RETURN [Concat[left, right]]};
};

FromChar: PUBLIC PROC [c: CHAR] RETURNS [Text] = TRUSTED {
rtn: Text _ NewText[1];
rtn[0] _ c;
RETURN [rtn];
};

FromRefText: PUBLIC PROC
[s: REF READONLY TEXT, start: NAT _ 0, len: NAT _ NAT.LAST]
RETURNS [rtn: Text _ NIL] = TRUSTED {
IF s # NIL THEN {
rem: NAT ~ s.length-start;
IF rem<len THEN len _ rem;
IF len = 0 THEN RETURN [emptyRope];
rtn _ NewText[len];
IF start=0 THEN MoveAlignedChars[from: LOOPHOLE[s, Text], to: rtn, len: len]
ELSE FOR i: NAT IN[0..len) DO rtn[i] _ s[start+i] ENDLOOP;
};
};

ToRefText: PUBLIC PROC [base: XROPE] RETURNS [rtn: REF TEXT] = TRUSTED {
len: NAT _ Short[InlineSize[base]];
rtn _ NEW[TEXT[len]];
IF len # 0 THEN {
r: Text = LOOPHOLE[rtn];
WITH base SELECT FROM
txt: Text => {
MoveAlignedChars[from: txt, to: LOOPHOLE[rtn, Text], len: len];
rtn.length _ len;
};
ENDCASE => {
[] _ AppendChars[rtn, base, 0, len];
};
};
};

MoveAlignedChars: PROC [from: Text, to: Text, len: NAT] = TRUSTED INLINE {
PrincOpsUtils.LongCopy[
from: LOOPHOLE[from, LONG POINTER]+SIZE[TEXT[0]],
nwords: (len+charsPerWord-1) / charsPerWord,
to: LOOPHOLE[to, LONG POINTER]+SIZE[TEXT[0]] ];
};

DoMoveChars: UNSAFE PROC
[pointer: LONG POINTER, index: INT, rope: XROPE, start: INT, len: INT] ~ {
WHILE len # 0 DO
base: XROPE; bStart, bLen: INT;
[base, bStart, bLen] _ ContainingPiece[rope, start];
IF bLen > len THEN bLen _ len;
IF bLen = 0 THEN ERROR NoRope;
IF index>NAT.LAST THEN {
offset: INT ~ index/charsPerWord;
pointer _ pointer+offset;
index _ index-(offset*charsPerWord);
};
WITH base SELECT FROM
txt: Text => {
toPointer: LONG POINTER TO Basics.RawChars ~ LOOPHOLE[pointer];
toIndex: CARDINAL _ QShort[index];
fromIndex: NAT _ QShort[bStart];
nChars: NAT _ QShort[bLen];
IF nChars > 4 AND (fromIndex MOD charsPerWord) = (toIndex MOD charsPerWord)
THEN {
WHILE (fromIndex MOD charsPerWord) # 0 AND nChars # 0 DO
TRUSTED { toPointer[toIndex] _ QFetch[txt, fromIndex] };
fromIndex _ fromIndex + 1;
toIndex _ toIndex + 1;
nChars _ nChars - 1;
ENDLOOP;
IF nChars # 0 THEN TRUSTED {
PrincOpsUtils.LongCopy[
from: LOOPHOLE[txt, LONG POINTER]+SIZE[TextRep[fromIndex]],
nwords: (nChars+charsPerWord-1) / charsPerWord,
to: LOOPHOLE[toPointer, LONG POINTER]+SIZE[Basics.RawChars[toIndex]]
];
};
}
ELSE {
FOR i: NAT IN [0..nChars) DO
TRUSTED { toPointer[toIndex+i] _ QFetch[txt, fromIndex+i] };
ENDLOOP;
};
};
n: REF node RopeRep => {
WITH n SELECT FROM
obj: REF object node RopeRep =>
SELECT TRUE FROM
obj.move # NIL => {
moved: INT;
TRUSTED { moved _ obj.move[[pointer, index, bLen], obj.base, bStart] };
IF moved # bLen THEN ERROR NoRope;
};
obj.map # NIL => {
toPointer: LONG POINTER TO Basics.RawChars _ LOOPHOLE[pointer];
toIndex: CARDINAL _ QShort[index];
moved: INT _ 0;
action: ActionType = TRUSTED {
IF toIndex>NAT.LAST THEN {
offset: CARDINAL ~ toIndex/charsPerWord;
toPointer _ toPointer+offset;
toIndex _ toIndex-(offset*charsPerWord);
};
toPointer[toIndex] _ c;
toIndex _ toIndex + 1;
moved _ moved + 1;
};
[] _ obj.map[obj.base, bStart, bLen, action];
IF moved # bLen THEN ERROR NoRope; -- should not happen
};
ENDCASE => {
toPointer: LONG POINTER TO Basics.RawChars _ LOOPHOLE[pointer];
toIndex: CARDINAL _ QShort[index];
fetch: FetchType _ obj.fetch;
data: REF _ obj.base;
FOR i: INT IN [0..bLen) DO
IF toIndex>NAT.LAST THEN {
offset: CARDINAL ~ toIndex/charsPerWord;
toPointer _ toPointer+offset;
toIndex _ toIndex-(offset*charsPerWord);
};
TRUSTED { toPointer[toIndex] _ fetch[data, bStart+i] };
toIndex _ toIndex + 1;
ENDLOOP;
};
ENDCASE => ERROR NoRope; -- this should not happen!
};
ENDCASE => ERROR NoRope; -- this should not happen!
len _ len - bLen;
start _ start + bLen;
index _ index + bLen;
ENDLOOP;
};

AppendChars: PUBLIC PROC
[buffer: REF TEXT, rope: XROPE, start: INT _ 0, len: INT _ LAST[INT]]
RETURNS [charsMoved: NAT _ 0] = {
rem: INT _ NonNeg[InlineSize[rope]-NonNeg[start]];
IF rem > len THEN rem _ len;
IF rem>0 AND buffer#NIL THEN {
bufPos: NAT _ buffer.length;
bufRem: NAT _ buffer.maxLength - bufPos;
IF bufRem > rem THEN bufRem _ QShort[rem];
TRUSTED { DoMoveChars[pointer: LOOPHOLE[buffer, LONG POINTER]+SIZE[TEXT[0]], index: bufPos, rope: rope, start: start, len: bufRem] };
buffer.length _ bufPos+bufRem;
RETURN [bufRem];
};
};

UnsafeMoveChars: PUBLIC UNSAFE PROC
[block: Basics.UnsafeBlock, rope: XROPE, start: INT _ 0]
RETURNS [charsMoved: INT _ 0] ~ {
rem: INT _ NonNeg[InlineSize[rope]-NonNeg[start]];
IF rem > block.count THEN rem _ block.count;
IF rem>0 THEN {
TRUSTED { DoMoveChars[pointer: block.base, index: NonNeg[block.startIndex], rope: rope, start: start, len: rem] };
RETURN [rem];
};
};

Equal: PUBLIC PROC [s1, s2: XROPE _ NIL, case: BOOL _ TRUE] RETURNS [BOOL] = TRUSTED {
len1,len2: INT; 
str1, str2: Text;
[len1, str1] _ SingleSize[s1];
[len2, str2] _ SingleSize[s2];
IF len1 # len2 THEN RETURN [FALSE];
IF s1 = s2 OR len1 = 0 THEN RETURN [TRUE];
IF case AND str1 # NIL AND str2 # NIL THEN {
FOR i: CARDINAL IN [0..QShort[len1]) DO
IF QFetch[str1, i] # QFetch[str2, i] THEN RETURN [FALSE];
ENDLOOP;
RETURN [TRUE]};
RETURN [Compare[s1,s2,case] = equal];
};

Compare: PUBLIC PROC
[s1, s2: XROPE _ NIL, case: BOOL _ TRUE] RETURNS [Basics.Comparison] = TRUSTED {
len1,len2: INT; 
str1, str2: Text;
[len1, str1] _ SingleSize[s1];
[len2, str2] _ SingleSize[s2];
IF str1 # NIL AND str2 # NIL THEN {
sz1: CARDINAL _ QShort[len1];
sz2: CARDINAL _ QShort[len2];
sz: CARDINAL _ MIN[sz1, sz2];
IF case
THEN 
FOR i: NAT IN [0..sz) DO
c1: CHAR _ QFetch[str1, i];
c2: CHAR _ QFetch[str2, i];
IF c1 = c2 THEN LOOP;
IF c1 < c2 THEN RETURN [less] ELSE RETURN [greater];
ENDLOOP
ELSE 
FOR i: NAT IN [0..sz) DO
c1: CHAR _ QFetch[str1, i];
c2: CHAR _ QFetch[str2, i];
IF c1 <= 'Z AND c1 >= 'A THEN c1 _ c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 _ c2 + ('a-'A);
IF c1 = c2 THEN LOOP;
IF c1 < c2 THEN RETURN [less] ELSE RETURN [greater];
ENDLOOP;
RETURN [Basics.CompareInt[sz1, sz2]];
};
{
r1,r2: XROPE _ NIL;
pos1,st1,sz1,lm1: INT _ 0;
pos2,st2,sz2,lm2: INT _ 0;
DO
IF st1 = lm1 THEN {
IF (pos1 _ pos1 + sz1) = len1
THEN RETURN [IF pos1 = len2 THEN equal ELSE less];
[r1, st1, sz1] _ ContainingPiece[s1, pos1];
IF sz1 = 0 THEN ERROR;
lm1 _ st1 + sz1;
};
IF st2 = lm2 THEN {
IF (pos2 _ pos2 + sz2) = len2 THEN RETURN [greater];
[r2, st2, sz2] _ ContainingPiece[s2, pos2];
IF sz2 = 0 THEN ERROR;
lm2 _ st2 + sz2;
};
{
c1: CHAR _ InlineFetch[r1, st1];
c2: CHAR _ InlineFetch[r2, st2];
IF c1 # c2 THEN {
IF NOT case THEN {
IF c1 <= 'Z AND c1 >= 'A THEN c1 _ c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 _ c2 + ('a-'A);
IF c1 = c2 THEN GO TO equal;
};
RETURN [Basics.CompareInt[ORD[c1], ORD[c2]]];
EXITS equal => {};
};
};
st1 _ st1 + 1; st2 _ st2 + 1;
ENDLOOP;
};
};

CompareSubstrs: PUBLIC PROC [
s1: XROPE, start1: INT _ 0, len1: INT _ MaxLen, 
s2: XROPE, start2: INT _ 0, len2: INT _ MaxLen, 
case: BOOL _ TRUE] RETURNS [Basics.Comparison] ~ {
rem1: INT _ IF len1 <= 0 THEN 0 ELSE MIN[len1, NonNeg[InlineLength[s1]-NonNeg[start1]]];
rem2: INT _ IF len2 <= 0 THEN 0 ELSE MIN[len2, NonNeg[InlineLength[s2]-NonNeg[start2]]];
rem: INT _ MIN[rem1, rem2];
r1, r2: XROPE _ NIL;
st1, sz1, lm1: INT _ 0;
st2, sz2, lm2: INT _ 0;
WHILE rem # 0 DO
IF st1 = lm1 THEN {
[r1, st1, sz1] _ ContainingPiece[s1, start1 _ start1 + sz1];
IF sz1 = 0 THEN EXIT;
lm1 _ st1 + sz1;
};
IF st2 = lm2 THEN {
[r2, st2, sz2] _ ContainingPiece[s2, start2 _ start2 + sz2];
IF sz2 = 0 THEN EXIT;
lm2 _ st2 + sz2;
};
{
c1: CHAR _ InlineFetch[r1, st1];
c2: CHAR _ InlineFetch[r2, st2];
IF c1 # c2 THEN {
IF NOT case THEN {
IF c1 <= 'Z AND c1 >= 'A THEN c1 _ c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 _ c2 + ('a-'A);
IF c1 = c2 THEN GO TO equal;
};
RETURN [Basics.CompareInt[ORD[c1], ORD[c2]]];
EXITS equal => {};
};
};
st1 _ st1 + 1;
st2 _ st2 + 1;
rem _ rem - 1;
ENDLOOP;
RETURN [Basics.CompareInt[rem1, rem2]];
};

EqualSubstrs: PUBLIC PROC [
s1: XROPE, start1: INT _ 0, len1: INT _ MaxLen, 
s2: XROPE, start2: INT _ 0, len2: INT _ MaxLen, 
case: BOOL _ TRUE] RETURNS [BOOL] ~ {
rem1: INT _ IF len1 <= 0 THEN 0 ELSE MIN[len1, NonNeg[InlineLength[s1]-NonNeg[start1]]];
rem2: INT _ IF len2 <= 0 THEN 0 ELSE MIN[len2, NonNeg[InlineLength[s2]-NonNeg[start2]]];
IF rem1 = rem2 THEN {
r1, r2: XROPE _ NIL;
st1, sz1, lm1: INT _ 0;
st2, sz2, lm2: INT _ 0;
WHILE rem1 # 0 DO
IF st1 = lm1 THEN {
[r1, st1, sz1] _ ContainingPiece[s1, start1 _ start1 + sz1];
IF sz1 = 0 THEN EXIT;
lm1 _ st1 + sz1;
};
IF st2 = lm2 THEN {
[r2, st2, sz2] _ ContainingPiece[s2, start2 _ start2 + sz2];
IF sz2 = 0 THEN EXIT;
lm2 _ st2 + sz2;
};
{
c1: CHAR _ InlineFetch[r1, st1];
c2: CHAR _ InlineFetch[r2, st2];
IF c1 # c2 THEN {
IF NOT case THEN {
IF c1 <= 'Z AND c1 >= 'A THEN c1 _ c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 _ c2 + ('a-'A);
IF c1 = c2 THEN GO TO equal;
};
RETURN [FALSE];
EXITS equal => {};
};
};
st1 _ st1 + 1;
st2 _ st2 + 1;
rem1 _ rem1 - 1;
ENDLOOP;
RETURN [TRUE];
};
RETURN [FALSE];
};

ContainingPiece: PUBLIC PROC [rope: XROPE, index: INT _ 0]
RETURNS [base: XROPE, start: INT, len: INT] = TRUSTED {
len _ InlineSize[rope];
IF index < 0 OR index >= len THEN RETURN [NIL, 0, 0];
base _ rope;
start _ index;
len _ len - start;
DO
nlen: INT _ len;
WITH x: base SELECT FROM
text => RETURN;
node =>
WITH x: x SELECT FROM
substr => {
nlen _ x.size - start;
start _ start + x.start;
base _ x.base;
};
concat => {
del1: INT _ x.pos - start;
IF del1 > 0
THEN {nlen _ del1; base _ x.base}
ELSE {nlen _ x.size - start; start _ -del1; base _ x.rest};
};
replace => {
del2: INT _ x.newPos - start;
del1: INT _ x.start - start;
SELECT TRUE FROM
del1 > 0 => {nlen _ del1; base _ x.base};
del2 > 0 => {start _ -del1; nlen _ del2; base _ x.replace};
ENDCASE => {
nlen _ x.size - start;
start _ x.oldPos - del2;
base _ x.base;
};
};
object => {RETURN};
ENDCASE => ERROR NoRope;
ENDCASE => ERROR NoRope;
IF nlen < len THEN len _ NonNeg[nlen];
ENDLOOP;
};

IsEmpty: PUBLIC PROC [r: XROPE] RETURNS [BOOL] = {
RETURN [InlineSize[r] = 0];
};

Length: PUBLIC PROC [base: XROPE] RETURNS [INT] = {
RETURN [InlineSize[base]];
};

Size: PUBLIC PROC [base: XROPE] RETURNS [INT] = {
RETURN [InlineSize[base]];
};

QShort: PROC [x: INT] RETURNS [CARDINAL] = TRUSTED INLINE {
RETURN [Basics.LowHalf[x]];
};

Run: PUBLIC PROC
[s1: XROPE, pos1: INT, s2: XROPE, pos2: INT, case: BOOL _ TRUE]
RETURNS [result: INT _ 0] = TRUSTED {
len1: INT; 
str1: Text;
[len1, str1] _ SingleSize[s1];
IF NonNeg[pos1] < len1 THEN {
len2: INT; 
str2: Text;
[len2, str2] _ SingleSize[s2];
IF NonNeg[pos2] < len2 THEN {
r1,r2: XROPE _ NIL;
st1,sz1,lm1: INT _ 0;
st2,sz2,lm2: INT _ 0;
DO
IF st1 = lm1 THEN {
[r1, st1, sz1] _ ContainingPiece[s1, pos1 _ pos1 + sz1];
IF sz1 = 0 THEN RETURN;
lm1 _ st1 + sz1;
};
IF st2 = lm2 THEN {
[r2, st2, sz2] _ ContainingPiece[s2, pos2 _ pos2 + sz2];
IF sz2 = 0 THEN RETURN;
lm2 _ st2 + sz2;
};
{
c1: CHAR _ InlineFetch[r1, st1];
c2: CHAR _ InlineFetch[r2, st2];
IF c1 # c2 THEN {
IF NOT case THEN {
IF c1 <= 'Z AND c1 >= 'A THEN c1 _ c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 _ c2 + ('a-'A);
IF c1 = c2 THEN GO TO equal;
};
RETURN;
EXITS equal => {};
};
};
result _ result + 1;
st1 _ st1 + 1; st2 _ st2 + 1;
ENDLOOP;
};
};
};

IsPrefix: PUBLIC PROC [prefix: XROPE, subject: XROPE, case: BOOL _ TRUE] RETURNS [BOOL] ~ {
RETURN [Run[prefix, 0, subject, 0, case]=InlineSize[prefix]];
};

Index: PUBLIC PROC
[s1: XROPE, pos1: INT, s2: XROPE, case: BOOL _ TRUE] RETURNS [INT] = TRUSTED {
len1,len2, rem: INT; both: BOOL;
[len1,len2,both] _ DoubleSize[s1, s2];
rem _ IF pos1 >= len1 THEN 0 ELSE len1 - NonNeg[pos1];
IF rem >= len2 THEN {
c: CHAR;
IF len2 = 0 THEN RETURN [pos1];
c _ InlineFetch[s2, 0];
rem _ rem - len2 + 1;
IF case
THEN {
Cmp: PROC [cc: CHAR] RETURNS [BOOL] = TRUSTED {
IF c = cc AND Run[s1, pos1+1, s2, 1, case]+1 = len2 THEN RETURN [TRUE];
pos1 _ pos1 + 1; RETURN [FALSE];
};
IF Map[s1, pos1, rem, Cmp] THEN RETURN [pos1]
}
ELSE {
LCmp: PROC [cc: CHAR] RETURNS [BOOL] = TRUSTED {
IF cc <= 'Z AND cc >= 'A THEN cc _ cc + ('a-'A);
IF c = cc AND Run[s1, pos1+1, s2, 1, case]+1 = len2 THEN RETURN [TRUE];
pos1 _ pos1 + 1; RETURN [FALSE];
};
IF c <= 'Z AND c >= 'A THEN c _ c + ('a-'A);
IF Map[s1, pos1, rem, LCmp] THEN RETURN [pos1];
};
};
RETURN [len1];
}; 

Find: PUBLIC PROC [s1, s2: XROPE, pos1: INT _ 0, case: BOOL _ TRUE] RETURNS [INT] = {
index: INT _ Index[s1, pos1, s2, case];
IF index = InlineSize[s1] THEN RETURN [-1];
RETURN [index];
};

FindBackward: PUBLIC PROC 
[s1, s2: XROPE, pos1: INT _ MaxLen, case: BOOL _ TRUE] RETURNS [INT] = {
len1,len2: INT; both: BOOL;
[len1,len2,both] _ DoubleSize[s1, s2];
IF NonNeg[pos1]>len1 THEN pos1 _ len1;
IF len2 = 0 THEN RETURN [pos1];
IF len1 >= len2 THEN {
c2: CHAR _ InlineFetch[s2, 0]; -- first char of pattern
rem2: INT ~ len2-1; -- remaining chars in pattern
IF (len1-pos1)<len2 THEN pos1 _ len1-len2;
IF case THEN {
FOR i: INT DECREASING IN[0..pos1] DO
c1: CHAR ~ InlineFetch[s1, i];
IF c1=c2 AND (rem2=0 OR Run[s1, i+1, s2, 1, case]=rem2) THEN RETURN [i];
ENDLOOP;
}
ELSE {
IF c2 <= 'Z AND c2 >= 'A THEN c2 _ c2 + ('a-'A);
FOR i: INT DECREASING IN[0..pos1] DO
c1: CHAR _ InlineFetch[s1, i];
IF c1 <= 'Z AND c1 >= 'A THEN c1 _ c1 + ('a-'A);
IF c1=c2 AND (rem2=0 OR Run[s1, i+1, s2, 1, case]=rem2) THEN RETURN [i];
ENDLOOP;
};
};
RETURN [-1];
};

Match: PUBLIC PROC [pattern, object: XROPE, case: BOOL _ TRUE] RETURNS [BOOL] = TRUSTED {
submatch: PROC [i1: INT, len1: INT, i2: INT, len2: INT] RETURNS [BOOL] = TRUSTED {
WHILE len1 > 0 DO
c1: CHAR _ InlineFetch[pattern, i1];
IF c1 = '* THEN {
IF len1 = 1 THEN RETURN [TRUE];
{-- first, accept the *
j1: INT _ i1 + 1;
nlen1: INT _ len1 - 1;
j2: INT _ i2;
nlen2: INT _ len2;
WHILE nlen2 >= 0 DO
IF submatch[j1, nlen1, j2, nlen2] THEN RETURN [TRUE];
j2 _ j2 + 1;
nlen2 _ nlen2 - 1;
ENDLOOP;
};
RETURN [FALSE];
};
IF len2 <= 0 THEN RETURN [FALSE];
{c2: CHAR _ InlineFetch[object, i2];
IF NOT case THEN {
IF c1 <= 'Z AND c1 >= 'A THEN c1 _ c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 _ c2 + ('a-'A);
};
IF c1 # c2 THEN RETURN [FALSE];
};
i1 _ i1 + 1;
len1 _ len1 - 1;
i2 _ i2 + 1;
len2 _ len2 - 1;
ENDLOOP;
RETURN [len2 = 0];
};
len1: INT _ InlineSize[pattern];
len2: INT _ InlineSize[object];
WHILE len1 > 0 DO
n: INT _ len1 - 1;
c1: CHAR _ InlineFetch[pattern, n];
c2: CHAR;
IF c1 = '* THEN EXIT;
IF len2 = 0 THEN RETURN [FALSE];
len1 _ n;
len2 _ len2 - 1;
c2 _ InlineFetch[object, len2];
IF NOT case THEN  {
IF c1 <= 'Z AND c1 >= 'A THEN c1 _ c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 _ c2 + ('a-'A);
};
IF c1 # c2 THEN RETURN [FALSE];
ENDLOOP;
RETURN [submatch [0, len1, 0, len2]];
}; 

SkipTo: PUBLIC PROC [s: XROPE, pos: INT, skip: XROPE] RETURNS [INT] = TRUSTED {
len: INT _ InlineSize[s];
skipText: Rope.Text = InlineFlatten[skip];
skiplen: NAT _ IF skipText = NIL THEN 0 ELSE skipText.length;
IF pos < len AND skiplen # 0 THEN {
CharMatch: PROC [c: CHAR] RETURNS [BOOL] = TRUSTED {
FOR i: NAT IN [0..skiplen) DO
IF c = skipText[i] THEN RETURN [TRUE];
ENDLOOP;
pos _ pos + 1;
RETURN [FALSE];
};
IF Map[s, pos, len - pos, CharMatch] THEN RETURN [pos];
};
RETURN [len];  
};

SkipOver: PUBLIC PROC [s: XROPE, pos: INT, skip: XROPE] RETURNS [INT] = TRUSTED {
len: INT _ InlineSize[s];
skipText: Rope.Text = InlineFlatten[skip];
skiplen: NAT _ IF skipText = NIL THEN 0 ELSE skipText.length;
IF pos >= len THEN RETURN [len];
IF skiplen # 0 THEN {
CharMatch: PROC [c: CHAR] RETURNS [BOOL] = TRUSTED {
FOR i: NAT IN [0..skiplen) DO
IF c = skipText[i] THEN GO TO found;
ENDLOOP;
RETURN [TRUE];
EXITS found => {pos _ pos + 1; RETURN [FALSE]};
};
IF Map[s, pos, len - pos, CharMatch] THEN RETURN [pos];
};
RETURN [pos];
};

VerifyStructure: PUBLIC PROC
[s: XROPE] RETURNS [leaves,nodes,maxDepth: INT _ 0] = TRUSTED {
IF s = NIL THEN RETURN;
WITH x: s SELECT FROM
text => {
leaves _ 1;
IF x.length > x.max THEN ERROR VerifyFailed};
node =>
WITH x: x SELECT FROM
substr => {
ref: XROPE _ x.base;
len1: INT _ Size[x.base];
IF x.start < 0 OR x.size <= 0 THEN ERROR VerifyFailed;
IF len1 < x.start + x.size THEN ERROR VerifyFailed;
[leaves, nodes, maxDepth] _ VerifyStructure[ref];
nodes _ nodes + 1};
concat => {
leaves1,nodes1,maxDepth1: INT;
left: XROPE _ x.base;
lSize: INT _ Size[left];
right: XROPE _ x.rest;
rSize: INT _ Size[right];
[leaves1, nodes1, maxDepth1] _ VerifyStructure[left];
[leaves, nodes, maxDepth] _ VerifyStructure[right];
leaves _ leaves + leaves1;
nodes _ nodes + nodes1 + 1;
IF maxDepth1 > maxDepth THEN maxDepth _ maxDepth1;
IF x.size # lSize + rSize THEN ERROR VerifyFailed;
IF x.pos # lSize THEN ERROR VerifyFailed;
};
replace => {
leaves1,nodes1,maxDepth1: INT;
old: XROPE _ x.base;
oldSize: INT _ Size[old];
repl: XROPE _ x.replace;
replSize: INT _ Size[repl];
[leaves, nodes, maxDepth] _ VerifyStructure[old];
[leaves1, nodes1, maxDepth1] _ VerifyStructure[repl];
leaves _ leaves + leaves1;
nodes _ nodes + nodes1 + 1;
IF maxDepth < maxDepth1 THEN maxDepth _ maxDepth1;
IF x.start > x.oldPos OR x.start > x.newPos THEN ERROR VerifyFailed;
IF x.newPos - x.start # replSize THEN ERROR VerifyFailed;
IF x.start < 0 OR x.start > x.size THEN ERROR VerifyFailed;
IF x.oldPos > oldSize THEN ERROR VerifyFailed;
};
object => {
leaves _ 1;
IF x.size < 0 OR x.fetch = NIL THEN ERROR VerifyFailed;
};
ENDCASE => ERROR NoRope;
ENDCASE => ERROR NoRope;
maxDepth _ maxDepth + 1;
IF maxDepth # InlineDepth[s] THEN ERROR VerifyFailed;
};

VerifyFailed: PUBLIC ERROR = CODE;

Stopper: TYPE = PROC [part: Part] RETURNS [BOOL];

Part: TYPE ~ RECORD [base: XROPE, start: INT, end: INT];

HeightArray: TYPE = ARRAY [0..RopePrivate.MaxDepth) OF INT;
minSizeForHeight: REF HeightArray _ NIL;
InitMinSizeForHeight: PROC ~ {
IF minSizeForHeight = NIL THEN {
h: REF HeightArray _ NEW[HeightArray];
h[0] _ 0;
h[1] _ 1;
h[2] _ Rope.FlatMax+1;
FOR i: NAT IN [3..RopePrivate.MaxDepth) DO
IF INT.LAST - h[i-1] < h[i-2]
THEN h[i] _ INT.LAST
ELSE h[i] _ h[i-1] + h[i-2];
ENDLOOP;
minSizeForHeight _ h;
};
};

PartIsBalanced: Stopper ~ {
size: INT ~ Rope.InlineSize[part.base];
height: INT ~ RopePrivate.InlineDepth[part.base];
IF part.start # 0
OR part.end # size
OR height >= RopePrivate.MaxDepth
THEN RETURN [FALSE];
IF minSizeForHeight = NIL THEN InitMinSizeForHeight[];
IF size < minSizeForHeight[height] THEN RETURN [FALSE];
WITH part.base SELECT FROM
substr: REF Rope.RopeRep.node.substr => RETURN [height<=1];
concat: REF Rope.RopeRep.node.concat => RETURN [TRUE];
replace: REF Rope.RopeRep.node.replace => RETURN [FALSE];
ENDCASE => RETURN [TRUE];
};

Balance: PUBLIC PROC [base: XROPE, start: INT _ 0, len: INT _ MaxLen, flat: INT _ FlatMax]
RETURNS [XROPE] = {
RETURN [Rope.Substr[NewBalance[base], start, len]];
};

d: NAT ~ 40;
ARep: TYPE ~ RECORD [index: INT_0, sub: ARRAY [0..d) OF AElement, rest: REF ARep_NIL];
AElement: TYPE ~ RECORD [base: XROPE, size: INT];
NewBalance: PROC [rope: XROPE] RETURNS [XROPE] ~ {
a: ARep; -- An extensible array that is very cheap if it is small.
accel: REF ARep _ NIL;
aN: INT _ 0;
StoreA: PROC [i: INT, e: AElement] ~ {
IF i-a.index < d
THEN a.sub[i-a.index] _ e
ELSE {
IF a.rest = NIL THEN {a.rest _ accel _ NEW[ARep]; accel.index _ d};
IF i < accel.index THEN accel _ a.rest;
WHILE i-accel.index >= d DO
IF accel.rest = NIL THEN {
accel.rest _ NEW[ARep];
accel.rest.index_accel.index+d};
accel _ accel.rest;
ENDLOOP;
accel.sub[i-accel.index] _ e;
};
};
ASub: PROC [i: INT] RETURNS [e: AElement] ~ {
IF i-a.index < d
THEN e _ a.sub[i-a.index]
ELSE {
IF i < accel.index THEN accel _ a.rest;
WHILE i-accel.index >= d DO accel _ accel.rest ENDLOOP;
e _ accel.sub[i-accel.index];
};
};
SavePart: PROC [part: Part] ~ {
IF part.end > part.start THEN {
rope: XROPE _ Rope.Substr[part.base, part.start, part.end-part.start];
StoreA[aN, [rope, Rope.InlineSize[rope]]];
aN _ aN + 1;
};
};
BalanceRange: PROC [first: INT, end: INT, size: INT] RETURNS [XROPE] ~ {
SELECT TRUE FROM
first = end => RETURN[NIL];
end-first = 1 => RETURN[ASub[first].base];
ENDCASE => {
i: INT _ first+1;
sizetoi: INT _ ASub[first].size;
FOR sizei: INT _ ASub[i].size, ASub[i].size
WHILE i < end-1 AND ((sizetoi+sizei)*2 < size OR ABS[sizetoi*2-size] > ABS[(sizetoi+sizei)*2-size]) DO
sizetoi _ sizetoi + sizei;
i _ i + 1;
ENDLOOP;
RETURN[Rope.Concat[BalanceRange[first, i, sizetoi], BalanceRange[i, end, size-sizetoi]]];
}
};
part: Part ~ [rope, 0, Rope.Size[rope]];
MapParts[part, SavePart, PartIsBalanced];
RETURN [BalanceRange[0, aN, part.end-part.start]]
};

BadPart: SIGNAL ~ CODE;

MapParts: PROC[part: Part, action: PROC[Part], stopDescent: Stopper_NIL] ~{
IF stopDescent#NIL AND stopDescent[part]
THEN action[part]
ELSE {
size: INT ~ Rope.InlineSize[part.base];
IF part.start < 0 OR part.end NOT IN [part.start..part.start+size] THEN ERROR BadPart;
WITH part.base SELECT FROM
substr: REF Rope.RopeRep.node.substr => {
MapParts[[substr.base, substr.start+part.start, substr.start+part.end], action, stopDescent];
};
concat: REF Rope.RopeRep.node.concat => {
IF part.start < concat.pos THEN {
MapParts[[concat.base, part.start, MIN[part.end, concat.pos]], action, stopDescent];
};
IF part.end > concat.pos THEN {
newStart: INT _ MAX[part.start-concat.pos, 0];
newEnd: INT _ part.end-concat.pos;
MapParts[[concat.rest, newStart, newEnd], action, stopDescent];
};
};
replace: REF Rope.RopeRep.node.replace => {
len1: INT ~ replace.start;
len2: INT ~ replace.newPos-replace.start;
len3: INT ~ replace.size-replace.newPos;
offset3: INT ~ replace.oldPos;
IF part.start < len1 THEN {
MapParts[[replace.base, part.start, MIN[part.end, len1]], action, stopDescent];
};
IF part.start < len1+len2 AND part.end > len1 THEN {
newStart: INT ~ MAX[part.start-len1, 0];
newEnd: INT ~ MIN[part.end-len1, len2];
MapParts[[replace.replace, newStart, newEnd], action, stopDescent];
};
IF part.end > len1+len2 THEN {
newStart: INT _ MAX[part.start-(len1+len2), 0]+offset3;
newEnd: INT _ MIN[part.end-(len1+len2), len3]+offset3;
MapParts[[replace.base, newStart, newEnd], action, stopDescent];
};
};
ENDCASE => action[part];
};
};

END.



#ΰXRopeImpl.mesa
Copyright Σ 1988 by Xerox Corporation.  All rights reserved.
Doug Wyatt, February 19, 1988 3:07:48 pm PST
errors peculiar to XRope
Watch out for startup problems with literals.  Don't use "" here!
procedure to allocate new Text objects
... returns a subrope of the base.  BoundsFault occurs if start < 0 or start > Length[base].
At this point the resulting rope is large enough to need a separate node.  The idea is to dive down through as many levels of rope objects until we get to the deepest such object that fully contains the specified rope.
(note: change base last, since it is aliased with x!)
substr starts in 1st section
entirely in first section, so go deeper
substr starts in middle or last sections
substr starts in middle section
entirely in middle section
entirely in last section
no sub-structure
Return the concatenation of the given 5 ropes.
Return the concatenation of the two ropes.  If the result is small enough, then it will be flat.  Otherwise we need to create a new node.
The result is small enough to make it flat.
Possibly can reduce depth by combining with a concat node.
result is small enough to be flat
We need to make a new node.  First, test for combining the replacement rope with a previous replacement rope, so that successive replacements at the same spot will not make ropes too deep.
(note: if you use unsafe discrimination here, change base last, since it is aliased with x!)
replacing the replacement string
adding to old replace string
... fetches indexed character from given ropes.  BoundsFault occurs if index < 0 or index is >= Length[base].
First time through, check the index against bounds
Now we really don't need bounds checking, since checking the top level is sufficient.  What we really need to do now is dive down to the right place as quickly as possible.
(note: change base last, since it is aliased with x!)
... applies the action to the given range of characters in the rope.  Returns TRUE when some action returns TRUE.  BoundsFault occurs when start < 0 or start > Length[base].
(note: change base last, since it is aliased with x!)
applies the translation to get a new rope
if the resulting size > 0, then new does not share with the original rope!
if translator = NIL, the identity translation is performed
no optimization for user-supplied strings
Force proper evaluation order, since the compiler might get it backwards if left to its own devices.
We assume start IN[0..size] AND len IN[0..size-start], where size=Size[rope]
The effect is ... FOR i: INT IN[0..len) DO pointer[index+i] _ rope.Fetch[start+i] ENDLOOP
grab the smallest piece of the rope containing the given start index
this piece is longer than we need to finish the transfer
this should not happen!  it means that some calculation or invariant is bad!
ensure index IN NAT
We are moving chars from a flat rope.
The source and destination are aligned, so we can BLT
Not yet aligned to a word boundary
The source and destination are not aligned, so we move chars slowly
We are moving chars from a user-defined object.
The user has supplied a fast move routine, so use it.
We asked for a perfectly legitimate # of chars, and the user's move routine blew it!  This rope is not reliable.
The user has supplied a fast map routine, so use it.
Sigh.  We have to do this one ourselves.
update the # of chars left in the transfer
start is now the starting index for the next piece
index is now the destination index for the next piece
... appends characters to the end of a REF TEXT buffer, starting at start within the rope.  The move stops if there are no more characters from the rope OR len characters have been moved OR the buffer is full (buffer.length = buffer.maxLength).  charsMoved is always the # of characters appended.  NOTE: the user is responsible for protecting buffer from concurrent modifications.
# of characters in rope after start
The user may have specified a shorter run of characters
position of next place to append character (cache for buffer.length)
# of chars remaining in the transfer
the caller may have specified a shorter amount
... moves characters to an UnsafeBlock, starting at start within the rope.  The move stops if there are no more characters from the rope OR block.count characters have been moved; charsMoved is always the # of characters moved.  This UNSAFE operation is mainly for the implementation of IO.RIS.  Most clients should use AppendChars.
# of characters in rope after start
The user may have specified a shorter run of characters
contents equality of s1 and s2
relatively cheap test for equality
contents comparison of s1 and s2 (less(0), equal(1), greater(2))
if NOT case, then upper case chars = lower case chars
contents equality of s1 and s2
The two ropes are both flat, so we don't have to discriminate for every character.
At least one rope is not flat, so we do it the hard way.
need a new piece from s1
need a new piece from s2
need a new piece from s1
need a new piece from s2
need a new piece from s1
need a new piece from s2
find the largest piece containg the given index
such that the resulting rope is either the text or the object variant
(NIL, 0, 0) is returned if the index is NOT in the given rope
(note: change base last, since it is aliased with x!)
returns the length of the rope (Length[NIL] = 0)
Size[base] = Length[base]
Formerly in RopeImplExt
Returns the largest number of characters N such that s1 starting at pos1 is equal to s2 starting at pos2 for N characters.  More formally: FOR i IN [0..N): s1[pos1+i] = s2[pos2+i].  If case is true, then case matters, otherwise upper and lower case characters are considered equal. 
need a new piece from s1
need a new piece from s2
Returns the smallest character position N such that s2 occurs in s1 at N and N >= pos1.  If s2 does not occur in s1 at or after pos1, s1.length is returned. pos1 <= N < s1.length => FOR i IN [0..s2.length): s1[N+i] = s2[i]; N = s1.length => s2 does not occur in s1.  If case is true, then case matters, otherwise upper and lower case characters are considered equal.
Returns TRUE if the object matches the pattern, where the pattern may contain * to indicate that 0 or more characters will match.  Returns FALSE otherwise.  For example, using a*b as a pattern, some matching objects are: ab, a#b, a###b, and some not matching objects: abc, cde, bb, a, Ab.  If case is true, then case matters, otherwise upper and lower case characters are considered equal.
quick kill for * at end of pattern
else must take all combinations
at this point demand an exact match in both strings
First, strip off the common tails until they differ (quick kill false), or the pattern has a * at the tail.  This strip is easy, because we just decrement the lengths.
... returns the lowest position N in s such that s[N] is in the skip string and N >= pos.  If no such character occurs in s, then return s.length.
... return the lowest position N in s such that s[N] is NOT in the skip string and N >= pos.  If no such character occurs in s, then return s.length.
... traverses the structure of the given rope object; extra checking is performed to verify invariants.
***** New Balance implementation
This implementation is courtesy of Michael Plass (March 1985).

Must have 0 <= start <= end <= Size[base];
Initializes the height array.  Does not need monitoring, since the array is completely initialized by the time the assignment occurs, and REF assignment is atomic.  Races can only cause a little extra allocation.
A NIL rope has no characters and height 0.
A flat rope ought to have at least one character.
Must be at least this big to warrant any non-flat structure.
Use Fibonacci recurrence to compute rest.
Be careful about overflow here...
Examines only the root.
This procedure is here mostly to match the new implementation against the old definition.
Balances pieces [first..end), whose sizes must sum to size.

26-Feb-81, Russ Atkinson, fixed bug in Substr (REF Tconcat case) found by Paxton
31-Mar-81, Russ Atkinson, fixed bug in Map (overlarge len to user's map) found by Morris
8-Apr-81, Russ Atkinson, fixed bug in Substr (REF Tconcat case) found by Paxton
11-May-81, Russ Atkinson, converted to use variant record representation
23-May-81, Russ Atkinson, added Balance, ContainingPiece
12-Jul-81, Russ Atkinson, added FromChar, fixed FromProc
22-Sep-81, Russ Atkinson, removed dependence on CedarString
14-Oct-81, Russ Atkinson, added stuff for depth maintenance
30-Oct-81 17:21:35, Russ Atkinson, added pz & changes to match new specs
November 24, 1981 12:11 pm, Russ Atkinson, fixed ContainingPiece and some defaults
17-Feb-82 14:50:00, Russ Atkinson, minor defs changes
19-Feb-82 12:00:25, Russ Atkinson, try to avoid returning NIL
April 8, 1982, Russ Atkinson, fix Compare bug
June 7, 1982, Russ Atkinson, convert to Cedar 3.2
September 9, 1982, Russ Atkinson, convert to Cedar 3.4 (Compare returns Comparison)
December 20, 1984, Russ Atkinson, formatting cleanup & performance improvements
Russ Atkinson (RRA) January 29, 1985 4:09:50 pm PST
Removed PieceMap and its support, added AppendChars and its support.  Other small changes to use AppendChars internally (like in Flatten).

Κ5Τ˜
codeš
œ™K™<K™,—K˜š
Οk	˜	Kšœœ'˜3Kš
œ˜—
headšΟn	œœ
˜Kšœ˜Kšœ˜
Kšœ˜
Kšœœ
œ˜K˜š
žœœœœœ˜6K˜—šž
œœœœœ
œ˜=šœœ
œœ˜<Kšœœœœ
œœ
œ˜>—K˜K˜—šžœœœœœœ˜7Kšœ˜ K˜K˜—šžœœœœœœ
œ˜DKšœœ
œ
œ˜šœ	œ
˜Kšœ	œ˜Kšœ
œ˜Kšœ
œ˜Kšœœ˜—K˜K˜—Kš
œ™Kšžœœ
œœ
˜K˜šœœ
˜"Kš
œA™A—K˜šžœœ
œœœœ˜AKš
œ&™&Kšœ
œ
œ
˜$Kšœœ˜K˜K˜K˜—šžœœ
œœ	œœœœœ˜eKš
œ\™\Kšœœ˜Kšœœ ˜(Kšœœ˜Kšœ
œ
œ
œ
œœ˜EKšœœœ
œ˜.Kšœœ
œ˜:š
œΪ
™Ϊ
K™5—šœ
˜šœœ
˜Kšœœ
˜
K˜3š
œ˜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šœœ
œ˜-Kšœ
˜—Kš
œ˜Kš
œ˜šœœ˜K˜H—Kšœœ˜-K˜K˜—šžœœ
œœœœœ˜FKš
œ.™.Kšœ6˜<K˜K˜—šžœœ
œ
œœœœ˜EKš
œ‰
™‰
K˜Kšœœ
˜Kšœœ˜Kšœœ
œ
œ˜!K˜&Kšœ
œ
œ˜"K˜&Kšœ
œ
œ˜"K˜%šœœ˜Kš
œ+™+K˜Kšœœ˜Kšžœ3˜:šœ˜Kšœ$˜(Kšœ
œœ
œœ*œ
˜T—šœ˜Kšœ$˜(Kšœ
œœ
œœ*œ
˜T—Kšœ˜—šœ
œ
˜Kš
œ:™:š
œ˜šœœ
˜šœœ˜šœœ˜"K˜K˜K˜K˜——Kšœ
˜——š
œ˜šœœ
˜šœœ˜šœœ˜K˜K˜K˜K˜——Kšœ
˜——Kšœ
˜—Kš
œ˜Kšœœ+˜6šœœ˜K˜Q—Kšœœ˜,K˜K˜—šžœœ
œœ	œœœœœœ˜qKšœ
œ˜!Kšœ
œ˜!Kšœœ$˜,Kšœœ˜šœœ
˜Kš
œ
œ	œ	œ
œœœ˜D—Kšœœ ˜+Kšœœ'˜0Kšœœ
œ˜%Kš	œ	œ
œ
œ
Οc˜Ašœœ˜Kš
œ!™!K˜Kšœœ˜Kšžœ3˜:Kšœœ#˜4Kšœ
œ%˜8Kšœœ+˜DKšœ˜—š
œΌ
™Ό
K™\—šœœ
˜šœœ˜Kšœ	œ˜Kšœœ˜šœ
œ
˜šœœ˜*Kš
œ ™ K˜'K˜Kš
œ˜—š
œ˜Kš
œ™šœ)œ˜1Kš
œ˜K˜K˜K˜K˜—K˜—Kšœ
˜—K˜—Kšœ
˜—K˜,K˜$K˜#Kšœœ+˜6šœœ˜K˜t—Kšœœ˜,K˜K˜—šžœœ
œœ	œœœ˜CKš
œm™mšœœ
˜KšœœŸ˜@šœ˜Kš
œ2™2Kšœœœœ
œœ˜.K˜K˜K˜——š
œ¬
™¬
K™5—š
˜šœœ
˜Kšœœœ˜)Kšœœ=˜Cšœœ˜Kšœœœ˜,K˜K˜—šœœ˜Kšœœœ˜.šœœ˜Kš
œ˜Kš
œ˜Kšœ˜—K˜$K˜—Kšœœœ˜:Kšœœ˜—Kšœ
˜—K˜K˜—šžœœ
œœ	œœœœœ˜qKšœNœœ=™­
Kšœœ,˜4Kšœœ˜šœ	˜šœ	œ
˜š
œ	˜	Kšœœ˜šœœ
œ˜*Kšœœ
œœ˜+Kšœ
˜—Kšœœ˜—˜K™5šœœ
˜Kšœ3œ˜9š
œ˜Kšœœ	˜Kšœœœ˜0šœœ˜Kšœœ˜Kšœ#œ
œœ˜9K˜"—K˜K˜K˜—š
œ˜Kšœœ˜Kšœœ˜šœœ˜Kšœœ˜Kšœœœ˜,Kšœ#œ
œœ˜9K˜$—šœœ˜Kšœœ˜Kšœœ˜Kšœœ œ˜;Kšœ#œ
œœ˜9K˜"—K˜ K˜—˜K˜Kšœœ
˜Kšœœ
œ
œ ˜8˜šœœ
œ˜#Kšœœ
œœ˜-Kšœ
˜—Kšœœ˜——Kšœœ˜——Kšœœ˜—Kšœ
˜—Kšœœ˜K˜K˜—šž	œœ
œœ	œœ(œ
œœœ˜‹
Kš
œ)™)Kš
œJ™JKš
œ:™:Kšœœ	˜Kšœœ,˜7Kšœœ
˜Kšœ
œ
˜Kšœ
œ	œ
œ
˜/Kšœœ˜šœœ
˜š
œ˜Kšœœ	˜K˜šœœ
œ
˜Kšœœ˜Kšœœ
œ˜+K˜K˜Kšœ
˜—Kš
œ˜K˜—šœ˜š	œœ
œœœ˜%Kšœœ˜#K˜Kšœœ
œ˜+Kšœ˜K˜—Kšœ˜Kš
œ˜——K˜K˜—šžœœ
œœ	œœœœ˜eKšœœ˜Kšœœ ˜(Kšœœ˜šœœœ˜!Kš
œœ
œ
œœ˜ Kšœœ
œœ˜0Kš
œ˜—Kšœ
œ
œ
˜$K˜K˜Kšœœ˜2˜K˜——šžœœ
œœœ2œœœ˜xKš
œ)™)Kšœ
œ
œ
˜$šœœ
˜Kš
œT˜T—š
œ˜K˜——šžœœ
œœœ
œœ
œœœœ˜lKšœ
œ
œ
˜$šœ˜Kšœ˜Kšœ
œœ
œœœ
œ˜7—šœ˜šœ˜Kš
œ!˜!Kš
œœ
œœœ
˜8Kšœ˜
—šœ˜Kš
œd™dKšœœ ˜+Kšœœ$˜0Kšœ˜——š
œ˜K˜——šžœœ
œœœ
œ˜:K˜K˜Kšœ˜
Kš
œ˜K˜—šžœœ
œœ
œ
œ	œœœ
œœœœ˜zšœœ
œ˜Kšœœ˜Kšœ	œ˜Kšœ	œ
œ
˜#K˜Kšœ	œœ˜LKšœ
œœ
œ	œœ
˜:K˜—˜K˜——šž	œœ
œœœœ
œœ˜HKšœœ˜#Kšœœ
œ˜šœ	œ˜Kšœ
œ˜šœœ
˜˜Kšœ œ˜?Kš
œ˜K˜—šœ˜Kš
œ$˜$K˜——K˜—Kš
œ˜K˜—šžœœœœ˜J˜Kšœœœ
œœ
œ˜1Kš
œ,˜,Kšœœœ
œœ
œ˜/—K˜K˜—šžœœ
œœ
œ	œœ	œœ˜cKšœœ
œœ&™LKš
œœœ
œ	œ(™Yšœ	˜Kšœœœ
˜š
œ4˜4Kš
œD™D—šœœ˜Kš
œ8™8—šœ
œ
œ˜Kš
œL™L—šœœ
œ
œ˜Kšœœ˜!Kš
œ˜Kš
œ$˜$K˜Kšœ
œ
™—šœœ
˜š
œ˜Kš
œ%™%Kš	œœ
œ
œœ
˜?Kšœ	œ˜"Kšœœ˜ Kšœœ˜šœœœœ˜Kšœ˜Kš
œ5™5šœœœ˜8Kš
œ"™"Kšœ1˜8Kš
œ˜Kš
œ˜Kš
œ˜Kšœ
˜—šœœ
œ˜˜Kš	œœœ
œœ˜;Kš
œ/˜/Kš	œœœ
œœ˜DKš
œ˜—K˜—K˜
—šœ˜Kš
œC™Cšœœ
œ
˜Kšœ5˜<Kšœ
˜—K˜——K˜—šœœ˜šœœ
˜šœœ˜Kš
œ/™/šœ
œ
˜šœœ˜Kš
œ5™5Kšœœ
˜Kšœ@˜Gšœœ
œ˜"Kš
œp™p—K˜—šœ
œ˜Kš
œ4™4Kš	œœ
œ
œœ
˜?Kšœ	œ˜"Kšœœ˜šœœ˜šœ	œ
œ
œ˜Kšœœ˜(Kš
œ˜Kš
œ(˜(K˜—K˜Kš
œ˜Kš
œ˜K˜—Kš
œ-˜-Kšœœ
œ	Ÿ˜7K˜—šœ˜Kš
œ(™(Kš	œœ
œ
œœ
˜?Kšœ	œ˜"Kš
œ˜Kšœœ˜šœœ
œ˜šœ	œ
œ
œ˜Kšœœ˜(Kš
œ˜Kš
œ(˜(K˜—Kšœ0˜7Kš
œ˜Kšœ
˜—K˜———Kšœœ	Ÿ˜3—K˜—Kšœœ	Ÿ˜3—š
œ˜Kš
œ*™*—š
œ˜Kš
œ2™2—š
œ˜Kš
œ5™5—Kšœ
˜—K˜K˜—šžœœ
œ	œ
œœ	œœœ
œœœ	˜€
Kšœ'œ
œΝ™όšœœ*˜2Kš
œ#™#—šœœ˜Kš
œ7™7—šœœœ
œ˜šœœ˜Kš
œD™D—šœœ˜(Kš
œ$™$—šœœ˜*Kš
œ.™.—Kšœœ	œ
œœ
œ>˜…
Kš
œ˜Kšœ
˜K˜—K˜K˜—šžœœ
œ
œ#œ	œœœ	˜~Kšœκ
œ/œ
œ'™Μšœœ*˜2Kš
œ#™#—šœœ˜,Kš
œ7™7—šœœ˜Kšœk˜rKšœ˜
K˜—K˜K˜—šžœœ
œ
œœœœœœœ˜VKš
œ™Kšœœ˜K˜K˜K˜Kšœ
œ
œœ˜#Kš
œ	œ
œ
œœ˜*šœœœ
œœ
œ˜,Kš
œ"™"šœœ
œ˜'Kšœ#œ
œœ˜9Kšœ
˜—Kšœœ˜—Kšœ˜%Kš
œ˜K˜—šžœœ
œ
œœœœ
œœ˜eKš
œ@™@Kš
œ5™5Kš
œ™Kšœœ˜K˜K˜K˜š
œœ
œœ
œ˜#Kš
œR™RKšœœ˜Kšœœ˜Kšœœœ˜šœ˜šœ
˜šœœ
œ	˜Kšœœ˜Kšœœ˜Kšœ	œ
œ
˜Kš
œ	œ
œœ
œ˜4Kš
˜——šœ
˜šœœ
œ	˜Kšœœ˜Kšœœ˜Kšœ
œ
œ˜0Kšœ
œ
œ˜0Kšœ	œ
œ
˜Kš
œ	œ
œœ
œ˜4Kšœ
˜———Kšœ˜%K˜—š
œ
˜
Kš
œ8™8Kšœœœ
˜Kšœœ˜Kšœœ˜š
˜šœœ˜Kš
œ™šœ˜Kš
œ
œœ
œœ˜2—K˜+Kšœ	œ
œ
˜K˜K˜—šœœ˜Kš
œ™Kšœœ
œ˜4K˜+Kšœ	œ
œ
˜K˜K˜—˜
Kšœœ˜ Kšœœ˜ šœ	œ˜šœ
œœ˜Kšœ
œ
œ˜0Kšœ
œ
œ˜0Kšœ	œ
œ
œ˜Kš
œ˜—Kšœœœ˜-Kšœ
˜K˜—K˜—K˜Kšœ
˜—K˜—˜K˜——šžœœ
œœ
œœœ
œœœœœ˜²
Kšœœœœœ
œ0˜XKšœœœœœ
œ0˜XKšœœœ
˜Kšœœœ
˜Kšœœ˜Kšœœ˜šœ	˜šœœ˜Kš
œ™Kš
œ<˜<Kšœ	œ
œ
˜K˜K˜—šœœ˜Kš
œ™Kš
œ<˜<Kšœ	œ
œ
˜K˜K˜—˜
Kšœœ˜ Kšœœ˜ šœ	œ˜šœ
œœ˜Kšœ
œ
œ˜0Kšœ
œ
œ˜0Kšœ	œ
œ
œ˜K˜—Kšœœœ˜-Kšœ
˜K˜—K˜—K˜K˜K˜Kšœ
˜—Kšœ!˜'K˜K˜—šžœœ
œœ
œœœ
œœœœœœ˜£
Kšœœœœœ
œ0˜XKšœœœœœ
œ0˜Xšœ
œ˜Kšœœœ
˜Kšœœ˜Kšœœ˜šœ
˜šœœ˜Kš
œ™Kš
œ<˜<Kšœ	œ
œ
˜K˜K˜—šœœ˜Kš
œ™Kš
œ<˜<Kšœ	œ
œ
˜K˜K˜—˜
Kšœœ˜ Kšœœ˜ šœ	œ˜šœ
œœ˜Kšœ
œ
œ˜0Kšœ
œ
œ˜0Kšœ	œ
œ
œ˜K˜—Kšœœ˜Kšœ
˜K˜—K˜—K˜K˜K˜Kšœ
˜—Kšœœ˜K˜—Kšœœ˜K˜K˜—šžœœ
œœ	œœœ	œœœ˜rKš
œ/™/Kš
œE™EKš
œ=™=Kš
œ˜Kš
œœœ
œœ˜5Kš
œ˜K˜K˜š
˜Kšœœ˜šœ	œ
˜K™5Kšœœ
˜˜šœœ
˜˜K˜K˜K˜K˜—˜Kšœœ˜šœ	˜Kšœ˜!Kšœ7˜;—K˜—˜Kšœœ˜Kšœœ˜šœ
œ
˜K˜)K˜;šœ˜Kš
œ˜K˜K˜K˜——K˜—Kšœœ˜Kšœœ˜——Kšœœ˜—Kšœœ˜&Kšœ
˜—K˜K˜—šžœœ
œœœœ˜2Kšœ˜Kš
œ˜K˜—šžœœ
œœœœ˜3Kš
œ0™0Kšœ˜Kš
œ˜K˜—šžœœ
œœœœ˜1Kš
œ™Kšœ˜Kš
œ˜K˜—šžœœœœœœ˜;Kšœ˜Kš
œ˜K˜——™šžœœ
œœœœœœœœ
œœ˜vKš
œš™šKšœœ˜K˜K˜šœœ˜Kšœœ˜K˜K˜šœœ˜Kšœœœ
˜Kšœ
œ˜Kšœ
œ˜š
˜šœœ˜Kš
œ™K˜8Kšœ	œ
œ
˜K˜K˜—šœœ˜Kš
œ™K˜8Kšœ	œ
œ
˜K˜K˜—˜
Kšœœ˜ Kšœœ˜ šœ	œ˜šœ
œœ˜Kšœ
œ
œ˜0Kšœ
œ
œ˜0Kšœ	œ
œ
œ˜K˜—Kšœ
˜Kšœ
˜K˜—K˜—K˜K˜Kšœ
˜—K˜—K˜—˜K˜——šžœœ
œ
œœœœœœ˜[Kšœ7˜=K˜K˜—šžœœ
œœœœœœ
œœœ˜aKš
œξ™ξKšœœœ
˜ K˜&Kšœœœœ˜6šœ
œ˜Kšœœ
˜Kšœ
œ
œ˜Kš
œ˜K˜šœ˜šœ˜šžœœœœœœ˜/Kš
œœ'œ
œœ˜GKšœœœ˜ K˜—Kšœœ
œ˜-Kš
œ
˜
—šœ˜šžœœœœœœ˜0Kšœ
œ
œ˜0Kš
œœ'œ
œœ˜GKšœœœ˜ K˜—Kšœ	œ	œ˜,Kšœœ
œ˜/Kš
œ˜——K˜—Kšœ˜K˜K˜—šžœœ
œ
œœœœ
œœ˜UKšœœ˜'Kšœœ
œ˜+Kšœ	˜K˜K˜—šžœœ
œœœœœœœ˜cKšœœœ
˜K˜&Kšœœ
˜&Kšœ
œ
œ˜šœœ˜KšœœŸ˜7KšœœŸ˜1Kšœœ˜*šœœ˜š	œœ

œ
œ
˜$Kšœœ˜Kš
œœ	œ!œ
œ˜HKšœ
˜—K˜
—šœ˜Kšœ
œ
œ˜0š	œœ

œ
œ
˜$Kšœœ˜Kšœ
œ
œ˜0Kš
œœ	œ!œ
œ˜HKšœ
˜—K˜—K˜—Kšœ˜K˜K˜—šžœœ
œœœœ
œœœ˜YKš
œ…™…šœ
œœœœœ
œœœ˜Ršœ
˜Kšœœ˜$šœ	œ˜Kš
œ"™"Kšœ
œ
œœ˜Kš
œ™šœ
Ÿ˜Kšœœ
˜Kšœœ˜Kšœœ˜
Kšœœ˜šœ˜Kšœ œ
œœ˜5K˜K˜Kšœ
˜—K˜—Kšœœ˜K˜—Kšœœ
œœ˜!Kš
œ3™3šœœ˜$šœ
œœ˜Kšœ
œ
œ˜0Kšœ
œ
œ˜0K˜—Kšœ	œ
œœ˜K˜—K˜K˜K˜K˜Kšœ
˜—Kšœ˜K˜—Kšœœ˜ Kšœœ˜Kš
Ϥ
™§
šœ
˜Kšœœ˜Kšœœ˜#Kšœœ
˜	Kšœ	œ
œ
˜Kšœ
œ
œœ˜ K˜	K˜Kš
œ˜šœ
œœ˜Kšœ
œ
œ˜0Kšœ
œ
œ˜0K˜—Kšœ	œ
œœ˜Kšœ
˜—Kšœ˜%K˜K˜—šžœœ
œœœœœœœ˜OKš
œ’
™’
Kšœœ˜Kš
œ*˜*Kšœ	œœœ
œœ˜=šœœ
œ˜#šž	œœœœœœ˜4šœœ
œ˜Kšœœ
œœ˜&Kšœ
˜—Kš
œ˜Kšœœ˜Kš
œ˜—Kšœ#œ
œ˜7K˜—Kšœ	˜K˜K˜—šžœœ
œœœœœœœ˜QKš
ϥ
™•
Kšœœ˜Kš
œ*˜*Kšœ	œœœ
œœ˜=Kšœœ
œ˜ šœ
œ˜šž	œœœœœœ˜4šœœ
œ˜Kšœœ
œ
œ˜$Kšœ
˜—Kšœœ˜Kšœœœ˜/Kš
œ˜—Kšœ#œ
œ˜7K˜—Kšœ˜
K˜K˜—šžœœ
œœœœœ˜\Kš
œg™gKšœœ
œ
œ
˜šœœ
˜˜	K˜Kšœœ
œ˜-—˜šœœ
˜˜Kšœœ
˜Kšœœ˜Kšœ
œ
œ
œ˜6Kšœœ
œ˜3K˜1K˜—˜Kšœœ
˜Kšœœ
˜Kšœœ˜Kšœœ
˜Kšœœ˜K˜5K˜3K˜K˜Kšœœ˜2Kšœœ
œ˜2Kšœœ
œ˜)K˜—˜Kšœœ
˜Kšœœ
˜Kšœ	œ
˜Kšœœ
˜Kšœ
œ˜K˜1K˜5K˜K˜Kšœœ˜2Kšœœœ
œ˜DKšœœ
œ˜9Kšœ
œœ
œ˜;Kšœœ
œ˜.K˜—˜Kš
œ˜Kš
œœœ
œ
œ˜7K˜—Kšœœ˜——Kšœœ˜—K˜Kšœœ
œ˜5K˜K˜Kšœœ
œœ
˜"K˜—š
œ ™ K™>K™š
žœœœœœ˜1K˜—šœœœœ	œœ˜8Kš
œ*™*K˜—Kš	œ
œœœ
œ
˜;Kšœœœ
˜(šžœœ˜KšœŠ
œG™Τ
šœœ
œ˜ Kšœœœ˜&š
œ	˜	Kš
œ*™*—š
œ	˜	Kš
œ1™1—š
œ˜Kš
œ<™<—šœœ
œ˜*K™)K™!šœ
œ
œ˜Kšœœ
˜Kšœ˜—Kšœ
˜—Kš
œ˜K˜—Kš
œ˜K˜—šžœ
˜K™Kšœœ˜'Kšœœ&˜1•StartOfExpansion[]šœ˜Kšœ˜Kšœ˜!Kšœ
œœ˜—Kšœœ
œ˜6Kšœ!œ
œœ˜7šœœ
˜Kšœœœ
˜;Kšœœœœ˜6Kšœ	œœœ˜9Kšœœœ˜—Kš
œ˜K˜——šžœœ
œœ	œœœœœ˜nKš
œY™YKšœ-˜3K˜K˜Kšœœ˜Kšœœœ	œ	œœœœ˜VKš	œ
œœœœ˜1š
ž
œœœœœ˜2Kšœ	Ÿ9˜BKšœœœ
˜Kšœœ˜šžœœœ˜&šœ˜Kšœ˜šœ˜Kšœ
œ
œœ˜CKšœœ˜'šœ˜šœœ
œ˜Kšœ
œ˜Kš
œ ˜ —Kš
œ˜Kšœ
˜—Kš
œ˜Kš
œ˜——Kš
œ˜—šžœœœœ˜-šœ˜Kšœ˜šœ˜Kšœœ˜'Kšœœœ
˜7Kš
œ˜Kš
œ˜——Kš
œ˜—šžœœ˜šœœ˜Kšœœ;˜FKš
œ*˜*Kš
œ˜Kš
œ˜—Kš
œ˜—šžœœ	œœœœœ˜HKš
œ;™;–[]šœ
œ
˜Kšœœ
œ˜Kšœœ˜*šœ˜Kšœœ˜Kšœ	œ˜ Kšœœ˜+šœ
œœ
œœ˜fKš
œ˜Kš
œ
˜
Kšœ
˜—KšœS˜YKš
œ
˜
——Kš
œ˜—Kš
œ(˜(Kš
œ)˜)Kšœ+˜1Kš
œ˜K˜—Kšœ	œœ
˜K˜šžœœœœ˜Kšœ
œ
œ˜(Kšœ
˜šœ˜Kšœœ˜'Kšœœ
œ
œœ
œ	˜Všœœ
˜šœœ˜)Kš
œ]˜]Kš
œ˜—šœœ˜)šœœ˜!Kšœ#œ.˜TKš
œ˜—šœœ˜Kšœ
œœ˜.Kšœœ˜"Kš
œ?˜?Kš
œ˜—Kš
œ˜—šœ	œ˜+Kšœœ˜Kšœœ ˜)Kšœœ˜(Kšœ	œ˜šœœ˜Kšœ$œ(˜OKš
œ˜—šœœœ˜4Kšœ
œœ˜(Kšœœœ˜'Kš
œC˜CKš
œ˜—šœœ˜Kšœ
œœ$˜7Kšœœœ%˜6Kš
œ@˜@Kš
œ˜—Kš
œ˜—Kšœ˜—Kš
œ˜——Kš
œ˜K˜——K™—šœ
˜K˜—Kšœ/œ™P™XKšœ.œ™O—K™HK™8K™8K™;K™;K™HK™RK™5Kšœ:™=K™-K™1K™SK™O™3K™Š
—K™J˜J˜—…—{VΥ