Examen final : corrigé

1 Nombres avec unité

Notez que cet exercice était très similaire à celui sur les polynômes de l'examen intermédiaire.

1.1 Partie 1

Le fait que la classe soit instanciable implique qu'elle soit finale. L'attribut contenant l'unité doit avoir le type Map<String, Integer> puisqu'il s'agit, comme le dit l'énoncé, d'une table associant à chaque nom d'unité (une chaîne de type String) l'exposant correspondant (un entier de type Integer). 

public final class DoubleU {
    private double value;
    private Map<String, Integer> unit;

    // … constructeurs et méthodes
}

1.2 Partie 2

Seul le premier constructeur n'est pas totalement trivial à écrire. Il doit bien entendu dupliquer la table représentant l'unité pour garantir l'immuabilité de la classe. Ce faisant, il ignore les exposants nuls comme demandé, ce qui garantit qu'un nombre avec unité donné a une unique représentation et simplifie beaucoup le reste de la classe.

Notez que la classe TreeMap est utilisée pour stocker l'unité, ce qui simplifie l'écriture de la méthode toString, puisque les composants de l'unité doivent y apparaître triés par nom.

Les deux autres constructeurs font simplement appel au premier en lui passant les tables d'unité leur correspondant. 

public DoubleU(double value, Map<String, Integer> unit) {
    Map<String, Integer> clonedUnit = new TreeMap<>();
    for (Map.Entry<String, Integer> u: unit.entrySet()) {
        if (u.getValue() != 0)
            clonedUnit.put(u.getKey(), u.getValue());
    }

    this.value = value;
    this.unit = Collections.unmodifiableMap(clonedUnit);
}

public DoubleU(double value, String unit) {
    this(value, Collections.singletonMap(unit, 1));
}

public DoubleU(double value) {
    this(value, Collections.emptyMap());
}

1.3 Partie 3

L'addition de deux nombres à unité n'est valide que lorsque les unités des deux nombres sont identiques, comme expliqué dans l'énoncé. Cette comparaison peut se faire simplement au moyen de la méthode equals appliquée aux tables représentant les unités, étant donné d'une part que les tables associatives sont comparées de manière structurelle, et d'autre part qu'à une unité correspond exactement une table puisqu'on a pris soin de supprimer les exposants nuls. 

public DoubleU add(DoubleU that) {
    if (! unit.equals(that.unit))
        throw new IllegalArgumentException();
    return new DoubleU(value + that.value, unit);
}

1.4 Partie 4

La multiplication de deux nombres à unité est un peu plus compliquée que l'addition, puisqu'il faut calculer l'unité du résultat, ce qui implique d'additionner les exposants des deux unités. 

public DoubleU multiply(DoubleU that) {
    Map<String, Integer> u = new HashMap<>(that.unit);
    for (Map.Entry<String, Integer> e: unit.entrySet()) {
        int f = e.getValue() + u.getOrDefault(e.getKey(), 0);
        u.put(e.getKey(), f);
    }
    return new DoubleU(value * that.value, u);
}

1.5 Partie 5

Etant donné que les tables associatives de la bibliothèque Java sont comparées de manière structurelle, on peut directement utiliser la méthode equals pour comparer les tables d'unités, et la méthode hash de Objects pour calculer la valeur de hachage. 

@Override
public boolean equals(Object thatO) {
    if (thatO instanceof DoubleU) {
        DoubleU that = (DoubleU)thatO;
        return value == that.value && unit.equals(that.unit);
    } else
        return false;
}

@Override
public int hashCode() {
    return Objects.hash(value, unit);
}

1.6 Partie 6

La méthode toString ne pose pas de problème particulier, il faut simplement penser à ne pas inclure l'exposant 1 comme demandé dans l'énoncé. Etant donné que l'unité est stockée dans une table de type TreeMap, ses composants sont automatiquement triés par ordre alphabétique. 

@Override
public String toString() {
    StringBuilder b =
        new StringBuilder(Double.toString(value));
    for (Map.Entry<String, Integer> e: unit.entrySet()) {
        b.append(" ");
        b.append(e.getKey());
        if (e.getValue() != 1) {
            b.append("^");
            b.append(e.getValue());
        }
    }
    return b.toString();
}

2 Ensembles d'entiers

