Rappels mathématiques

Avant d'aborder la représentation des ensembles en Java, il m'a semblé utile de rappeler quelques termes mathématiques de la théorie des ensembles.

La notion d'ensemble constitue la brique de base des mathématiques, car c'est à partir de cette notion que toutes les autres notions mathématiques sont définies (y compris le concept de nombre!).

Comme toutes les choses fondamentales, cette notion est difficile à définir. Je ne reviendrais donc pas la dessus et supposerais que vous avez une compréhension intuitive correcte de la notion d'ensemble et de ce que signifie l'appartenance d'un élément à un ensemble.

A la base, les ensembles sont toujours définis comme des parties d'un ensemble (fini ou infini) de tous les éléments possibles. Notons le Ω.

Prenons par exemple Ω = {a; b; c; d ; e; f; g; h; i}

Les deux ensembles E1 et E2 représentés ci-dessous, sont des parties de Ω :

L'intersection des deux ensembles E1 et E2, notée E1 ∩ E2 est l'ensemble des éléments appartenant aux deux ensembles. Dans notre exemple: E1 ∩ E2 = {d ; e}.

L'union des deux ensembles E1 et E2, notée E1 ∪ E2 est l'ensemble des éléments appartenant à au moins un des deux ensembles (donc éventuellement les deux). Dans notre exemple: E1 ∪ E2 = {a; b; c; d ; e; f; g}.

La différence des deux ensembles E1 et E2, notée E1 \ E2 est l'ensemble des éléments de E1 n'appartenant pas à E2. Dans notre exemple: E1 \ E2 = {a; b; c}. Notez que cette opération n'est pas symétrique puisque:
E2 \ E1 = {f; g} ≠ E1 \ E2

Le complémentaire d'un ensemble E, noté E^C est l'ensemble des éléments (de Ω sous-entendu) qui n'appartiennent pas à cet ensemble. Par exemple E1^C = {f; g; h; i}.

Principes

Dans toute cette section, nous allons voir les principes généraux de définition et d'utilisation d'un ensemble d'objets à l'aide de la classe générique TreeSet. Les éléments de l'ensemble doivent tous être de la même classe. Nous la noterons C. Les exemples font tous référence au projet Presence que nous présenterons plus loin.

---

Déclaration

Voici comme déclarer un ensemble E dont les éléments sont des instances de la classe C:

          
TreeSet <C> E;

Exemple

---

Instanciation

Pour créer un ensemble E vide :

          
 E =  new TreeSet <C> ( );

Exemple

---

Parcours

La boucle pour chaque, utilisable pour les listes génériques et les tableaux, peut également être utilisée pour effectuer un traitement pour chaque élément e d'un ensemble E:

for (C e : E) {

     Traitement de l'élément e 

}

Exemple

---

Méthodes utiles

Dans les explications qui suivent E désigne l'ensemble auquel la méthode est appliquée et E2 un deuxième ensemble (construit sur les éléments de la même classe) éventuellement passé en paramètre.

• boolean add (e) : ajoute l'élément e à E, s'il n'y est pas déjà. Retourne false si l'élément e est déjà présent.
  Exemple
• boolean addAll (E2) : cette méthode réalise l'union des deux ensembles E et E2. Plus précisément, elle rajoute à E tous les éléments de E2 qui n'y sont pas déjà. La valeur retournée est true si E a changé, ou autrement dit si l'ensemble E2 n'est pas inclu dans E.
  Exemple
• boolean remove (e) : supprime l'élément e de E. Si E ne contient pas e, il n'est pas modifié et la valeur retournée est false.
  Exemple
• boolean removeAll (E2) : cette méthode réalise la différence ensembliste E - E2. Plus précisément, elle supprime dans E tous les éléments qui sont également dans E2. La valeur retournée est true si E a changé, ou autrement dit si l'intersection des deux ensembles n'est pas vide.
  
• boolean retainAll (E2) : cette méthode réalise l'intersection des deux ensembles E et E2. Plus précisément, elle supprime dans E tous les éléments qui ne sont pas dans E2. La valeur retournée est true si E a changé, ou autrement dit si E n'est pas inclu dans E2.
  Exemple
• boolean contains (e) : retourne true si E contient e.
  Exemple
• int size () : retourne le nombre d'éléments de E.
  
• boolean isEmpty () : retourne true si E est vide (équivalent à E.size() == 0).
  
