La structure OrderdSet implémente un ensemble ordonné,
où la position d'un élément est donné à
l'insertion par le client. Soit en donnant l'élément précédent
ou suivant, soit en donnant un rang.
OrderedSet utilise un double référencement de
ses éléments : dans une table pour savoir rapidement si un
élément est présent, et dans un AVL pour calculer
rapidement le rang d'un élément. De plus, la table permet
de récupérer la position de l'élément dans
l'AVL.
A cause de l'utilisation des positions, il n'est plus possible de déplacer
une donnée sur un autre noeud, sinon une position ne correspondra
plus à la donnée pour laquelle elle a été renvoyée.
L'interface AVLPosition n'a pas de classe instanciante publique.
Elle est implémentée par une classe interne privée
AVL.Cell
dont les instances sont renvoyées par des méthodes de la
classe AVL.
Comme il est possible d'insérer ou d'enlever un élément
sans rechercher au préalable sa position depuis la racine, il est
nécessaire de maintenir à jour un lien de chaque noeud vers
son père afin de pouvoir remonter jusqu'à la racine lors
de la phase de balancement. Pour simplifier le code, on utilise une sentinelle
également à la racine.