La taille limitée de la file d'attente qui détient des N derniers éléments en Java

Question

Un très simple et rapide à la question sur les bibliothèques Java: est-il un ready-made de classe qui implémente une Queue avec une taille maximale fixe - c'est à dire qu'il permet toujours plus d'éléments, mais il en silence enlever de la tête les éléments pour accueillir l'espace pour les nouveaux éléments ajoutés.

Bien sûr, il est facile à 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;
    }
}

Autant que je le vois, il n'y a pas de norme de mise en œuvre en Java stdlibs, mais peut être il y en a un dans Apache Commons ou quelque chose comme ça?

Answer 1

Apache commons collections de 4 a un CircularFifoQueue qui est ce que vous cherchez. Citant la javadoc:

CircularFifoQueue est un premier entré, premier sorti de la file d'attente avec une taille fixe qui remplace le plus ancien élément si complet.

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

Mise à jour: mise à jour de réponse suite à la publication de communes des collections de la version 4

Answer 2

La goyave a maintenant un EvictingQueue -- "non-blocage de file d'attente qui expulse automatiquement les éléments de la tête de la file d'attente lorsque vous essayez d'ajouter de nouveaux éléments sur la file d'attente est pleine."

http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/EvictingQueue.html

Answer 3

J'aime @FractalizeR solution. Mais je voudrais en plus de garder et de renvoyer 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;
    }
}

Answer 4

Utilisation de la composition s'étend pas (oui, je veux dire s'étend, comme une référence au mot-clé extends java, et oui, c'est l'héritage). La Composition est superier parce que c'complètement boucliers de votre application, vous permettant de modifier la mise en œuvre, sans impact sur les utilisateurs de votre classe.

Je vous recommande d'essayer quelque chose comme ça (je suis en tapant directement dans cette fenêtre, afin que l'acheteur méfiez-vous 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 (en fonction de la réponse par Asaf) pourrait être à envelopper l' 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
}

Answer 5

La seule chose que je sais qui a limité l'espace est l'interface BlockingQueue (qui est par exemple mis en œuvre par le ArrayBlockingQueue classe) - mais ils ne retirez pas le premier élément s'il est rempli, mais au lieu de bloquer l'opération de placement jusqu'à ce que l'espace est libre (supprimé par un autre thread).

À ma connaissance de votre implémentation triviale est la façon la plus simple d'obtenir un tel comportement.