Skip to content

Latest commit

 

History

History
288 lines (267 loc) · 14.3 KB

cs108.md

File metadata and controls

288 lines (267 loc) · 14.3 KB
Raw

CS108

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Spring 2014: Pratique de la Programmation Orientée Object

[TOC]

Eléments de génie logiciel

  1. les paquetages
    • nom unique
    • nom qualifié : collections.Map
    • visible dans le même paquetage
    • interdiction de redéfinir un même nom au sein d'un paquetage ou d'un import
    • import multiple peu conseillé : import java.util.*;
    • visibilité des classes dans un paquetage :
      • rien : visible uniquement dans le même paquetage
      • protected : visible dans leur paquetage et dans toutes les sous-classes
      • private
      • public
    • nommage : ch.epfl.[...]
    • import statique peut être utilisé pour utiliser une methode sans nommé sa classe : import static Math.sin;
  2. les assertions
    • peut être supprimé à la compilation (-ea = enable assertion)
    • vérifier la validité de certaine condition
    • assert l > l0 || h < h0 : "l="+l+" h="+h;
    • les exceptions sont plutôt utilisées pour vérifier les données saisies par l'utilisateur
  3. le test unitaire
    • pour tester automatique des entités uniques
    • @Test devant la méthode et utiliser assertEquals, assertTrue, assertNull de import static org.junit.Assert.*;
    • @Test(expected = ArithmeticException.class) (toujours le .class)
    • vérification probalisitique
    • "Le test peut être utilisé pour démontrer la présence de problèmes, mais jamais pour démontrer leur absence !" Dijkstra

Enumérations et classes imbriquées

  1. énumaration
    • facilite la comprehension
    • public enum Suit {SPADES, DIAMONDS, CLUBS, HEARTS};
    • Java transforme cela en classe
    • Suit.values() => {SPADES, DIAMONDS, CLUBS, HEARTS}
    • SPADES.ordinal() => 0
    • toString, compareTo, equals, hashCode
    • possible d'ajouter nos propres methodes
    • switch (toujours avec un cas default)
    • constructeur : private Suit(String frenchName) {this.frenchName = frenchName;}
    • variables au constructeur : public enum Suit {SPADES("piques");}
    • variables : public enum Suit {private final String frenchName;}
    • methode : public enum Suit {public String frenchName() {return frenchName;}}
    • class traduite toujours statique
  2. classes imbriquées statiques
    • public class LinkedIntStack{ private static class Node {}}
    • builder
    • accès aux variables statiques de la classe englobant (y compris les prives)
  3. annotations
    • toujours attachée à une déclaration (classe, interface, variable, methode, etc.)
    • peut avoir des paramètres entre parenthèse (voir test unitaire)
    • @Deprecated si la methode est destinee à ne plus être utilisée
    • @Override pour redéfinir une methode (à toujours utiliser)
    • @SuppressWarningssupprime les alertes du compilateur

