-- /ivy/binding/ropesets/RopeSetsImpl.mesa
-- Implementing the operations on RopeSets
-- Last edited by: Binding, August 8, 1984 8:03:50 am PDT
DIRECTORY
Basics USING [ Comparison],
Rope USING [ ROPE, Equal, Compare],
RopeSets USING [ RopeSetEl, RopeSet, Direction, IsSetEmpty]
;
RopeSetsImpl: CEDAR PROGRAM
IMPORTS Rope, RopeSets
EXPORTS RopeSets
= BEGIN OPEN RopeSets;
IsValueInSet: PUBLIC PROCEDURE [ val: Rope.ROPE, set: RopeSet] RETURNS [ BOOLEAN] = BEGIN
scan through ordered list and test on membership
IF set.Head = NIL THEN RETURN[ FALSE];
FOR l: REF RopeSetEl ← set.Head, l.Next UNTIL l = NIL DO
comp: Basics.Comparison ← Rope.Compare[ val, l.Value];
IF comp = less THEN EXIT;
IF comp = equal THEN RETURN[ TRUE];
ENDLOOP;
RETURN[ FALSE];
END; --IsInValueSet
InsertValueIntoSet: PUBLIC PROCEDURE [ val: Rope.ROPE, set: RopeSet] RETURNS [ newSet: RopeSet] = BEGIN
assuming an increasingly ordered list of ropes, insert a new element
new: REF RopeSetEl;
newSet ← set;
IF newSet.Head = NIL THEN BEGIN
new ← NEW[ RopeSetEl];
new.Value ← val;
newSet.Head ← new; newSet.Tail ← new;
END
ELSE IF Rope.Compare[ val, set.Head.Value] = less THEN BEGIN -- insert before head
new ← NEW[ RopeSetEl];
new.Value ← val;
new.Next ← newSet.Head;
newSet.Head.Prev ← new;
newSet.Head ← new;
END
ELSE IF Rope.Compare[ val, set.Tail.Value] = greater THEN BEGIN -- insert after tail
new ← NEW[ RopeSetEl];
new.Value ← val;
new.Prev ← newSet.Tail;
newSet.Tail.Next ← new;
newSet.Tail ← new;
END
ELSE BEGIN -- insert in middle
cur, prev: REF RopeSetEl;
prev ← NIL; cur ← newSet.Head;
WHILE cur # NIL AND Rope.Compare[ val, cur.Value] = greater DO
prev ← cur;
cur ← cur.Next;
ENDLOOP;
IF cur # NIL AND Rope.Equal[ val, cur.Value] THEN NULL -- duplicate
ELSE BEGIN -- insert in middle
new ← NEW[ RopeSetEl];
new.Value ← val;
new.Next ← cur;
new.Prev ← prev;
prev.Next ← new;
cur.Prev ← new;
END;
END;
RETURN[ newSet];
END; -- InsertValueInto
DeleteValueFromSet: PUBLIC PROCEDURE [ val: Rope.ROPE, set: RopeSet] RETURNS [ newSet: RopeSet] = BEGIN
assuming an increasingly ordered list of ropes, removes an element
aux: REF RopeSetEl;
cur, prev: REF RopeSetEl;
IF set.Head = NIL THEN RETURN[ set];
IF Rope.Compare[ val, set.Head.Value] = less OR Rope.Compare[ val, set.Tail.Value] = greater THEN RETURN[ set] ; -- el not in set
prev ← NIL; cur ← set.Head;
WHILE cur # NIL AND Rope.Compare[ val, cur.Value] = greater DO
prev ← cur;
cur ← cur.Next;
ENDLOOP;
IF cur = NIL THEN NULL -- el not in list and at end, i.e. el > all list elements
ELSE IF Rope.Equal[ val, cur.Value] THEN BEGIN
aux ← cur;
IF aux.Prev # NIL THEN aux.Prev.Next ← aux.Next;
IF aux.Next # NIL THEN aux.Next.Prev ← aux.Prev;
IF set.Head = aux THEN set.Head ← aux.Next;
IF set.Tail = aux THEN set.Tail ← aux.Prev;
aux.Prev ← NIL; aux.Next ← NIL;
END;
RETURN[ set];
END; -- DeleteValueFromSet
Union: PUBLIC PROCEDURE [ set1, set2: RopeSet] RETURNS [ set: RopeSet] = BEGIN
copy semantics... This is slower, but safer...
cur1, cur2, new: REF RopeSetEl;
cur1 ← set1.Head;
cur2 ← set2.Head;
set.Head ← NIL; set.Tail ← NIL;
DO
IF cur2 = NIL THEN EXIT;
WHILE cur1 # NIL AND Rope.Compare[ cur1.Value, cur2.Value] = less DO
new ← NEW[ RopeSetEl];
new.Value ← cur1.Value;
IF set.Head = NIL THEN set.Head ← new ELSE set.Tail.Next ← new;
new.Prev ← set.Tail; set.Tail ← new;
cur1 ← cur1.Next;
ENDLOOP;
IF cur1 = NIL THEN EXIT;
IF Rope.Compare[ cur1.Value, cur2.Value] = equal THEN BEGIN
new ← NEW[ RopeSetEl];
new.Value ← cur1.Value;
IF set.Head = NIL THEN set.Head ← new ELSE set.Tail.Next ← new;
new.Prev ← set.Tail; set.Tail ← new;
cur1 ← cur1.Next;
cur2 ← cur2.Next;
END;
IF cur1 = NIL THEN EXIT;
WHILE cur2 # NIL AND Rope.Compare[ cur2.Value, cur1.Value] = less DO
new ← NEW[ RopeSetEl];
new.Value ← cur2.Value;
IF set.Head = NIL THEN set.Head ← new ELSE set.Tail.Next ← new;
new.Prev ← set.Tail; set.Tail ← new;
cur2 ← cur2.Next;
ENDLOOP;
ENDLOOP;
IF cur1 = NIL THEN
WHILE cur2 # NIL DO
new ← NEW[ RopeSetEl];
new.Value ← cur2.Value;
IF set.Head = NIL THEN set.Head ← new ELSE set.Tail.Next ← new;
new.Prev ← set.Tail; set.Tail ← new;
cur2 ← cur2.Next;
ENDLOOP
ELSE -- cur2 = NIL
WHILE cur1 # NIL DO
new ← NEW[ RopeSetEl];
new.Value ← cur1.Value;
IF set.Head = NIL THEN set.Head ← new ELSE set.Tail.Next ← new;
new.Prev ← set.Tail; set.Tail ← new;
cur1 ← cur1.Next;
ENDLOOP;
RETURN[ set];
END; -- Union
Difference: PUBLIC PROCEDURE [ set1, set2: RopeSet] RETURNS [ set: RopeSet] = BEGIN
copy semantics...
new: REF RopeSetEl;
set.Head ← NIL; set.Tail ← NIL;
IF IsSetEmpty[ set2] THEN BEGIN
cur1: REF RopeSetEl← set1.Head;
WHILE cur1 # NIL DO
new ← NEW[ RopeSetEl];
new.Value ← cur1.Value;
IF set.Head = NIL THEN set.Head ← new ELSE set.Tail.Next ← new;
new.Prev ← set.Tail; set.Tail ← new;
cur1 ← cur1.Next;
ENDLOOP;
END
ELSE BEGIN
cur1: REF RopeSetEl← set1.Head;
WHILE cur1 # NIL DO
IF NOT IsValueInSet[ cur1.Value, set2] THEN BEGIN
new ← NEW[ RopeSetEl];
new.Value ← cur1.Value;
IF set.Head = NIL THEN set.Head ← new ELSE set.Tail.Next ← new;
new.Prev ← set.Tail; set.Tail ← new;
END;
cur1 ← cur1.Next;
ENDLOOP;
END;
RETURN[ set];
END; -- Difference
Intersection: PUBLIC PROCEDURE [ set1, set2: RopeSet] RETURNS [ set: RopeSet] = BEGIN
copy semantics...
new: REF RopeSetEl;
IF IsSetEmpty[ set1] OR IsSetEmpty[ set2] THEN RETURN[ [ NIL, NIL]];
set.Head ← NIL; set.Tail ← NIL;
FOR cur1: REF RopeSetEl ← set1.Head, cur1.Next UNTIL cur1 = NIL DO
IF IsValueInSet[ cur1.Value, set2] THEN BEGIN
new ← NEW[ RopeSetEl];
new.Value ← cur1.Value;
IF set.Head = NIL THEN set.Head ← new ELSE set.Tail.Next ← new;
new.Prev ← set.Tail; set.Tail ← new;
END;
ENDLOOP;
RETURN[ set];
END; -- Intersection
MoveRover: PUBLIC PROCEDURE [ rover: REF RopeSetEl, dir: Direction, howFar: CARDINAL, passLast: BOOLEAN] RETURNS [ newRover: REF RopeSetEl] = BEGIN
Moves set.Rover. If 'passLast' set, then returns NIL if howFar > length of the list
starting at set.Rover in given Direction. Else, return set.Head or set.Tail. If set is empty
always return NIL.
LookAhead: PROCEDURE [ head: REF RopeSetEl, howFar: CARDINAL, passLast: BOOLEAN] RETURNS [ rover: REF RopeSetEl] = BEGIN
we look 'howFar' els into list and return the element. IF passLast = TRUE, we
return NIL if the list is shorter than 'howFar'. Otherwise, listEl will point to last
element in list.
cur: REF RopeSetEl;
assume head # NIL
cur ← head;
FOR i: INT IN [ 1..howFar] DO
IF passLast AND cur = NIL THEN RETURN[ NIL]
ELSE IF cur.Next = NIL AND NOT passLast THEN RETURN[ cur];
cur ← cur.Next;
ENDLOOP;
RETURN[ cur];
END; -- LookAhead
LookBehind: PROCEDURE [ tail: REF RopeSetEl, howFar: CARDINAL, passLast: BOOLEAN] RETURNS [ rover: REF RopeSetEl] = BEGIN
we look 'howFar' els into list and return the element. IF passLast = TRUE, we
return NIL if the list is shorter than 'howFar'. Otherwise, listEl will point to last
element in list.
cur: REF RopeSetEl;
assume tail # NIL
cur ← tail;
FOR i: INT IN [ 1..howFar] DO
IF passLast AND cur = NIL THEN RETURN[ NIL]
ELSE IF cur.Prev = NIL AND NOT passLast THEN RETURN[ cur];
cur ← cur.Prev;
ENDLOOP;
RETURN[ cur];
END; -- LookBehind
IF rover = NIL THEN RETURN[ NIL];
IF dir = Right THEN newRover ← LookAhead[ rover, howFar, passLast]
ELSE newRover ← LookBehind[ rover, howFar, passLast];
RETURN[ newRover];
END; -- MoveRover
END.