-- /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.