ntro.ca

        • Contrats de classe
        • Liens utiles
        • Calendrier
        • Calendrier groupe 2
        • Calendrier groupes 1, 3
        • Structure du cours
        • Évaluations
        • Matériel à se procurer
        • Les profs
          • Marc-Olivier Tremblay
          • Mathieu Bergeron
        • Module 1.1: installation + trier des cartes
        • Module 1.2: rappels POO
        • Module 1.3: tableau d'objets
        • Examen 1
        • Module 2.1: données JSON
        • Module 2.2: données en Java
        • Module 2.3: récursivité
        • Examen 2
        • Module 3.1: structure générique
        • Module 3.2: efficacité (1)
        • Module 3.3: efficacité (2)
        • Examen 3
        • Module 4.1: liste naïve
        • Module 4.2: liste par tableau
        • Module 4.3: liste chaînée
        • Examen 4
        • Module 5.1: mappage naïf
        • Module 5.2: mappage par hachage
        • Module 5.3: mappage par arbre
        • Examen 5
        • Équipes
          • Horaire groupe 1
          • Horaire groupe 2
          • Horaire groupe 3
          • Groupe 1
          • Groupe 2
          • Groupe 3
        • Projets vedettes 2022
        • Projets vedettes 2023
        • Projets vedettes 2024
        • Projets vedettes 2025
        • Survol
        • Structure
        • Calendrier
        • Calendrier des séances
        • Évaluations
        • Exemples de jeu
        • Exemples de pages
        • Réponses à vos questions
        • Module 1: créer le projet
        • Module 2: concevoir l'application
        • Module 3: vues NtroFx
        • Module 4: modèle et navigation
        • Module 5: ajouter le dorsal, modifier le modèle
        • Module 7: améliorer l'affichage
        • Module 8: jeu en 2d
        • Module 9: client/serveur
        • Module 10: plusieurs instances du même modèle
        • TP1
        • Examen 1
        • TP2
        • Examen 2
        • Projet de fin de session
        • Calendrier
        • Structure du cours
        • Évaluations
        • Contrat de classe
        • Le prof
        • 01: Windows et Word
          • Astuces et raccourcis
        • 02: Word
        • 03: Word
          • Exercice Word: insertion d'éléments spéciaux
          • Exercice Word: tableaux
        • 04: Word
          • Exercice Word: références
          • TP01: Word (15%)
        • 05: PowerPoint
          • TP02: PowerPoint (10%)
        • 06: Examen Word (20%)
        • 07: Excel
        • 08: Excel
        • 09: Excel
          • TP03: Excel (15%)
        • 10: Excel
        • 11: Examen Excel (20%)
        • 12: Access
        • 13: Access
        • 14: Access
        • 15: Examen Access
      • Sondage H2023 (dept. info)
      • Vision H2023 (dept. info)
      • P1) exercices interactifs de lecture
      • P2) transition Excel vers Python
        • Atelier 2: un exemple
      • Jquery
      • Jquery Ui
      • Point de vue sur l'IA
    Structures Generiques01
    • Théorie 3.1: structure générique (1)
      • Première version: Object[] valeurs
      • Implanter Object[] valeurs
      • Problème avec Object[] valeurs
      • Deuxième version: Comparable[] valeurs
      • Recapitulation
      • Problèmes avec Comparable[] valeurs

    Théorie 3.1: structure générique (1) #

    • Comment définir une liste générique contenant des méthodes comme

      • valeurMinimale (le plus petit élément de la liste)
      • trierListe
    • Comment s’assurer que le même code fonctionne pour:

      • liste d’entiers, liste de chaînes, liste de Vehicule, etc.
    • On regarde deux techniques ici:

      • mémoriser les éléments de la liste dans un tableau d’objets Object[] valeurs;
      • mémoriser les éléments de la liste dans un tableau d’objets comparables Comparable[] valeurs;

    Première version: Object[] valeurs #

    • En java, une classe hérite toujours de Object

    • Un tableau Object[] valeurs peut alors stoquer n’importe quel sorte d’objet

    • Voici l’interface de la première version de notre Liste générique:

    public interface Liste {
    
        Object obtenirValeur(int index);
    
        void modifierValeur(int index, Object nouvelleValeur);
    
        Object valeurMinimale();
    }
    
    • La Liste peut faire trois choses:
      • obtenirValeur: récupérer la valeur stoquée à un certain index
      • modifierValeur: stoquer une valeur à un certain index
      • valeurMinimale: trouver et retourner la plus petite valeur de la liste

    Implanter Object[] valeurs #

    • L’implantation commence comme suit:
    public class MaListe implements Liste {
        
        private Object[] valeurs;
        
        public MaListe(Object[] valeurs) {
            this.valeurs = valeurs;
        }
    }
    
    • Le constructeur permet de spécifier les valeurs initiales de la liste (le tableau d’objets Object[] valeurs)

      • ces valeurs sont mémorisées dans un attribut privé
    • La liste est générique. On peut créer plusieurs types de liste:

    public static void main(String[] args) {
    
        MaListe listeEntiers = new MaListe(new Integer[] {54,1,5,43,6});
    
        MaListe listeChaines = new MaListe(new String[] {"25","45","4","5"});
    
        MaListe listeVehicules = new MaListe(new Vehicule[] {new Auto(13.0), new Moto(23.9), new Camion(134.0)});
    
    }
    
    • L’utilisation de la liste est simple:

      int entier = listeEntiers.obtenirValeur(1);
      listeEntiers.modifierValeur(1, entier+10);
      
      String chaine = listeChaines.obtenirValeur(3);
      listeChaines.modifierValeur(0,"Ah!");
      
      Vehicule vehicule = listeVehicules.obtenirValeur(0);
      listeVehicules.modifierValeur(2, new Auto(21.0));
      
      • NOTE: contrairement à un tableau, on en peut pas utiliser
        • liste[index] pour accéder à un élément de la liste ou
        • liste[index] = 3 pour modifier un élément.
        • il faut toujours appeler des méthodes, comme
          • liste.obtenirValeur(index) ou
          • liste.modifierValeur(index, 3)

    • L’implantation de modifierValeur et obtenirValeur est simple:

      @Override
      public Object obtenirValeur(int index) {
          return valeurs[index];
      }
      
      @Override
      public void modifierValeur(int index, Object nouvelleValeur) {
          valeurs[index] = nouvelleValeur;
      }
      
      • NOTE: ça va se compliquer quand on va vouloir modifier la taille de la liste en ajoutant des éléments (c’est le sujet de l’étape 4)

    • L’implantation de valeurMinimale est simple aussi… à première vue:
    @Override
    public Object valeurMinimale() {
        
        Object valeurMinimale = null;
        
        if(valeurs.length > 0) {
            valeurMinimale = valeurs[0];
        }
        
        for(int i = 1; i < valeurs.length; i++) {
            if(siValeurPlusPetite(valeurs[i], valeurMinimale)) {
                valeurMinimale = valeurs[i];
            }
        }
        
        return valeurMinimale;
    }
    }
    
    • Le problème est dans l’implantation de siValeurPlusPetite

    Problème avec Object[] valeurs #

    • Comparer les valeurs est un problème:
    private boolean siValeurPlusPetite(Object valeur, Object valeurMinimale) {
        
        boolean siValeurPlusPetite = false;
        
        if(valeur instanceof Integer && valeurMinimale instanceof Integer) {
            
            siValeurPlusPetite = siEntierPlusPetit((Integer) valeur, (Integer) valeurMinimale);
    
        }else if(valeur instanceof String && valeurMinimale instanceof String) {
            
            siValeurPlusPetite = siChainePlusPetite((String) valeur, (String) valeurMinimale);
    
        }else if(valeur instanceof Vehicule && valeurMinimale instanceof Vehicule) {
    
            siValeurPlusPetite = ((Vehicule)valeurMinimale).siMoinsDeKilometrageQue((Vehicule)valeurMinimale);
    
        }else {
            
            // ?????
        }
        
        return siValeurPlusPetite;
    }
    
    • Il faudrait ajouter du code à la méthode ci-haut pour chaque type d’objet

    • Notre classe Liste n’est plus vraiment générique

    • La solution est de déléguer aux objets la tâche de se comparer

    • On a besoin pour ça d’un contrat avec ces objets

    Deuxième version: Comparable[] valeurs #

    • L’interface Comparable est un contrat qui signifie qu’un objet sait se comparer (à un autre)

    • Pour remplir ce contrat, il faut implanter la méthode int compareTo(Object autre)

      • retourner -1 si l’objet courant est plus petit que l'autre objet
      • retourner 0 si l’objet courant est égal à l'autre objet
      • retourner +1 si l’objet courant plus grand que l'autre objet
    • Avec Comparable, l’interface de notre liste générique devient:

    public interface Liste {
    
        Comparable obtenirValeur(int index);
    
        void modifierValeur(int index, Comparable nouvelleValeur);
    
        Comparable valeurMinimale();
    
    }
    
    • En VSCode, vous allez avoir des avertissements de type incomplet

    • On peut les ignorer pour l’instant

    • L’implantation commence comme suit:

    public class MaListe implements Liste {
        
        Comparable[] valeurs;
    
        public MaListe(Comparable[] valeurs) {
            this.valeurs = valeurs;
        }
    }
    
    • Cette fois-ci, on mémorise un tableau de Comparable

      • on ne connaît rien des objets, sauf qu’ils implante compareTo(Object autre)
    • Les méthodes obtenirValeur, modifierValeur et valeurMinimale sont pareilles

    • La méthode siValeurPlusPetite n’est plus du tout problématique

        return valeur.compareTo(valeurMinimale) < 0;
    }
    
    
    • Par contre, il faut maintenant que Vehicule implante Comparable
    public abstract class Vehicule implements Comparable {
    
    	private double totalKilometres = 0;
    	
    	public Vehicule(double totalKilometres) {
    		this.totalKilometres = totalKilometres;
    	}
    
    	@Override
    	public int compareTo(Object autre){
    	    int resultat = 0;
    
    	    if(this.totalKilometres < ((Vehicule) autre).totalKilometres){
    	        resultat = -1;
    	    }else if(this.totalKilometres > ((Vehicule) autre).totalKilometres){
    	        resultat = +1;
    	    }
    
    	    return resultat;
    	}
    
    	//...
    }
    
    • NOTE: les classes String et Integer (et d’autres) implantent déjà Comparable

    Recapitulation #

    • Pour créer une liste générique, il faut mémoriser des objets qu’on ne connaît pas

    • Pour comparer ces objets, il faut exiger qu’ils implantent l’interface Comparable

    • Pour en faire plus, il faut exiger une interface avec plus de méthodes

    • Par exemple, si on veut que Liste affiche les valeurs, on peut demander:

      • que chaque objet implante ElementListe qui contient String formater()
      • alors on a:
    public class MaListe implements Tableau, Formateur {
        
        ElementListe[] valeurs;
    
        //...
        
        @Override
        public String formater(){
            StringBuilder builder = new StringBuidler();
    
            builder.append("[");
    
            if(valeurs.length > 0){
                builder.append(valeurs[0].formater());
            }
    
            for(int i = 1; i < valeurs.length; i++) {
                builder.append(", ");
                builder.append(valeurs[i].formater());
            }
    
            builder.append("]");
    
            return builder.toString();
        }
    }
    

    Problèmes avec Comparable[] valeurs #

    • Notre Liste ne permet pas vraiment de spécifier le type des éléments

    • En particulier, on peut faire:

    public static void main(String[] args) {
    
        MaListe listeChaines = new MaListe(new String[] {"25","45","4","5"});
    
        // Permis?
        listeChaines.modifierValeur(0, 12);
        listeChaines.modifierValeur(0, new Auto(12.9));
    
        // Oups, erreur d'exécution
        String chaine = (String) listeChaines.valeurMinimale();
    }
    
    • Est-ce qu’on peut ajouter un entier ou une Auto à une liste de chaînes?

    • Comment bloquer cette option pour éviter les erreurs d’exécution?

    • Réponse ici: structures génériques (2)

    Creative Commons License Creative Commons Attribution Creative Commons ShareAlike
    • Théorie 3.1: structure générique (1)
      • Première version: Object[] valeurs
      • Implanter Object[] valeurs
      • Problème avec Object[] valeurs
      • Deuxième version: Comparable[] valeurs
      • Recapitulation
      • Problèmes avec Comparable[] valeurs