java - 有限的SortedSet

Question

我正在寻找具有有限数量元素的 SortedSet 的实现。因此，如果添加的元素超过指定的最大值，则比较器决定是否添加该项目并从 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]

标准 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 正确指出的那样，上面的实现违反了 Collection#add() api 契约规定，如果一个集合出于任何原因拒绝添加一个元素，而不是因为它是重复的，则必须抛出异常。

在上面的示例中，元素首先被添加，但由于大小限制可能会再次被删除，或者其他元素可能会被删除，因此这违反了契约(Contract)。

要解决这个问题，您可能需要更改 add()和 addAll()在这些情况下抛出异常(或者可能在任何情况下为了使它们不可用)并提供替代方法来添加不违反任何现有 api 契约(Contract)的元素。

在任何情况下，上面的示例都应该小心使用，因为将它与不知道违规的代码一起使用可能会导致不需要且难以调试的错误。