Multiset in Android

Question

I have a structure

class A
{
    float key;
    Foo data;
}

I need to maintain an array of these structures sorted by key. Insertion and deletion of elements into the array must be efficient (say O(log n)). key is not guaranteed to be unique. Also I need to enumerate the array in the sorted order. Random access by index is not needed.

If I were using C++, I would use std::multiset here.

What would you suggest to use for Java for Android?

Do you require your key to be `float` or would `Float` work? There is overhead for boxing primitives into objects but if your set of data doesn't change at high rate you could use a `TreeMap`. — zapl, Jul 07 '16 at 08:51
`TreeMap` only works with unique keys, doesn't it? In my situation key is not unique. So two or more elements may have the same key value. — Nick, Jul 07 '16 at 09:02
Arf, yes. You could potentially work around that with a `TreeSet` with a comparator that includes the `Foo` object in the comparison in case `key`s are identical. Requires that foo is somehow comparable and not duplicate. Or `TreeMap>` for true multi mapping (or guava's implementation https://github.com/google/guava/wiki/NewCollectionTypesExplained). Otherwise a sorted list / tree structure of `A`s but there is no standard collection for that: http://stackoverflow.com/questions/8725387/why-is-there-no-sortedlist-in-java — zapl, Jul 07 '16 at 09:57

score 2 · Accepted Answer · answered Jul 07 '16 at 09:58

2

You can use Guava Multiset in order to achieve what you want. In Android Studio you just need to add the following dependancy to your build.gradle:

compile 'com.google.guava:guava:19.0'

Then you just need to declare a Multiset of your class, like this:

Multiset<A> multiset = HashMultiset.create();

multiset.add(new A(1.5, "a"));

If you take a look at the docs the available methods should allow you to do what you need.

answered Jul 07 '16 at 09:58

LS_

6,763
9
52
88

When I enumerate `Multiset`, does it yield entries in the sorted order? – Nick Jul 07 '16 at 10:14
There is also an implementation of [SortedMultiset](http://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/SortedMultiset.html) , from the docs: `A Multiset which maintains the ordering of its elements, according to either their natural order or an explicit Comparator.` – LS_ Jul 07 '16 at 10:27

score 1 · Answer 2 · answered Jul 07 '16 at 18:04

You can look into the PriorityQueue class. Pushing items to a priority queue is O(logn) and deleting is O(logn). As well, you can have duplicates unlike TreeSet. You cannot go through index by index, but you can go through the queue sequentially. Lastly, order is of course sorted!

Swapnil · Answer 3 · 2016-07-07T11:23:50.393

Hi You can use Comparable interface and TreeSet to solve your issue as bellow

Create your Data Structure class as bellow

public class YourDataSructure implements Comparable<YourDataSructure> {

    public float key;
    public String data;

    public YourDataSructure(float key,String data) {
        this.key = key;
        this.data = data;
    }

    @Override
    public int compareTo(YourDataSructure o) {
        if(key > o.key)
        {
            return 1;
        }else if(key <= o.key)
        {
            return -1;
        }
        return 0;
    }

}

And use this code to add the data

TreeSet<YourDataSructure> treeset = new TreeSet<>();

        treeset.add(new YourDataSructure(34,"test 1"));
        treeset.add(new YourDataSructure(22.11f,"test 2"));
        treeset.add(new YourDataSructure(34.12f,"test 3"));
        treeset.add(new YourDataSructure(11.12f,"test 4"));
        treeset.add(new YourDataSructure(11.1f,"test 5"));
        treeset.add(new YourDataSructure(66.32f,"test 6"));
        treeset.add(new YourDataSructure(69.55f,"test 7"));
        treeset.add(new YourDataSructure(34.43f,"test 8"));
        treeset.add(new YourDataSructure(11f,"test 9"));
        treeset.add(new YourDataSructure(11f,"test 10"));

        treeset.forEach(new Consumer<YourDataSructure>() {
            @Override
            public void accept(YourDataSructure t) {
                System.out.println(t.key + " " + t.data);
            }
        });

Works fine for me

Here is the output sorted w.r.t. key value and duplicate keys also allowed.

11.0 test 10
11.0 test 9
11.1 test 5
11.12 test 4
22.11 test 2
34.0 test 1
34.12 test 3
34.43 test 8
66.32 test 6
69.55 test 7

In your example `test 10` will overwrite `test 9`, won't it? Because their key is `11f`, and duplicated keys are not allowed in `TreeSet`. — Nick, Jul 07 '16 at 10:11
I have added output of the code here duplicate keys are allowed as you can see. This is happening due to overriding of compareTo() — Swapnil, Jul 07 '16 at 11:25

Multiset in Android

3 Answers3