Rosary.mesa
Copyright Ó 1985, 1986, 1991 by Xerox Corporation. All rights reserved.
Michael Plass, April 1, 1985 10:11:09 am PST
Willie-s, May 28, 1991 12:21 pm PDT
Doug Wyatt, November 26, 1991 3:13 pm PST
Provides the analogy for ROPEs, with REFs in place of CHARs. A Rosary.ROSARY is immutable; clients are encouraged, but not obliged, to treat the objects pointed to by the REFs as immutable as well.
An accelerator is provided for the case where consecutive items are equal.
Rosary:
CEDAR
DEFINITIONS ~
BEGIN
ROSARY: TYPE ~ REF RosaryRep;
Item: TYPE ~ REF ANY;
Segment: TYPE ~ RECORD [base: ROSARY, start: INT ¬ 0, size: INT ¬ INT.LAST];
nullSegment: Segment ~ [
NIL, 0, 0];
Size: PROC [r: ROSARY] RETURNS [INT];
Fetch:
PROC [base:
ROSARY, index:
INT]
RETURNS [Item];
FromItem: PROC [item: Item, repeat: INT ¬ 1] RETURNS [ROSARY];
Substr: PROC [base: ROSARY, start: INT ¬ 0, len: INT ¬ INT.LAST] RETURNS [ROSARY];
Concat:
PROC [base, rest:
ROSARY]
RETURNS [
ROSARY];
Cat: PROC [r0, r1, r2, r3, r4: ROSARY ¬ NIL] RETURNS [ROSARY];
CatSegments:
PROC [s0, s1, s2: Segment ¬ nullSegment]
RETURNS [
ROSARY];
FromProc:
PROC [size:
INT, proc:
PROC
RETURNS[Item]]
RETURNS [
ROSARY];
The proc is called size times, to get the contents for the new ROSARY.
FromRuns:
PROC [p:
PROC[q:
PROC[item: Item, repeat:
INT ¬ 1]]]
RETURNS [
ROSARY];
The client-supplied p is called once; it should call q once for each run.
ActionType: TYPE ~ PROC [item: Item] RETURNS [quit: BOOLEAN ¬ FALSE];
Map:
PROC [s: Segment, action: ActionType]
RETURNS [quit:
BOOLEAN];
Calls action for each item in s; stops and returns TRUE if action does.
RunActionType: TYPE ~ PROC [item: Item, repeat: INT] RETURNS [quit: BOOLEAN ¬ FALSE];
MapRuns:
PROC [s: Segment, action: RunActionType]
RETURNS [quit:
BOOLEAN];
Run: TYPE ~ RECORD [item: Item, repeat: INT];
FetchRun:
PROC [base:
ROSARY, index:
INT]
RETURNS [Run];
ContainingRun: TYPE ~ RECORD [item: Item, start, end: INT]; -- [start..end)
FetchContainingRun:
PROC [base:
ROSARY, index:
INT]
RETURNS [ContainingRun];
bufferSize: NAT ~ 32;
BufferRep: TYPE ~ RECORD [count: NAT, a: ARRAY [0..bufferSize) OF Item];
Buffer: TYPE ~ REF BufferRep;
FetchBuffer:
PROC [base:
ROSARY, index:
INT, maxCount: [0..bufferSize] ¬ bufferSize]
RETURNS [Buffer];
FromList:
PROC [list:
LIST
OF
REF]
RETURNS [
ROSARY];
ToList:
PROC [r:
ROSARY]
RETURNS [
LIST
OF
REF];
FromObject:
PROC [size:
INT, data:
REF
ANY, fetchContainingRun: FetchContainingRunProc,
mapRuns: MapRunsProc ¬
NIL, substr: SubstrProc ¬
NIL]
RETURNS [
ROSARY];
FetchContainingRunProc:
TYPE ~
PROC [base:
ROSARY, index:
INT]
RETURNS [ContainingRun];
MapRunsProc:
TYPE ~
PROC [s: Segment, action: RunActionType]
RETURNS [quit:
BOOLEAN];
SubstrProc:
TYPE ~
PROC [base:
ROSARY, start:
INT, len:
INT]
RETURNS [
ROSARY];
maxHeight: NAT ~ 48;
RosaryRep:
TYPE ~
RECORD [
size: INT,
height: [0..maxHeight],
var:
SELECT tag: *
FROM
leaf => [item: Item],
concat => [base, rest: ROSARY],
object => [data: REF ANY, fetchContainingRun: FetchContainingRunProc,
mapRuns: MapRunsProc, substr: SubstrProc]
ENDCASE
];