Ensemble par hachage préservant l'ordre

Le code du corrigé est disponible dans une archive Zip. Les solutions aux différents exercices sont brièvement discutées ci-dessous.

Les attributs de la classe SOrderPreservingSet1 sont ceux présentés à la figure 2 de l'énoncé, ou presque, puisque la taille n'a pas besoin d'être mémorisée explicitement. En effet, dans cette première version, la taille de l'ensemble est égale à la taille du tableau contenant les éléments.

Dès lors, la méthode size n'a rien d'autre à faire que retourner la taille du tableau elements :

public int size() {
  return elements.size();
}

Pour ajouter un élément à l'ensemble, il faut parcourir l'amas correspondant à l'élément à ajouter, depuis son index (tI dans le code plus bas). Si, lors de ce parcours, on rencontre un élément égal à celui à ajouter, alors l'élément est déjà dans l'ensemble, et il n'y a rien à faire. Par contre, si on atteint la fin de l'amas, alors on ajoute l'élément au tableau des éléments, et place son index dans le premier emplacement libre après l'amas.

public void add(E e) {
  int tI = table.indexFor(requireNonNull(e));
  for (; table.isNonEmpty(tI); tI += 1) {
    if (elements.get(table.get(tI)).equals(e))
      return;
  }
  table.set(tI, elements.size());
  elements.add(e);
}

Comme on le constate, le parcours de cette portion d'amas est très similaire au parcours de la liste à laquelle appartient l'élément dans la classe SHashSet du cours.

Pour déterminer si un élément appartient à l'ensemble, il faut faire la même chose que pour ajouter un élément, si ce n'est qu'aucune modification n'est à apporter à l'ensemble.

public boolean contains(E e) {
  for (int tI = table.indexFor(requireNonNull(e));
       table.isNonEmpty(tI);
       tI += 1) {
    if (elements.get(table.get(tI)).equals(e))
      return true;
  }
  return false;
}

Finalement, pour créer un itérateur permettant de parcourir les éléments, il suffit d'en créer un sur une vue non modifiable sur le tableau les contenant :

public Iterator<E> iterator() {
  return Collections.unmodifiableList(elements).iterator();
}

Le redimensionnement de la table se fait de manière assez similaire à ce qui est fait dans la classe SHashSet du cours, c.-à-d. que le contenu de l'ensemble est parcouru — dans l'ordre d'insertion — et ses éléments ajoutés l'un après l'autre à une table nouvellement créée et destinée à remplacer la précédente.

On notera que lors de cette réinsertion, il faut connaître l'index de chacun des éléments, puisque c'est ce qui est stocké dans la table. Il aurait bien entendu été possible de le stocker dans une variable incrémentée à chaque insertion, mais une autre solution consiste à utiliser un itérateur de type ListIterator pour parcourir les éléments, qui offre la méthode previousIndex pour connaître l'index du dernier élément retourné par next. C'est la solution que nous avons choisi d'utiliser ci-dessous.

private void rehashIfNeeded() {
  int idealLogCapacity = Table.idealLogCapacity(size());
  if (table.logCapacity() >= idealLogCapacity) return;

  Table<E> newTable = Table.ofLogCapacity(idealLogCapacity);

  ListIterator<E> elementsIt = elements.listIterator();
  while (elementsIt.hasNext()) {
    int tI = newTable.indexFor(elementsIt.next());
    while (newTable.isNonEmpty(tI)) tI += 1;
    newTable.set(tI, elementsIt.previousIndex());
  }

  table = newTable;
}

Comme le dit l'énoncé, la suppression affecte la totalité des opérations, ainsi que les attributs, en tout cas si on la met en œuvre au moyen de la technique proposée, basée sur les « pierres tombales ».

La première chose à faire pour gérer la suppression est d'ajouter un attribut pour mémoriser la taille de l'ensemble, puisque celle-ci n'est plus égale à celle du tableau contenant les éléments — qui pourra désormais contenir des valeurs nulles lors de suppression d'éléments. La méthode size doit être adaptée en fonction :

private int size = 0;

public int size() {
  return size;
}

La méthode add doit être modifiée pour ignorer les pierres tombales lors du parcours de l'amas. Cette modification est la seule qui soit obligatoire, mais il est avantageux d'en faire une autre, qui consiste à remplacer la première pierre tombale de l'amas par la valeur à ajouter. Pour ce faire, notre version de add mémorise la position de cette pierre tombale dans la variable firstDeleted.

public void add(E e) {
  int tI = table.indexFor(requireNonNull(e));
  int firstDeleted = Integer.MAX_VALUE;
  for (; table.isNonEmpty(tI); tI += 1) {
    int eI = table.get(tI);
    if (eI == Table.SLOT_DELETED)
      firstDeleted = Math.min(firstDeleted, tI);
    else if (elements.get(eI).equals(e))
      return;
  }

  table.set(Math.min(firstDeleted, tI), elements.size());
  elements.add(e);
  size += 1;
  rehashIfNeeded();
}

