-- /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 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 ]; 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]; Union: PROCEDURE [ set1, set2: RopeSet] RETURNS [ set: RopeSet]; Intersection: PROCEDURE [ set1, set2: RopeSet] RETURNS [ set: RopeSet]; Difference: PROCEDURE [ set1, set2: RopeSet] RETURNS [ set: RopeSet]; MinMaxValues: PROCEDURE [ set: RopeSet] RETURNS [ min, max: Rope.ROPE] = INLINE BEGIN 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]; END. ºType Definitions A double linked list, that is kept increasingly ordered. This allows faster traversal in both directions.... Operations NoOp if set is empty copy semantics... copy semantics... copy semantics... Returns [ NIL, NIL] if set is empty 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. Ê{˜J˜&J˜-J˜9J˜šÏk ˜ Jšœœœ˜J˜J˜—Jšœ œ œ˜J˜šœ˜J˜šœ™J˜JšœU™UJšœ™J˜J˜!J˜šœ œœ˜Jšœ œœ˜Jšœœ œ˜Jšœœ ˜J˜J˜—šœ œ ˜Jšœœ ˜Jšœœ ˜J˜J˜——šœ ™ J˜š Ïn œ œœœœ˜GJšœ œ˜JšœÏc ˜J˜—š ž œ œ œœœ˜KJ˜—Jšžœ œ œœ˜YJ˜šžœ œ œœ˜YJšœ™J˜—šžœ œœ˜@Jšœ™—J˜šž œ œœ˜GJšœ™—J˜šž œ œœ˜EJšœ™—J˜š ž œ œœœœ˜UJšœ#™#Jš œ œœœœœ˜)Jšœ"˜(JšœŸ˜J˜—šž œ œ œ$œ œœ œ ˜…JšœO™OJšœH™HJšœ"™"—J˜Jšœ˜———…—T ‰