Apprenez à programmer en Python
Last updated on Monday, September 8, 2014
  • 4 semaines
  • Facile

Ce cours est visible gratuitement en ligne.

Paperback available in this course

Ce cours existe en eBook.

Certificate of achievement available at the end this course

Got it!

TP : un dictionnaire ordonné

Voici enfin le moment de la pratique. Vous avez appris pas mal de choses dans cette partie, beaucoup de concepts, souvent théoriques. Il est temps de les mettre en application, dans un contexte un peu différent des TP précédents : on ne va pas créer un jeu mais plutôt un objet conteneur tenant à la fois du dictionnaire et de la liste.

Notre mission

Notre énoncé va être un peu différent de ceux dont vous avez l'habitude. Nous n'allons pas créer ici un jeu mais simplement une classe, destinée à produire des objets conteneurs, des dictionnaires ordonnés.

Peut-être ne vous en souvenez-vous pas mais je vous ai dit dans le chapitre consacré aux dictionnaires que c'était un type non-ordonné. Ainsi, l'ordre dans lequel vous entrez les données n'a pas d'importance. On ne peut ni les trier, ni les inverser, tout cela n'aurait aucun sens pour ce type particulier.

Mais nous allons profiter de l'occasion pour créer une forme de dictionnaire ordonné. L'idée, assez simplement, est de stocker nos données dans deux listes :

  • la première contenant nos clés ;

  • la seconde contenant les valeurs correspondantes.

L'ordre d'ajout sera ainsi important, on pourra trier et inverser ce type de dictionnaire.

Spécifications

Voici la liste des mécanismes que notre classe devra mettre en œuvre. Un peu plus bas, vous trouverez un exemple de manipulation de l'objet qui reprend ces spécifications :

  1. On doit pouvoir créer le dictionnaire de plusieurs façons :

    • Vide : on appelle le constructeur sans lui passer aucun paramètre et le dictionnaire créé est donc vide.

    • Copié depuis un dictionnaire : on passe en paramètre du constructeur un dictionnaire que l'on copie par la suite dans notre objet. On peut ainsi écrire constructeur(dictionnaire) et les clés et valeurs contenues dans le dictionnaire sont copiées dans l'objet construit.

    • Pré-rempli grâce à des clés et valeurs passées en paramètre : comme les dictionnaires usuels, on doit ici avoir la possibilité de pré-remplir notre objet avec des couples clés-valeurs passés en paramètre (constructeur(cle1 = valeur1, cle2 = valeur2, …)).

  2. Les clés et valeurs doivent être couplées. Autrement dit, si on cherche à supprimer une clé, la valeur correspondante doit également être supprimée. Les clés et valeurs se trouvant dans des listes de même taille, il suffira de prendre l'indice dans une liste pour savoir quel objet lui correspond dans l'autre. Par exemple, la clé d'indice 0 est couplée avec la valeur d'indice 0.

  3. On doit pouvoir interagir avec notre objet conteneur grâce aux crochets, pour récupérer une valeur (objet[cle]), pour la modifier (objet[cle] = valeur) ou pour la supprimer (del objet[cle]).

  4. Quand on cherche à modifier une valeur, si la clé existe on écrase l'ancienne valeur, si elle n'existe pas on ajoute le couple clé-valeur à la fin du dictionnaire.

  5. On doit pouvoir savoir grâce au mot-clé in si une clé se trouve dans notre dictionnaire (cle in dictionnaire).

  6. On doit pouvoir demander la taille du dictionnaire grâce à la fonction len.

  7. On doit pouvoir afficher notre dictionnaire directement dans l'interpréteur ou grâce à la fonction print. L'affichage doit être similaire à celui des dictionnaires usuels ({cle1: valeur1, cle2: valeur2, …}).

  8. L'objet doit définir les méthodes sort pour le trier et reverse pour l'inverser. Le tri de l'objet doit se faire en fonction des clés.

  9. L'objet doit pouvoir être parcouru. Quand on écrit for cle in dictionnaire, on doit parcourir la liste des clés contenues dans le dictionnaire.

  10. À l'instar des dictionnaires, trois méthodes keys() (renvoyant la liste des clés), values() (renvoyant la liste des valeurs) et items() (renvoyant les couples (clé, valeur)) doivent être mises en œuvre. Le type de retour de ces méthodes est laissé à votre initiative : il peut s'agir d'itérateurs ou de générateurs (tant qu'on peut les parcourir).

  11. On doit pouvoir ajouter deux dictionnaires ordonnés (dico1 + dico2) ; les clés et valeurs du second dictionnaire sont ajoutées au premier.

