Une queue qui assure l’unicité des éléments?

Je recherche une implémentation de java.util.Queue ou quelque chose dans la collection Google qui se comporte comme une queue, mais veille également à ce que chaque élément de la queue soit unique. (toute insertion ultérieure n’aura aucun effet)

C’est possible, ou dois-je le faire à la main?

Pour l’instant, j’utilise une queue, avec une implémentation LinkedList, et je vérifie l’unicité avant l’insertion. (J’utilise une carte latérale pour ce faire, append / supprimer des éléments de la carte latérale avant / après la queue). Je n’aime pas trop ça.

Toute consortingbution est la bienvenue. Si ce n’est pas dans le package java.util, alors c’est peut-être une mauvaise idée?

Que diriez-vous d’un LinkedHashSet ? Son iterator préserve l’ordre d’insertion, mais comme c’est un Set , ses éléments sont uniques.

Comme l’indique sa documentation,

Notez que l’ordre d’insertion n’est pas affecté si un élément est réinséré dans l’ensemble.

Afin de supprimer efficacement les éléments de la tête de cette “file”, passez par son iterator:

 Iterator i = queue.iterator(); ... Object next = i.next(); i.remove(); 

Cela n’existe pas pour autant que je sache, mais serait assez simple à mettre en œuvre en utilisant une LinkedList en conjonction avec un Set :

 /** * Thread unsafe implementation of UniqueQueue. */ public class UniqueQueue implements Queue { private final Queue queue = new LinkedList(); private final Set set = new HashSet(); public boolean add(T t) { // Only add element to queue if the set does not contain the specified element. if (set.add(t)) { queue.add(t); } return true; // Must always return true as per API def. } public T remove() throws NoSuchElementException { T ret = queue.remove(); set.remove(ret); return ret; } // TODO: Implement other Queue methods. } 

Je serais tenté de maintenir un HashSet contenant une clé qui identifie de manière unique les éléments de la queue côte à côte. Ensuite, vérifiez simplement le HashSet pour voir si l’élément est dans la queue avant de l’append. Lorsque vous supprimez un élément de la queue, retirez simplement la clé du HashSet également.

Vérifier l’unicité du cours a un coût (dans l’espace ou dans le temps). Il semble intéressant de travailler à partir de quelque chose comme PriorityQueue qui maintiendra un tas sortingé par Comparateur des éléments. Vous pourriez être en mesure de tirer parti de cela plus efficacement (O (log n)) vérifier l’existence sans conserver de carte latérale.

Si vous souhaitez emballer une queue avec un vérificateur d’unicité, je vous recommande fortement d’utiliser la fonction de collecte des collections de Google pour générer une telle chose.

Juste pour compléter la réponse d’Adamski:

 /** * A queue that keeps each element only once. * If you try to add an element that already exists - nothing will happen. * * @author Adamski http://stackoverflow.com/a/2319156/827927 * @NotThreadSafe */ public class UniqueQueue implements Queue { private final Queue queue = new LinkedList(); private final Set set = new HashSet(); @Override public boolean add(T t) { // Only add element to queue if the set does not contain the specified element. if (set.add(t)) queue.add(t); return true; // Must always return true as per API def. } @Override public boolean addAll(Collection arg0) { boolean ret = false; for (T t: arg0) if (set.add(t)) { queue.add(t); ret = true; } return ret; } @Override public T remove() throws NoSuchElementException { T ret = queue.remove(); set.remove(ret); return ret; } @Override public boolean remove(Object arg0) { boolean ret = queue.remove(arg0); set.remove(arg0); return ret; } @Override public boolean removeAll(Collection arg0) { boolean ret = queue.removeAll(arg0); set.removeAll(arg0); return ret; } @Override public void clear() { set.clear(); queue.clear(); } @Override public boolean contains(Object arg0) { return set.contains(arg0); } @Override public boolean containsAll(Collection arg0) { return set.containsAll(arg0); } @Override public boolean isEmpty() { return set.isEmpty(); } @Override public Iterator iterator() { return queue.iterator(); } @Override public boolean retainAll(Collection arg0) { throw new UnsupportedOperationException(); } @Override public int size() { return queue.size(); } @Override public Object[] toArray() { return queue.toArray(); } @Override public  T[] toArray(T[] arg0) { return queue.toArray(arg0); } @Override public T element() { return queue.element(); } @Override public boolean offer(T e) { return queue.offer(e); } @Override public T peek() { return queue.peek(); } @Override public T poll() { return queue.poll(); } } 

C’est une très bonne question. Il n’y a pas de solution simple existante. Je vais déterrer un code que j’ai écrit il y a quelque temps et qui a tenté de le faire, et revenir et modifier cette réponse.

EDIT: Je suis de retour. En vérité, si vous n’avez pas besoin de simultanéité, il est préférable de conserver une queue et un ensemble séparément. Pour ce que je faisais, la concurrence était un objective, mais la meilleure solution que je pouvais trouver étant donné que la contrainte était problématique; En gros, comme il utilisait une ConcurrentHashMap, plus vous supprimiez l’élément “head” de la queue (élément de base d’une queue), plus la table de hachage deviendrait déséquilibrée avec le temps. Je peux toujours partager ce code avec vous, mais je doute que vous le souhaitiez vraiment.

EDIT: Dans le cas où une concurrence est requirejse, j’ai donné cette réponse:

Malheureusement, il n’existe pas. Depuis que j’ai besoin d’une telle queue, j’ai développé une queue de blocage soutenue par un ensemble, inspirée de java.util.concurrent.LinkedBlockingQueue .

Vous pouvez le trouver ici :

https://github.com/bvanalderweireldt/concurrent-unique-queue

Exemple :

 final BlockingQueue queue = new ConcurrentSetBlockingQueue<>(1); queue.offer(new Integer(1)); //True queue.offer(new Integer(1)); //False 

Vous pouvez l’utiliser avec Maven:

  com.hybhub concurrent-util 0.1