有限的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来检查实现:

@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 正确指出的那样，应该删除的第一个元素是位于 index 的元素maxSize。因此不需要重新添加（重新添加？）最后一个想要的元素。

重要提示： 正如 @DieterDP 正确指出的那样，上面的实现违反了Collection#add()api 契约，该契约规定，如果集合因重复以外的任何原因拒绝添加元素，则必须抛出异常。

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

要解决这个问题，您可能需要在这些情况下进行更改add()并addAll()抛出异常（或者在任何情况下都可能使它们不可用），并提供 alterante 方法来添加不违反任何现有 api 约定的元素。

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