INF3105 —­­­­­ Structure de données et algorithmes
Automne 2016

Laboratoire 9 : Dictionnaire basé sur un arbre (ArbreMap)

Lecture préalable

• Section 8.11 des notes de cours.
• Présentation en classe.

Objectifs

• Implémentation et application d'une classe générique ArbreMap<K,V>.
• Réaliser une partie du TP2.

Tâches

1. Télécharger les fichiers du Lab9

wget http://ericbeaudry.ca/INF3105/lab9/lab9.zip
unzip lab9.zip

2. Récupérer la classe ArbreAVL du Lab6

Remplacez le fichier arbreavl.h par votre dernière version réalisée au Lab6.

Il est important de compléter le Lab6 avant d'amorcer le Lab9.

3. Tests de base

• Complétez la représentation d'un ArbreMap
• Pour compiler test_arbremap.cpp :

g++ -o test_arbremap test_arbremap.cpp.

• Faites en sorte que les tests dans test1() et test2() réussissent.

4. Itérateurs

Pour le TP2, il est utile d'avoir un itérateur d'ArbreMap, soit une classe ArbreMap<K,V>::Iterateur, afin d'itérer sur les entrées, des paires (clé,valeur), d'un dictionnaire de type ArbreMap.

La représentation d'un ArbreMap<K,V>::Iterateur est tout simplement un autre itérateur de type ArbreAVL<Entree>::Iterateur. La déclaration d'un itérateur devrait ressembler à cela.

class ArbreMap{
  // ...
  public:
    class Iterateur {
      public:
        Iterateur(const ArbreMap& a) : iter(a.entrees.debut()) {}
        Iterateur(typename ArbreAVL<Entree>::Iterateur i) : iter(i) {}
        operator bool() const;
        bool operator!() const;
        
        Iterateur& operator++();
        Iterateur operator++(int);

        const K& cle() const;
        const V& valeur() const; // ?? constant ou non ??

      private:
        typename ArbreAVL<Entree>::Iterateur iter;
    };
    // ...

    Iterateur debut() const;
    Iterateur fin() const;
    Iterateur rechercher(const K& cle) const;
    Iterateur rechercherEgalOuSuivant(const K& cle) const;
    Iterateur rechercherEgalOuPrecedent(const K& cle) const;
};

Utilisation appropriée des mots clés const

Il ne faut pas perdre de vue qu'on peut utiliser des itérateurs d'ArbreMap sur des dictionnaires constants ou non constants. Voici deux cas d'utilisation.

Cas #1 : ArbreMap constant :

    void fonction(const ArbreMap<string, int>& dictionnaire){
        ArbreMap<string, int>::Iterateur iter = dictionnaire.debut();
        const string& cle = iter.cle();
        const int& v = iter.valeur();
        ...
    }

Cas #2 : ArbreMap non constant :

    void fonction(ArbreMap<string, int>& dictionnaire){
        ArbreMap<string, int>::Iterateur iter = dictionnaire.debut();
        const string& cle = iter.cle();
        int& v = iter.valeur();
        v++;
        ...
    }

Il y a plusieurs façons de bien gérer les const. En voici deux :

1. Deux types d'itérateurs :
• un objet de type ArbreMap::Iterateur est un itérateur non constant qui permet de lire la clé et de modifier la valeur d'une entrée.
• un objet de type ArbreMap::IterateurConst est un itérateur constant qui ne permet pas de modifier la valeur d'une entrée.
2. Un seul type d'itérateur :
• un objet de type ArbreMap::Iterateur est un itérateur qui ne permet pas de modifier la valeur d'une entrée.
• Pour obtenir une référence non constante, afin de modifier la valeur d'une entrée, on crée deux nouveaux opérateurs [] dans ArbreMap:
• const V& ArbreMap<K,V>::operator[] (const Iterateur& iter) const;
• V& ArbreMap<K,V>::operator[] (const Iterateur& iter);

L'option B est plus simple à implémenter. L'option A peut être plus conviviale pour l'utilisateur. À vous de choisir!

Enfin, décommentez les fonctions test3() et test4() dans test_arbremap.cpp et les appels de ces fonctions dans main().