Mise en œuvre du TAD `set` à l'aide d'un tableau trié à sentinelle

Dans cette première mise en œuvre, les entiers sont stockés dans un tableau trié. On rappelle que seuls des entiers positifs ou nuls sont stockés dans les struct set. La fin des données contenues dans ce tableau est marquée par une sentinelle (ou butée). La taille de l’ensemble représenté est donc au plus égale à la capacité du tableau moins 1 puisqu’il faut obligatoirement placer la butée. La butée est un entier distinct de tous ceux qui peuvent apparaître dans un ensemble. N’importe quel entier négatif peut convenir. Ce choix de réalisation est laissé libre. Par exemple:

Pour cette mise en œuvre, la struct set est définie de la manière suivante dans le fichier sentinel/set_sentinel.h.

#ifndef SET__SIZE
#define SET__SIZE 10
#endif

#define SET__BOUND (-1)

struct set {
  int s[SET__SIZE];
};

Afin d’aider l’écriture des fonctions de set/set.h, nous avons ajouté trois fonctions outils: find, shift_left et shift_right dans le fichier sentinel/set_sentinel.h.

Mise en œuvre

Quelle est la principale différence entre la fonction find (fichier sentinel/set_sentinel.h) et la fonction set__find (fichier set/set.h)?

Dans le fichier sentinel/set_sentinel.c, programmer tout d’abord les trois fonctions utilitaires find, shift_left et shift_right déclarées dans le fichier sentinel/set_sentinel.h.

Puis, toujours dans le fichier sentinel/set_sentinel.c, mettre en œuvre les fonctions du type set déclarées dans set/set.h.

Tests structurels

Pour vous assurer du bon fonctionnement de votre code, écrire des tests structurels dans le fichier sentinel/test_sentinel_struc.c qui définit une architecture de test, dont une fonction main().

Ces tests vérifient, pour chaque fonction, la gestion de la sentinelle, le tri des éléments du tableau, etc. Il est particulièrement crucial de tester les trois fonctions outils find, shift_left et shift_right. Il faut également vérifier le respect des axiomes du TAD par votre mise en œuvre. Vos tests structurels devront vérifier chaque fonction indépendamment des autres fonctions. Pour cela, il pourra être nécessaire de créer des struct set ``à la main’’.

L’approche structurelle du test autorise un accès direct aux champs de la structure de données. Voici un exemple de test structurel pour la fonction set__remove:

static void test_set__remove_with_shift (void) {
  printf("%s", __func__);

  struct set st = { {1,2,3,4, SET__BOUND} };

  set__remove(&st, 3);
  assert(st.s[0] == 1);
  assert(st.s[1] == 2);
  assert(st.s[2] == 4);
  assert(st.s[3] == SET__BOUND);

  set__remove(&st, 4);
  assert(st.s[0] == 1);
  assert(st.s[1] == 2);
  assert(st.s[2] == SET__BOUND);

  set__remove(&st, 1);
  assert(st.s[0] == 2);
  assert(st.s[1] == SET__BOUND);

  set__remove(&st, 2);
  assert(st.s[0] == SET__BOUND);

  printf("\tOK\n");
}

NB: on ne testera pas la fonction set__print.