DIRECTORY Basics, RefText, Rope, RopeHash, RopeParts;

RopePartsImpl: CEDAR PROGRAM
IMPORTS RefText, Rope, RopeHash, RopeParts
EXPORTS RopeParts
= BEGIN OPEN RopeParts;
FromChar: PUBLIC PROC [c: CHAR] RETURNS [RopePart]
~ {RETURN InlineMake[Rope.FromChar[c]]};

Make: PUBLIC PROC [base: ROPE, start: INT _ 0, len: INT _ MaxLen] RETURNS [RopePart]
~ {limit: INT ~ base.InlineLength[];
IF start>limit THEN RETURN [nil];
RETURN [[base, start, MIN[len, limit-start]]]};

ToRope: PUBLIC PROC [rp: RopePart] RETURNS [ROPE]
~ {RETURN rp.base.Substr[start: rp.start, len: rp.len]};

Simplify: PUBLIC PROC [rp: RopePart, start, end: BOOL _ TRUE] RETURNS [RopePart] ~ {
IF
((NOT start) OR rp.start=0) AND
((NOT end) OR rp.start+rp.len = rp.base.Length)
THEN RETURN [rp]
ELSE RETURN InlineMake[InlineToRope[rp]]};

Cat: PUBLIC PROC [r1, r2, r3, r4, r5: RopePart _ nil] RETURNS [RopePart] ~ {
IF r2#nil THEN r1 _ Concat[r1, r2];
IF r3#nil THEN r1 _ Concat[r1, r3];
IF r4#nil THEN r1 _ Concat[r1, r4];
IF r5#nil THEN r1 _ Concat[r1, r5];
RETURN [r1]};

Concat: PUBLIC PROC [base, rest: RopePart _ nil] RETURNS [ans: RopePart] ~ {
easy: BOOL;
[easy, ans] _ EasyConcat[base, rest];
IF NOT easy THEN ans _ InlineMake[InlineToRope[base].Concat[InlineToRope[rest]]];
RETURN};

EasyConcat: PUBLIC PROC [base, rest: RopePart _ nil] RETURNS [BOOL, RopePart] ~ {
IF Rope.EqualSubstrs[base.base, base.start+base.len, rest.len, rest.base, rest.start, rest.len] THEN RETURN [TRUE, [base.base, base.start, base.len+rest.len]];
IF rest.start>=base.len AND Rope.EqualSubstrs[base.base, base.start, base.len, rest.base, rest.start-base.len, base.len] THEN RETURN [TRUE, [rest.base, rest.start-base.len, rest.len+base.len]];
RETURN [FALSE, nil]};

Compare: PUBLIC PROC [s1, s2: RopePart, case: BOOL _ TRUE] RETURNS [Basics.Comparison]
~ {RETURN Rope.CompareSubstrs[s1.base, s1.start, s1.len, s2.base, s2.start, s2.len, case]};

Equal: PUBLIC PROC [s1, s2: RopePart, case: BOOL _ TRUE] RETURNS [BOOL]
~ {RETURN Rope.EqualSubstrs[s1.base, s1.start, s1.len, s2.base, s2.start, s2.len, case]};

EqualToRope: PUBLIC PROC [s1: RopePart, s2: ROPE, case: BOOL _ TRUE] RETURNS [BOOL]
~ {RETURN Rope.EqualSubstrs[s1.base, s1.start, s1.len, s2, 0, MaxLen, case]};

Fetch: PUBLIC PROC [base: RopePart, index: INT _ 0] RETURNS [c: CHAR]
~ {RETURN base.base.InlineFetch[base.start+index]};

Index: PUBLIC PROC [s1, s2: RopePart, pos1: INT _ 0, case: BOOL _ TRUE, clipBeforeSeek: BOOL _ FALSE] RETURNS [INT] ~ {
r2: ROPE ~ InlineToRope[s2];
IF clipBeforeSeek THEN RETURN InlineToRope[s1].Index[pos1, r2, case];
{ans: INT _ s1.base.Index[s2: r2, pos1: s1.start+pos1, case: case] - s1.start;
IF ans > s1.len - s2.len THEN RETURN [s1.len];
RETURN [ans]}};

