Examen final : corrigé

La classe Linear est similaire aux générateurs d'images du mini-projet images continues. Elle est paramétrisée par les valeurs de a et b et sa méthode valueAt est une simple traduction en Java de la formule mathématique de l'énoncé.

public final class Linear implements FunctionRR {
    private final double a, b;

    public Linear(double a, double b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public double valueAt(double x) {
        return a * x + b;
    }
}

La classe Derivative est similaire aux transformateurs d'images dans le projet images continues. Là aussi l'idée est de « modifier » une fonction existante, en l'occurence en calculant sa dérivée au moyen de la formule donnée dans l'énoncé.

public final class Derivative implements FunctionRR {
    private final FunctionRR f;
    private final double delta;

    public Derivative(FunctionRR f, double delta) {
        this.f = f;
        this.delta = delta;
    }

    @Override
    public double valueAt(double x) {
        return (f.valueAt(x + delta) - f.valueAt(x - delta))
            / (2.0 * delta);
    }
}

La classe Composition est quant à elle similaire aux « composeurs » d'images du mini-projet images continues. Là aussi l'idée est de composer deux fonctions existantes pour en obtenir une nouvelle.

public final class Composition implements FunctionRR {
    private final FunctionRR f1, f2;

    public Composition(FunctionRR f1, FunctionRR f2) {
        this.f1 = f1;
        this.f2 = f2;
    }

    @Override
    public double valueAt(double x) {
        return f1.valueAt(f2.valueAt(x));
    }
}

La classe Derivative utilise bien entendu le patron Decorator tandis que Composition utilise le patron Composite.

La classe InterpolatedFunction doit mémoriser les deux tableaux passés à son constructeur et décrivant les points connus. Pour ce faire, elle contient deux champs nommés xs et ys ci-dessous.

public final class InterpolatedFunction implements FunctionRR {
    private final double[] xs, ys;

    // ... constructeur et méthodes
}

Le constructeur doit commencer par vérifier la validité des tableaux reçus puis en stocker une copie dans ces champs, afin de garantir l'immuabilité de la classe. Pour vérifier que le premier tableau est trié et sans doublon, il suffit de vérifier que chacun de ses éléments est strictement inférieur à son successeur.

public final class InterpolatedFunction implements FunctionRR {
    private final double[] xs, ys;

    public InterpolatedFunction(double[] xs, double[] ys) {
        if (xs.length != ys.length)
            throw new IllegalArgumentException();
        if (xs.length == 0)
            throw new IllegalArgumentException();
        for (int i = 1; i < xs.length; ++i) {
            if (! (xs[i - 1] < xs[i]))
                throw new IllegalArgumentException();
        }

        this.xs = Arrays.copyOf(xs, xs.length);
        this.ys = Arrays.copyOf(ys, ys.length);
    }

    // ... méthode valueAt
}

Le premier tableau étant trié, la méthode valueAt peut y faire une recherche dichotomique (au moyen de la méthode binarySearch) afin de calculer son résultat. Elle peut ensuite distinguer quatre cas :

1. le point reçu fait partie des points connus, auquel cas on retourne son image connue sans faire de calcul,
2. le point reçu est inférieur au plus petit point connu, auquel cas on retourne l'image du plus petit point,
3. le point reçu est supérieur au plus grand point connu, auquel cas on retourne l'image du plus grand point,
4. le point reçu est entre deux points connus, auquel cas on doit interpoler linéairement.

Dans le premier cas, la fonction binarySearch retourne une valeur positive, dans les autres cas elle retourne une valeur négative qu'il convient d'adapter pour obtenir la position d'insertion. Au moyen de cette dernière, il est facile de distinguer les trois derniers cas.

public final class InterpolatedFunction implements FunctionRR {
    private final double[] xs, ys;

    // ... constructeur

    @Override
    public double valueAt(double x) {
        int p = Arrays.binarySearch(xs, x);
        if (p >= 0)
            return ys[p];
        else {
            int i = -(p + 1);
            if (i == 0)
                return ys[0];
            else if (i == xs.length)
                return ys[ys.length - 1];
            else {
                assert 0 < i && i < xs.length;
                double dx = xs[i] - xs[i - 1];
                double dy = ys[i] - ys[i - 1];
                return ys[i - 1] + (x - xs[i - 1]) / dx * dy;
            }
        }
    }
}

Bien entendu, il est aussi possible de faire une simple recherche linéaire dans le tableau xs plutôt qu'une recherche dichotomique.

Le bâtisseur doit stocker les paires \((x, f(x))\) ajoutés via addPair, et pour ce faire une table associative est un bon choix, pour deux raisons :

1. la méthode put remplace l'éventuelle association existante pour la clef reçue par la nouvelle, ce qui est le comportement demandé,
2. en utilisant une table associative de type TreeMap, les éléments sont triés par ordre croissant de clef, ce qui est exactement ce qu'exige le constructeur de InterpolatedFunction écrit ci-dessus.

Le bâtisseur se contente donc de stocker les paires passées à addPair dans une table associative en utilisant x comme clef et y (c-à-d f(x)) comme valeur. Dans la méthode build, les éléments de cette table associative sont parcourus afin de créer les tableaux à passer au constructeur de InterpolatedFunction, qui est finalement appelé.

public static final class Builder {
    private Map<Double, Double> points = new TreeMap<>();