• Object clone () : retourne l'adresse (référence à un objet) d'une copie de l'ensemble. Les éléments eux mêmes ne sont pas clonés.
  Exemple
• String toString (): retourne la représentation d'un ensemble sous la forme d'une chaine de caractères commençant par un [ et se terminant par ]. Les éléments de l'ensemble sont séparés par des virgules. Cette méthode est particulièrement utile pour afficher un ensemble. L'utilisation de cette méthode sera vue dans les exercices.

Présentation de l'exemple

Il s'agit d'un projet manipulant deux ensembles: les élèves présents le lundi et les élèves présents le mardi. Ce projet se trouve dans le dossier Exemple-Java-ProgObjet2/Presence.

Voici l'interface graphique du projet:

Les zones de texte de gauche à droite se nomment ZT_Lundi, ZT_Mardi et ZT_Lundi_Et_Mardi. Elles sont respectivement destinées à afficher l'ensemble des élèves présents le lundi, le mardi et les deux jours (intersection des deux ensembles précédents).

---

Déclaration et instanciation

L'ensemble des élèves présents le lundi se nomme Lundi. Il est déclaré comme suit:

   TreeSet <String> Lundi = new TreeSet <String> ();

De même pour l'ensemble des élèves présents le mardi:

   TreeSet <String> Mardi = new TreeSet <String> ();

---

Affichage

La procédure suivante affiche un ensemble d'élèves E dans une zone de texte zt:

void Afficher_L_Ensemble (TreeSet  E, JTextArea zt) {
     es.Effacer(zt);
    for (String eleve : E)
          es.Afficher(eleve, zt);     
} 

Nous utilisons ici la boucle for pour afficher chaque élément de l'ensemble E.

---

Génération aléatoire d'un ensemble d'élèves

Les ensembles d'élèves sont générés aléatoirement à partir du tableau Eleve contenant les prénoms de tous les élèves:

 String Eleve [] = 
    {"albert","beatrice","chistine","eric", "esther","francois", 
    "george","ivan","lucie","marc","pierre","sophie"};

Voici la fonction qui nous permet de constuire un ensemble d'élèves au hasard:

  TreeSet  Un_Ensemble_D_Eleve_Au_Hasard () {
  int n = Un_Nombre_D_Eleves_Au_Hasard ();
  int m = 0;
  String un_eleve;
  TreeSet  resultat = new TreeSet  ();
  while (m < n) {
      un_eleve = Un_Eleve_Au_Hasard ();
      while (resultat.contains(un_eleve)) 
          un_eleve = Un_Eleve_Au_Hasard ();
      resultat.add(un_eleve);
      m++;
   }
        
  return resultat;
} 

Elle utilise deux fonctions que nous ne détaillerons pas ici:

• Un_Nombre_D_Eleves_Au_Hasard : retourne un nombre entier compris entre 0 et la taille de tableau Eleve. Ce nombre nous sert à déterminer la taille n de l'ensemble.
• Un_Eleve_Au_Hasard: retourne un élève au hasard (classe String) parmis les élèves du tableau Eleve.

La méthode contains nous permet de tester si l'élève tiré au hasard a déjà été placé dans l'ensemble resultat. Tant que c'est le cas, on re-sélectionne un élève au hasard. Dès que ce n'est plus le cas, on rajoute l'élève en question à l'ensemble resultat avec la méthode add.

---

Intersection

La méthode suivante construit l'intersection des deux ensembles Lundi et Mardi et l'affiche dans la zone de texte ZT_Lundi_Et_Mardi:

void Intersection () {
    TreeSet  Lundi_Et_Mardi = new TreeSet  ();
    Lundi_Et_Mardi.addAll(Lundi);
    Lundi_Et_Mardi.retainAll (Mardi);
    Afficher_L_Ensemble (Lundi_Et_Mardi,ZT_Lundi_Et_Mardi);        
} 

La méthode addAll est tout d'abord utilisée pour recopier l'ensemble Lundi dans le résultat, puis la méthode retainAll, pour ne retenir que les élèves également présents le mardi

.

---

Suppression d'un élève

Le bouton intitulé "Enlever un élève dans lundi" supprime un élève au hasard dans l'ensemble Lundi. Voici la procédure évènementielle associée:

private void BT_Enlever_Un_Eleve_Dans_LundiActionPerformed(...) {                                                               
boolean suppression;  
  do
      suppression = Lundi.remove(Un_Eleve_Au_Hasard());
      
  while (!suppression);
        
        Afficher_L_Ensemble (Lundi,ZT_Lundi);
        Afficher_L_Ensemble (Mardi,ZT_Mardi);
    }  

