Una cola que garantiza la singularidad de los elementos?

Question

Estoy buscando una implementación de java.util.Queue o algo en la colección de Google que se comporte como una cola, pero también asegúrese de que cada elemento de la cola sea único. (toda inserción adicional no tendrá ningún efecto)

¿Es posible, o tendré que hacerlo a mano?

Por ahora estoy usando una cola, con una implementación LinkedList, y compruebo la exclusividad antes de la inserción. (Utilizo un Mapa lateral para hacer esto, agregar/eliminar elemento del mapa lateral antes/después de la queu). No me gusta demasiado

Cualquier entrada es bienvenida. Si no está en el paquete java.util, ¿tal vez es una mala idea?

Answer 1

¿Qué tal un LinkedHashSet? Su iterador conserva el orden de inserción, pero debido a que es un Set, sus elementos son únicos.

Como dice su documentación,

Tenga en cuenta que el fin de inserción es no afectado si un elemento es reinserta en el conjunto.

Con el fin de eliminar eficazmente los elementos de la cabeza de esta "cola", vaya a través de su iterador:

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

Answer 2

Tendría la tentación de mantener un HashSet que contenga una clave que identifique de forma exclusiva los elementos en la cola junto a él. Luego, simplemente verifique el HashSet para ver si el artículo está en la cola antes de agregarlo. Cuando eliminas un elemento de la Cola, simplemente también quita la clave del HashSet.

Answer 3

Esto no existe por lo que yo sé, pero sería bastante fácil de implementar utilizando un LinkedList en conjunción con un Set:

/** 
* Thread unsafe implementation of UniqueQueue. 
*/ 
public class UniqueQueue<T> implements Queue<T> { 
    private final Queue<T> queue = new LinkedList<T>(); 
    private final Set<T> set = new HashSet<T>(); 

    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. 
} 

Answer 4

Comprobación de singularidad, por supuesto, tiene un costo (ya sea en el espacio o el tiempo). Parece que podría ser interesante trabajar desde algo como PriorityQueue que mantendrá un montón ordenado por el Comparador de los elementos. Es posible que pueda aprovechar eso para que sea más eficiente (O (log n)) verificar la existencia sin mantener un mapa lateral.

Si desea envolver una cola con un comprobador de exclusividad, le recomiendo usar Google Collections ForwardingQueue para compilar tal cosa.

Answer 5

Esta es una muy buena pregunta. No hay una solución directa existente. Desenterraré algún código que escribí hace un tiempo que intentó hacer esto, y volveré a editar esta respuesta.

EDIT: Estoy de vuelta. Verdaderamente, si no necesita concurrencia, es mejor mantener una cola y establecer por separado. Por lo que estaba haciendo, la concurrencia era un objetivo, pero la mejor solución que podía encontrar dado que la restricción era problemática; Básicamente, dado que usaba un ConcurrentHashMap, cuanto más eliminaba el elemento "head" de la cola (algo básico que hacer con una cola), más desequilibrado se volvería la tabla hash con el tiempo. Todavía puedo compartir este código contigo, pero dudo que realmente lo quieras.

EDIT: Para el caso en que se requiere la concurrencia le di esta respuesta: Concurrent Set Queue

Answer 6

TreeSet. Es un conjunto ordenado y Set implica "sin elementos duplicados".

Answer 7

sólo para completar la respuesta de 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<T> implements Queue<T> { 

private final Queue<T> queue = new LinkedList<T>(); 
private final Set<T> set = new HashSet<T>(); 

@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<? extends T> 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<T> 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> 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(); 
} 
} 

Answer 8

Por desgracia, no existe. Como necesitaba esa Cola, he desarrollado una Cola de bloqueo respaldada por un conjunto, inspirada en java.util.concurrent.LinkedBlockingQueue.

Se puede encontrar aquí:

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

Ejemplo:

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

Puede utilizarlo con Maven:

<dependency> 
    <groupId>com.hybhub</groupId> 
    <artifactId>concurrent-util</artifactId> 
    <version>0.1</version> 
</dependency>