implementazione java.util.Queue che fornisce elementi uguali al massimo una volta

Question

Sto cercando un'implementazione java.util.Queue che accoda una volta gli elementi uguali al massimo.

esempio un tale specialQueue dovrebbe comportarsi in questo modo:

E e1; 
E e2; 
E e3; 
//... 
assertThat(e1, is(e2)); 
assertThat(e1, is(not(e3))); 

Queue<E> specialQueue; 
//... 
specialQueue.offer(e1); 
specialQueue.offer(e2); 
specialQueue.offer(e3); 


assertThat(specialQueue.poll(), is(e1)); 
assertThat(specialQueue.poll(), is(e3)); 
assertThat(specialQueue.poll(), is(null)); 
// FIFO semantics are not relevant to the question 

specialQueue.offer(e3) 
assertThat(specialQueue.poll(), is(null)); 

mi si avvicinò con un'implementazione che gestisce un interno Set<E> alreadySeenElements, e le guardie contro l'aggiunta di elementi a una coda delegato controllando contro quel set. Mi stavo chiedendo se esiste già un'implementazione "collaudata".

Answer 1

Come suggeriscono i commentatori, si sta descrivendo un tipo speciale di Set rispetto a Queue. Da quello che ho capito, le vostre esigenze sono:

• Inserimento ordine di iterazione
• Ogni elemento della collezione è unica (non uguale)
• elementi visto in precedenza possono mai essere nuovamente aggiunti

I primi due requisiti sono ben serviti da un LinkedHashSet, come suggerisce this question. L'ultimo requisito è molto più strano e richiede una sorta di archivio interno dei valori visti in precedenza. Qualcosa di simile:

public class SeenOnceLinkedHashSet<E> implements Set<E> { 
    private LinkedHashSet<E> data; 
    private HashSet<E> seen; 

    public boolean add(E e) { 
    boolean newValue = seen.add(e); 
    if (newValue) { 
     return data.add(e); 
    } 

    // and so on in other methods 
} 

Si noti che questa classe ha memoria interna illimitata. Si potrebbe facilmente causare un problema di esaurimento della memoria utilizzando questa classe in un modo che altri Set potrebbero gestire senza problemi. Se hai bisogno di una nozione di "è mai stato aggiunto" questo è inevitabile. Potresti usare qualcosa di più elegante come un BloomFilter, ma questo introdurrebbe falsi positivi.

Personalmente, vorrei rivedere le vostre esigenze. Qualsiasi tipo di struttura di dati dello spazio illimitato è quasi certamente un odore di codice. Potresti, ad esempio, utilizzare una classe wrapper che fornisca una definizione più utile di .equals()? O aggiungere ulteriori controlli di sicurezza al momento della costruzione dell'oggetto, quindi gli oggetti non validi non vengono costruiti in primo luogo?