CODEWITHSUNDEEP
javacollectionstrimtreesetsortedset
Bart van Heukelom
Bart van Heukelom

Reputation: 44114

Trimming a sorted set

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:

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?

Upvotes: 5

Views: 3824

Answers (5)

Wojtek Sierka
Wojtek Sierka

Reputation: 31

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

Upvotes: 3

Nestor Milyaev
Nestor Milyaev

Reputation: 6595

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
}

Upvotes: 0

AlexR
AlexR

Reputation: 115378

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.

Upvotes: 2

sje397
sje397

Reputation: 41852

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

Upvotes: 5

Bart van Heukelom
Bart van Heukelom

Reputation: 44114

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);

Upvotes: 0

Related Questions