Find: PUBLIC PROC [s1, s2: RopePart, pos1: INT _ 0, case: BOOL _ TRUE, clipBeforeSeek: BOOL _ FALSE] RETURNS [INT] ~ {
r2: ROPE ~ InlineToRope[s2];
IF clipBeforeSeek THEN RETURN InlineToRope[s1].Find[r2, pos1, case];
{ans: INT _ s1.base.Find[s2: r2, pos1: s1.start+pos1, case: case];
IF ans = -1 THEN RETURN [ans];
ans _ ans-s1.start;
IF ans > s1.len - s2.len THEN RETURN [-1];
RETURN [ans]}};

FindBackward: PUBLIC PROC [s1, s2: RopePart, pos1: INT _ MaxLen, case: BOOL _ TRUE, clipBeforeSeek: BOOL _ FALSE] RETURNS [INT] ~ {
r2: ROPE ~ InlineToRope[s2];
IF clipBeforeSeek THEN RETURN InlineToRope[s1].FindBackward[r2, pos1, case];
pos1 _ MIN[pos1, MaxLen-s1.start];
{ans: INT _ s1.base.FindBackward[s2: r2, pos1: s1.start+pos1, case: case];
RETURN [MAX[ans-s1.start, -1]]}};

IsEmpty: PUBLIC PROC [r: RopePart] RETURNS [BOOL]
~ {RETURN [r.len = 0]};

Length: PUBLIC PROC [base: RopePart] RETURNS [INT]
~ {RETURN [base.len]};

Size: PUBLIC PROC [base: RopePart] RETURNS [INT]
~ {RETURN [base.len]};

Substr: PUBLIC PROC [base: RopePart, start: INT _ 0, len: INT _ MaxLen] RETURNS [RopePart] ~ {
IF start >= base.len THEN RETURN [nil];
RETURN [[base.base, base.start+start, MIN[len, base.len-start]]]};

Replace: PUBLIC PROC [base: RopePart, start: INT _ 0, len: INT _ MaxLen, with: RopePart _ nil] RETURNS [RopePart]
~ {RETURN Make[InlineToRope[base].Replace[start, len, InlineToRope[with]]]};

ReplaceElt: PUBLIC PROC [base: RopePart, index: INT, with: CHAR] RETURNS [RopePart]
~ {RETURN Replace[base, index, 1, FromChar[with]]};

Run: PUBLIC PROC [s1: RopePart, pos1: INT _ 0, s2: RopePart, pos2: INT _ 0, case: BOOL _ TRUE] RETURNS [INT] = {
RETURN [RopeRun[s1.base, s2.base, s1.start+pos1, s2.start+pos2, MIN[s1.InlineLength, s2.InlineLength], case]]};

