Type abstrait de données ensemble (`set`)

Cet enseignement a pour objectif d’étudier plusieurs techniques et bonnes pratiques de programmation en langage C pour la mise en œuvre de types de données et d’algorithmes.

Pour cela, vous allez mettre en œuvre le Type Abstrait de Données (TAD) set défini ci-dessous. Ce type permet de représenter et de manipuler des ensembles d’entiers positifs ou nuls.

type set;

set__empty    :                set
set__is_empty : set         -> boolean
set__add      : set * int   -> set
set__remove   : set * int   -> set
set__find     : set * int   -> boolean
set__size     : set         -> int

Ces opérations satisfont les axiomes suivants:

set__is_empty(set__empty)       = true
set__is_empty(set__add(s, i))   = false

set__find(set__empty, i)        = false
set__find(set__add(s, i), i)    = true
set__find(set__add(s, i), i')   = set__find(s, i')

set__add(s, i)                  = s   [if set__find(s,i)=true]

set__remove(set__empty, i)      = set__empty
set__remove(set__add(s, i), i)  = s
set__remove(set__add(s, i), i') = set__add(set__remove(s, i'), i)

set__size(set__empty)           = 0
set__size(set__add(s, i))       = set__size(s)+1 [if set__find(s,i)=false]
set__size(set__add(s, i))       = set__size(s)   [if set__find(s,i)=true]

Chaque opération du type set correspondra à une fonction du langage C. Les entiers sont représentés par le type int. Let type set est représenté en langage C par une structure struct set dont la définition sera précisée ultérieurement.

En plus des fonctions ci-dessous, on programmera la fonction set__print qui affiche le contenu d’un ensemble et ne renvoie aucune valeur. Cette fonction permettra de déboguer plus facilement le code. Voici sont type:

set__print : set -> void