RosaryTest.mesa
Copyright Ó 1985, 1986, 1991, 1992 by Xerox Corporation. All rights reserved.
Michael Plass, October 9, 1986 4:52:07 pm PDT
Doug Wyatt, November 4, 1991 3:12 pm PST
DIRECTORY Rosary, Atom, Random;
RosaryTest: CEDAR PROGRAM
IMPORTS Rosary, Atom, Random ~ BEGIN
ROSARY: TYPE ~ Rosary.ROSARY;
list: LIST OF REF ¬ CreateList[11];
CreateList: PROC [n: INT] RETURNS [list: LIST OF REF ¬ NIL] ~ {
i: LONG CARDINAL ¬ 0;
p: PROC[atom: ATOM] ~ {
IF INT[i] >= n THEN RETURN;
IF i MOD 11 = 0 THEN {
FOR j: LONG CARDINAL IN [0..4] DO
list ¬ CONS[atom, list];
i ¬ i + 1;
ENDLOOP;
}
ELSE {list ¬ CONS[atom, list]; i ¬ i + 1}
};
UNTIL INT[i] >= n DO
Atom.MapAtoms[p];
ENDLOOP;
};
ConsecFetchContainingRun: Rosary.FetchContainingRunProc ~ {
refInt: REF INT ~ NARROW[NARROW[base, REF Rosary.RosaryRep.object].data];
n: INT ~ refInt­+index;
RETURN[[item: NEW[INT ¬ n], start: index, end: index+1]];
};
Consec: PROC [start, size: INT] RETURNS [ROSARY] ~ {
RETURN [Rosary.FromObject[size, NEW[INT¬start], ConsecFetchContainingRun]]
};
Check: PROC [segment: Rosary.Segment, list: LIST OF REF] ~ {
l: LIST OF REF ¬ list;
action: Rosary.ActionType ~ {
IF item # l.first THEN ERROR;
l ¬ l.rest;
};
[] ¬ Rosary.Map[segment, action];
IF l # NIL THEN ERROR;
};
Equal: PROC [r1, r2: ROSARY] RETURNS [BOOL] ~ {
i: INT ¬ 0;
size: INT ¬ Rosary.Size[r1];
IF size # Rosary.Size[r2] THEN RETURN [FALSE];
WHILE i # size DO
b1: Rosary.Buffer ¬ Rosary.FetchBuffer[r1, i];
b2: Rosary.Buffer ¬ Rosary.FetchBuffer[r2, i];
FOR j: NAT IN [0..b1.count) DO
IF b1.a[j] # b2.a[j] THEN RETURN [FALSE];
ENDLOOP;
i ¬ i + b1.count;
ENDLOOP;
RETURN [TRUE]
};
CheckBuffer: PROC [rosary: ROSARY, list: LIST OF REF] ~ {
l: LIST OF REF ¬ list;
index: INT ¬ 0;
WHILE index < Rosary.Size[rosary] DO
b: Rosary.Buffer ¬ Rosary.FetchBuffer[rosary, index];
IF b.count = 0 THEN ERROR;
FOR i: NAT IN [0..b.count) DO
IF b.a[i] # l.first THEN ERROR;
l ¬ l.rest;
ENDLOOP;
index ¬ index + b.count;
ENDLOOP;
};
CheckControl: PROC [list1, list2: LIST OF REF] ~ {
l1: LIST OF REF ¬ list1;
l2: LIST OF REF ¬ list2;
WHILE l1 # NIL DO
IF l1.first # l2.first THEN ERROR;
l1 ¬ l1.rest;
l2 ¬ l2.rest;
ENDLOOP;
};
FromList: PROC [list: LIST OF REF] RETURNS [rosary: ROSARY] ~ {
rosary ¬ NIL;
FOR l: LIST OF REF ¬ list, l.rest UNTIL l = NIL DO
rosary ¬ Rosary.Concat[rosary, Rosary.FromItem[l.first]];
ENDLOOP;
};
Run: PROC [ops: INT, paranoid: BOOL ¬ FALSE] ~ {
rosary: ROSARY ¬ Rosary.FromList[list];
Check[[rosary], list];
FOR i: INT IN [0..ops) DO
s1, e1, s2, e2, s3, e3, tail: LIST OF REF;
a1: INT ¬ Random.ChooseInt[NIL, 0, rosary.Size];
a2: INT ¬ Random.ChooseInt[NIL, 0, rosary.Size];
IF a1 > a2 THEN {t: INT ~ a1; a1 ¬ a2; a2 ¬ t};
[s1, e1, tail] ¬ SplitOff[list, a1];
[s2, e2, tail] ¬ SplitOff[tail, a2-a1];
[s3, e3, tail] ¬ SplitOff[tail, rosary.Size-a2];
IF i MOD 2 = 0 THEN {
list ¬ Join[s2, e2, s1, e1, s3];
rosary ¬ Rosary.Cat[Rosary.Substr[rosary, a1, a2-a1], Rosary.Substr[rosary, 0, a1], Rosary.Substr[rosary, a2, rosary.Size-a2]];
}
ELSE {
list ¬ Join[s1, e1, s3, e3, s2];
rosary ¬ Rosary.Cat[Rosary.Substr[rosary, 0, a1], Rosary.Substr[rosary, a2, rosary.Size-a2], Rosary.Substr[rosary, a1, a2-a1]];
};
IF paranoid THEN Check[[rosary], list];
ENDLOOP;
Check[[rosary], list];
};
SplitOff: PROC [list: LIST OF REF, n: INT] RETURNS [first, last, tail: LIST OF REF] ~ {
IF n = 0 THEN RETURN [NIL, NIL, list];
first ¬ last ¬ list;
FOR i: INT IN [0..n-1) DO last ¬ last.rest ENDLOOP;
tail ¬ last.rest;
last.rest ¬ NIL;
};
Join: PROC [s1, e1, s2, e2, s3: LIST OF REF] RETURNS [LIST OF REF] ~ {
IF s1 # NIL THEN {e1.rest ¬ s2; s2 ¬ s1; IF e2 = NIL THEN e2 ¬ e1};
IF s2 # NIL THEN {e2.rest ¬ s3; s3 ¬ s2};
RETURN [s3]
};
Reverse: PROC [r: ROSARY] RETURNS [ROSARY] ~ {
IF Rosary.Size[r] < 2 THEN RETURN [r]
ELSE RETURN [Rosary.FromObject[size: Rosary.Size[r], data: r,
fetchContainingRun: ReverseFetchContainingRun, substr: ReverseSubstr]];
};
ReverseFetchContainingRun: Rosary.FetchContainingRunProc ~ {
r: ROSARY ~ NARROW[NARROW[base, REF Rosary.RosaryRep.object].data];
RETURN[[item: Rosary.Fetch[r, r.size-1-index], start: index, end: index+1]];
};
ReverseSubstr: Rosary.SubstrProc ~ {
data: ROSARY ~ NARROW[NARROW[base, REF Rosary.RosaryRep.object].data];
RETURN [Reverse[Rosary.Substr[data, data.size-(start+len), len]]]
};
END.