Cours 12 du 11 avril :
Notion de types abstraits de données
Exemple:
Une Pile est une structure de données avec (essentiellement) les deux opérations empiler et dépiler, a priori on peut manipuler une Pile sans pour autant savoir comment elle est réalisée.
Quelques principes:
- Séparer la définition (abstraite) de la représentation
- Type abstrait: défini par des opérations sur le type et des propriétés de ces opérations
- Type concret: implémentation du type abstrait. l'implémentation doit vérifier les propriétés du type abstrait
- A un type abstrait peut correspondre de nombreux types concrets qui l'implémentent
En supposant qu'un programme n'utilise que ce qui est définit par le type abstrait de données, on peut développer le programme indépendamment des implémentations du type de abstrait.
Type abstrait de données: exemple de la Pile
Définition du type Pile de X (ici X est un type quelconque)
· Nom du type : Pile[X]
· types des opérateurs (signature des méthodes)
o création
§ Pile :-> Pile[X]
o test à vide
§ estVide: Pile[X] -> Boolean
§ empiler: XxPile[X] -> Pile[X]
§ dépiler: Pile[X] -> XxPile[X]
· propriétés des opérateurs:
o préconditions:
§ dépiler(X): non etsVide(X)
o axiomes:
§ Pour tout x de X pour tout s de Pile[X]
· estVide(Pile()) (une pile créée est initialement vide)
· non estVide(empiler(x,s))
·
dépiler(empiler(x,s))=(x,s)
Toutes les Piles au sens usuel vérifient ces propriétés et ces propriétés caractérisent les Piles.
Ces définitions et propriétés sont indépendantes de toute représentations (on ne sait même pas s'il peut y avoir une représentation) et avec un peu de formalisme supplémentaire on pourrait montrer d'autres propriétés sur les Piles uniquement à partir des axiomes.
Interface Java pour une Pile
On a vu dans le chapitre précédent le type Object qui peut contenir n'importe quel objet d'u type référence. On va donc construire un type Pile de Object. On pourra ainsi construire des piles sur n'importe quel objet. (On notera cependant que dans ce cas, on ne peut assurer que tous les objets de la pile sont du même type. Il existe en java un moyen –la généricité- permettant d'avoir des Piles construites avec des objets d'un type particulier).
Une interface en Java est composée de déclarations de méthodes mais sans définition de méthodes ni présence de variables d'instance:
// Interface Pile simple
interface Pile {
public Object
depiler();
public void empiler(Object o);
public boolean
estVide();
}
On peut ensuite avoir diverses implémentations de la cette interface.
Implémentation avec des listes:
// listes d Object
class Noeud {
Object item;
Noeud suivant;
public Noeud(Object o) {
item=o;
suivant=null;
}
public Noeud(Object o, Noeud n){
item=o;
suivant=n;
}
}
// implémenter les Pile avec des listes
class PileListe implements Pile{
private Noeud sommet;
public PileListe(){sommet=null;}
public
boolean estVide(){ return (sommet==null);}
public void empiler(Object o){
sommet=new Noeud(o,sommet);
}
public Object depiler(){
Object tmp=sommet.item;
sommet=sommet.suivant;
return tmp;
}
}
Implémentation avec des tableaux :
// implémenter les piles avec une table
class PileTable implements Pile{
private Object[] v;
private int
taillemax=1000;
private int sommet;
public PileTable(){
v=new Object[taillemax];
sommet=0;
}
public PileTable(int
n){
taillemax=n;
v=new
Object[taillemax];
sommet=0;
}
public boolean estVide(){return sommet==0;}
public Object depiler(){
return v[--sommet];
}
public void empiler(Object o){
v[sommet++]=o;
}
}
On notera que:
- la classe PileListe et la classe PileTable déclarent dans leur entête qu'elles implémentent l'interface Pile.
- à chaque déclaration de méthodes de l'interface correspond une définition de méthode de même signature.
- ce qui concerne l'implémentation particulière est déclaré comme private: l'utilisateur ne doit avoir accès qu'à ce qui concerne la Pile abstraite.
- chacune des implémentations a ses propres constructeurs.
- (dans la suite on parlera d'abstrait pour ce qui concerne l'interface et de concret pour ce qui concerne les implémentations de l'interface.
La déclaration d'une variable de type PileTable ou PileListe, comme la création d'un objet correspondant ne change pas de l'habitude:
PileListe q=new PileListe();
PileTable r=new PileTable(100);
Bien sûr il ne peut y avoir d'objet Pile général: aucune implémentation n'est présente, mais un objet PileTable ou PileListe peut toujours être considéré comme une Pile.
Pile q=new
PileListe();
PileTable r
q=r;
r= (PileTable)q;
/* ce qui suit est incorrect
Pile t=new Pile();
PileListe u=new PileTable();
*/
On notera:
- la première ligne ne pose pas de problème: q est déclaré comme une Pile, il peut donc contenir un objet PileListe
- idem pour la troisième ligne: q contient maintenant un objet PileTable
- dans la ligne suivante la conversion (PileTable) est indispensable:
- même si PileTable et PileListe implémentent tous les deux des Piles, les deux types ne sont pas compatibles: une PileTable n'est pas une PileListe!
- au moment de la compilation on sait seulement d'après sa déclaration que q est une Pile (il est possible que q soit null ou une PileListe
- pour éviter les erreurs il faut au moment de l'exécution que q soit à ce moment là une PileTable: le (PileTable) force cette vérification et s'il se trouvait que q ne soit pas une PileTable on aura une erreur à l'exécution (plus précisément une exception)
- le compilateur exige cette conversion (PileTable).
- new Pile() n'a pas de sens: Pile n'est qu'une interface
- les types PileListe et PileTable sont différents (même s'ils implémentent tous les deux une Pile).
Notons que:
§ au moment de la compilation le compilateur vérifie la compatibilité des types d'après les déclarations des variables.
§ au moment de l'exécution la machine virtuelle java vérifie que les affectations ont bien un sens de façon à assurer par exemple que tout objet PileTable est bien une PileTable (de façon similaire pour les tableaux le machine virtuelle Java vérifie qu'on ne sort pas des indices du tableau).
On peut ensuite travailler avec une pile de façon générale sans se préoccuper de savoir s'il s'agit d'une PileTable ou d'une PileListe (ou de n'importe quelle autre implémentation de Pile!):
public
static Noeud Pile2Liste(Pile p){
Noeud tmp;
Noeud tete=tmp=new Noeud(null);
while(!p.estVide())
tmp=tmp.suivant=new
Noeud(p.depiler());
return
tete;
}
Cette méthode transforme une pile en liste chaînée: elle peut être utilisée avec n'importe quelle implémentation de Pile. Elle est utilisée dans le morceau de code suivant:
Pile q=new
PileListe();
for (int i = 0;
i < 100; i++)
q.empiler(i);
Noeud
n=Pile2Liste(q);
Il est important de noter qu'au moment de la compilation le compilateur
ne sait pas à quelle méthode concrète sera associée empiler ou depiler,
il ne connaît que les méthodes abstraites depiler
et empiler qui ont été déclarées
dans l'interface Pile. Ce n'est
qu'au moment de l'exécution que, suivant l'objet qui sera passé en paramètre (PileTable, PileListe ou autre Pile)
dans le premier cas ou qui a été affecté
dans le deuxième cas, à quelle méthode concrète (empiler
ou depiler de PileTable, PileListe ou autre Pile)
sera associée à p.depiler ou q.depiler. Il faut noter qu'au moment
de la compilation du programme, il est tout à fait possible que la méthode
concrète ne soit pas encore définie. Il s'agit d'un mécanisme nouveau:
jusqu'ici l'association entre un nom (p.depiler)
et le code se faisait à
Pour résumer:
- une interface I ne contient que des déclarations de méthodes (abstraites)
- une classe C (concrète) qui implémente une interface doit définir les méthodes déclarées dans l'interface
- la signature et la valeur retournée de ces méthodes doivent être identiques pour l'interface et la classe qui l'implémente
- on peut déclarer des variables de type I, mais on ne peut pas créer d'objet pour une interface I
- tout objet de C qui implémente I
peut être considéré comme étant de type I
- une variable déclarée de type I contenant un objet de type C qui implémente I peut être affectée à une variable de type C à condition d'explicitement faire un "cast" ((C)).
- l'association du nom d'une méthode de l'interface avec la méthode concrète qui l'implémente se fait à l'exécution suivant le type de l'objet.
Ces mécanismes sont à la base de la programmation orientée objets. Ils se généralisent en Java à d'autres constructions que les interfaces. Pour l'essentiel on a les deux notions liées:
- héritage: un objet de type A peut être considéré comme étant de type B (similaire à: un objet de type C implémentant une interface I peut être considéré comme un I). De cette façon une variable déclarée d'un type B peut en fait contenir un objet de type A.
- liaison dynamique: l'association d'un nom à une méthode se fait à l'exécution suivant le type de l'objet référencé et non suivant le type de la déclaration.