Skip to content

Ressources

Description du problème

On s'intéresse à la programmation d'une structure abstraite permettant de stocker un ensemble de ressources. Chaque ressource est unique et identifiable par un entier compris entre 0 et le nombre total de ressources - 1. On ne stocke dans cet exercice que ces identifiants entiers.

Afin de stocker les ressources, on pourrait utiliser un set de Python. Si nous utilisions cette structure de donnée, alors if faudrait stocker toutes les ressources. Afin de diminuer les besoins de stockage, on se propose donc de programmer nous même une structure de donnée, en réalisant une compression des données stockées par plages contiguës. On utilisera pour ce faire un tableau dynamique d'intervalles. Chaque intervalle sera lui-même représenté par un tableau de deux éléments :

  • l'identifiant de la première ressource de l'intervalle.
  • l'identifiant suivant l'identifiant de la dernière ressource de l'intervalle.

Par exemple, l'ensemble de ressources 0, 1, 3, 5, 6, 9, 10, 11, 12 sera représenté par les quatre intervalles [0,2], [3,4], [5,7], [9, 13]. Inversement les intervalles [1,3], [5,7], [8,10] représentent l'ensemble de ressources 1, 2, 5, 6, 8, 9.

Travail demandé

Pour manipuler un ensemble de ressources, nous utiliserons :

  • une structure namedtuple contenant une liste d'intervalles ainsi que le nombre total de ressources que l'ensemble peut contenir ;
  • un ensemble de fonctions opérant sur cette structure.

Le squelette du code que vous devez réaliser est affiché ci-dessous et disponible ici :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#!/usr/bin/env python3
"""Manipulations complexes de tableaux dynamiques : listes d'intervalles"""

from collections import namedtuple

# Un ensemble de ressource est représenté par un intervalle et le nombre total
# de ressources qu'il peut contenir.
# Concernant la façon de définir les attributs de notre namedtuple,
# le code ci-dessous est correct car la documentation de la fonction
# collections.namedtuple dit :
#   "The field_names are a sequence of strings such as ['x', 'y'].
#     Alternatively, field_names can be a single string with each
#     fieldname separated by whitespace **and/or** commas,
#     for example 'x y' or 'x, y'."
EnsembleRessources = namedtuple("EnsembleRessources", "intervalles, nb_ressources")


def cree_ensemble_ressource(nb_ressources):
    """Créé un ensemble de ressources de taille nb_ressources.

    L'ensemble est représenté par un namedtuple EnsembleRessources.

    L'ensemble créé contient toutes les ressources avec un identifiant id
    tel que 0 <= id < nb_ressources.
    """
    # TODO
    ...


def contient(ensemble_ressources, identifiant):
    """Test d'appartenance d'une ressource à un ensemble.

    Renvoie True si la ressource identifiée par l'identifiant donné
    est contenu dans ensemble_ressources et False sinon.
    """
    # TODO
    ...


def get_chaine(ensemble_ressources):
    """Renvoie une chaîne de caractère représentant l'ensemble donné".

    Par exemple, '|x..xxxxx..|' indique qu'il y a 10 ressources,
    et que les ressources 0, 3, 4, 5, 6 et 7 sont contenues dans l'ensemble.
    """
    # TODO
    ...


def ajoute(ensemble_ressources, ensemble_ressources_a_ajouter):
    """Ajoute des ressources précédemment enlevées dans un ensemble.

    Ajoute toutes les ressources de ensemble_ressources_a_ajouter dans
    l'ensemble ensemble_ressources.

    Le fait que les ressources ajoutées aient été précédemment enlevées
    implique qu'aucune des ressources à ajouter ne soit déjà présente dans
    ensemble_ressources.

    Enfin, les deux ensembles de ressources ont le même nb_ressources et les
    tableaux dynamiques d'intervalles de ces deux ressources sont triés.
    """
    # TODO
    ...


def enleve(ensemble_ressources, nb_ressources):
    """Enlève nb_ressources de l'ensemble donnée.

    Les ressources enlevées sont les nb_ressources *premières ressources* de
    l'ensemble donné.

    Cette fonction *doit renvoyer* un nouvel ensemble de ressources de même
    taille que l'ensemble donné contenant uniquement les ressources qui ont
    été enlevées.
    """
    # TODO
    ...


def test():
    """On teste en gruyerisant un ensemble de ressources"""
    ressources_disponibles = cree_ensemble_ressource(10)
    print(
        "Disponibles après création d'un ensemble à 10 éléments     :",
        get_chaine(ressources_disponibles),
    )
    ressources_reservees = [enleve(ressources_disponibles, c) for c in (2, 2, 3, 2, 1)]
    print(
        "Disponibles après 5 appels à enlève pour un total de 10    :",
        get_chaine(ressources_disponibles),
    )
    ajoute(ressources_disponibles, ressources_reservees[1])
    print(
        "Disponibles après appel à ajout avec ressources 2 et 3     :",
        get_chaine(ressources_disponibles),
    )
    ajoute(ressources_disponibles, ressources_reservees[3])
    print(
        "Disponibles après appel à ajout avec ressources 7 et 8     :",
        get_chaine(ressources_disponibles),
    )
    print(
        "Reservees renvoyées par appel à enlève 3 sur disponibles   :",
        get_chaine(enleve(ressources_disponibles, 3)),
    )
    print(
        "Disponibles après le même appel à enlève 3                 :",
        get_chaine(ressources_disponibles),
    )
    print(
        "Les intervalles de disponibles avec uniquement ressource 8 :",
        ressources_disponibles.intervalles,
    )


if __name__ == "__main__":
    test()

La spécification de chacune des fonctions est donnée directement dans le squelette de code en tant que docstring. Prenez donc le temps de lire cette documentation et d'analyser la fonction test pour bien comprendre ce que chacune des fonctions doit faire.

Exercices