RopeRun: PUBLIC PROC [s1, s2: ROPE, pos1, pos2, limit: INT, case: BOOL] RETURNS [result: INT _ 0] = {
len1: INT _ Rope.InlineLength[s1];
IF NonNeg[pos1] < len1 THEN {
len2: INT _ Rope.InlineLength[s2];
IF NonNeg[pos2] < len2 THEN {
r1,r2: ROPE _ NIL;
st1,sz1,lm1: INT _ 0;
st2,sz2,lm2: INT _ 0;
WHILE result<limit DO
IF st1 = lm1 THEN {
[r1, st1, sz1] _ Rope.ContainingPiece[s1, pos1 _ pos1 + sz1];
IF sz1 = 0 THEN RETURN;
lm1 _ st1 + sz1;
};
IF st2 = lm2 THEN {
[r2, st2, sz2] _ Rope.ContainingPiece[s2, pos2 _ pos2 + sz2];
IF sz2 = 0 THEN RETURN;
lm2 _ st2 + sz2;
};
{
c1: CHAR _ Rope.InlineFetch[r1, st1];
c2: CHAR _ Rope.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, subject: RopePart, case: BOOL _ TRUE] RETURNS [BOOL]
~ {RETURN Rope.EqualSubstrs[prefix.base, prefix.start, prefix.len, subject.base, subject.start, MIN[subject.len, prefix.len]]};

IsSuffix: PUBLIC PROC [suffix, subject: RopePart, case: BOOL _ TRUE] RETURNS [BOOL]
~ {IF subject.len < suffix.len THEN RETURN [FALSE];
RETURN Rope.EqualSubstrs[suffix.base, suffix.start, suffix.len, subject.base, subject.start+subject.len-subject.len, suffix.len]};

Match: PUBLIC PROC [pattern, object: RopePart, case: BOOL _ TRUE] RETURNS [BOOL]
~ {RETURN MatchSubstrs[pattern.base, pattern.start, pattern.len, object.base, object.start, object.len, case]};

MatchSubstrs: PROC [pattern: ROPE, start1: INT _ 0, len1: INT _ INT.LAST, object: ROPE, start2: INT _ 0, len2: INT _ INT.LAST, case: BOOL _ TRUE] RETURNS [BOOL] ~ {
submatch: PROC [i1: INT, len1: INT, i2: INT, len2: INT] RETURNS [BOOL] = TRUSTED {
WHILE len1 > 0 DO
c1: CHAR _ pattern.InlineFetch[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 _ object.InlineFetch[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];
};
after1: INT _ start1+MIN[pattern.InlineSize[]-start1, len1];
after2: INT _ start2+MIN[object.InlineSize[]-start2, len2];
WHILE after1 > start1 DO
n: INT _ after1 - 1;
c1: CHAR _ pattern.InlineFetch[n];
c2: CHAR;
IF c1 = '* THEN EXIT;
IF after2 = 0 THEN RETURN [FALSE];
after1 _ n;
after2 _ after2 - 1;
c2 _ object.InlineFetch[after2];
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 [start1, after1-start1, start2, after2-start2]];
};

SkipTo: PUBLIC PROC [s: RopePart, pos: INT _ 0, skip: RopePart] RETURNS [INT]
~ {RETURN InlineToRope[s].SkipTo[pos, InlineToRope[skip]]};

SkipOver: PUBLIC PROC [s: RopePart, pos: INT _ 0, skip: RopePart] RETURNS [INT]
~ {RETURN InlineToRope[s].SkipOver[pos, InlineToRope[skip]]};

Map: PUBLIC PROC [base: RopePart, action: ActionType] RETURNS [BOOL]
~ {RETURN base.base.Map[base.start, base.len, action]};

Translate: PUBLIC PROC [base: RopePart, translator: TranslatorType _ NIL] RETURNS [RopePart]
~ {RETURN InlineMake[base.base.Translate[base.start, base.len, translator]]};

ToRefText: PUBLIC PROC [base: RopePart] RETURNS [REF TEXT] ~ {
rt: REF TEXT ~ RefText.New[base.len];
IF AppendChars[rt, base] # base.len THEN ERROR;
RETURN [rt]};

AppendChars: PUBLIC PROC [to: REF TEXT, from: RopePart] RETURNS [charsMoved: NAT]
~ {RETURN Rope.AppendChars[to, from.base, from.start, from.len]};

UnsafeMoveChars: PUBLIC UNSAFE PROC [to: Basics.UnsafeBlock, from: RopePart] RETURNS [charsMoved: INT]
~ UNCHECKED {to.count _ MIN[to.count, from.len];
RETURN Rope.UnsafeMoveChars[to, from.base, from.start]};

Hash: PUBLIC PROC [base: RopePart, case: BOOL _ TRUE, seed: CARDINAL _ defaultSeed] RETURNS [CARDINAL]
~ {RETURN RopeHash.FromRope[base.base, case, base.start, base.len, seed]};

NonNeg: PROC [x: INT] RETURNS [NAT] = INLINE {RETURN [x]};

END.
φRopePartsImpl.mesa
Copyright Σ 1990 by Xerox Corporation.  All rights reserved.
Last tweaked by Mike Spreitzer on March 30, 1992 4:11 pm PST
Some of the impls are not yet as smart as they could be.

Part 1:  Basic operations and definitions
Part 2:  Extended operations and definitions
need a new piece from s1
need a new piece from s2
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.
This routine is used to check that the argument is not negative.  This version depends on the compiler for the bounds checking.
Κ³˜
codeš
œ™Kš
œ<™<K™<—K˜K™8K™KšΟk	œ,˜5K˜šΡbln
œœ
˜Kšœ#˜*Kšœ
˜—Kšœœ
œ˜
headš
œ)™)š
Οnœœ
œœœ˜2Kšœœ˜(K˜—šŸœœ
œœ	œœœ˜Tšœ
œ˜$Kšœ
œ
œ˜!Kšœœ˜/——K˜š
Ÿœœ
œœœ
˜1Kšœœ/˜8—K˜šŸœœ
œœœœ˜Tš
˜Kšœœœ
˜Kšœœœ"˜/—Kšœ
œ˜Kšœ
œ˜*—K˜šŸœœ
œ&œ˜LKšœœ˜#Kšœœ˜#Kšœœ˜#Kšœœ˜#Kšœ˜
K˜—šŸœœ
œœ˜LKšœœ
˜Kš
œ%˜%Kšœ
œœA˜QKšœ˜—K˜š
Ÿ
œœ
œœœ˜QKšœ^œ
œœ.˜Ÿ
Kš
œœ^œ
œœ7˜Α
Kšœœ˜K˜—šŸœœ
œœœœ˜VKšœœR˜[K˜—šŸœœ
œœœœœ
˜GKšœœP˜YK˜—šŸœœ
œœœœœœ
˜SKšœœD˜MK˜—šŸœœ
œœœœ
˜EKšœœ*˜3K˜—šŸœœ
œœœœœœœœ˜wKšœœ˜Kšœœ
œ(˜EKšœœE˜NKšœœ
œ
˜.Kšœ	˜K˜—šŸœœ
œœœœœœœœ˜vKšœœ˜Kšœœ
œ'˜DKšœœ9˜BKšœ
œ
œ˜Kš
œ˜Kšœœ
œ˜*Kšœ	˜K˜—šŸœœ
œœœœœœœœ˜ƒ
Kšœœ˜Kšœœ
œ/˜LKšœœ˜"KšœœA˜JKšœœ˜!K˜—š
Ÿœœ
œœœ
˜1Kšœœ˜K˜—š
Ÿœœ
œœœ
˜2Kšœœ
˜K˜—š
Ÿœœ
œœœ
˜0Kšœœ
˜K˜—šŸœœ
œœœœ˜^Kšœœ
œ˜'Kšœ œ˜BK˜—šŸœœ
œœœ!œ˜qKšœœC˜LK˜—šŸ
œœ
œœœœ˜SKšœœ*˜3K˜——š
œ,™,šŸœœ
œœœœœœœ˜pKšœ:œ,˜o—K˜šŸœœ
œ
œœœœ
œ	˜eKšœœ˜"šœœ˜Kšœœ˜"šœœ˜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˜—šŸœœ
œ#œœœœ
˜SKšœœWœ˜—K˜šŸœœ
œ#œœœœ
˜Sš	œœœ
œœ˜3Kšœ|˜‚
—K˜—šŸœœ
œ#œœœœ
˜PKšœœf˜oK˜—š Ÿœœœ
œœœ
œ
œ
œœœ
œœœœœ˜€
šœ
œœœœœœœœ˜Ršœ
˜Kšœœ˜#šœ	œ˜Kš
œ"™"Kšœ
œ
œœ˜Kš
œ™šœ
Οc˜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šœ;˜AK˜—K˜šŸœœ
œœœœ
˜MKšœœ2˜;—K˜šŸœœ
œœœœ
˜OKšœœ4˜=K˜—š
Ÿœœ
œ&œœ
˜DKšœœ.˜7K˜—š
Ÿ	œœ
œ/œœ˜\KšœœD˜MK˜—šŸ	œœ
œœœ
œ˜>Kšœœ
œ˜%Kšœ"œ
œ
˜/Kšœ˜
K˜—šŸœœ
œœ
œœœ
˜QKšœœ8˜AK˜—šŸœœ
œ
œ*œœ
˜fšœ	œ
œ˜0Kšœ2˜8—K˜—šŸœœ
œœœœœœ
˜fKšœœA˜J—K˜šŸœœœœœœœ˜:K™——K˜Kšœ
˜—…—"°2Y