Trimming a sorted set

Question

I have a SortedSet (specifically a TreeSet) containing updates. An update is something like an SVN commit, Facebook wall post, new Trac ticket, etc. I'm storing these in a SortedSet because:

• Sorted: The updates need to be sorted by date, descending.
• Set: When fetching the latest updates from an update source, I'll usually receive updates that are already in the set.

Now, after a while the set will grow really huge, so I'd like to remove anything but the first X items from the set (because others won't be displayed anyway). How can I do this, since it's not a List?

Answer 1

While(mySet.size() > limit) {
  mySet.remove(mySet.last());
}

Answer 2

The solution here should depend on the fact whether you need the "extra" data in future. If you need your solution based on additional list is ok. If not, I'd suggest the following:

Create your own sorted set that extends the java.util.SortedSet and overrides its add() method. This method should do nothing after certain limit. Alternatively you can create "wrapper" Set that holds payload set and delegates all methods except add(). The add() method should delegate its call only if size of payload set is less than the predefined limit. This is how FixedSizeSortedMap of jakarta collection framework works, so you can just use it.

Answer 3

The accepted answer in not really efficient O(ln n) because it uses remove function. Here is a better one since pollLast() is O(1) and size is O(1). Complexity will be only affected by trimmed size.

While(mySet.size() > limit) {
  mySet.pollLast();
}

Answer 4

My own workaround is:

        List<Update> trimmed = new ArrayList<Update>(20);
        int i = 0;
        for (Update u : updates) {
            trimmed.add(u);
            i++;
            if (i > 20) break;
        }
        updates = new TreeSet<Update>(trimmed);

Answer 5

Here's a working solution method for Java, given a TreeSet results, and a variable size specifying the size of the resulting set:

void setLimit(Set<T> resutls, int size) {
    List<T> items = new ArrayList<T>();
    items.addAll(resutls);
    resutls.clear();
    int trim = size>items.size() ? items.size() : size;
    resutls.addAll(items.subList(0,trim));
    // return results; // optionally, if required
}