有限排序集 [英] Limited SortedSet

问题描述

我正在寻找具有有限数量元素的 SortedSet 实现.因此，如果添加了更多元素，则比较器会决定是否添加指定的最大值并从 Set 中删除最后一个.

i'm looking for an implementation of SortedSet with a limited number of elements. So if there are more elements added then the specified Maximum the comparator decides if to add the item and remove the last one from the 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 中是否有一种优雅的方式来实现这一点?

Is there an elegant way in the standard API to accomplish this?

我写了一个 JUnit 测试来检查实现:

I've wrote a JUnit Test for checking implementations:

@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());
}

推荐答案

使用标准 API，您必须自己完成，即扩展排序集类之一并将您想要的逻辑添加到 add() 和 addAll() 方法.应该不会太难.

With the standard API you'd have to do it yourself, i.e. extend one of the sorted set classes and add the logic you want to the add() and addAll() methods. Shouldn't be too hard.

顺便说一句，我不完全理解你的例子:

Btw, I don't fully understand your example:

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

集合之后不应该包含[1,2,9]吗?

Shouldn't the set contain [1,2,9] afterwards?

编辑:我想现在我明白了:您只想保留添加到集合中的最小的 3 个元素，对吗?

Edit: I think now I understand: you want to only keep the smallest 3 elements that were added to the set, right?

编辑 2:示例实现(未优化)可能如下所示:

Edit 2: An example implementation (not optimised) could look like this:

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() 返回包含参数的子集(如果在集合中).这意味着如果您无法计算下一个更高的值(不需要在集合中)，您将必须读取该元素.这是在上面的代码中完成的.

Note that tailSet() returns the subset including the parameter (if in the set). This means that if you can't calculate the next higher value (doesn't need to be in the set) you'll have to readd that element. This is done in the code above.

<打击>如果您可以计算下一个值，例如如果你有一组整数，做一些事情 tailSet( lastElement + 1 ) 就足够了，你不必阅读最后一个元素.

If you can calculate the next value, e.g. if you have a set of integers, doing something tailSet( lastElement + 1 ) would be sufficient and you'd not have to readd the last element.

<打击>或者，您可以自己迭代该集合并删除您想要保留的最后一个元素之后的所有元素.

<打击>另一种选择，虽然这可能需要更多的工作，但在插入元素之前检查大小并相应地删除.

更新:正如 msandiford 正确指出的那样，应该删除的第一个元素是索引 maxSize 处的元素.因此没有必要阅读(重新添加?)最后一个想要的元素.

Update: as msandiford correctly pointed out, the first element that should be removed is the one at index maxSize. Thus there's no need to readd (re-add?) the last wanted element.

重要提示:正如@DieterDP 正确指出的那样，上面的实现违反了 Collection#add() api 契约，该契约指出，如果集合因任何原因拒绝添加元素而不是重复元素，则例外 必须被抛出.

Important note: As @DieterDP correctly pointed out, the implementation above violates the Collection#add() api contract which states that if a collection refuses to add an element for any reason other than it being a duplicate an excpetion must be thrown.

在上面的例子中，元素是先添加的，但由于尺寸限制可能会再次删除，或者其他元素可能会被删除，因此这违反了约定.

In the example above the element is first added but might be removed again due to size constraints or other elements might be removed, so this violates the contract.

要解决您可能希望更改 add() 和 addAll() 以在这些情况下抛出异常(或者可能在任何情况下使它们无法使用)的问题) 并提供替代方法来添加不违反任何现有 API 合同的元素.

To fix that you might want to change add() and addAll() to throw exceptions in those cases (or maybe in any case in order to make them unusable) and provide alterante methods to add elements which don't violate any existing api contract.

在任何情况下，上述示例应该谨慎使用，因为将它与不知道违规的代码一起使用可能会导致不必要的和难以调试的错误.

In any case the above example should be used with care since using it with code that isn't aware of the violations might result in unwanted and hard to debug errors.

这篇关于有限排序集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！