-- /ivy/binding/ropesets/RopeSets.mesa
-- Defining a double linked list of Rope.ROPE
-- Last edited by: Binding, August 8, 1984 7:45:58 am PDT

DIRECTORY
Rope USING [ ROPE]
;

RopeSets: CEDAR DEFINITIONS 

= BEGIN

<<Type Definitions>>

<<A double linked list, that is kept increasingly ordered. This allows faster traversal>>
<<in both directions....>>

Direction: TYPE = { Left, Right};

RopeSetEl: TYPE = RECORD [ 
Value: Rope.ROPE _ NIL,
Next: REF RopeSetEl _ NIL,
Prev: REF RopeSetEl _ NIL
];

RopeSet: TYPE = RECORD [ 
Head: REF RopeSetEl _ NIL,
Tail: REF RopeSetEl _ NIL
];

<<Operations>>

IsSetEmpty: PROCEDURE [ set: RopeSet] RETURNS [ BOOLEAN] = INLINE BEGIN
RETURN[ set.Head = NIL];
END; -- IsSetEmpty

IsValueInSet: PROCEDURE [ val: Rope.ROPE, set: RopeSet] RETURNS [ BOOLEAN];

InsertValueIntoSet: PROCEDURE [ val: Rope.ROPE, set: RopeSet] RETURNS [ newSet: RopeSet];

DeleteValueFromSet: PROCEDURE [ val: Rope.ROPE, set: RopeSet] RETURNS [ newSet: RopeSet];
<<NoOp if set is empty>>

Union: PROCEDURE [ set1, set2: RopeSet] RETURNS [ set: RopeSet];
<<copy semantics...>>

Intersection: PROCEDURE [ set1, set2: RopeSet] RETURNS [ set: RopeSet];
<<copy semantics...>>

Difference: PROCEDURE [ set1, set2: RopeSet] RETURNS [ set: RopeSet];
<<copy semantics...>>

MinMaxValues: PROCEDURE [ set: RopeSet] RETURNS [ min, max: Rope.ROPE] = INLINE BEGIN
<<Returns [ NIL, NIL] if set is empty>>
IF set.Head = NIL THEN RETURN[ NIL, NIL];
RETURN[ set.Head.Value, set.Tail.Value];
END; -- MinMaxValues

MoveRover: PROCEDURE [ rover: REF RopeSetEl, dir: Direction, howFar: CARDINAL, passLast: BOOLEAN] RETURNS [ newRover: REF 
RopeSetEl];
<<Moves rover. If 'passLast' set, then returns NIL if howFar > length of the list>>
<<starting at rover in given Direction. Else, return set.Head or set.Tail.>>
<<If set is empty always return NIL.>>

END.