\documentclass[10pt,a4paper,oneside]{article}
\usepackage[T1]{fontenc} % pour avoir des accents
\usepackage{amsmath}
\usepackage{amsthm} 
\usepackage{amsfonts}
\usepackage[francais]{babel}
\usepackage[dvips]{graphics}
\pagestyle{headings} 

\def\vsp   {\vspace{2 ex}}
\def\vvsp  {\vspace{4 ex}}
\def\vvvsp {\vspace{6 ex}}

\begin{document}
\setlength{\parindent}{0pt} % valeur par défaut 12pt
\setlength{\parskip}{6pt plus 3pt minus 3pt} %blanc vert entre 2 paragraphes


\author{Daniel Tounissoux\thanks{Université Claude-Bernard Lyon1 43 Bd du 11 Novembre 69622 Villeurbanne Cedex}}
\date{\today}
\title{Java - Document Tp.2}
\maketitle
\tableofcontents  

\section{Compléments sur les classes et objets}

\subsection{Structure générale d'une classe}

Jusqu'alors nous n'avons considéré que des classes dont tous les champs étaient "static". L'exemple suivant reprend notre premier exemple sans cette contraite :

\begin{verbatim}
public class Bonjour  {

    public Bonjour(){ };

    public void affiche(){
        System.out.println("bonjour");
    }

    public static void main(String args[]){
        Bonjour x=new Bonjour();
        x.affiche();
    }
} // Bonjour
\end{verbatim}
    
On voit que :

\begin{itemize}
\item La fonction principale "main" reste toujours "static"
\item La première fonction {\em public Bonjour(){ };} s'appelle un constructeur ; cette fonction n'a pas de type de retour.
\item L'utilisation de la classe est assez différente ; l'instruction {\em Bonjour x=new Bonjour(); } crée une {\em instance } x de la classe Bonjour, en faisant appel au constructeur. Toutes les méthodes de la classe sont accessibles à partir de x, mais ne sont plus accessibles directement à partir du nom de la classe.
\end{itemize}

Une classe peut mélanger des champs statiques et non statiques, mais une fonction statique ne doit pas utiliser des champs non statiques. Les méthodes statiques sont aussi appelées des méthodes de classe. Les champs statiques ont la même valeur dans toutes les instances de la classe.

\subsection{Constructeurs}

Un constructeur est une méthode particulière qui est toujours appelée lors de la création d'une intance de la classe. 

Quand nous écrivons :
\begin{verbatim}
   Bonjour x=new Bonjour();
\end{verbatim} 
Bonjour() correspond à l'appel d'un constructeur. Si, dans la définition de la classe, il n'existe pas de constructeur, java prévoit un constructeur par défaut ne possédant pas de paramètre. 

Un constructeur porte le même nom que la classe et ne possède pas de type de retour. 

Il peut exister plusieurs constructeurs différents pourvu que leurs signatures soit différentes. Par exemple, on peut constater que la classe Integer possède deux constructeurs, l'un avec pour paramètre un type {\tt int} l'autre avec un type {\tt String} ; ainsi on pourra écrire indifféremment :
\begin{verbatim}
   Integer a=new Integer(35);
\end{verbatim}
ou
\begin{verbatim}
   Integer a=new Integer("35");
\end{verbatim}





\subsection{Héritage}

L'héritage permet de définir une nouvelle classe à partir d'une classe existente en lui apportant quelques modifications.

L'en-tête d'une classe dérivée de la classe {\tt MaClasse} a une syntaxe du type suivant :
\begin{verbatim}
  public class AutreClasse extends MaClasse { ... }
\end{verbatim}

On dit que {\tt AutreClasse} hérite ou étend {\tt MaClasse}, ou qu'elle en est une classe dérivée. On dit aussi que {\tt MaClasse} est une classe ancêtre, ou la classe parente de  {\tt AutreClasse}. 

Dans {\tt AutreClasse} on pourra trouver :
\begin{itemize}
\item de nouveaux champs
\item de nouvelles méthodes
\item des méthodes portant le même nom et la même signature que dans MaClasse : on dit que ces méthodes sont redéfinies, et elles viennent remplacer les méthodes correspondantes de MaClasse.
\item des méthodes portant le même nom et des signatures différentes : on dit que ces méthodes sont surdéfinies.
\end{itemize}

Le plus souvent, afin de simplifier les initialisations, le constructeur de la classe dérivée fera appel au constructeur de la classe ancêtre, de la manière suivante :

\begin{verbatim}
  public class AutreClasse extends MaClasse { 
    public AutreClasse( ...) { // nouveau constructeur
      super(...);     // appel du constructeur de la classe parente
      ... ;
    }
\end{verbatim}

Remarque. Si {\tt AutreClasse} est une classe descendante de {\tt MaClasse}, on peut considérer que tout objet de la classe {\tt AutreClasse} est aussi un objet de la classe {\tt MaClasse}. Ainsi, il est correct d'écrire :
\begin{verbatim}
   MaClasse x = new AutreClasse(...) ;
\end{verbatim}
En Java toutes les classe ont pour ancêtre ultime, une classe nommée {\tt Object}. Ainsi tout objet appartient à la classe {\tt Object}.

{\bf Exercice}

La classe {\tt Stat} suivante calcule les statistiques élémentaires sur les $n$ premiers entiers
 
\begin{verbatim}
public class Stat  {
    double x[];  int n ;

    public Stat(int n){
        this.n=n ; x=new double[n];
        for (int i=0;i<n;i++) x[i]=i;
    }

    public double moyenne(){
        double m=0;
        for (int i=0;i<n;i++) m+=x[i];
        m=m/n;  return m;
    }

    private double moyenneCarres(){
        double m=0;
        for (int i=0;i<n;i++) m+=x[i]*x[i];
        m=m/n ; return m;
    }

    public double variance(){
        double m=moyenne();
        return moyenneCarres()-m*m ;
    }

    public double ecartType(){
        return Math.sqrt(variance());
    }

    public void afficheStat(){ 
        System.out.println("moyenne = "+moyenne());
        System.out.println("variance = "+variance());
        System.out.println("ecart-type = "+ecartType());
    }

    public static void main(String args[]){
        Stat s= new Stat(10);
        s.afficheStat();
    }
} // Stat
\end{verbatim}

1- Tester cette classe.

2- Ajouter un constructeur dont le paramètre est un tableau de réels.

3- Supprimer la fonction main ; créer un nouvelle classe, comportant une fonction {\tt main} qui définira un tableau de réels, et qui utilisera la classe {\tt Stat} pour opérer sur ce tableau les calculs de moyenne. 

4- Ecrire une classe {\tt StatPoids} dérivant de {\tt Stat} mais dans laquelle les termes de la série sont affectés d'un coefficient positif {\tt p[i]} (ne réécrire dans cette classe que les méthodes présentant une modification)

En incluant des instructions d'écriture dans chaque fonction, faire afficher la liste des fonctions appelées (avec la classe d'appartenance) lors de l'exécution du programme.


\section{Utilistation de quelques classes importantes}

Nous étudions ici quelques structures de données classiques, leur mise en \oe uvre et leur utilisation.

\subsection{Préliminaire : évaluation d'un temps de calcul}

La classe {\tt Date} permet de récupérer la date avec l'heure. En procédant comme suit, on peut déterminer le temps de calcul.
\begin{verbatim}
        import java.util.Date ;

        long time;
        Date date=new Date();time=date.getTime();
        ... // calculs
        date=new Date();time=date.getTime()-time ;
\end{verbatim}
{\tt getTime()} retourne l'heure en millisecondes (type long).

{\em remarque : en dehors des classes d'utilisations très courantes, les classes de la librairie standard doivent être explicitement importées ; c'est le rôle de la directive :  {\em import java.util.Date ;}
}

\subsection{Listes, files, piles}

Les listes sont des structures de données dynamiques permettant de gérer des ensembles dont les éléments sont repérés par leur rang.

Les listes sont des structures dynamiques, c'est-à-dire que le nombre d'éléments qu'elles contiennent n'est pas fixé à l'avance.

Les listes sont constistuées de cellules. Chaque cellule contiendra un élément ainsi qu'une information permettant de trouver la cellule suivante (et éventuellement la cellule précédente) dans la liste. On parle de listes chaînées.

La structure d'objet est bien adaptée pour représenter les cellules.

Les principales fonctions permettant de gérer les listes sont
\begin{itemize}
\item {\em initialiser} une liste vide
\item {\em ajouter} un élément en un rang donné,
\item {\em supprimer} un élément de rang donné,
\item déterminer de la {\em longueur} de la liste
\item déterminer si la liste est {\em vide}
\end{itemize}
On peut envisager de nombreuses autres fonctions pour faciliter la gestion d'une liste.

Voici une implémentation d'une liste qui ne demande qu'à être améliorée. Nous avons utilisé un double chaînage, ce qui permet de parcourir la liste dans les deux sens.

\begin{verbatim}
public class Liste  {

    Cellule first,last ;
    Cellule courant ;
    int lg ;

    public Liste () { first=null ; last=null; lg=0; }
    
    public void affiche(){
        System.out.println("longueur =" + longueur());
        if (first==null) return ;
        courant=first ;
        while (courant!=null) {
            afficheCellule(courant);
            afficheCellule(courant.suivant);
            afficheCellule(courant.precedent);  
            System.out.print('\n');
            courant=courant.suivant;
        }
    }

    private void afficheCellule(Cellule c){
        String s ;
        if (c==null) s="null"; 
        else s=(c.element).toString();
        System.out.print(s+" ");
    }

    public boolean listeVide(){ return first==null ; }

    public Cellule premier(){ 
        return first ; 
    }

    public int longueur(){ return lg ; }


    public void ajouter(Object e, int rang){
        if (rang<=0 || rang>lg+1) return ; 
        Cellule m=new Cellule(e);
        if (listeVide()) {first=m;last=m;lg++; return ; }
        if (rang==1) { 
          m.suivant=first; first.precedent=m; first=m;lg++;return; 
        } 
        if (rang==lg+1) {
          m.precedent=last ; last.suivant=m ;last=m;lg++;return; 
        }
        courant=first ;int r=1;
        while (r<rang-1) { courant=courant.suivant ; r++ ; }
        m.suivant=courant.suivant ; m.precedent=courant ;
        (courant.suivant).precedent=m ;courant.suivant=m ; 
        lg++ ;
    }

    public void supprimer(int rang){ // à faire
    }

    public void ajouterFin(Object e){
        System.out.println("ajouter"+e);
        Cellule m=new Cellule(e);
        if (first==null) {first=m;last=m;} 
        else {last.suivant=m;m.precedent=last;last=m;} 
        lg++ ;
    }

    public void supprimerFin(){
        if (first==null) return ;
        if (first==last) {first=null ; last=null;lg=0;return ; }
        last=last.precedent; last.suivant=null; 
        lg--;
    }

    public static void main(String a[]){
        Liste l=new Liste();
        l.ajouter("A",1);l.ajouter("B",1);l.ajouter("X",3);
        l.affiche();
    }

    class Cellule {
        Cellule(Object e){ 
            element=e ;
            suivant = null;precedent=null ;
        } 
        Cellule suivant,precedent ;
        Object element ;
    }

}// Liste
\end{verbatim}

(la fonction {\tt supprimer} n'a pas été implantée : on peut le faire à titre d'exercice).

Il faut remarquer la simplicité d'une telle implantation. Noter que la classe {\tt Cellule} comporte 2 champs {\tt Cellule}.

La fonction {\tt main} permet de faire des essais, mais il serait intéressant de faire une interface graphique permettant d'effectuer des essais sur une liste (avec un menu déroulant pour {\tt ajouter}... ).

Sous cette forme les éléments de la liste, peuvent être des objets de n'importe quel type. On peut essayer d'inclure dans une même liste des {\tt Integer}, des {\tt String}, des {\tt Double}, etc...

{\bf Exercice} Sur le même modèle, créer une structure de pile (une pile est une liste qui permet seulement d'ajouter au début ({\em empiler}) et de supprimer au début ({\em dépiler}))


\subsection{Les classes Vector, ArrayList, LinkedList}

La classe {\tt LinkedList} permet de créer les listes beaucoup plus simplement.

Voici une classe qui possède à peu près les mêmes fonctions que la précédente :


\begin{verbatim}
import java.util.* ;

public class LListe extends LinkedList {
    public LListe () {  }

    public void affiche(){
        System.out.println("longueur =" + longueur());
        for (int i=0;i<size();i++)System.out.println(get(i));
    }

    public int longueur(){ return size() ; }

    public void ajouter(Object e, int rang){
        add(rang-1,e);
    }

    public void supprimer(int rang){
        remove(rang-1);
    }

    public static void main(String a[]){
        LListe l=new LListe();
        l.ajouter("A",1);l.ajouter("B",1);l.ajouter("X",3);
        l.affiche();
    }
}// LListe
\end{verbatim}
Nous avons procédé à un décalage des indices pour que le rang du premier élément soit égal à 1.

Les classes {\tt Vector} et {\tt ArrayList} sont très semblables à {\tt LinkedList}; ces 3 classes  diffèrent surtout par leur implantation, et seront plus ou moins efficaces selon l'usage qui en est fait.

{\bf Exercice} Comparer les performances des implantations des listes au moyen des 3 classes précédentes {\tt Vector, ArrayList, LinkedList}. Par exemple on peut essayer de créer un liste en insérant 1000 éléments au début, puis à la fin ...

\subsection{Arbres binaires de recherche}

Rappelons qu'un arbre binaire de recherche est un arbre binaire étiqueté tel que pour tout sommet $s$ de l'arbre :
\begin{itemize}
\item les éléments des sommets du sous-arbre de gauche sont inférieurs à l'élément contenu dans s,
\item les éléments des sommets du sous-arbre de droite sont supéérieurs à l'élément contenu dans s.
\end{itemize}


\begin{verbatim}
public class Arbre  {
    Sommet racine ;

    public Arbre(){ racine = null; }

    /**
     * ajoute un élément aux feuilles d'un arbre de recherche. 
     * Version itérative
     *
     */
    void ajouter( Integer e){ 
        Sommet sc ; // sommet courant
        if (racine==null) {
            racine =new Sommet(e) ; 
        }
        else {
            sc=racine ;boolean ok=false ;
            do { 
                if (sc.val.intValue() > e.intValue())
                    if (sc.gauche==null) {sc.gauche=new Sommet(e);ok=true;} 
                    else sc=sc.gauche; 
                else //if (sc.val.intValue() < e.intValue())
                    if (sc.droit==null){ sc.droit=new Sommet(e);ok=true;} 
                    else sc=sc.droit; 
            } while(! ok) ;
        }
    }

    void ajouter (int e){ ajouter(new Integer(e)); }

    void ajouter (int e[]){
        for (int i=0;i<e.length;i++)  ajouter (e[i]); 
    }

    void affiche(){ 
        if (racine!=null) racine.affiche();
        System.out.println(); 
    }

    void affichePrefixe(){ 
        System.out.println("Prefixe");
        if (racine!=null) racine.affichePrefixe();
        System.out.println(); 
    }

    void affichePostfixe(){ 
        System.out.println("Postfixe");
        if (racine!=null) racine.affichePostfixe(); 
        System.out.println();
    }

    void afficheInfixe(){ 
        System.out.println("infixe");
        if (racine!=null) racine.afficheInfixe();
        System.out.println(); 
    }


    public static void main(String arg[]){
        Arbre a=new Arbre();
        int e[]={5,3,7,1,4,6,8};
        a.ajouter(e);
        a.affiche();System.out.println();
        a.afficheInfixe();System.out.println();
        a.affichePrefixe();System.out.println();
        a.affichePostfixe();System.out.println();
    }


    class Sommet {
        Integer val ;
        Sommet gauche=null ;
        Sommet droit=null ;

        Sommet(Integer e){ 
            val = e ; gauche=null;droit=null ; }

        void affiche(){
            System.out.print(val+" ( ");
            if (gauche!=null) gauche.affiche() ;
              else System.out.print(". ");
            if (droit !=null) droit.affiche(); 
              else System.out.print(". ");
            System.out.print(") ");
        }

        void affichePrefixe(){
            System.out.print(val+" ");
            if (gauche!=null) gauche.affichePrefixe() ;
            if (droit !=null) droit.affichePrefixe();
        }

        void affichePostfixe(){
            if (gauche!=null) gauche.affichePostfixe() ;
            if (droit !=null) droit.affichePostfixe();
            System.out.print(val+" ");
        }

        void afficheInfixe(){
            if (gauche!=null) gauche.afficheInfixe() ;
            System.out.print(val+" ");
            if (droit !=null) droit.afficheInfixe();
        }

    } 

}// Arbre
\end{verbatim}

Les éléments associés aux sommets sont des entiers {\tt Integer} ; il serait aussi possible d'utiliser des objets quelconques, pourvu qu'ils soient comparables par une relation d'ordre.

Seule la fonction {\tt ajouter} a été implantée; mais nous avons utilisé les possibilités de Java pour passer en paramètre un entier ({\tt int} ou {\tt Integer}, ou bien un tableau d'entiers.Ces fonctions permettent d'ajouter des éléments aux feuilles de l'arbre.

{\bf Exercice} Modifier la fonction main pour pouvoir générer de façon aléatoire un arbre possédant 1000 sommets.

Ecrire une fonction permettant de calculer le nombre de feuilles de l'arbre.

Ecrire une fonction permettant de calculer la hauteur de l'arbre (longueur du plus grand chemin)..

Ecrire une fonction permettant de déterminer si une valeur donnée est présente dans l'arbre.


\subsection{Les arbres syntaxiques}

Les arbres syntaxiques permettent de représenter des expressions numériques. Pour simplifier, nous ne considérons que deux opérateurs binaires $*$ et $+$ opérants sur des entiers.

Voici une implantation Java d'un tel arbre.

\begin{verbatim}
public class ArbreSyntax  {
    Sommet racine; 
    int debut=0; // debut de la partie non traitée 

    public ArbreSyntax (String s[]) { racine = new Sommet() ;racine.ajouter(s);  }
    
    public static void main(String a[]){
        String s[]={"*","+","2","3","+","4","5"};
        ArbreSyntax x=new ArbreSyntax(s);
        x.racine.afficheInfixe();
        System.out.println(" = "+x.racine.eval());
    }

    class Sommet {
        String val="" ;
        Sommet gauche ;
        Sommet droit ;

        Sommet(){ 
            val ="" ;gauche=null;droit=null ; 
        }

        void ajouter(String s[]){
            if (debut>s.length) return ;
            val=s[debut];debut++;
            if (val.equals("+") || val.equals("*")) {
                gauche=new Sommet();gauche.ajouter(s);
                droit=new Sommet();droit.ajouter(s);
            } 
        }

        int eval(){
            if (!(val.equals("+") || val.equals("*")) )
                return Integer.parseInt(val);
            else {
                if (val.equals("+")) return (gauche.eval()+droit.eval());
                if (val.equals("*")) return (gauche.eval()*droit.eval());
                else return(9999);
            }
        }

        void affiche(){
            System.out.print(val+" ( ");
            if (gauche!=null) gauche.affiche() ; else System.out.print(". ");
            if (droit !=null) droit.affiche(); else System.out.print(". ");
            System.out.print(") ");
        }

        void affichePrefixe(){
            System.out.print(val+" ");
            if (gauche!=null) gauche.affichePrefixe() ;
            if (droit !=null) droit.affichePrefixe();
        }

        void afficheInfixe(){ System.out.print("( ");
            if (gauche!=null) gauche.afficheInfixe() ;
            System.out.print(val+" ");
            if (droit !=null) droit.afficheInfixe();
            System.out.print(") ");
        }
    }
}// ArbreSyntax
\end{verbatim}

Pour construire un tel arbre, on devra passer au constructeur une expression sous forme polonaise (on écrit $*\ +\ 2\ 3\ 4$ pour $(2+3)*4$). Le cas d'une expression incorrecte n'est pas prévu ...

{\bf Exercice.} Modifier cette classe pour qu'elle puisse traiter des réels, et permette l'utilisation d'une fonction telle que $\tt sinus$.

Il est difficile de faire un analyseur syntaxique complet, pouvant prendre en compte des variables. Certains sont diffusés gratuitement sut Internet, c'est le cas de {\tt jep212}. Les classes sont compactées dans un fichier {\tt jep212.jar}. Voici un programme permettant de calculer une expression numérique fournie sur la ligne de commande.

(La classe principale de la librairie {\tt jep212} s'appelle {\tt JEP})

\begin{verbatim}
/* illustration élémentaire du parser jep 
   Exemple d'utilisation :
   compilation 
   # javac -classpath jep212.jar:. Evalc.java 
   exécution   
   # java -classpath jep212.jar:. Evalc "2^2+3^2+4^2" 
*/
import org.nfunk.jep.*;

public class Evalc  {

    JEP myParser=new JEP();
    Double result ;

    public Evalc (String s) {
        myParser.addStandardFunctions();
        myParser.addStandardConstants();

        myParser.parseExpression(s);
        if (s!=null) {
            result=(Double)myParser.getValueAsObject();
        }
    }

    public Evalc () {
        myParser.addStandardFunctions();
        myParser.addStandardConstants();
    }

    public Double getResult(String s){ 
        myParser.parseExpression(s);
        return result = (Double)myParser.getValueAsObject(); 
    }

    public Double getResult(){ return result ; }

    public static void main(String a[]){
        Evalc e ;
        if (a.length > 0) { e = new Evalc(a[0]) ;System.out.println(e.getResult()); }   
        else { e = new Evalc();System.out.println(e.getResult("6^2"));}
    }
    
}// Evalc
\end{verbatim}

Il est facile de se procurer les sources sur internet, ainsi que le mode d'emploi et des exemples.


% =================================== Annexe

\newpage
\begin{center}
{\huge Annexe}
\end{center}

%\annexe
\section{Javadoc}

Il est possible de générer automatiquement une documentation  à partir des commentaires des fichiers sources.

Pour cela on place avant chaque méthode publique, champ ou classe un commentaire commençant par /** au lieu de /*, de la façon suivante :

\begin{verbatim}
/** 
* <commentaires sur la fonction> 
* @param <liste des paramètres >  
* @return <valeur retournée> 
* @view <liste des fonctions en rapport avec cette fonction>
*/
\end{verbatim}

On lance alors javadoc en lui donnant comme paramètre le ou les fichiers sources, ce qui va avoir pour effet de générer des fichiers HTML semblables à ceux de la documentation de Sun.
 
(Pour plus de détails, consulter la doc "Tool documentation")

\section{Fichiers jar}

Les fichiers {\tt .jar} sont des fichiers compactés analogues aux les fichiers {\tt .zip}. Un utilitaire  {\tt jar} fourni avec  {\tt java} permet de les gérer. 

Java a la possibilité d'exécuter les classes contenues dans des fichiers compactés {\tt .jar} ou {\tt .zip}.

Par exemple on crée, un fichier {\tt bonjour.jar} comme suit :
\begin{verbatim}
   # jar cvf bonjour.jar Bonjour.class
\end{verbatim}
On pourra exécuter la classe {\tt Bonjour.class} (supposée contenir une fonction {\tt main} ne demandant pas de paramètre sur la ligne de commande), en tapant :
\begin{verbatim}
   # java -classpath bonjour.jar Bonjour
\end{verbatim}
Tout ceci fonctionne aussi bien avec un fichier {\tt bonjour.zip}. Il est naturellement possible de placer toutes les classes dans un fichier {\tt jar}.

Mais les fichiers {\tt jar} offrent des possibilités supplémentaires par rapport aux fichiers {\tt zip} : il est possible d'inclure dans le fichier {\ jar} des informations supplémentaires sur la classe principale. On procède ainsi :

1- Créer un fichier texte {\tt xx.txt } contenant :
\begin{verbatim}
Manifest-Version: 1.0
Main-Class: Bonjour  
\end{verbatim}
( {\tt Bonjour} représente la classe principale. Attention : faire suivre le nom de la classe principale {\tt Bonjour} uniquement d'un retour chariot, sans espace  )

2- Créer le fichier {\tt jar} en tapant 
\begin{verbatim}
  # jar cvfm bonjour.jar xx.txt Bonjour.class
\end{verbatim}

3- Vérifier que le fichier {\tt bonjour.jar } a bien été créé.

4- Exécuter le programme en tapant :
\begin{verbatim}
  # java -jar bonjour.jar
\end{verbatim}
Sous Windows, il suffit de double-cliquer sur l'icône du fichier pour l'exécuter.

Des indications supplémentaires pourront être trouvées en tapant {\tt jar}, et dans la documentation de Sun.




\end{document}
