RopeSequence.mesa
Copyright Ó 1990 by Xerox Corporation. All rights reserved.
Coolidge, July 9, 1990 6:37:44 pm GMT
Last changed by Coolidge on July 17, 1990 10:37 am PDT
Last tweaked by Mike Spreitzer on October 5, 1990 8:03:42 am PDT
A RopeSequence represents an immutable sequence of RopeParts (which in turn represent immutable sequences of characters - thus, a RopeSequence represents an immutable sequence of immutable sequence of character).
DIRECTORY Basics, RopeParts;
RopeSequence: CEDAR DEFINITIONS
= BEGIN
Part 1: Basic operations and definitions
RopePart: TYPE ~ RopeParts.RopePart;
nilPart: RopePart ~ RopeParts.nil;
RopeSeq: TYPE = REF RopeSeqPrivate;
RopeSeqPrivate: TYPE;
nil: RopeSeq ~ NIL;
MaxLen: INT ~ INT.LAST;
QuaRopeSeq: PROC [REF ANY] RETURNS [MaybeRopeSeq];
MaybeRopeSeq: TYPE ~ RECORD [is: BOOL, as: RopeSeq];
(NOT is) => (as = NIL).
IsRopeSeq: PROC [ra: REF ANY] RETURNS [BOOL]
~ INLINE {RETURN [QuaRopeSeq[ra].is]};
AsRopeSeq: PROC [ra: REF ANY] RETURNS [RopeSeq];
ParsePartToSeq: PROC [part: RopePart, seperator: CHAR] RETURNS [RopeSeq];
The length of the result is one more than the number of occurrences of seperator in part; each element of the result is the chars between two seperators.
UnparseSeqToPart: PROC [seq: RopeSeq, seperator: CHAR] RETURNS [RopePart];
For all x, s: RopeParts.Equal[Equal[x, UnparseSeqToPart[ParsePartToSeq[x, s], s]].
Equal[x, ParsePartToSeq[UnparseSeqToPart[x, s], s]] when s doesn't occur in x.
Cons: PROC [parts: LIST OF RopePart] RETURNS [RopeSeq];
Builds, from a list of RopeParts, a RopeSeq which contains the parts.
FromProc: PROC [len: INT, Generate: PROC [INT] RETURNS [RopePart]] RETURNS [RopeSeq];
Generate is given the index, and is called len times, on 0, 1, ... len-1, in that order.
Cat: PROC [r1, r2, r3, r4, r5: RopeSeq ← nil] RETURNS [RopeSeq];
Concat: PROC [base, rest: RopeSeq ← nil] RETURNS [RopeSeq];
Compare: PROC [s1, s2: RopeSeq, case: BOOL ← TRUE] RETURNS [Basics.Comparison];
CompareSubseqs: PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOL ← TRUE]
RETURNS [Basics.Comparison];
Equal: PROC [s1, s2: RopeSeq, case: BOOL ← TRUE] RETURNS [BOOL];
EqualSubseqs: PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOL ← TRUE]
RETURNS [BOOL];
Fetch: PROC [base: RopeSeq, index: INT ← 0] RETURNS [RopePart];
Index: PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOL ← TRUE]
RETURNS [INT];
Returns the smallest N such that 0 <= N-start1 < len1 and EqualSubseqs[s1, N, s2.Subseq[start2, len2].Length, s2, start2, len2, case]. If no such N exists, returns MIN[start1+len1, s1.Length].
Find: PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOL ← TRUE]
RETURNS [INT];
Like Index, but returns -1 when s2 not found.
FindBackward: PROC
[
s1: RopeSeq, start1: INT ← 0, len1: INT ← MaxLen,
s2: RopeSeq, start2: INT ← 0, len2: INT ← MaxLen,
case: BOOL ← TRUE]
RETURNS [INT];
Like Find, but returns largest such N.
IsEmpty: PROC [RopeSeq] RETURNS [BOOL];
Length: PROC [RopeSeq] RETURNS [INT];
Subseq: PROC [base: RopeSeq, start: INT ← 0, len: INT ← MaxLen] RETURNS [RopeSeq];
Replace: PROC [base: RopeSeq, start: INT ← 0, len: INT ← MaxLen, with: RopeSeq ← nil] RETURNS [RopeSeq];
ReplaceElt: PROC [base: RopeSeq, index: INT, with: RopePart] RETURNS [RopeSeq];
Bounds fault if index not in [0 .. base.Length).
Part 2: Extended operations and definitions
ActionType: TYPE ~ PROC [RopePart] RETURNS [quit: BOOL ← FALSE];
TranslatorType: TYPE ~ PROC [RopePart] RETURNS [RopePart];
Run: PROC [s1: RopeSeq, pos1: INT ← 0, s2: RopeSeq, pos2: INT ← 0, case: BOOL ← TRUE] RETURNS [INT];
IsPrefix: PROC [prefix, subject: RopeSeq, case: BOOL ← TRUE] RETURNS [BOOL];
IsSuffix: PROC [suffix, subject: RopeSeq, case: BOOL ← TRUE] RETURNS [BOOL];
Match: PROC [pattern, object: RopeSeq, case: BOOL ← TRUE] RETURNS [BOOL];
MatchSubseqs: PROC
[
pattern: RopeSeq, pStart: INT ← 0, pLen: INT ← MaxLen,
object: RopeSeq, oStart: INT ← 0, oLen: INT ← MaxLen,
case: BOOL ← TRUE]
RETURNS [BOOL];
SkipTo: PROC [s: RopeSeq, pos: INT ← 0, skip: RopeSeq] RETURNS [INT];
SkipOver: PROC [s: RopeSeq, pos: INT ← 0, skip: RopeSeq] RETURNS [INT];
Map: PROC [base: RopeSeq, action: ActionType] RETURNS [BOOL];
Translate: PROC [base: RopeSeq, translator: TranslatorType ← NIL] RETURNS [RopeSeq];
Hash: PROC [base: RopeSeq, case: BOOL ← TRUE, seed: CARDINAL ← defaultSeed] RETURNS [CARDINAL];
defaultSeed: CARDINAL ~ 27183;
END.