Ограниченный SortedSet

Question

Я ищу реализацию SortedSet с ограниченным количеством элементов.Таким образом, если добавлено больше элементов, то в указанном максимуме компаратор решит, добавить ли элемент и удалить последний из набора.

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]

Есть ли в стандартном API элегантный способ добиться этого?

Я написал тест JUnit для проверки реализаций:

@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

Со стандартным API вам придется делать это самостоятельно, то есть расширять один из классов отсортированных множеств и добавлять желаемую логику к методам add() и addAll(). Не должно быть слишком сложно.

Кстати, я не совсем понимаю ваш пример:

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

Разве набор не должен содержать [1,2,9] впоследствии?

Редактировать : Думаю, теперь я понимаю: вы хотите сохранить только самые маленькие 3 элемента, которые были добавлены в набор, верно?

Редактировать 2 : Пример реализации (не оптимизирован) может выглядеть следующим образом:

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;
  }
}

Обратите внимание, что tailSet() возвращает подмножество, включая параметр (если оно есть в наборе). Это означает, что если вы не можете рассчитать следующее более высокое значение (не обязательно должно быть в наборе), вам придется прочитать этот элемент. Это сделано в коде выше.

Если вы можете рассчитать следующее значение, например, если у вас есть набор целых чисел, достаточно сделать что-то tailSet( lastElement + 1 ), и вам не придется читать последний элемент.

Кроме того, вы можете перебрать набор самостоятельно и удалить все элементы, которые следуют за последним, который вы хотите сохранить.

Другой альтернативой, хотя это может быть больше работы, будет проверка размера перед вставкой элемента и удаление соответственно.

Обновление : как правильно указал msandiford, первый элемент, который должен быть удален, - это элемент с индексом maxSize. Таким образом, нет необходимости читать (повторно добавлять?) Последний требуемый элемент.

Важное примечание: Как правильно указал @DieterDP, приведенная выше реализация нарушает контракт API Collection#add(), который гласит, что если коллекция отказывается добавлять элемент по любой причине, кроме того, что она является дубликатом, исключение должно быть брошено .

В приведенном выше примере элемент сначала добавляется, но может быть снова удален из-за ограничений размера или других элементов, что может нарушить договор.

Чтобы исправить это, вы можете изменить add() и addAll(), чтобы они выдавали исключения в этих случаях (или, может быть, в любом случае, чтобы сделать их непригодными для использования) и предоставлять альтернативные методы для добавления элементов, которые не нарушают какие-либо существующий контракт API.

В любом случае приведенный выше пример следует использовать с осторожностью , поскольку его использование с кодом, который не знает о нарушениях, может привести к нежелательным и трудным для отладки ошибкам.

Answer 2

Я бы сказал, что это типичное приложение для шаблона декоратора, похожее на коллекции декораторов, представленные классом Collections: unmodifiableXXX, synchronizedXXX, singletonXXX и т. Д. Я бы взял ForwardingSortedSet в Guava в качестве основы класс и напишите класс, который украшает существующий SortedSet требуемой функциональностью, что-то вроде этого:

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

Нет, ничего подобного в существующей библиотеке Java нет.

Но да, вы можете создать такой, как показано ниже, используя композицию. Я верю, что это будет легко.

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"

}

UPDATE Прочитав ваш комментарий

Так как последний элемент нужно удалять всегда:

• вы можете рассмотреть внутреннюю поддержку стека
• увеличит сложность памяти с O (n)
• но возможно получить последний элемент всего за O (1) ... постоянное время

Это должно сработать, я верю