Abstraction du parcours avec un curseur

En comparant le code de la fonction set__filter dans les trois réalisations, vous pouvez remarquer que l’algorithme est très similaire. Nous cherchons à écrire cet algorithme une unique fois pour les trois réalisations.

Mise en œuvre par une opération externe

En utilisant les opérations définies dans set/set.h, il est possible de réaliser une seule implémentation de set__filter qui fonctionne pour toutes les réalisations:

struct set * set__filter(struct set const * se, int (*filter)(void*))
{
    struct set * filtered = set__empty();
    for (int i = 0; i < INT_MAX; ++i)
        if (filter(i) && set__find(se, i))
            set__add(filtered, i);
    return filtered;
}
  1. Quelle est la complexité de la fonction set__filter pour chacune des réalisations? Comparer aux complexités des fonctions internes que vous avez implémentées précédemment.

Abstraire le parcours avec un curseur interne

Commencer par créer une branche nommée cursor-int sur votre dépôt git à partir de la branche principale. Pour la suite de cet exercice, vous travaillerez dans la branche cursor-int. Nous allons modifier l’API de set et la rendre incompatible avec d’autres exercices. Vous pourrez ainsi revenir à la branche principale au besoin.

Pour obtenir une meilleure complexité, nous avons besoin d’une abstraction du parcours d’un ensemble. Il faut néanmoins cacher certains détails de réalisation propres à chacune des mises en œuvre. Pour cela nous allons ajouter un curseur interne à nos ensembles struct set.

  1. Quelles sont les quatre opérations à introduire pour manipuler ce curseur sans connaître la mise en œuvre de struct set?
  2. Donner le prototype de ces opérations en considérant que le curseur est stocké dans struct set.
  3. Réécrire le code de la fonction set__filter ci-dessus en utilisant ces opérations.
  4. Donner le code de ces opérations et la modification de struct set dans les trois réalisations.
  5. Quelles sont les opérations de l’ensemble qui peuvent rendre le curseur incohérent?
  6. Quelle(s) autre(s) opération(s) définie(s) dans le fichier set/set.h peut-on écrire en utilisant le curseur, tout en préservant la complexité?
  7. Quelle est la limite principale due au stockage du curseur dans la structure struct set?
  8. On remarque que set__filter ajoute toujours en fin. Pour chaque mise en œuvre, quelle optimisation de set__add peut être envisagée?

Abstraire le parcours avec un curseur externe

Commencer par créer une branche nommée cursor-ext sur votre dépôt git à partir de la branche principale. Pour la suite de cet exercice, vous travaillerez dans la branche cursor-ext. Nous allons modifier l’API de set et la rendre incompatible avec d’autres exercices. Vous pourrez ainsi revenir à la branche principale au besoin.

Certains traitements nécessitent de réaliser plusieurs parcours simultanés d’une structure de données. Le curseur interne ne le permet pas. Dans cette partie, nous souhaitons donc mettre en œuvre un curseur externe qui est stocké dans une structure dédiée struct cursor. Chaque mise en œuvre de struct set proposera sa propre réalisation de struct cursor. Cette structure sera abstraite: l’utilisateur ne manipulera que des pointeurs struct cursor *.

  1. Ajouter la déclaration du type struct cursor ainsi que les prototypes des opérations nécessaires dans le fichier set/set.h.
  2. Quelles informations doit stocker struct cursor pour chacune des mises en œuvre de struct set?
  3. Définir la structure struct cursor pour chacune des implémentations dans les fichiers sentinel/set_sentinel.h, dynamic/set_dynamic.h et link/set_link.h.
  4. Mettre en œuvre les nouvelles fonctions déclarées dans le fichier set/set.h pour chaque implémentation dans les fichiers sentinel/set_sentinel.c, dynamic/set_dynamic.c, link/set_link.c.
  5. Réécrire la fonction set__filter ci-dessus en utilisant un curseur externe. Adapter vos tests fonctionnels et assurez-vous que tous vos tests soient bien validés.
  6. Les opérations set__add, set__remove, etc., peuvent invalider les curseurs. Quel mécanisme pouvez-vous mettre en œuvre pour que l’utilisation d’un curseur invalide puisse être détectée?
  7. Ajouter la fonction int set__remove_cursor(struct set * se, struct cursor * c); qui retire l’élément pointé par le curseur c de l’ensemble se. Votre implémentation doit s’assurer que c est bien un curseur valide sur se, et que le curseur reste valide après la suppression.
  8. On souhaite ajouter à une position donnée dans un struct set à l’aide d’un curseur via la fonction int set__add_cursor(struct set * se, struct cursor * c, void* x);. Cette fonction ajoute l’élément x dans l’ensemble se à la position donnée par le curseur c. Cette fonction doit notamment vérifier que la position c est valide. Comment implémenter cette vérification en temps constant dans chaque mise en œuvre de struct set? Que peut-on en déduire sur la mise en œuvre de set__filter en temps linéaire?