Liste de tableaux triés en Java

Question

Je suis déconcerté de ne pas pouvoir trouver une réponse rapide à cette question. Je suis essentiellement à la recherche d'une structure de données en Java qui implémente la fonction java.util.List mais qui stocke ses membres dans un ordre trié. Je sais que vous pouvez utiliser une interface normale ArrayList et utiliser Collections.sort() mais j'ai un scénario où j'ajoute occasionnellement et récupère souvent des membres de ma liste et je ne veux pas avoir à la trier à chaque fois que je récupère un membre au cas où un nouveau membre a été ajouté. Quelqu'un peut-il m'indiquer une telle chose qui existe dans le JDK ou même dans des bibliothèques tierces ?

EDIT : La structure de données devra préserver les doublons.

SOMMAIRE DE LA RÉPONSE : J'ai trouvé tout cela très intéressant et j'ai appris beaucoup de choses. Aioobe en particulier mérite une mention pour sa persévérance à essayer de réaliser mes exigences ci-dessus (principalement une implémentation triée de java.util.List qui supporte les doublons). J'ai accepté sa réponse comme étant la plus précise par rapport à ce que j'ai demandé et celle qui m'a le plus fait réfléchir sur les implications de ce que je cherchais, même si ce que j'ai demandé n'était pas exactement ce dont j'avais besoin.

Le problème avec ce que j'ai demandé réside dans l'interface List elle-même et dans le concept de méthodes optionnelles dans une interface. Pour citer la javadoc :

L'utilisateur de cette interface a un contrôle précis de l'endroit où chaque élément est inséré dans la liste.

L'insertion dans une liste triée ne permet pas un contrôle précis du point d'insertion. Ensuite, vous devez réfléchir à la manière dont vous allez gérer certaines méthodes. Prenons l'exemple de add par exemple :

public boolean add(Object o)

 Appends the specified element to the end of this list (optional operation).

Vous vous retrouvez alors dans une situation inconfortable où vous devez soit 1) rompre le contrat et mettre en œuvre une version triée d'add 2) Laisser add ajouter un élément à la fin de la liste, brisant ainsi l'ordre de tri. 3) Sortir add (car il est optionnel) en lançant un UnsupportedOperationException et en implémentant une autre méthode qui ajoute les éléments dans un ordre trié.

L'option 3 est probablement la meilleure, mais je trouve déplaisant d'avoir une méthode add qu'on ne peut pas utiliser et une autre méthode sortedAdd qui n'est pas dans l'interface.

Autres solutions connexes (sans ordre particulier) :

• java.util.PriorityQueue qui est probablement plus proche de ce dont j'avais besoin que de ce que j'ai demandé. Une file d'attente n'est pas la définition la plus précise d'une collection d'objets dans mon cas, mais fonctionnellement, elle fait tout ce dont j'ai besoin.
• net.sourceforge.nite.util.SortedList . Cependant, cette implémentation rompt le contrat de l'interface List en implémentant le tri dans la section add(Object obj) et bizarrement a une méthode sans effet pour add(int index, Object obj) . Le consensus général suggère throw new UnsupportedOperationException() pourrait être un meilleur choix dans ce scénario.
• Le TreeMultiSet de Guava Une implémentation d'ensemble qui supporte les doublons
• ca.odell.glazedlists.SortedList Cette classe est accompagnée d'un avertissement dans sa javadoc : Warning: This class breaks the contract required by List

Answer 1

Solution minimaliste

Voici une solution "minimale".

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

L'insertion s'exécute en temps linéaire, mais c'est ce que vous obtiendriez en utilisant une ArrayList de toute façon (tous les éléments à droite de l'élément inséré devraient être décalés d'une manière ou d'une autre).

L'insertion d'un élément non comparable entraîne une ClassCastException. (C'est l'approche adoptée par PriorityQueue également : Une file d'attente prioritaire reposant sur l'ordre naturel ne permet pas non plus l'insertion d'objets non comparables (ce qui peut entraîner une ClassCastException). )

Remplacement de List.add

Notez que le remplacement de List.add (ou List.addAll d'ailleurs) pour insérer des éléments de manière triée serait une violation directe de la spécification de l'interface . Ce que vous pourrait est de surcharger cette méthode pour lancer un UnsupportedOperationException .

D'après les documents de List.add :

boolean add(E e)
     Ajoute l'élément spécifié à la fin de cette liste (opération facultative).

Le même raisonnement s'applique aux deux versions de add les deux versions de addAll y set . (Toutes ces opérations sont facultatives selon l'interface de la liste).

Quelques tests

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

....prints :

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

Answer 2

Utilisez java.util.PriorityQueue .

Answer 3

Jetez un coup d'œil à Liste triée

Cette classe implémente une liste triée. Elle est construite avec un comparateur qui peut comparer deux objets et trier les objets en conséquence. Lorsque vous ajoutez un objet à la liste, il est inséré à la bonne place. Les objets qui sont égaux selon le comparateur, seront dans la liste dans l'ordre où ils ont été ajoutés à cette liste. N'ajoutez que les objets que le comparateur peut comparer.

---

Lorsque la liste contient déjà des objets qui sont égaux selon le comparateur, le nouvel objet sera inséré immédiatement après ces autres objets.

Answer 4

Vous pouvez essayer Goyave ArbreMultiSet .

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);

Answer 5

Les listes conservent généralement l'ordre dans lequel les éléments sont ajoutés. Avez-vous vraiment besoin d'une liste ou est-ce qu'un set (par exemple TreeSet<E> ) vous conviennent ? En fait, avez-vous besoin de préserver les doublons ?