Cela vous en fait, du boulot !

Et vous pourrez encore trouver le moyen d'améliorer votre classe par la suite, si vous le désirez.

Exemple de manipulation

Ci-dessous se trouve un exemple de manipulation de notre dictionnaire ordonné. Quand vous aurez codé le vôtre, vous pourrez voir s'il réagit de la même façon que le mien.

>>> fruits = DictionnaireOrdonne()
>>> fruits
{}
>>> fruits["pomme"] = 52
>>> fruits["poire"] = 34
>>> fruits["prune"] = 128
>>> fruits["melon"] = 15
>>> fruits
{'pomme': 52, 'poire': 34, 'prune': 128, 'melon': 15}
>>> fruits.sort()
>>> print(fruits)
{'melon': 15, 'poire': 34, 'pomme': 52, 'prune': 128}
>>> legumes = DictionnaireOrdonne(carotte = 26, haricot = 48)
>>> print(legumes)
{'carotte': 26, 'haricot': 48}
>>> len(legumes)
2
>>> legumes.reverse()
>>> fruits = fruits + legumes
>>> fruits
{'melon': 15, 'poire': 34, 'pomme': 52, 'prune': 128, 'haricot': 48, 'carotte':
26}
>>> del fruits['haricot']
>>> 'haricot' in fruits
False
>>> legumes['haricot']
48
>>> for cle in legumes:
...     print(cle)
...
haricot
carotte
>>> legumes.keys()
['haricot', 'carotte']
>>> legumes.values()
[48, 26]
>>> for nom, qtt in legumes.items():
...     print("{0} ({1})".format(nom, qtt))
...
haricot (48)
carotte (26)
>>>

Tous au départ !

Je vous ai donné le nécessaire, c'est maintenant à vous de jouer. Concernant l'implémentation, les fonctionnalités, il reste des zones obscures, c'est volontaire. Tout ce qui n'est pas clairement dit est à votre initiative. Tant que cela fonctionne et que l'exemple de manipulation ci-dessus affiche la même chose chez vous, c'est parfait. Si vous voulez mettre en œuvre d'autres fonctionnalités, méthodes ou attributs, ne vous gênez pas… mais n'oubliez pas d'y aller progressivement.

C'est parti !

Correction proposée

Voici la correction que je vous propose. Je suis sûr que vous êtes, de votre côté, arrivés à quelque chose, même si tout ne fonctionne pas encore parfaitement. Certaines fonctionnalités, comme le tri, l'affichage, etc. sont encore un peu complexes à appréhender. Cependant, faites attention à ne pas sauter trop rapidement à la correction et essayez au moins d'obtenir par vous-mêmes un dictionnaire ordonné avec des fonctionnalités opérationnelles d'ajout, de consultation et de suppression d'éléments.

