5.5 Exemple : arbres, types abstraits et exceptions

Voici une utilisation d'une interface et du sous-typage pour représenter tous les arbres, même l'arbre vide, par des objets. On commence par définir un type abstrait ArbreBinaire, puis deux sous-types concrets, un pour les arbres non-vides, et un pour les arbres vides :

interface ArbreBinaire {
  boolean estVide();
}

class AVide implements ArbreBinaire {
  public boolean estVide() {
    return true;
  }
}

class ACons implements ArbreBinaire {
  int étiquette;
  ArbreBinaire gauche, droit;

  ACons(int étiquette, 
        ArbreBinaire gauche, 
        ArbreBinaire droit) {
   this.étiquette = étiquette;
   this.gauche = gauche;
   this.droit = droit;
  }

  public boolean estVide() {
    return false;
  }
}

On remarquera que la classe ACons n'est plus directement auto-référencée : les champs gauche et droit ne sont pas de type ACons, mais ArbreBinaire, de manière à permettre à un sous-arbre d'être vide. Une application pourra déclarer une variable a de type abstrait ArbreBinaire, et pourra l'initialiser à l'aide des constructeurs des classes concrètes :

    ArbreBinaire a = 
      new ACons(1,
                new ACons(2, new AVide(), new AVide()),
                new ACons(3, new AVide(), new AVide()));

Figure: Représentation d'un arbre binaire où l'arbre vide est un objet.

L'exécution de l'appel a.estVide() conduit à invoquer la méthode estVide de ACons, qui retourne false.

La définition de la classe AVide a cependant un défaut : chaque invocation du constructeur AVide retourne un nouvel arbre vide, et tous les arbres vides retournés sont distincts. Ce défaut peut être corrigé en interdisant l'invocation de ce constructeur (il suffit de le rendre privé), et en s'assurant de l'existence d'une unique instance de la classe (ce qui s'obtient en en faisant une variable de classe arbreVide) : ceci est un exemple de classe singleton (voir § ). Pour empêcher toute modification de cette variable, on la rend également privée et on y accède en lecture seulement par une méthode de classe val :

class AVide implements ArbreBinaire {
  private static AVide arbreVide = new AVide();
  private AVide(){}
  static AVide val() {
    return arbreVide;
  }

  public boolean estVide() {
    return true;
  }
}

    ArbreBinaire a = 
      new ACons(1,
        new ACons(2, AVide.val(), AVide.val()),
        new ACons(3, AVide.val(), AVide.val()));

Figure: Représentation d'un arbre binaire avec l'arbre vide comme l'unique instance de la classe AVide.

5.5.0.0.1 Destructeurs

Alors que les constructeurs ne sont définis que dans les classe concrètes AVide et ACons, il est tentant de déclarer des destructeurs étiquette, gauche et droit dans l'interface ArbreBinaire :

interface ArbreBinaire {
  // ...
  int étiquette();
  ArbreBinaire gauche();
  ArbreBinaire droit();
}

La définition de ces méthodes dans la classe ACons est immédiate :

class ACons implements ArbreBinaire {
  // ...
  public int étiquette() { return étiquette; }
  public ArbreBinaire gauche() { return gauche; }
  public ArbreBinaire droit() { return droit; }
}

Par contre, leur définition dans la classe AVide est problématique ; l'idéal serait de ne pas les définir, mais dans ce cas AVide ne serait plus une réalisation de ArbreBinaire. Il faut donc les définir, mais au lieu de retourner une valeur, ces méthodes vont déclencher une exception, à l'aide de l'instruction throw :

class AVide implements ArbreBinaire {
  // ...
  public int étiquette() { 
    throw new UnsupportedOperationException(); 
  }
  public ArbreBinaire gauche() { 
    throw new UnsupportedOperationException(); 
  }
  public ArbreBinaire droit() { 
    throw new UnsupportedOperationException(); 
  }
}

Cette solution peut s'appliquer à toute méthode, déclarée dans l'interface, mais qui n'est pas définie dans une classe. Dans le cas d'une méthode partielle, c'est-à-dire qui n'est pas définie pour certaines valeurs de ses arguments, on pourra déclencher plutôt l'exception java.util.NoSuchElementException. Ainsi, dépiler une pile vide devrait déclencher cette exception.