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:
BOOL ←
TRUE]
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: BOOL ← TRUE]
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:
BOOL ←
TRUE]
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: BOOL ← TRUE]
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: BOOL ← TRUE]
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: BOOL ← TRUE]
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: BOOL ← TRUE]
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.