How to create SortedSet (e.g. TreeSet) for elements of type BitSet

Question

I have a number (power(2,k)) of BitSet objects and I want to store them in a SortedSet. I use the code:

Set <BitSet> S= new TreeSet<>();

However, I am getting this error: java.lang.ClassCastException: java.util.BitSet cannot be cast to java.lang.Comparable

How do I implement comparable interface? Or is there any other way to sort these elements of type BitSet?

Answer 1

There are two ways to use a TreeSet.

1. Have it contain objects that implement Comparable
2. Have a custom Comparator object that compares the elements of your TreeSet.

Since you want to have your TreeSet contain BitSets, and BitSet does not implement Comparable, you need to give your TreeSet a custom Comparator. How you implement that Comparator is up to you.

SortedSet<BitSet> s = new TreeSet<BitSet>(new CustomBitSetComparator());
s.add(bitSet1);
s.add(bitSet2);
//etc ...

The Comparator may look something like this

class CustomBitSetComparator implements Comparator<BitSet>{
    int compare(BitSet a, BitSet b) {
        if(a == b){
            return 0;
        } else if(a == null) {
            return -1;
        } else if(b == null) {
            return 1;
        } else if(a.equals(b)) {
            return 0;
        } else if(a.length() > b.length()) {
            return 1;
        } else if(b.lenght() > a.length()) {
            return -1;
        } else {
            for(int i = 0; i < a.length(); i++) {
               if(a.get(i) != b.get(i)) {
                   if(a.get(i)) {
                      return 1;
                   } else {
                      return -1;
                   }
                }
             }
             return 0;
         }
    }
}

Answer 2

I would convert them to BigIntegers (O(N)) and use a TreeSet. Otherwise you will have to write yourself a Comparator, which in the nature of things will run excruciatingly slowly, as you can see from other answers. I would also consider using PriorityQueue instead of a Set.