    public void addPair(double x, double y) {
        points.put(x, y);
    }

    public InterpolatedFunction build() {
        double[] xs = new double[points.size()];
        double[] ys = new double[points.size()];
        int i = 0;
        for (double x: points.keySet()) {
            xs[i] = x;
            ys[i] = points.get(x);
            i++;
        }
        return new InterpolatedFunction(xs, ys);
    }
}

On pourrait utiliser le patron Strategy pour paramétrer la classe InterpolatedFunction avec une technique d'interpolation.

Le but étant de permettre de voir des éléments d'un premier type (ici « tableau de E ») comme des éléments d'un second type (ici « table associative d'entiers vers E »), il faut utiliser le patron Adapter.

La classe ArrayToMap doit bien entendu être générique pour pouvoir adapter des tableaux de n'importe quel type. A l'exception de iterator, les méthodes s'écrivent en une simple ligne :

public final class ArrayToMap<E> implements Map<Integer, E> {
    private final E[] array;

    public ArrayToMap(E[] array) {
        this.array = array;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public int size() {
        return array.length;
    }

    @Override
    public E get(Integer key) {
        return containsKey(key) ? array[key] : null;
    }

    @Override
    public boolean containsKey(Integer key) {
        return 0 <= key && key < array.length;
    }

    // ... iterator (voir plus bas)
}

A première vue, l'itérateur ne paraît pas très difficile à écrire : il suffit qu'il stocke l'index du prochain élément à retourner, qui parcourt le tableau, et le tour est joué. Malheureusement, ce n'est pas aussi simple que cela, étant donné que sa méthode next doit produire des instances d'une classe implémentant l'interface Map.Entry<Integer, E>…

Pour ce faire, le plus simple consiste à retourner, dans la méthode next, une instance d'une classe anonyme implémentant l'interface Map.Entry. Etant donné que l'itérateur lui-même se définit naturellement avec une classe anonyme, on se retrouve avec deux classes anonymes imbriquées, mais cela ne pose pas de problème particulier.

public final class ArrayToMap<E> implements Map<Integer, E> {
    private final E[] array;

    // ... autres méthode (voir ci-dessus)

    @Override
    public Iterator<Map.Entry<Integer, E>> iterator() {
        return new Iterator<Map.Entry<Integer,E>>() {
            int nextIndex = 0;

            @Override
            public boolean hasNext() {
                return nextIndex < array.length;
            }

            @Override
            public Map.Entry<Integer, E> next() {
                return new Map.Entry<Integer, E>() {
                    private final int key = nextIndex++;

                    @Override
                    public Integer key() {
                        return key;
                    }

                    @Override
                    public E value() {
                        return array[key];
                    }
                };
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}

A noter que le nœud G est inatteignable, donc son heure de première arrivée reste à sa valeur initiale infinie (∞).

Pour dessiner l'arbre des trajets les plus rapides, il suffit de consulter la table construite ci-dessus. Le prédécesseur d'un nœud est simplement le nœud visité lors de l'itération précédant la dernière mise à jour de l'heure de première arrivée du nœud. Par exemple, l'heure de première arrivée au nœud E a été mise à jour pour la dernière fois à l'itération 6, donc son prédécesseur est le nœud visité lors de l'itération précédente, D.

Le nœud G étant inatteignable, il ne fait pas partie de l'arbre des trajets les plus rapides.

Etant donné que la tuile peut être traversée d'un côté à l'autre en 40 minutes et est découpée en 8, chaque carré quadrillé représente 5 minutes de marche. Le rayon de chaque cercle à dessiner se calcule simplement en soustrayant de 15 minutes le temps nécessaire pour arriver à l'arrêt concerné en partant à 12h05 de l'arrêt A. Par exemple, il faut 10 minutes pour arriver à l'arrêt C, il reste alors 5 minutes de marche, donc le cercle associé à cet arrêt a un rayon de 1 unité.

Non, cette optimisation n'est pas correcte car il est possible que des arrêts soient en dehors d'une tuile mais qu'ils permettent néanmoins d'atteindre, à pied, certains de ses points. Par exemple, si l'arrêt A était déplacé de deux unités sur la gauche, il sortirait de la tuile mais son cercle recouvrirait toujours une partie de celle-ci.