有限的SortedSet
我正在寻找具有有限数量元素的SortedSet的实现。 因此，如果添加了更多元素，则指定的最大值比较器决定是否添加项目并从集合中删除最后一个项目。
SortedSet t1 = new LimitedSet(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 t1 = new LimitedSortedSet(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()到add()和addAll()方法中。 不应该太难。
顺便说一句，我不完全理解你的例子：
t1.add(9); // [1,2,3]
之后该套装不应包含[1,2,9]吗？
编辑 ：我想我现在明白了：你只想保留添加到集合中的最小3个元素，对吧？
编辑2 ：示例实现（未优化）可能如下所示：
class LimitedSortedSet extends TreeSet { private int maxSize; LimitedSortedSet( int maxSize ) { this.maxSize = maxSize; } @Override public boolean addAll( Collection 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契约，该契约声明如果集合因为重复而拒绝添加元素，则必须抛出一个excpetion。
在上面的示例中，首先添加元素，但由于大小限制可能会再次删除元素，或者可能会删除其他元素，因此这违反了合同。
要解决此问题，您可能需要更改add()和addAll()以在这些情况下抛出exception（或者在任何情况下为了使它们无法使用）并提供alterante方法来添加不违反任何现有api契约的元素。
在任何情况下都应该小心使用上面的示例，因为使用不知道违规的代码可能会导致不必要的和难以调试的错误。
我说这是装饰器模式的典型应用程序，类似于Collections类公开的装饰器集合：unmodifiableXXX，synchronizedXXX，singletonXXX等。我将把Guava的ForwardingSortedSet作为基类，并编写一个装饰现有SortedSet使用您所需的function，如下所示：
public final class SortedSets { public SortedSet maximumSize( final SortedSet original, final int maximumSize){ return new ForwardingSortedSet () { @Override protected SortedSet delegate() { return original; } @Override public boolean add(final T e) { if(original.size()
不，使用现有的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" }
更新阅读完评论后
因为您需要始终删除最后一个元素：
- 你可以考虑在内部维护一个堆栈
- O（n）会增加内存复杂度
- 但可以用O（1）…常数时间检索最后一个元素
它应该做我相信的技巧