File d'attente à taille limitée contenant les derniers N éléments en Java

Une question très simple et rapide sur les bibliothèques Java: existe-t-il une classe prête à l'emploi qui implémente un Queueavec une taille maximale fixe - c'est-à-dire qu'elle permet toujours l'ajout d'éléments, mais elle supprimera silencieusement les éléments head pour accueillir l'espace pour les éléments nouvellement ajoutés.

Bien sûr, il est trivial de l'implémenter manuellement:

import java.util.LinkedList;

public class LimitedQueue<E> extends LinkedList<E> {
    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

Pour autant que je vois, il n'y a pas d'implémentation standard dans stdlibs Java, mais peut-être qu'il y en a une dans Apache Commons ou quelque chose comme ça?

Apache commons collections 4 a un CircularFifoQueue <> qui est ce que vous recherchez. Citant le javadoc:

CircularFifoQueue est une file d'attente premier entré, premier sorti avec une taille fixe qui remplace son élément le plus ancien s'il est plein.

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

Si vous utilisez une ancienne version des collections communes Apache (3.x), vous pouvez utiliser CircularFifoBuffer qui est fondamentalement la même chose sans génériques.

Mise à jour : réponse mise à jour après la publication de la version 4 des collections communes qui prend en charge les génériques.

La goyave a désormais une EvictingQueue , une file d'attente non bloquante qui expulse automatiquement les éléments de la tête de la file d'attente lors de la tentative d'ajouter de nouveaux éléments dans la file d'attente et elle est pleine.

import java.util.Queue;
import com.google.common.collect.EvictingQueue;

Queue<Integer> fifo = EvictingQueue.create(2); 
fifo.add(1); 
fifo.add(2); 
fifo.add(3); 
System.out.println(fifo); 

// Observe the result: 
// [2, 3]

J'aime la solution @FractalizeR. Mais je voudrais en plus garder et retourner la valeur de super.add (o)!

public class LimitedQueue<E> extends LinkedList<E> {

    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
           super.remove();
        }
        return added;
    }
}

Utilisez la composition et non les étendues (oui, je veux dire les étendues, comme dans une référence au mot clé extend en java et oui, c'est l'héritage) La composition est supérieure car elle protège complètement votre implémentation, vous permettant de modifier l'implémentation sans impact sur les utilisateurs de votre classe.

Je recommande d'essayer quelque chose comme ça (je tape directement dans cette fenêtre, donc l'acheteur se méfie des erreurs de syntaxe):

public LimitedSizeQueue implements Queue
{
  private int maxSize;
  private LinkedList storageArea;

  public LimitedSizeQueue(final int maxSize)
  {
    this.maxSize = maxSize;
    storageArea = new LinkedList();
  }

  public boolean offer(ElementType element)
  {
    if (storageArea.size() < maxSize)
    {
      storageArea.addFirst(element);
    }
    else
    {
      ... remove last element;
      storageArea.addFirst(element);
    }
  }

  ... the rest of this class

Une meilleure option (basée sur la réponse d'Asaf) pourrait être d'encapsuler Apache Collections CircularFifoBuffer avec une classe générique. Par exemple:

public LimitedSizeQueue<ElementType> implements Queue<ElementType>
{
    private int maxSize;
    private CircularFifoBuffer storageArea;

    public LimitedSizeQueue(final int maxSize)
    {
        if (maxSize > 0)
        {
            this.maxSize = maxSize;
            storateArea = new CircularFifoBuffer(maxSize);
        }
        else
        {
            throw new IllegalArgumentException("blah blah blah");
        }
    }

    ... implement the Queue interface using the CircularFifoBuffer class
}

La seule chose que je sais qui a un espace limité est l'interface BlockingQueue (qui est par exemple implémentée par la classe ArrayBlockingQueue) - mais ils ne suppriment pas le premier élément s'il est rempli, mais bloquent plutôt l'opération put jusqu'à ce que l'espace soit libre (supprimé par un autre thread) ).

À ma connaissance, votre implémentation triviale est le moyen le plus simple d'obtenir un tel comportement.

Vous pouvez utiliser une MinMaxPriorityQueue de Google Guava , à partir du javadoc:

Une file d'attente prioritaire min-max peut être configurée avec une taille maximale. Si c'est le cas, chaque fois que la taille de la file d'attente dépasse cette valeur, la file d'attente supprime automatiquement son plus grand élément en fonction de son comparateur (qui pourrait être l'élément qui vient d'être ajouté). Ceci est différent des files d'attente limitées conventionnelles, qui bloquent ou rejettent les nouveaux éléments lorsqu'ils sont pleins.

Un LRUMap est une autre possibilité, également d'Apache Commons.

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/LRUMap.html

    public class ArrayLimitedQueue<E> extends ArrayDeque<E> {

    private int limit;

    public ArrayLimitedQueue(int limit) {
        super(limit + 1);
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
            super.remove();
        }
        return added;
    }

    @Override
    public void addLast(E e) {
        super.addLast(e);
        while (size() > limit) {
            super.removeLast();
        }
    }

    @Override
    public boolean offerLast(E e) {
        boolean added = super.offerLast(e);
        while (added && size() > limit) {
            super.pollLast();
        }
        return added;
    }
}