Comme nous ne pouvons pas être sur que l'élève tiré au hasard soit présent dans l'ensemble, on applique la méthode remove tant que ce n'est pas le cas (le résultat retourné est false).

L'ensemble Mardi est également affiché pour faire apparaitre un bug intéressant dans la section suivante.

---

Copie d'un ensemble d'élèves

L'interface graphique du programme contient deux boutons permettant de recopier l'ensemble Lundi dans l'ensemble Mardi.

Le premier bouton, intitulé "Copier lundi dans mardi (=)" utilise l'affectation simple pour effectuer cette opération. Voici la procédure évènementielle associée:

private void BT_Copier_Lundi_Ds_MardiActionPerformed(...) {                                                         
  Mardi = Lundi;
  Afficher_L_Ensemble (Mardi,ZT_Mardi);
}                                                         

Le second, intitulé "Copier lundi dans mardi (clone)" affecte à l'ensemble Mardi, un clone de l'ensemble Lundi:

private void BT_Copier_Lundi_Ds_Mardi_En_Clonant...{                                                                    
    Mardi = (TreeSet <String>) Lundi.clone();
    Afficher_L_Ensemble (Mardi,ZT_Mardi);
}    

Remarquez le cast obligatoire en TreeSet <String> dans l'affectation car la méthode clone retourne un Object.

En exécutant l'exemple, vous constaterez le phénomène suivant:

• si vous recopiez Lundi dans Mardi avec une affectation simple, toute suppression d'élève dans l'ensemble Lundi sera automatiquement répercutée sur l'ensemble Mardi !!
• si vous recopiez un clone de Lundi dans Mardi, la suppression d'un élève dans l'ensemble Lundi n'est pas répercutée sur l'ensemble Mardi.

Comment expliquer ceci ?

Tout d'abord, les ensembles, tout comme les listes génériques sont représentés en mémoire par une liste de paire de pointeurs. La seule différence avec une liste générique, est que les méthodes interdisent de dupliquer une valeur. Un ensemble n'est donc rien d'autre qu'un pointeur sur la première paire de pointeurs de la liste.

Lorsque vous recopiez Lundi dans Mardi avec une affectation simple, vous ne "recopiez" pas réellement le premier ensemble dans le deuxième. En réalité, vous ne faite que recopier le pointeur contenu dans Lundi dans la variable Mardi. Les deux variables pointent donc sur la même paire de pointeur (celle qui est associé au premier élément de la liste Lundi):

Par conséquent, si on supprime un élément dans la liste Lundi ("eric" dans l'exemple ci-dessus), il sera automatiquement supprimé dans Mardi.

Par contre, en clonant Lundi, vous créez une véritable copie de tous les éléments de la liste Lundi (plus précisément, les paires de pointeurs sont dupliquées):

Dans ce cas, Mardi contient l'adresse de cette copie et supprimer un élément dans Lundi, n'a aucune répercussion sur Mardi.

Limitations

Les explications de ce cours sur l'utilisation de la classe générique TreeSet sont limitées aux ensembles dont les éléments appartiennent à la classe String ou à la classe enveloppe d'un type primitif (comme Integer par exemple).

Pour des ensembles dont les éléments appartiennent à d'autres classes, la déclaration de la classe des éléments fait appel à la notion d'interface dont je ne parlerais pas. De plus, il faut également redéfinir la méthode compareTo de la classe Object.

Le lecteur interessé pourra néanmoins consulter l'exemple de projet Presence2, une variante du projet Presence dans lequel les élèves sont représentés par une classe à deux attributs (nom et prenom):

Cet exemple vous permettra également de comprendre une autre subtilité du clonage: lorsque vous clonez un ensemble, les éléments de l'ensemble eux mêmes ne sont pas clonés. La JVM créé uniquement un double de la liste des paires de pointeurs. Par conséquent, si vous modifiez un élément, cette modification sera automatiquement répercutée sur tout ensemble utilisant cet élément, même s'il s'agit d'un clone.

Vous pouvez vous en assurez en copiant Lundi dans Mardi par clonage. Si vous cliquez ensuite sur Modifier un élève dans lundi, vous constaterez qu'il sera modifié simultanément dans les deux ensembles (son prénom est remplacé par gaston).