有限的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

不，在现有的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)来检索最后一个元素...constant time

它应该能起到我相信的作用

Answer 2

我想说这是一个典型的装饰器模式应用程序，类似于集合类公开的装饰器集合: unmodifiableXXX、synchronizedXXX、singletonXXX等。我会将Guava的ForwardingSortedSet作为基类，并编写一个类，用所需的功能装饰现有的SortedSet，如下所示：

public final class SortedSets {

    public <T> SortedSet<T> maximumSize(
        final SortedSet<T> original, final int maximumSize){

        return new ForwardingSortedSet<T>() {

            @Override
            protected SortedSet<T> delegate() {
                return original;
            }

            @Override
            public boolean add(final T e) {
                if(original.size()<maximumSize){
                    return original.add(e);
                }else return false;
            }

            // implement other methods accordingly
        };
    }

}