<> <> <> <> <<>> 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> [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.