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.