Una cola que garantizar la singularidad de los elementos?

Question

Estoy buscando una aplicación de java.util.Queue o algo en la colección de Google que se comportan como una cola, sino también asegurarse de que cada elemento de la cola es único. (Todo inserción adicional no tendrá ningún efecto)

Es eso posible, o voy a tener que hacerlo a mano?

Por ahora estoy usando una cola, con una aplicación LinkedList, y comprobar la singularidad antes de la inserción. (Yo uso un lado Mapa para hacer esto, añadir / quitar el elemento del mapa lado antes / después de la queu). No me gusta demasiado.

Cualquier entrada es bienvenido. Si no es en el paquete java.util, entonces tal vez es una mala idea?

Answer 1

¿Qué tal un LinkedHashSet ? Su iterador para conservas de inserción, sino porque 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 reinsertada en el conjunto.

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

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

Answer 2

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 3

Estaría tentado a mantener un HashSet que contiene una clave que identifica de manera única los elementos de la cola de lado a lado con ella. A continuación, sólo comprobar el HashSet para ver si el elemento está en la cola antes de añadirla. Cuando se elimina un elemento de la cola, basta con quitar la llave del HashSet también.

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 para el trabajo de algo así como un PriorityQueue que mantendrá un montón ordenadas según la Comparador de los elementos. Usted puede ser capaz de apalancamiento que a más eficiente (O (log n)) la existencia cheque sin mantener un mapa lado.

Si desea envolver una cola con un comprobador de unicidad, lo recomiendo encarecidamente el uso de las colecciones de Google ForwardingQueue para construir tal cosa.

Answer 5

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 6

Esta es una muy buena pregunta. No hay una solución sencilla existente. Voy a cavar un poco de código que escribí hace un tiempo que trataba de hacer esto, y volver y editar esta respuesta.

EDIT: Ya estoy de vuelta. En verdad, si es que no es necesario la concurrencia, que es mejor mantener una cola y ajustar por separado. Por lo que estaba haciendo, la concurrencia era un objetivo, pero la mejor solución que se le ocurrió dado que la restricción era problemático; básicamente, ya que utiliza un ConcurrentHashMap, cuanto más se estaban retirando el elemento de "cabeza" de la cola (una cosa básica que ver con una cola), la más desequilibrada la tabla hash se convertiría con el tiempo. Todavía puedo compartir con ustedes este código, pero dudo que realmente lo desea.

EDIT: En el caso en que se requiere la concurrencia le di esta respuesta: Concurrente Conjunto cola

Answer 7

Desafortunadamente no existe. Ya que necesitaba una cola que tales han desarrollado una cola de bloqueo con el respaldo de un conjunto, inspirado por 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

Se puede utilizar con Maven:

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

Answer 8

Soy un poco tarde para responder pero terminé la solución de un problema similar usando un ArrayDeque y reemplazando el método complemento que necesitaba.

    Deque<Long> myQueue = new ArrayDeque<Long>() {
        @Override
        public boolean add(Long e) { return !this.contains(e) && super.add(e);}
    };