java: get count of values within a given key range of Guava Multimap

Question

I have a TreeMultimap<Integer, String>, which includes duplicate keys also.

I want to get the count of values which lies within a specific key range, that too with O(logN) time complexity.

I tried by first converting the TreeMultimap to a SortedMap by using its method asMap() and then creating a submap in the required range and fetching its size.

SortedMap<Integer, Collection<String>> sortedMap = mapList.getTmm().asMap();
return sortedMap.subMap(beg,end).size();

Is it having complexity O(logN)?

Also, I faced a problem here. When a TreeMultimap is converted to SortedMap, the values are objects of Collection class. i.e. The key-value pair having duplicate keys in TreeMultimap is included in a single Collection class. So the method size() returns wrong value.

Is there any other way I an achieve this? Any help is appreciated.

Answer 1

You can try SortedMultiset, which has a method for ranged query:

subMultiset:

Returns a view of this multiset restricted to the range between lowerBound and upperBound.

Sample code:

import com.google.common.collect.*;

public class GuavaMultiMap {
    public static void main(String [] args) {
        Multimap<Integer, String> map = TreeMultimap.create();
        map.put(0, "-1");
        map.put(1, "a");
        map.put(1, "b");
        map.put(2, "c");
        map.put(2, "d");
        map.put(3, "e");

        SortedMultiset<Integer> keys = TreeMultiset.create();
        keys.addAll(map.keys());

        SortedMultiset<Integer> range = keys.subMultiset(1, BoundType.CLOSED, 3, BoundType.OPEN);
        System.out.println(range.size());
    }
}

Output: 4

The above code does not operate in O(log(N)) time because this line keys.addAll(...); is O(n). However, if you keep a SortedMultiset updated together with the Multimap, you should be able to trade space for time.