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

重要说明：
正如@DieterDP正确指出的那样，以上实现违反了Collection#add()api合同，该合同规定，如果集合出于某种原因（而不是重复）拒绝添加元素，则
必须 抛出一个例外。

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

为了解决这个问题，您可能想在这些情况下进行更改add()并addAll()引发异常（或者在任何情况下都使其无法使用），并提供alterante方法来添加不违反任何现有api合同的元素。

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