La principale difficulté de cet exercice était de savoir comment calculer, étant donné un élément de l'ensemble, l'index de l'entier long du tableau contenant le bit le représentant, et l'index de ce bit dans cet entier.

Cela peut se faire bien entendu au moyen de la division entière et de son reste. Ainsi, l'élément \(i\) de l'ensemble est représenté par le bit \(b\) de l'entier \(l\), où \(l\) et \(b\) sont donnés par :

\begin{align} \newcommand{\bdiv}{\mathop{\rm div}\nolimits}\newcommand{\bmod}{\mathop{\rm mod}\nolimits} l &= (i - \mathrm{min}) \bdiv 64\\ b &= (i - \mathrm{min}) \bmod 64 \end{align}

\(\mathrm{min}\) étant la borne inférieure de l'intervalle des éléments potentiels.

Notez que le code ci-dessous n'utilise pas directement la valeur 64 mais la constante SIZE qui contient cette valeur. Cette constante a été importée statiquement depuis la classe Long.

2.1 Partie 1

Etant donné que les bornes min et max sont inclusives, le nombre d'éléments potentiels est donné par min - max + 1. Si cette valeur est négative, une exception est levée, comme demandé. Sinon, un tableau d'entiers suffisamment grand est alloué. Sa taille est égale au plus petit entier supérieur ou égal à la longueur divisée par 64. Cette taille peut soit se calculer au moyen de la division puis de la méthode ceil, soit en ajoutant 64 - 1 à la longueur et en faisant une division entière, solution retenue ici. 

public DenseIntSet(int min, int max) {
    int len = max - min + 1;
    if (len < 0)
        throw new IllegalArgumentException();

    this.min = min;
    this.max = max;
    this.bits = new long[(len + SIZE - 1) / SIZE];
    this.size = 0;
}

2.2 Partie 2

L'ajout d'un élément consiste à mettre à 1 le bit \(b\) de l'entier d'index \(l\), où \(l\) et \(b\) sont calculés selon les formules données plus haut. Pour mettre ce bit à 1, on utilise simplement la technique donnée dans le cours, consistant à produire un masque dans lequel seul ce bit est à 1, puis à faire un « ou » bit à bit entre ce masque et l'entier.

Cela fait, il reste à savoir comment mettre la taille à jour. La solution retenue ici consiste à voir si l'entier contenant le bit correspondant à l'élément a changé, et si oui, incrémenter la taille. 

public void add(Integer i) {
    if (! (min <= i && i <= max))
        throw new IllegalArgumentException();

    int il = (i - min) / SIZE, ib = (i - min) % SIZE;
    long l = bits[il];
    bits[il] |= 1l << ib;
    if (bits[il] != l)
        ++size;
}

2.3 Partie 3

La suppression d'un élément est très similaire à l'ajout, à deux petites différences près :

  1. le bit \(b\) de l'entier d'index \(l\) doit être mis à zéro, ce qui se fait toujours selon la technique donnée au cours,
  2. la taille doit être décrémentée plutôt qu'incrémentée en cas de changement.
public void remove(Integer i) {
    if (! (min <= i && i <= max))
        throw new IllegalArgumentException();

    int il = (i - min) / SIZE, ib = (i - min) % SIZE;
    long l = bits[il];
    bits[il] &= ~(1l << ib);
    if (bits[il] != l)
        --size;
}

2.4 Partie 4

Le test d'appartenance est également très similaire aux autres opérations, mais il faut ici tester si le bit \(b\) de l'entier d'indice \(l\) est à 1, ce qui se fait encore une fois en suivant le cours. 

public boolean contains(Integer i) {
    if (! (min <= i && i <= max))
        throw new IllegalArgumentException();

    int il = (i - min) / SIZE, ib = (i - min) % SIZE;
    return ((bits[il] >> ib) & 1) == 1;
}

3 Transformation OSM en géométrie

Les deux relations de type multipolygon \(R_1\) et \(R_2\) produisent chacune un polygone attribué, étant donné qu'elles sont complètes. De plus, le chemin \(W_5\) étant fermé, il produit lui aussi un polygone. Les trois polygones suivants sont donc produits par la transformation :

Enveloppe Trous Attributs
\((P_1,P_2,P_3,P_4)\) \((P_5,P_6,P_7,P_8), (P_9,P_{10},P_{11},P_{12})\) building=yes
\((P_5, P_6, P_7, P_8)\) \((P_{13},P_{14},P_{15},P_{16})\) natural=grass
\((P_{13},P_{14},P_{15},P_{16})\) — natural=water

