Uma fila que garante a singularidade dos elementos?

Question

Estou procurando uma implementação de java.util.queue ou algo na coleção do Google que se comportem como uma fila, mas também garante que cada elemento da fila seja único. (toda inserção adicional não terá efeito)

É possível, ou terei que fazer isso à mão?

Por enquanto, estou usando uma fila, com uma implementação do LinkedList, e verifico a singularidade antes da inserção. (Eu uso um mapa lateral para fazer isso, adicione / remova o elemento do mapa lateral antes / depois do Queu). Eu não gosto muito disso.

Qualquer entrada é bem -vinda. Se não estiver no pacote Java.util, talvez seja uma má ideia?

Answer 1

Que tal a LinkedHashSet? Seu iterador preserva a ordem de inserção, mas porque é um Set, seus elementos são únicos.

Como diz sua documentação,

Observe que a ordem de inserção é não afetado se um elemento for re-inserido no conjunto.

Para remover com eficiência os elementos da cabeça desta "fila", passe por seu iterador:

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

Answer 2

Isso não existe tanto quanto eu sei, mas seria bastante simples de implementar usando um LinkedList em conjunto com um 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

Eu ficaria tentado a manter um Hashset contendo uma chave que identifica exclusivamente os itens na fila lado a lado com ela. Em seguida, verifique o hashset para ver se o item está na fila antes de adicioná -lo. Ao remover um item da fila, basta remover a chave do hashset também.

Answer 4

Verificar a singularidade, é claro, tem um custo (no espaço ou no tempo). Parece que pode ser interessante funcionar de algo como uma prioridade que manterá uma pilha classificada pelo comparador dos elementos. Você pode aproveitar isso para mais eficientemente (O (Log N)) verificar a existência sem manter um mapa lateral.

Se você deseja envolver uma fila com um verificador de exclusividade, eu recomendo fortemente usar as coleções do Google ForwardingQueue Para construir uma coisa dessas.

Answer 5

Apenas para completar a resposta 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 é uma pergunta muito boa. Não existe solução direta existente. Vou desenterrar algum código que escrevi há algum tempo que tentou fazer isso e voltar e editar esta resposta.

EDITAR: Voltei. Na verdade, se você não precisa de simultaneidade, é melhor manter uma fila e definir separadamente. Para o que eu estava fazendo, a simultaneidade era uma meta, mas a melhor solução que eu poderia criar, uma vez que a restrição era problemática; Basicamente, como usava um sapão concorrente, mais você estava removendo o elemento "cabeça" da fila (uma coisa básica a fazer com uma fila), mais desequilibrada a tabela de hash se tornaria ao longo do tempo. Ainda posso compartilhar esse código com você, mas duvido que você realmente queira.

EDITAR: Para o caso em que a concorrência é necessária, dei esta resposta:Fila de conjunto simultânea

Answer 7

Infelizmente, não existe. Desde que eu precisava dessa fila, desenvolvi uma fila de bloqueio apoiada por um conjunto, inspirado por java.util.Concurrent.LinkedBlockingQueue.

Você pode encontrá-lo aqui :

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

Exemplo :

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

Você pode usá -lo com maven:

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

Answer 8

Estou um pouco tarde para responder, mas acabei resolvendo um problema semelhante usando um Arraydeque e substituindo o método Adicionar que eu precisava.

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