Write an ADT specification for a set of n elements.

Operations include (create set, add an element to a set, delete an element from a set, check whether an element is in a set, union of 2 sets, intersection of 2 sets, cardinality of a set, complement of a set)

Difficulty level
This exercise is mostly suitable for students 
Type 		Set

Parameter 	element

Use 		Boolean, integer

Operations
	Create				-->	Set
	Add: Set x element		-->	Set
	isEmpty: Set			-->	Boolean
	belong : Set x element		-->	Boolean
	union : Set x Set		-->	Set
	intersection : Set x Set	-->	Set
	Delete: Set x element		-->	Set
	Card: Set			-->	Integer
	Comp: Set			-->	Set
	Difference: Set x Set		-->	Set

Constructors
	Create, Add

Preconditions
	No preconditions

Axioms
	Let E1, E2 be 2 sets, a an element, E full Set
	* isEmpty(Create())=true
	* isEmpty(Add(E1,a))=false
	* Belong(Create(),a)=False
	* Belong(Add(E1,a),a)=True
	* Union(Create(),E1)=E1
	* Union(Add(E1,a),E2)=Add(Union(E1,E2),a)
	* Intersection(Create(),E1)=Create()
	* Intersection(Add(E1,a),E2)=if  Belong(E2,a) then Add(Intersection(E1,E2),a)  else  Intersection(E1,E2)
	* Delete(create(),a)=Create()
	* Delete(Add(E1,a),a) = if  (E1,a) then delete(E1,a)  else  E1
	* Card(Create())=0
	* Card(Add(E1,a)) = if  Belong(E1,a) then card(E1)  else  card(E1) +1
	* Comp(Create())=E
	* Comp(Add(E1,a))= if  Belong(E1,a) then Comp(E1)  else  delete(Comp(E1),a)
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Implementation of a deque