Examen intermédiaire 2006 - corrigé

Méthode hashCode (Note: on peut utiliser n'importe quelle fonction qui combine les lettres sans dépendre de leur ordre) :

@Override
public int hashCode() {
    int hash = 0;
    for (int i = 0; i < word.length(); ++i)
        hash += code(word.charAt(i));
    return hash;
}

Méthode equals :

@Override
public boolean equals(Object that) {
    return (that instanceof Word) && ((Word)that).word.equals(word);
}

Oui.

Justification : les méthodes hashCode et equals sont compatibles au sens de Java si et seulement si

pour tout x, y, on a x.equals(y) => x.hashCode() == y.hashCode()

D'après la définition de la méthode equals ci-dessus, il est clair que deux mots ne sont égaux que s'ils sont composés des mêmes lettres dans le même ordre. Appelons ces lettres l1, …, ln. Les deux mots x et y sont donc :

x = l1 l2 ... ln
y = l1 l2 ... ln

La méthode hashCode calcule la valeur de hachage en sommant les codes de chacune des lettres. Les valeurs de hachage de x et y sont donc :

x.hashCode() = code(l1) + code(l2) + ... + code(ln)
y.hashCode() = code(l1) + code(l2) + ... + code(ln)

Il est ainsi évident que x.equals(y) => x.hashCode() == y.hashCode().

On ajoute un champ contenant l'histogramme du mot :

private final int[] histogram;

que l'on initialise dans le constructeur :

public Word(String word) {
    this.word = word;
    this.histogram = new int[26];
    for (int i = 0; i < word.length(); ++i)
        histogram[code(word.charAt(i))]++;
}

et finalement on compare les histogrammes dans la méthode isAnagramOf (il ne faut pas oublier de tester que les deux mots ne sont pas égaux, car comme dit dans l'énoncé, un mot ne doit pas être considéré comme une anagramme de lui-même) :

private boolean histogramEquals(int[] h1, int[] h2) {
    for (int i = 0; i < h1.length; ++i)
        if (h1[i] != h2[i])
            return false;
    return true;
}

public boolean isAnagramOf(Word that) {
    return !this.equals(that)
        && histogramEquals(this.histogram, that.histogram);
}

Note : on peut également imaginer une solution basée sur le tri des lettres. L'idée est de créer une chaîne comportant les mêmes lettres que le mot, et de les trier par ordre alphabétique. Ensuite, pour voir si deux mots sont anagrammes, on compare ces chaînes triées.

On ajoute la méthode suivante à la classe IntSet :

public Iterator<Integer> iterator() {
    return new IntSetIterator(intervals);
}

et on définit la classe IntSetIterator de la manière suivante :

public class IntSetIterator implements Iterator<Integer> {
    private final Iterator<Interval> intervalsIt;

    // Invariant: if currInterval is non-null, then 
    // nextInteger is the next iteration integer; if
    // currInterval is null, nextInteger can be anything.
    private Interval currInterval = null;
    private int nextInteger = 0;

    public IntSetIterator(List<Interval> intervals) {
        this.intervalsIt = intervals.iterator();
    }

    public boolean hasNext() {
        return currInterval != null || intervalsIt.hasNext();
    }

    public Integer next() {
        if (!hasNext())
            throw new NoSuchElementException();
        if (currInterval == null) {
            currInterval = intervalsIt.next();
            nextInteger = currInterval.begin;
        }
        int integer = nextInteger++;
        if (nextInteger > currInterval.end)
            currInterval = null;
        return integer;
    }

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

Il suffit de déclarer que la classe IntSet implémente l'interface Iterable, ainsi :

public class IntSet implements Iterable<Integer> {
  ...
}

                                      +---+
                                      | 7 |
                                      +---+
                                     /     \
                                +---+       o
                                | 6 |
                                +---+
                               /     \
                          +---+       o
                          | 5 |
                          +---+
                         /     \
                    +---+       o
                    | 4 |
                    +---+
                   /     \
              +---+       o
              | 3 |
              +---+
             /     \
        +---+       o
        | 2 |
        +---+
       /     \
  +---+       o
  | 1 |
  +---+
 /     \
o       o

Il est totalment déséquilibré : il a dégénéré en liste chaînée, ce qui implique que les opérations comme la recherche, l'insertion, etc. se feront avec une complexité en O(n).

L'idée est de procéder par dichotomie : on ajoute pour commencer l'élément qui est au milieu du tableau, qui se trouvera à la racine ; ensuite, on ajoute récursivement les deux sous-tableaux gauche et droite.

Pour ce faire, on utilise une méthode auxilliaire addAllSorted qui prend trois arguments, et on l'utilise pour définir la méthode principale.

public void addAllSorted(E[] sortedNewElements) {
    addAllSorted(sortedNewElements, 0, sortedNewElements.length - 1);
}

private void addAllSorted(E[] newElems, int f, int l) {
    if (f <= l) {
        int m = (f + l) / 2;
        add(newElems[m]);
        addAllSorted(newElems, f, m - 1);
        addAllSorted(newElems, m + 1, l);
    }
}