class DictionnaireOrdonne:
    """Notre dictionnaire ordonné. L'ordre des données est maintenu
    et il peut donc, contrairement aux dictionnaires usuels, être trié
    ou voir l'ordre de ses données inversées"""
    
    def __init__(self, base={}, **donnees):
        """Constructeur de notre objet. Il peut ne prendre aucun paramètre
        (dans ce cas, le dictionnaire sera vide) ou construire un
        dictionnaire remplis grâce :
        -   au dictionnaire 'base' passé en premier paramètre ;
        -   aux valeurs que l'on retrouve dans 'donnees'."""
        
        self._cles = [] # Liste contenant nos clés
        self._valeurs = [] # Liste contenant les valeurs correspondant à nos clés
        
        # On vérifie que 'base' est un dictionnaire exploitable
        if type(base) not in (dict, DictionnaireOrdonne):
            raise TypeError( \
                "le type attendu est un dictionnaire (usuel ou ordonne)")
        
        # On récupère les données de 'base'
        for cle in base:
            self[cle] = base[cle]
        
        # On récupère les données de 'donnees'
        for cle in donnees:
            self[cle] = donnees[cle]
    
    def __repr__(self):
        """Représentation de notre objet. C'est cette chaîne qui sera affichée
        quand on saisit directement le dictionnaire dans l'interpréteur, ou en
        utilisant la fonction 'repr'"""
        
        chaine = "{"
        premier_passage = True
        for cle, valeur in self.items():
            if not premier_passage:
                chaine += ", " # On ajoute la virgule comme séparateur
            else:
                premier_passage = False
            chaine += repr(cle) + ": " + repr(valeur)
        chaine += "}"
        return chaine
    
    def __str__(self):
        """Fonction appelée quand on souhaite afficher le dictionnaire grâce
        à la fonction 'print' ou le convertir en chaîne grâce au constructeur
        'str'. On redirige sur __repr__"""
        
        return repr(self)
    
    def __len__(self):
        """Renvoie la taille du dictionnaire"""
        return len(self._cles)
    
    def __contains__(self, cle):
        """Renvoie True si la clé est dans la liste des clés, False sinon"""
        return cle in self._cles
    
    def __getitem__(self, cle):
        """Renvoie la valeur correspondant à la clé si elle existe, lève
        une exception KeyError sinon"""
        
        if cle not in self._cles:
            raise KeyError( \
                "La clé {0} ne se trouve pas dans le dictionnaire".format( \
                cle))
        else:
            indice = self._cles.index(cle)
            return self._valeurs[indice]
    
    def __setitem__(self, cle, valeur):
        """Méthode spéciale appelée quand on cherche à modifier une clé
        présente dans le dictionnaire. Si la clé n'est pas présente, on l'ajoute
        à la fin du dictionnaire"""
        
        if cle in self._cles:
            indice = self._cles.index(cle)
            self._valeurs[indice] = valeur
        else:
            self._cles.append(cle)
            self._valeurs.append(valeur)
    
    def __delitem__(self, cle):
        """Méthode appelée quand on souhaite supprimer une clé"""
        if cle not in self._cles:
            raise KeyError( \
                "La clé {0} ne se trouve pas dans le dictionnaire".format( \
                cle))
        else:
            indice = self._cles.index(cle)
            del self._cles[indice]
            del self._valeurs[indice]
    
    def __iter__(self):
        """Méthode de parcours de l'objet. On renvoie l'itérateur des clés"""
        return iter(self._cles)
    
    def __add__(self, autre_objet):
        """On renvoie un nouveau dictionnaire contenant les deux
        dictionnaires mis bout à bout (d'abord self puis autre_objet)"""
        
        if type(autre_objet) is not type(self):
            raise TypeError( \
                "Impossible de concaténer {0} et {1}".format( \
                type(self), type(autre_objet)))
        else:
            nouveau = DictionnaireOrdonne()
            
            # On commence par copier self dans le dictionnaire
            for cle, valeur in self.items():
                nouveau[cle] = valeur
            
            # On copie ensuite autre_objet
            for cle, valeur in autre_objet.items():
                nouveau[cle] = valeur
            return nouveau
    
    def items(self):
        """Renvoie un générateur contenant les couples (cle, valeur)"""
        for i, cle in enumerate(self._cles):
            valeur = self._valeurs[i]
            yield (cle, valeur)
    
    def keys(self):
        """Cette méthode renvoie la liste des clés"""
        return list(self._cles)
    
    def values(self):
        """Cette méthode renvoie la liste des valeurs"""
        return list(self._valeurs)
    
    def reverse(self):
        """Inversion du dictionnaire"""
        # On crée deux listes vides qui contiendront le nouvel ordre des clés
        # et valeurs
        cles = []
        valeurs = []
        for cle, valeur in self.items():
            # On ajoute les clés et valeurs au début de la liste
            cles.insert(0, cle)
            valeurs.insert(0, valeur)
        # On met ensuite à jour nos listes
        self._cles = cles
        self._valeurs = valeurs
    
    def sort(self):
        """Méthode permettant de trier le dictionnaire en fonction de ses clés"""
        # On trie les clés
        cles_triees = sorted(self._cles)
        # On crée une liste de valeurs, encore vide
        valeurs = []
        # On parcourt ensuite la liste des clés triées
        for cle in cles_triees:
            valeur = self[cle]
            valeurs.append(valeur)
        # Enfin, on met à jour notre liste de clés et de valeurs
        self._cles = cles_triees
        self._valeurs = valeurs

Le mot de la fin

Le but de l'exercice était de présenter un énoncé simple et laissant de la place aux choix de programmation. Ce que je vous propose n'est pas l'unique façon de faire, ni la meilleure. L'exercice vous a surtout permis de travailler sur des notions concrètes que nous étudions depuis le début de cette partie et de construire un objet conteneur qui n'est pas dépourvu d'utilité.

N'hésitez pas à améliorer notre objet, il n'en sera que plus joli et utile avec des fonctionnalités supplémentaires !

Ne vous alarmez pas si vous n'avez pas réussi à coder tous les aspects du dictionnaire. L'essentiel est d'avoir essayé et compris la correction.

Example of certificate of achievement
Example of certificate of achievement