La méthode contains doit elle aussi être adaptée pour ignorer les pierres tombales.

public boolean contains(E e) {
  for (int tI = table.indexFor(requireNonNull(e));
       table.isNonEmpty(tI);
       tI += 1) {
    int eI = table.get(tI);
    if (eI != Table.SLOT_DELETED
	&& elements.get(eI).equals(e))
      return true;
  }
  return false;
}

La méthode remove doit parcourir l'amas contenant l'élément à supprimer de la même manière que add et contains. Dès que cet élément est trouvé, il est supprimé en :

• le remplaçant par null dans le tableau des éléments,
• remplaçant son index dans la table par une pierre tombale — si cet index se trouve au milieu de l'amas — ou en le libérant — si cet index se trouve à la fin de l'amas.

Cela fait, la taille de l'ensemble peut être diminuée d'une unité.

public void remove(E e) {
  for (int tI = table.indexFor(requireNonNull(e));
       table.isNonEmpty(tI);
       tI += 1) {
    int eI = table.get(tI);
    if (eI != Table.SLOT_DELETED
	&& elements.get(eI).equals(e)) {
      elements.set(eI, null);
      table.set(tI, table.isNonEmpty(tI + 1)
		? Table.SLOT_DELETED
		: Table.SLOT_EMPTY);
      size -= 1;
      break;
    }
  }
}

La méthode rehashIfNeeded doit être adaptée afin de :

• prenant en compte les pierres tombales pour décider si un rehachage est nécessaire ou non — en utilisant elements.size(), qui inclut les éléments supprimés, plutôt que size(), lors du test initial,
• supprimant les éléments nuls du tableau des éléments, ce qui se fait facilement au moyen de la méthode remove de l'itérateur utilisé pour les parcourir.

private void rehashIfNeeded() {
  if (table.logCapacity() >= idealLogCapacity(elements.size()))
    return;

  Table<E> newTable =
    Table.ofLogCapacity(idealLogCapacity(size));

  ListIterator<E> elementsIt = elements.listIterator();
  while (elementsIt.hasNext()) {
    E e = elementsIt.next();
    if (e == null) {
      elementsIt.remove();
      continue;
    }
    int tI = newTable.indexFor(e);
    while (newTable.isNonEmpty(tI)) tI += 1;
    newTable.set(tI, elementsIt.previousIndex());
  }

  table = newTable;
}

La méthode iterator est de loin la plus compliquée à modifier, puisqu'elle ne peut plus se baser sur un itérateur parcourant les éléments du tableau, pour deux raisons : premièrement, ce tableau contient des éléments nuls, et deuxièmement, la méthode remove de l'itérateur ne peut pas se contenter de supprimer les éléments du tableau, la table de hachage doit également être mise à jour.

Néanmoins, l'itérateur n'est pas excessivement difficile à écrire car il combine des techniques déjà utilisées précédemment, à savoir :

• l'utilisation d'un attribut nommé remaining mémorisant le nombre d'éléments restants à fournir, qui simplifie l'écriture de la méthode hasNext,
• l'utilisation d'un attribut nommé canRemove permettant de savoir si un appel à remove est autorisé,
• l'utilisation d'un index nommé currI désignant le dernier élément fourni par l'itérateur, et similaire à nextI utilisé dans d'autres contextes, si ce n'est que nextI désigne le prochain élément fourni.

Finalement, et comme souvent, le code de la méthode remove de l'itérateur ressemble beaucoup à celui de la méthode remove de la classe elle-même. La différence principale est que la méthode remove de l'itérateur a la garantie que l'élément se trouve dans l'ensemble, ce qui simplifie sa mise en œuvre.

public Iterator<E> iterator() {
  return new Iterator<>() {
    int remaining = size();
    int currI = -1;
    boolean canRemove = false;

    @Override
    public boolean hasNext() {
      return remaining > 0;
    }

    @Override
    public E next() {
      if (!hasNext()) throw new NoSuchElementException();
      canRemove = true;
      remaining -= 1;
      do currI += 1; while (elements.get(currI) == null);
      return elements.get(currI);
    }

    @Override
    public void remove() {
      if (!canRemove) throw new IllegalStateException();
      canRemove = false;

      int tI = table.indexFor(elements.get(currI));
      while (table.get(tI) != currI) tI += 1;
      elements.set(currI, null);
      table.set(tI, table.isNonEmpty(tI + 1)
		? Table.SLOT_DELETED
		: Table.SLOT_EMPTY);
      size -= 1;
    }
  };
}