Collections et généricité

  1. collections
    • structure de données abstraite
    • tableaux, listes, piles, queues, ensembles, tables associations, etc.
  2. généricité
    • permet à une classe de gérer plusieurs types sans redefinir les methodes à chaque fois
    • interface Stack<E> {public void addFirst(E value); avec le paramètre E
    • utilisation du diamant depuis Java 7 Stack<Character> s = new LinkedStack<>();
    • paramètres multiples possibles : public final class Pair<F, S>
    • les methodes peuvent aussi être génériques : static <E> Stack<E> newLinkedStack(E e)
    • des fois il faut spécifier les arguments de type au méthode générique : Stacks.<String>newLinkedStack("hello")
  3. généricité et types de base
    • boolean, byte, short, int, long, char, float, double impossible
    • Boolean, Character, Integer, Double emballage des types de base
    • emballage/deballage peut être automatique ou appellé via les methodes
  4. limitations de la généricité en Java
    • interdiction pour des raisons historiques
      • creation de tableau avec elements génériques
      • tests d'instance (instanceof) impliquant des types génériques
      • transtypages (casts) sur des types génériques ne sont pas sûr
      • définition d'exceptions génériques
  5. collections génériques de Java
    • pour chaque collection dans java.util. il existe une interface et des mises en oeuvres
    • Collection
      • List (ordonnée, taille variable)
        • LinkedList
        • ArrayList
      • Set (ensemble non ordonnée (l'ordre peut varier), pas de duplicata)
        • HashSet
        • TreeSet
    • Map (table associative, élàments indexés par des clefs d'un certain type)
      • TreeMap
      • HashMap

Mise en œuvre des collections : introduction

  1. listes
    • LinkedList
      • noeufs chainés entre-eux
      • un noeud de tête
      • accès séquentiel (doit connaître les noeuds précédents pour accéder à un élément)
      • peut être circulaire et doublement liée (prochain/précdent noeud)
      • ajout & suppression $O(1)$ / indexation $O(n)$ / taille $O(1)$
    • ArrayList
      • stocke les élements dans un tableau redimensionnable
      • copie le tableau quand redimensionné
      • ajout & suppression $O()$ / indexation $O(1)$ / taille $O(1)$
    • parcourir avec un for each : for (Node n : list) sinon le temps des listes chaînées est $O(n^2)$
    • intertion & suppression $O(n)$ / appartenance $On)$
  2. itérateur
    • permet de se déplacer sur une liste à l'aide d'un curseur
    • hasNext() vérifie s'il existe bel et bien un prochain
    • next() retourne l'élement et avance le curseur
    • remove() supprime l'élement précédent
    • Iterator<String> i = l.iterator(); while (i.hasNext()) { String s = i.next();}
  3. ensembles
    • HashSet
      • table de hachage
      • elements doivent être transformable en entier
      • fonction de hachage doit être le plus unique possible et doit toujours retourner la même valeur (hashCode)
      • si les elements hachés sont bien répartis, on profite de $O(1)$
      • ajout & suppression $O(1)$ / appartenance $O(1)$
    • TreeSet
      • arbre binaire
      • elements doivent être comparable
      • du plus petit ou plus grand
      • intertion & suppression $O(\log n)$ / appartenance $O(\log n)$
  4. equals & hashCode
    • doivent être compatible $x.equals(y)\Rightarrow x.hashCode()==y.hashCode()$ (pas forcément réciproque)
  5. interface Comparable
    • x.compareTo(y) retourne un entier
      • négatif si $x$ est strictement inférieur à $y$
      • 0 si égaux
      • positif si $x$ est strictement supérieur à $y$
    • compareTo et equals doivent être aussi compatible $x.equals(y) \iff x.compareTo(y)$
  6. tables associatives
    • même chose que pour les ensembles
    • itération sur les clés : set.keySet()
    • itération sur les valeurs : set.values()
    • itération sur les pairs : set.entrySet() (de type Entry, .getKey(), .getValue(), .setValue())

Mise en œuvre des listes

  • création
    • capcité initial définie ou dans le constructeur
  • redimensionnement
    • lorsque le tableau est plein, on en recrée un plus grand par copie
  • intertion/suppression
    • décaler les élements
    • ne pas oublier d'effacer les éléments décalés qui seraient à double
  • interface Iterable
    • besoin d'avoir la methode iterator() redéfinie
    • permet de rendre la classe itérable grâce à la boucle for each

Mise en œuvre des ensembles (I)

  • interface Set
    • boolean isEmpty();
    • int size();
    • void add(E elem);
    • void remove(E elem);
    • boolean contains(E elem);
    • Iterator<E> iterator();
  • ListSet
    • ajout oblige la verification de duplicata $O(n)$
    • suppression $O(n)$ et peut ne rien supprimer
    • appartenance $O(n)$ car simple parcourt de tous les elements
  • HashSet
    • l'efficacité dépend de la fonction de hachage
    • les elements se trouvent dans des listes determinées par le hachage
    • on essaie d'avoir des listes avec une moyenne proche de 1 par liste, c'est le facteur de charge
    • on peut rehacher pour avoir un meilleur facteur de hachage
  • classe imbriquée non statique
    • a accès à tous les membres de la classe englobante (y compris privés)
  • classe imbriquée anonyme
    • return new Iterator<E>() {private int remaining = size;};
    • constructeur new Iterator<E>() {{remaining = size;}};
    • a accès aux variables locales si elles sont déclarés finales

Mise en oeuvre des tables associatives

  • tables associatives
    • listes associatives ListMap
      • paires clef/valeur appelées entries
        • méthode pratique entryFor car souvent parcourt $O(n)$
          • ajout vérifie l'existence et remplace, ou ajoute
          • remove si trouvé
          • get si trouvé
      • tables de hachage HashMap
      • arbre binaires de recherche `TreeMap
      • iterable seulement sur les entry, clef ou valeur
      • incompatibilité encore Entry et Map.Entry

Patrons de conception : Iterator, Builder, fabriques

  • patrons de conception : solutions à des problèmes généraux
  • nom, description du problème résolu, description de la solution et des conséquences de l'utilisation
  • diagramme de classe
    • héritage : flèche grasse
    • association (utilisation) : flèche fine
    • instanciation (crée) : flèche traitillée
  • Iterator ou Cursor
    • problème : exposer la representation interne sans violé les principes de l'encapsulation
    • solution : méthode permettant d'obtenir un objet d'une collection et d'avancer vers un suivant
  • Builder
    • problème : creation d'objet immuables, pas facile d'avoir un gros constructeur
    • solution : proposer une classe qui construit un objet
    • cela permet le contrôle des données et la mise en place de caractéristiques automatiques
  • Factory Method
    • problème : permettre l'extension en créant des sous-classes n'assure pas que la sous-classe soit utilisé par le programme
    • solution : une méthode fabrique qui regroupe la construction de l'objet
  • Abstract Factory
    • même chose mais regroupe les méthodes fabriques dans une classe externe et abstraite

Patrons : Adapter, Observer, MVC

  • Adapter
    • problème : rendre compatible des méthodes pour d'autres structures de données
    • solution : écrire une classe qui adapte les données et qui sert interface d'adaptation
  • Observer :
    • problème : mettre à jour une donnée basé sur une autre classe/instance
    • solution : permettre d'observer et d'être informé entre les classes (observer et subject)
    • attention aux cycles de dépendances et glitches
  • MVC
    • problème : séparer et classer les bouts de code
    • solution : découper le code entre trois partie (modèle, vue, contrôleur)

Patrons : Strategy, Decorator, Composite

  • Strategy ou Policy
    • problème : spécifier une action en fonction de la variable d'entrée (tri, comment trier ?)
    • solution : permettre la spécification d'un objet s'appliquant sur les variables d'entrées (comparateur)
  • Decorator ou Wrapper
    • problème : comment modifier à la volée l'effet d'une méthode
    • solution : appliquer une transformation (autre méthode) au résultat de la méthode (comparateur inverse) principe de l'emballage
  • flots java symbolisé par le paquetage java.io
    • accès séquentiel
    • input vs output streams
    • flots de caractères : Reader et Writer
    • flots d'octets : InputStream et OutputStream
    • possibilité de décorer ces flots (compression, cryptage, tampon)
  • Composite
    • problème : comment représenter les ordres composés de plusieurs critères
    • solution : définir un macro-comparateur et une hiérarchie des comparaisons
  • arisé des méthodes
    • ìnt sum(int... vs)` permet la génération d'un tableau avec le nombre d'élément donné
    • on peut avec des arguments obligatoires (spécification avant les ...)

Héritage et modifiabilité

  • héritage
    • mal utilisé
    • compter le nombre d'éléments ajouter : la résolution dynamique des liens empêche une solution sur si on utilise l'héritage
    • on a meilleur temps de décorer l'ensemble et est hérité dans une autre classe qui redéfini les méthodes d'ajouts
    • classe instanciable ne sont pas fait pour être hérité, on les mets final
    • classe héritable est une classe dont le rôle est de servir de super-classe
  • modifiabilité
    • classe muable ne sont pas faites pour être stocké (hashcode) et modifiée dans des collections
    • avantage aux classes immuables (sinon il faut redéfinir clone, etc.)
    • Les instances d'une classe non modifiable doivent être comparées structurellement, celles d'une classe modifiable doivent l'être par identité
    • désavantage de la mutabilité face à la concurrence, pas facile de raisonner correctement
    • par défaut immuable
      • final à tous les champs
      • pas de setters
      • pas de getters modifiable
      • copie profonde
    • collections peuvent être non modifiable
      • coûteux, mais pas tant, en effet, elles peuvent partager les noeuds car elles sont non modifiables
      • permet les systèmes de version facilement

Généricité avancée, gestion mémoire

  • sous-typage
    • réflexif (sous-type de lui-même), transitif (sous-type est sous-type d'un sous-type de parent) et anti-symétrique (sous-type entre eux = même objet)
    • ordre partiel
    • polymorphisme d'inclusion est le principe de substitution de type
  • généricité
    • valide d'ajouter un sous-type à une collection générique cas par cas
    • impossible d'ajouter en bloc une collection car un instanciation d'un type générique n'est jamais un sous-type
    • possible de définir addall quand même en rendant la méthode générique et bornée
    • jokers (wildcards) : pas besoin de nommer une généricité si elle est utilisée qu'une seule fois, on peut mettre un joker ?
    • borne inférieur <? super E> uniquement pour les jokers
    • lois des bornes PECS (Producer Extends, Consumer Super)
      • quand on lit dans une structure, on utilise une borne supérieure (extends)
      • quand on écrit dans une structure, on utilise une borne inférieure (super)
      • quand on fait les deux, pas de borne
    • types brutes jamais sauf vieille collection ou List était valide avant la généricité
  • gestion mémoire
  • ramasse miettre
    • ne pas oublier de mettre à null en cas de remove