Sortificato limitato

Question

Sto cercando un'implementazione di SordSet con un numero limitato di elementi. Quindi, se sono aggiunti più elementi, il massimo specificato, il comparatore decide se aggiungere l'elemento e rimuovere l'ultimo dal set.

SortedSet<Integer> t1 = new LimitedSet<Integer>(3);
t1.add(5);
t1.add(3);
t1.add(1);
// [1,3,5]
t1.add(2);
// [1,2,3]
t1.add(9);
// [1,2,3]
t1.add(0);
// [0,1,2]

Esiste un modo elegante nell'API standard per raggiungere questo obiettivo?

Ho scritto un test JUnit per il controllo delle implementazioni:

@Test
public void testLimitedSortedSet() {
final LimitedSortedSet<Integer> t1 = new LimitedSortedSet<Integer>(3);
t1.add(5);
t1.add(3);
t1.add(1);
System.out.println(t1);
// [1,3,5]
t1.add(2);
System.out.println(t1);
// [1,2,3]
t1.add(9);
System.out.println(t1);
// [1,2,3]
t1.add(0);
System.out.println(t1);
// [0,1,2]
Assert.assertTrue(3 == t1.size());
Assert.assertEquals(Integer.valueOf(0), t1.first());
}

Answer 1

Con l'API standard dovresti farlo da solo, cioè estendere una delle classi di set ordinate e aggiungere la logica che desideri al add() e addAll() metodi. Non dovrebbe essere troppo difficile.

A proposito, non capisco appieno il tuo esempio:

t1.add(9);
// [1,2,3]

Il set non dovrebbe contenere [1,2,9] dopo?

Modificare: Penso che ora capisco: vuoi mantenere solo i 3 elementi più piccoli che sono stati aggiunti al set, giusto?

EDIT 2: Un'implementazione di esempio (non ottimizzata) potrebbe apparire così:

class LimitedSortedSet<E> extends TreeSet<E> {

  private int maxSize;

  LimitedSortedSet( int maxSize ) {
    this.maxSize = maxSize;
  }

  @Override
  public boolean addAll( Collection<? extends E> c ) {
    boolean added = super.addAll( c );        
    if( size() > maxSize ) {
      E firstToRemove = (E)toArray( )[maxSize];
      removeAll( tailSet( firstToRemove ) );
    }   
    return added;
  }

  @Override
  public boolean add( E o ) {    
    boolean added =  super.add( o );
    if( size() > maxSize ) {
      E firstToRemove = (E)toArray( )[maxSize];
      removeAll( tailSet( firstToRemove ) );
    }
    return added;
  }
}

Notare che tailSet() Restituisce il sottoinsieme incluso il parametro (se nel set). Ciò significa che se non riesci a calcolare il valore successivo successivo (non è necessario essere nel set) dovrai leggere quell'elemento. Questo viene fatto nel codice sopra.

Se puoi calcolare il valore successivo, ad esempio se hai un insieme di numeri interi, facendo qualcosa tailSet( lastElement + 1 ) Sarebbe sufficiente e non dovresti leggere l'ultimo elemento.

In alternativa, puoi ripetere il set da solo e rimuovere tutti gli elementi che seguono l'ultimo che si desidera conservare.

Un'altra alternativa, sebbene potrebbe essere più lavoro, sarebbe quella di controllare le dimensioni prima di inserire un elemento e rimuovere di conseguenza.

Aggiornare: come ha sottolineato correttamente Msandiford, il primo elemento che dovrebbe essere rimosso è quello su indice maxSize. Quindi non è necessario leggere (ri-add?) L'ultimo elemento ricercato.

Nota importante:Come ha sottolineato correttamente @DieterDP, l'implementazione sopra viola il Collection#add() Contratto API che afferma che se una raccolta rifiuta di aggiungere un elemento per qualsiasi motivo diverso da essere un duplicato di un'eccitazione dovere essere gettato.

Nell'esempio sopra l'elemento viene prima aggiunto ma potrebbe essere rimosso di nuovo a causa di vincoli di dimensioni o altri elementi potrebbero essere rimossi, quindi questo viola il contratto.

Per risolvere che potresti voler cambiare add() e addAll() Per lanciare eccezioni in questi casi (o forse in ogni caso per renderle inutilizzabili) e fornire metodi alterante per aggiungere elementi che non violano alcun contratto API esistente.

In ogni caso l'esempio sopra dovrebbe essere usato con cura Dal momento che l'utilizzo con codice che non è a conoscenza delle violazioni potrebbe comportare errori indesiderati e difficili da debug.

Answer 2

Direi che questa è un'applicazione tipica per il motivo del decoratore, simile alle collezioni del decoratore esposte dalla classe di collezioni: non modificatexxx, synchronizedxxx, singletonxx ecc. ForwardingSortedSet come classe base e scrivi una classe che decora un esistente SortedSet Con la tua funzionalità richiesta, qualcosa del genere:

public final class SortedSets {

    public <T> SortedSet<T> maximumSize(
        final SortedSet<T> original, final int maximumSize){

        return new ForwardingSortedSet<T>() {

            @Override
            protected SortedSet<T> delegate() {
                return original;
            }

            @Override
            public boolean add(final T e) {
                if(original.size()<maximumSize){
                    return original.add(e);
                }else return false;
            }

            // implement other methods accordingly
        };
    }

}

Answer 3

No, non c'è niente del genere usando la libreria Java esistente.

Ma sì, puoi costruirne uno come sotto usando la composizione. Credo che sarà facile.

public class LimitedSet implements SortedSet {

    private TreeSet treeSet = new TreeSet();

    public boolean add(E e) {
        boolean result = treeSet.add(e);
        if(treeSet.size() >= expectedSize) {
            // remove the one you like ;)
        }
        return result;
    }

    // all other methods delegate to the "treeSet"

}

AGGIORNAREDopo aver letto il tuo commento

Come devi rimuovere sempre l'ultimo elemento:

• Puoi considerare di mantenere uno stack internamente
• aumenterà la complessità della memoria con O (n)
• ma possibile recuperare l'ultimo elemento con solo O (1) ... tempo costante

Dovrebbe fare il trucco che credo