The class "simset" contains facilities for the manipulation of circular two-way lists, called "sets".
class simset; begin class linkage; ...........11.1 ; linkage class link; ..............11.2 ; linkage class head; ..............11.3 ; end simset;
The reference variables and procedures necessary for set handling are introduced in standard classes declared within the class "simset". Using these classes as prefixes, their relevant data and other properties are made parts of the object themselves.
Both sets and objects which may acquire set membership have references to a successor and a predecessor. Consequently they are made subclasses of the "linkage" class.
The sets are represented by objects belonging to a subclass "head" of "linkage". Objects which may be set members belong to subclasses of "link" which is itself another subclass of "linkage".
class linkage; begin ref (linkage) SUC, PRED; ref (link) procedure suc; suc:- if SUC in link then SUC else none; ref (link) procedure pred; pred:- if PRED in link then PRED else none; ref (linkage) procedure prev; prev:- PRED; end linkage;
The class "linkage" is the common denominator for set heads and set members.
SUC is a reference to the successor of this linkage object in the set, PRED is a reference to the predecessor.
The value of SUC and PRED may be obtained through the procedures "suc" and "pred". These procedures give the value none if the designated object is not a set member, i.e. of class "link" or a subclass of "link".
The attributes SUC and PRED may only be modified through the use of procedures defined within "link" and "head". This protects the user against certain kinds of programming errors.
The procedure "prev" enables a user to access a set head from its first member.
linkage class link; begin procedure out; if SUC=/=none then begin SUC.PRED :- PRED; PRED.SUC :- SUC; SUC :- PRED :- none end out; procedure follow(ptr); ref (linkage) ptr; begin out; if ptr=/=none and then ptr.SUC=/=none then begin PRED :- ptr; SUC :- ptr.SUC; SUC.PRED :- ptr.SUC :- this linkage end end follow; procedure precede(ptr); ref (linkage) ptr; begin out; if ptr=/=none and then ptr.SUC=/=none then begin SUC :- ptr; PRED :- ptr.PRED; PRED.SUC :- ptr.PRED :- this linkage end if end precede; procedure into(S); ref (head) S; precede(S); end link;
Objects belonging to subclasses of the class "link" may acquire set membership. An object may only be a member of one set at a given instant.
In addition to the procedures "suc" and "pred", there are four procedures associated with each "link" object: "out", "follow", "precede" and "into".
The procedure "out" removes the object from the set (if any) of which it is a member. The procedure call has no effect if the object has no set membership.
The procedures "follow" and "precede" remove the object from the set (if any) of which it is a member and insert it in a set at a given position. The set and the position are indicated by a parameter which is inner to "linkage". The procedure call has the same effect as "out" (except for possible side effects from evaluation of the parameter) if the parameter is none or if it has no set membership and is not a set head. Otherwise the object is inserted immediately after ("follow") or before ("precede") the "linkage" object designated by the parameter.
The procedure "into" removes the object from the set (if any) of which it is a member and inserts it as the last member of the set designated by the parameter. The procedure call has the same effect as "out" if the parameter has the value none (except for possible side effects from evaluating the actual parameter).
linkage class head; begin ref (link) procedure first; first :- suc; ref (link) procedure last; last :- pred; Boolean procedure empty; empty := SUC == this linkage; integer procedure cardinal; begin integer i; ref (link) ptr; ptr :- first; while ptr =/= none do begin i := i+1; ptr :- ptr.suc end while; cardinal := i end cardinal; procedure clear; while first =/= none do first.out; SUC :- PRED :- this linkage end head;
An object of the class "head", or a subclass of "head" is used to represent a set. "head" objects may not acquire set membership. Thus, a unique "head" is defined for each set.
The procedure "first" may be used to obtain a reference to the first member of the set, while the procedure "last" may be used to obtain a reference to the last member.
The Boolean procedure "empty" gives the value true only if the set has no members.
The integer procedure "cardinal" counts the number of members in a set.
The procedure "clear" removes all members from the set.
The references SUC and PRED initially point to the "head" itself, which thereby represents an empty set.