Una Coda che garantisca l'unicità degli elementi?

Question

Sto cercando un'implementazione di java.util.Queue o qualcosa nella raccolta Google che si comporti come una coda, ma assicuri anche che ogni elemento della coda sia unico.(ogni ulteriore inserimento non avrà alcun effetto)

E' possibile oppure devo farlo a mano?

Per ora sto utilizzando una Queue, con un'implementazione LinkedList, e ne controllo l'unicità prima dell'inserimento.(Utilizzo una mappa laterale per fare ciò, aggiungi/rimuovi elementi dalla mappa laterale prima/dopo la coda).Non mi piace troppo.

Qualsiasi input è il benvenuto.Se non è nel pacchetto java.util, forse è una cattiva idea?

Answer 1

Che ne dici di a LinkedHashSet?Il suo iteratore preserva l'ordine di inserimento, ma poiché è un file Set, i suoi elementi sono unici.

Come dice la sua documentazione,

Tieni presente che l'ordine di inserzione è non influenzato se un elemento lo è reinserito nel set.

Per rimuovere in modo efficiente gli elementi dalla testa di questa "coda", passa attraverso il suo iteratore:

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

Answer 2

Questa non esiste per quanto ne so, ma sarebbe abbastanza semplice da realizzare utilizzando un LinkedList in combinazione 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

sarei tentato di mantenere un HashSet contenente una chiave che identifica in modo univoco gli elementi nella coda side-by-side con esso. Poi basta controllare la HashSet per vedere se l'articolo è in coda prima di aggiungerlo. Quando si rimuove un elemento dalla coda, è sufficiente rimuovere la chiave dal HashSet pure.

Answer 4

Controllo unicità ovviamente ha un costo (spaziale o tempo). Sembra che potrebbe essere interessante lavorare da qualcosa di simile a un CodaConPriorita che manterrà un mucchio ordinato secondo comparatore degli elementi. Potreste essere in grado di sfruttare in modo più efficiente che a (O (log n)) verificare l'esistenza senza mantenere una mappa lato.

Se si vuole avvolgere una coda con un controllo di unicità, vi consiglio vivamente di utilizzare le collezioni di Google ForwardingQueue per costruire una cosa del genere.

Answer 5

Giusto per completare la risposta di 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

Questa è una domanda molto buona. Non esiste una soluzione semplice esistente. Tirerò un po 'di codice che ho scritto un po' indietro che ha tentato di fare questo, e tornare a modificare questa risposta.

Modifica sono tornato. In verità, se non hai bisogno di concorrenza, si sta meglio mantenere una coda e impostato separatamente. Per quello che stavo facendo, la concorrenza era un obiettivo, ma la soluzione migliore che potesse venire con data tale vincolo era problematico; in sostanza, dal momento che ha utilizzato un ConcurrentHashMap, più si stavano rimuovendo l'elemento "testa" dalla coda (una cosa semplice da fare con una coda), il più sbilanciato la tabella hash sarebbe diventato nel corso del tempo. Riesco ancora a condividere questo codice con te, ma dubito che si vuole veramente.

Modifica Per il caso in cui è richiesto concorrenza mi ha dato questa risposta: Concurrent Set coda

Answer 7

Purtroppo non esiste. Da quando ho avuto bisogno di una tale coda ho sviluppato una coda di blocco sostenuta da una serie, ispirata da java.util.concurrent.LinkedBlockingQueue .

È possibile trovare qui:

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

Esempio:

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

Si può usare con Maven:

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

Answer 8

Sono un po 'tardi per rispondere, ma ho finito per risolvere un problema simile con un ArrayDeque e l'override del metodo Add di cui avevo bisogno.

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