Guava: Access elements in TreeMultiset via position in expanded entrySet

Question

Is there an efficient way to get the n upper entries from a sorted Multiset (TreeMultiset)?

To specify what I mean I post my inefficient solution:

public SortedMultiset<DataTuple> headMultiset(int upperBound, BoundType boundType){
    int i=0;
    DataTuple act= this.coreData.firstEntry().getElement();
    Iterator<DataTuple> itr = this.coreData.iterator();
    while(i<=upperBound){
        act = itr.next();
        i+=this.coreData.count(act);
    }
    return headMultiset(act, boundType);
}

In this example DataSet can be seen as Object and this.coreData is the underling TreeMultiset.

I'm really new to that topic, so all kinds of comments would be appreciated.

Answer 1

Actually the solution with the HashMap seems to have a acceptable performance. I built the hash map via:

public NavigableMap<Integer, E> BuildHashMap (SortedMultiset<E> multiset){
    NavigableMap<Integer, E>  ret = new TreeMap<Integer, E>();
    int n = 0;
    for (Entry<E> e : multiset.entrySet()) {
        ret.put(n, e.getElement());
        n += e.getCount();
    }
    return ret;
}

and access it with .floorEntry(n).getValue().

However elementSet().asList() is the function I'm actually looking for.

Answer 2

I'm not 100% sure what result you're looking for. Let's take an example: say the multiset has contents [5 x a, 3 x b, 7 x c, 2 x d, 5 x e]. (As in Multiset.toString(), I am writing "count x object" to represent count occurrences of object.) If I understand the problem correctly, if n is 5, then the result you want is [5 x a], correct?

(It's also not clear whether you want the size of the result multiset to "round." For example: if n was 6 in the above multiset, would you want [5 x a, 1 x b], [5 x a], or [5 x a, 3 x b] ?)

For the moment, I'll assume that you want to round up, that is, you would expect [5 x a, 3 x b]. Then your answer isn't that far off, although I think it's subtly wrong as written. Here's how I would write it:

public <E> SortedMultiset<E> takeElements(SortedMultiset<E> multiset, int n) {
    if (n == 0) { return ImmutableSortedMultiset.of(); }
    Iterator<Multiset.Entry<E>> iterator = multiset.entrySet().iterator();
    E cutoff = null;
    for (int count = 0; count < n && iterator.hasNext(); ) {
        Multiset.Entry<E> entry = iterator.next();
        count += entry.getCount();
        cutoff = entry.getElement();
    }
    if (count < n) { return multiset; }
    // cutoff is not null, since the loop must iterate at least once
    return multiset.headMultiset(cutoff, BoundType.CLOSED);
}