RopeListImpl.mesa
Copyright Ó 1986, 1991 by Xerox Corporation. All rights reserved.
Last Edited by: Stewart.pa, December 16, 1983 11:21 am
Doug Wyatt, December 15, 1986 3:12:00 pm PST
This module provides some utilities for manipulating lists of ropes.
DIRECTORY
Basics USING [Comparison],
Rope USING [Compare, Equal, ROPE],
RopeList;
RopeListImpl: CEDAR PROGRAM
IMPORTS Rope
EXPORTS RopeList =
BEGIN
OPEN RopeList;
Predicates.
EqualLists: PUBLIC PROC [l1, l2: LIST OF Rope.ROPE, case: BOOL ¬ TRUE] RETURNS [BOOL] = {
IF l1 = l2 THEN RETURN[TRUE];
IF l1 = NIL OR l2 = NIL THEN RETURN[FALSE];
UNTIL l1 = NIL DO
IF l2 = NIL THEN RETURN[FALSE];
IF Rope.Equal[l1.first, l2.first, case] THEN NULL ELSE RETURN[FALSE];
l1 ¬ l1.rest;
l2 ¬ l2.rest;
ENDLOOP;
RETURN[l2 = NIL];
};
Memb: PUBLIC PROC [list: LIST OF Rope.ROPE, r: Rope.ROPE, case: BOOL ¬ TRUE] RETURNS [BOOL] = {
WHILE list # NIL DO
IF Rope.Equal[list.first, r, case] THEN RETURN[TRUE];
list ¬ list.rest;
ENDLOOP;
RETURN[FALSE];
};
Constructors.
These procedures do not disturb their arguments.
Cons: PUBLIC PROC [list: LIST OF Rope.ROPE, r: Rope.ROPE] RETURNS [LIST OF Rope.ROPE] = {
RETURN[CONS[r, list]];
};
Append: PUBLIC PROC [l1, l2: LIST OF Rope.ROPE] RETURNS [val: LIST OF Rope.ROPE] = {
z: LIST OF Rope.ROPE ¬ NIL;
val ¬ l2;
IF l1 = NIL THEN RETURN[val];
val ¬ CONS[l1.first, val];
z ¬ val;
UNTIL (l1 ¬ l1.rest) = NIL DO
z.rest ¬ CONS[l1.first, z.rest];
z ¬ z.rest;
ENDLOOP;
RETURN[val];
};
CopyTopList: PUBLIC PROC [list: LIST OF Rope.ROPE] RETURNS [LIST OF Rope.ROPE] = {
RETURN[Append[list, NIL]];
};
Returns a copy of the list.
Remove: PUBLIC PROC [list: LIST OF Rope.ROPE, r: Rope.ROPE, case: BOOL ¬ TRUE] RETURNS [val: LIST OF Rope.ROPE ¬ NIL] = {
z: LIST OF Rope.ROPE ¬ NIL;
UNTIL list = NIL DO
IF NOT Rope.Equal[list.first, r, case] THEN {
IF val = NIL THEN {
val ¬ CONS[list.first, NIL];
z ¬ val;
}
ELSE {
z.rest ¬ CONS[list.first, z.rest];
z ¬ z.rest;
};
};
list ¬ list.rest;
ENDLOOP;  
}; -- of Remove  
Reverse: PUBLIC PROC [list: LIST OF Rope.ROPE] RETURNS [val: LIST OF Rope.ROPE ¬ NIL] = {
UNTIL list = NIL DO
val ¬ CONS[list.first, val];
list ¬ list.rest;
ENDLOOP;
};
Destructive Constructors.
DAppend: PUBLIC PROC [l1, l2: LIST OF Rope.ROPE] RETURNS [val: LIST OF Rope.ROPE] = {
IF l1 = NIL THEN RETURN[l2];
IF l2 = NIL THEN RETURN[l1];
val ¬ l1;
WHILE l1.rest # NIL DO
l1 ¬ l1.rest;
ENDLOOP;
l1.rest ¬ l2;
};
DReverse: PUBLIC PROC [list: LIST OF Rope.ROPE] RETURNS [LIST OF Rope.ROPE] = {
destructivell2 reverses list. copied from Lisp DREVERSE function
l1, l2, l3: LIST OF Rope.ROPE ¬ NIL;
IF list = NIL THEN RETURN[NIL];
l3 ¬ list;
UNTIL (l1 ¬ l3) = NIL DO
l3 ¬ l3.rest;
l1.rest ¬ l2;
l2 ¬ l1;
ENDLOOP;
RETURN[l2];
};
DRemove: PUBLIC PROC [list: LIST OF Rope.ROPE, r: Rope.ROPE, case: BOOL ¬ TRUE] RETURNS [LIST OF Rope.ROPE] = {
l, l1: LIST OF Rope.ROPE ¬ NIL;
l ¬ list;
UNTIL l = NIL DO
IF Rope.Equal[l.first, r, case] THEN {
IF l1 = NIL THEN RETURN[l.rest]; -- ref was first object on list
l1.rest ¬ l.rest;
RETURN[list];
};
l1 ¬ l;
l ¬ l.rest;
ENDLOOP;
RETURN [list];
};
Miscellaneous.
Length: PUBLIC PROC [list: LIST OF Rope.ROPE] RETURNS [length: INT ¬ 0] = {
WHILE list # NIL DO
length ¬ length + 1;
list ¬ list.rest;
ENDLOOP;
RETURN[length];
};
Map: PUBLIC PROC [list: LIST OF Rope.ROPE, proc: PROC [Rope.ROPE]] = {
WHILE list # NIL DO
proc[list.first];
list ¬ list.rest;
ENDLOOP;
};
Sorting.
Sort: PUBLIC PROC [list: LIST OF Rope.ROPE, compareProc: CompareProc] RETURNS [LIST OF Rope.ROPE] = {
The sort is destructive and NOT stable, that is, the relative positions in the result of
nodes with equal keys is unpredictible. For a nondestructive sort, copy l first.
The sort does one CONS.
a, b, mergeTo: LIST OF Rope.ROPE;
mergeToCons: LIST OF Rope.ROPE = CONS[NIL, NIL];
max: CARDINAL = 22; --number of bits in word-address space minus 2
lists: ARRAY [0..max) OF LIST OF Rope.ROPE ¬ ALL [NIL];
lists[0] is a sorted list of length 2 or NIL, lists[1] is a sorted list of length
4 or NIL, lists[2] is a sorted list of length 8 or NIL, etc.
When Sort returns, lists = ALL [NIL] again (we do some extra work to assure this).
x: CARDINAL; --[0..max]
xMax: CARDINAL ¬ 0; --[0..max)
make each pair of consecutive elements of l into a sorted list of length 2,
then merge it into lists.
UNTIL (a ¬ list) = NIL OR (b ¬ a.rest) = NIL DO
list ¬ b.rest;
IF compareProc[a.first, b.first] = less THEN {
a.rest ¬ b;
b.rest ¬ NIL;
}
ELSE {
b.rest ¬ a;
a.rest ¬ NIL;
a ¬ b;
};
x ¬ 0;
DO
IF (b ¬ lists[x]) = NIL THEN {
lists[x] ¬ a; EXIT }
ELSE { --merge (equal length) lists a and b
lists[x] ¬ NIL;
mergeTo ¬ mergeToCons;
DO --assert a#NIL, b#NIL
IF compareProc[a.first, b.first] = less THEN {
mergeTo.rest ¬ a; mergeTo ¬ a;
IF (a ¬ a.rest) = NIL THEN { mergeTo.rest ¬ b; EXIT } }
ELSE { 
mergeTo.rest ¬ b; mergeTo ¬ b;
IF (b ¬ b.rest) = NIL THEN { mergeTo.rest ¬ a; EXIT } }
ENDLOOP;
a ¬ mergeToCons.rest;
x ¬ x+1;
IF x > xMax AND (xMax ¬ x) = max THEN ERROR }
ENDLOOP;
ENDLOOP;
xMax now contains the largest x such that lists[x] # NIL.
if l's length was even, a = NIL; if l's length was odd, a = single element list.
merge a and elements of lists into result (held in a).
x ¬ 0;
IF a = NIL THEN {
try to make a # NIL.
UNTIL (lists[x] # NIL OR x = xMax) DO x ¬ x+1 ENDLOOP;
a ¬ lists[x]; lists[x] ¬ NIL; x ¬ x+1 };
a # NIL OR x > xMax.
UNTIL x > xMax DO
IF (b ¬ lists[x]) # NIL THEN {
lists[x] ¬ NIL;
mergeTo ¬ mergeToCons;
DO
a#NIL AND b#NIL
IF compareProc[a.first, b.first] = less THEN {
mergeTo.rest ¬ a; mergeTo ¬ a;
IF (a ¬ a.rest) = NIL THEN { mergeTo.rest ¬ b; EXIT } }
ELSE { 
mergeTo.rest ¬ b; mergeTo ¬ b;
IF (b ¬ b.rest) = NIL THEN { mergeTo.rest ¬ a; EXIT } }
ENDLOOP;
a ¬ mergeToCons.rest };
x ¬ x+1;
ENDLOOP;
RETURN [a]
};
Compare: PUBLIC CompareProc = {
RETURN [Rope.Compare[s1: r1, s2: r2, case: TRUE]];
};
IgnoreCase: PUBLIC CompareProc ={
RETURN [Rope.Compare[s1: r1, s2: r2, case: FALSE]];
};
END.