Notez en particulier que ni \(W_6\) ni \(W_7\) ne produisent de polygone, étant donné que ce sont deux chemins ouverts.

4 Ensembles vérifiants

4.1 Partie 1

La classe CheckingSet doit bien entendu définir la totalité des méthodes de l'interface SimpleSet qu'elle implémente. De plus, chacune de ces méthodes appelle la méthode correspondante de l'ensemble vérifié, avec le même paramètre (s'il y en a un) et retourne la même valeur que celle retournée par la méthode de l'ensemble vérifié.

En plus de cela, les vérifications mentionnées dans l'énoncé sont faites dans les méthodes size, add et remove. 

public final class CheckingSet<E> implements SimpleSet<E> {
    private final SimpleSet<E> s;

    public CheckingSet(SimpleSet<E> s) {
        this.s = s;
    }

    @Override
    public int size() {
        int r = s.size();
        check(r >= 0);
        return r;
    }

    @Override
    public void add(E e) {
        boolean containedBefore = s.contains(e);
        int sizeBefore = s.size();
        s.add(e);
        int sizeDelta = s.size() - sizeBefore;
        check(s.contains(e));
        check(sizeDelta == (containedBefore ? 0 : 1));
    }

    @Override
    public void remove(E e) {
        boolean containedBefore = s.contains(e);
        int sizeBefore = s.size();
        s.remove(e);
        int sizeDelta = s.size() - sizeBefore;
        check(!s.contains(e));
        check(sizeDelta == (containedBefore ? -1 : 0));
    }

    @Override
    public boolean contains(E e) {
        return s.contains(e);
    }

    private void check(boolean b) {
        if (! b)
            throw new UnsatisfiedCondition();
    }
}

4.2 Partie 2

Il s'agit du patron Decorator.

5 Encodage Base32

Cet exercice était très similaire à la série 7, étant donné que la classe Base32OutputStream est presque identique à la classe BitsOutputStream, à deux différences près :

  1. le flot sous-jacent de BitsOutputStream est ici un écrivain (ce qui implique que le patron utilisé est Adapter et pas Decorator),
  2. Base32OutputStream reçoit toujours 8 bits à la fois, pas un nombre variable, et doit écrire ces bits par paquets de 5, pas de 8, dans l'écrivain sous-jacent.

Ces deux différences n'impliquant que des changements minimes à la classe BitsOutputStream, le code ci-dessous n'est pas décrit en détail. Pour le comprendre, il est conseillé de se référer au corrigé de la série 7.

5.1 Partie 1

public final class Base32OutputStream extends OutputStream {
    private Writer writer;
    private int waitingBits, waitingBitsCount;

    public Base32OutputStream(Writer writer) {
        this.writer = writer;
        this.waitingBits = 0;
        this.waitingBitsCount = 0;
    }

    @Override
    public void write(int b) throws IOException {
        waitingBits = (waitingBits << 8) | (b & 0xFF);
        waitingBitsCount += 8;
        while (waitingBitsCount >= 5) {
            waitingBitsCount -= 5;
            int nextBits =
                (waitingBits >> waitingBitsCount) & 0b11111;
            writer.append(alphabet.charAt(nextBits));
        }
    }

    @Override
    public void close() throws IOException {
        if (waitingBitsCount > 0) {
            int paddedBits =
                (waitingBits << (5 - waitingBitsCount))
                & 0b11111;
            writer.append(alphabet.charAt(paddedBits));
            waitingBitsCount = 0;
        }
        writer.close();
    }
}

6 Peintre

Le dessin des données ne pose pas de problème particulier si l'on se rend compte que :

  1. la polyligne attribuée highway=secondary ne produit aucun dessin car aucun filtre ne la retient,
  2. les routes (étiquetées highway) sont dessinées par dessus les voies de chemin de fer (étiquetées railway), mais l'utilisation de la méthode layered implique que la voie de chemin de fer portant l'étiquette layer=1 est dessinée au-dessus du reste des données.

Ces constatations faite, il reste à faire le dessin en prenant garde à bien placer les lignes sur la toile et à les dimensionner correctement. On obtient l'image ci-dessous :

Sorry, your browser does not support SVG.