RopeSequenceImpl.mesa
Copyright Ó 1990 by Xerox Corporation. All rights reserved.
Coolidge, July 9, 1990 6:57:20 pm GMT
Last changed by Coolidge, July 11, 1990 0:34 am GMT
Last tweaked by Mike Spreitzer on October 5, 1990 8:10:39 am PDT
DIRECTORY Basics, IO, Rope, RopeParts, RopeSequence, RopeSequencePrivate, RuntimeError, SafeStorage;
RopeSequenceImpl: CEDAR PROGRAM
IMPORTS IO, Rope, RopeParts, RuntimeError, SafeStorage
EXPORTS RopeSequence
~ BEGIN OPEN RP:RopeParts, RopeSequence;
ROPE: TYPE ~ Rope.ROPE;
RopeSeq: TYPE = REF RopeSeqPrivate;
RopeSeqPrivate: PUBLIC TYPE ~ RopeSequencePrivate.RopeSeqPrivate;
QuaRopeSeq: PUBLIC PROC [ra: REF ANY] RETURNS [MaybeRopeSeq] ~ {
IF ra=NIL THEN RETURN [[TRUE, NIL]];
WITH ra SELECT FROM
x: RopeSeq => RETURN [[TRUE, x]];
ENDCASE => RETURN [[FALSE, NIL]]};
AsRopeSeq: PUBLIC PROC [ra: REF ANY] RETURNS [RopeSeq] ~ {
IF ra=NIL THEN RETURN [NIL];
WITH ra SELECT FROM
x: RopeSeq => RETURN [x];
ENDCASE => SafeStorage.NarrowRefFault[ra, CODE[RopeSeq]]};
ParsePartToSeq: PUBLIC PROC [part: RopePart, seperator: CHAR] RETURNS [RopeSeq] ~ {
seperatorRope: ROPE ← Rope.FromChar[seperator];
partRope: ROPE ← part.InlineToRope[];
seperatorPos: INT ← -1;
lastSeperatorPos: INT;
resultSeq: RopeSeq ← NIL;
resSeq: RopePart;
componentCount: INT ← 1;
IF partRope = NIL THEN RETURN[NIL];
Count the components
seperatorPos ← partRope.Find[seperatorRope, 0, FALSE];
WHILE seperatorPos # -1 DO
componentCount ← componentCount + 1;
seperatorPos ← partRope.Find[seperatorRope, seperatorPos + 1, FALSE];
ENDLOOP;
Allocate a RopeSeqPrivate to hold the parts
resultSeq ← NEW[RopeSeqPrivate[componentCount]];
And stuff the parsed bits into it
componentCount ← 0;
lastSeperatorPos ← -1;
seperatorPos ← partRope.Find[seperatorRope, 0, FALSE];
WHILE seperatorPos # -1 DO
resSeq ← [partRope, lastSeperatorPos+1, seperatorPos-lastSeperatorPos-1];
resultSeq.elts[componentCount] ← resSeq;
componentCount ← componentCount + 1;
lastSeperatorPos ← seperatorPos;
seperatorPos ← partRope.Find[seperatorRope, seperatorPos+1, FALSE];
ENDLOOP;
resultSeq.elts[componentCount] ← [partRope, lastSeperatorPos+1, partRope.Length - (lastSeperatorPos+1)];
IF componentCount+1 # resultSeq.len THEN ERROR;
RETURN[resultSeq]};
UnparseSeqToPart: PUBLIC PROC [seq: RopeSeq, seperator: CHAR] RETURNS [ans: RopePart] ~ {
IF seq=NIL OR seq.len=0 THEN RETURN [RP.nil];
IF seq.len=1 THEN RETURN [seq[0]];
{sepPart: RopePart ~ RP.FromChar[seperator];
ans ← seq[0];
FOR i: INT IN (0..seq.len) DO
easy: BOOL;
tmp: RopePart;
[easy, tmp] ← ans.EasyConcat[sepPart];
IF easy THEN [easy, tmp] ← tmp.EasyConcat[seq[i]];
IF NOT easy THEN {
buf: IO.STREAM ~ IO.ROS[];
buf.PutRope[ans.base, ans.start, ans.len];
FOR j: INT IN [i..seq.len) DO
elt: RopePart ~ seq[j];
buf.PutChar[seperator];
buf.PutRope[elt.base, elt.start, elt.len];
ENDLOOP;
RETURN [RP.Make[buf.RopeFromROS[]]]};
ENDLOOP;
RETURN}};
Cons: PUBLIC PROC [parts: LIST OF RopePart] RETURNS [RopeSeq] ~ {
resultSeq: RopeSeq ← NIL;
componentCount: NAT ← 0;
First, need to know how many parts we have.
FOR part: LIST OF RopePart ← parts, part.rest WHILE part # NIL DO
componentCount ← componentCount + 1;
ENDLOOP;
Allocate a RopeSeqPrivate to hold the parts
resultSeq ← NEW[RopeSeqPrivate[componentCount]];
componentCount ← 0;
And stuff the parts into it
FOR part: LIST OF RopePart ← parts, part.rest WHILE part # NIL DO
resultSeq[componentCount] ← part.first;
componentCount ← componentCount + 1;
ENDLOOP;
RETURN[resultSeq]};
FromProc: PUBLIC PROC [len: INT, Generate: PROC [INT] RETURNS [RopePart]] RETURNS [ans: RopeSeq] ~ {
ans ← NEW [RopeSeqPrivate[len]];
FOR i: INT IN [0..len) DO ans[i] ← Generate[i] ENDLOOP;
RETURN};
Cat: PUBLIC PROC [r1, r2, r3, r4, r5: RopeSeq ← nil] RETURNS [RopeSeq] ~ {
len: INT ~ Length[r1] + Length[r2] + Length[r3] + Length[r4] + Length[r5];
ans: RopeSeq ~ NEW [RopeSeqPrivate[len]];
n: INT ← 0;
Append: PROC [rs: RopeSeq] ~ {
FOR i: INT IN [0..Length[rs]) DO ans[n] ← rs[i]; n ← n+1 ENDLOOP;
RETURN};
Append[r1]; Append[r2]; Append[r3]; Append[r4]; Append[r5];
IF n#len THEN ERROR;
RETURN [ans]};
Concat: PUBLIC PROC [base, rest: RopeSeq ← nil] RETURNS [ans: RopeSeq] ~ {
lb: INT ~ Length[base];
lr: INT ~ Length[rest];
ans ← NEW [RopeSeqPrivate[lb+lr]];
FOR i: INT IN [0..lb) DO ans[i] ← base[i] ENDLOOP;
FOR i: INT IN [0..lr) DO ans[lb+i] ← rest[i] ENDLOOP;
RETURN};
Compare: PUBLIC PROC [s1, s2: RopeSeq, case: BOOLTRUE] RETURNS [Basics.Comparison]
~ {RETURN CompareSubseqs[s1: s1, s2: s2, case: case]};
CompareSubseqs: PUBLIC PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOLTRUE]
RETURNS [cmp: Basics.Comparison] ~ {
len1 ← MIN[len1, s1.len-start1];
len2 ← MIN[len2, s2.len-start2];
WHILE len1>0 AND len2>0 DO
p1: RopePart ~ s1[start1];
p2: RopePart ~ s2[start2];
IF (cmp ← p1.Compare[p2, case]) # equal THEN RETURN;
start1 ← start1+1; start2 ← start2+1;
len1 ← len1-1; len2 ← len2-1;
ENDLOOP;
IF len1>0 THEN RETURN [greater];
IF len2>0 THEN RETURN [less];
RETURN [equal]};
Equal: PUBLIC PROC [s1, s2: RopeSeq, case: BOOLTRUE] RETURNS [BOOL]
~ {RETURN EqualSubseqs[s1: s1, s2: s2, case: case]};
EqualSubseqs: PUBLIC PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOLTRUE]
RETURNS [eq: BOOL] ~ {
len1 ← MIN[len1, s1.len-start1];
len2 ← MIN[len2, s2.len-start2];
IF len1 # len2 THEN RETURN [FALSE];
FOR i: INT IN [0 .. len1) DO
IF NOT s1[start1+i].Equal[s2[start2+i], case] THEN RETURN [FALSE];
ENDLOOP;
RETURN [TRUE]};
Fetch: PUBLIC PROC [base: RopeSeq, index: INT ← 0] RETURNS [RopePart]
~ {RETURN [base[index]]};
Index: PUBLIC PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOLTRUE]
RETURNS [INT] ~ {
len1b: INT ~ MIN[len1, s1.len - start1];
len2b: INT ~ MIN[len2, s2.len - start2];
len1c: INT ~ MIN[len1b, s1.len+1-len2b-start1];
IF start1<0 OR start2<0 THEN RuntimeError.BoundsFault[];
IF len1c <= 0 THEN RETURN [start1+len1b];
{rp20: RopePart ~ s2[start2];
FOR N: INT IN [start1 .. start1+len1c) DO
IF s1[N].Equal[rp20, case] THEN {
FOR j: INT IN (0..len2b) DO
IF NOT s1[N+j].Equal[s2[start2+j], case] THEN GOTO Mismatch;
ENDLOOP;
RETURN [N];
EXITS Mismatch => case ← case};
ENDLOOP;
RETURN [start1+len1b]}};
Find: PUBLIC PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOLTRUE]
RETURNS [INT] ~ {
len1b: INT ~ MIN[len1, s1.len - start1];
len2b: INT ~ MIN[len2, s2.len - start2];
len1c: INT ~ MIN[len1b, s1.len+1-len2b-start1];
IF start1<0 OR start2<0 THEN RuntimeError.BoundsFault[];
IF len1c <= 0 THEN RETURN [-1];
{rp20: RopePart ~ s2[start2];
FOR N: INT IN [start1 .. start1+len1c) DO
IF s1[N].Equal[rp20, case] THEN {
FOR j: INT IN (0..len2b) DO
IF NOT s1[N+j].Equal[s2[start2+j], case] THEN GOTO Mismatch;
ENDLOOP;
RETURN [N];
EXITS Mismatch => case ← case};
ENDLOOP;
RETURN [-1]}};
FindBackward: PUBLIC PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOLTRUE]
RETURNS [INT] ~ {
len1b: INT ~ MIN[len1, s1.len - start1];
len2b: INT ~ MIN[len2, s2.len - start2];
len1c: INT ~ MIN[len1b, s1.len+1-len2b-start1];
IF start1<0 OR start2<0 THEN RuntimeError.BoundsFault[];
IF len1c <= 0 THEN RETURN [-1];
{rp20: RopePart ~ s2[start2];
FOR N: INT DECREASING IN [start1 .. start1+len1c) DO
IF s1[N].Equal[rp20, case] THEN {
FOR j: INT IN (0..len2b) DO
IF NOT s1[N+j].Equal[s2[start2+j], case] THEN GOTO Mismatch;
ENDLOOP;
RETURN [N];
EXITS Mismatch => case ← case};
ENDLOOP;
RETURN [-1]}};
IsEmpty: PUBLIC PROC [rs: RopeSeq] RETURNS [BOOL] ~ {RETURN [rs.len = 0]};
Length: PUBLIC PROC [rs: RopeSeq] RETURNS [INT] ~ {RETURN [rs.len]};
Subseq: PUBLIC PROC [base: RopeSeq, start: INT ← 0, len: INT ← MaxLen] RETURNS [ans: RopeSeq] ~ {
len ← MIN[len, base.len-start];
IF start=0 AND len=base.len THEN RETURN [base];
ans ← NEW [RopeSeqPrivate[len]];
FOR i: INT IN [0..len) DO ans[i] ← base[start+i] ENDLOOP;
RETURN};
Replace: PUBLIC PROC [base: RopeSeq, start: INT ← 0, len: INT ← MaxLen, with: RopeSeq ← nil] RETURNS [ans: RopeSeq] ~ {
wl: INT ~ Length[with];
d: INT ~ wl-len;
len ← MIN[len, base.len-start];
IF len=0 AND wl=0 THEN RETURN [base];
ans ← NEW [RopeSeqPrivate[base.len + d]];
FOR i: INT IN [0..start) DO ans[i] ← base[i] ENDLOOP;
FOR i: INT IN [0..wl) DO ans[start+i] ← with[i] ENDLOOP;
FOR i: INT IN [start+len..base.len) DO ans[i+d] ← base[i] ENDLOOP;
RETURN};
ReplaceElt: PUBLIC PROC [base: RopeSeq, index: INT, with: RopePart] RETURNS [RopeSeq] ~ {
GenReplaced: PROC [i: INT] RETURNS [RopePart] ~ {
IF i=index THEN RETURN [with];
RETURN [base[i]]};
IF index<0 OR index>=base.len THEN RuntimeError.BoundsFault[];
RETURN FromProc[base.len, GenReplaced]};
END.