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?

Windflower

What meaning do you intend for compareTo()? Cardinality? – Berti

The intention is to sort this collection of BitSet objects and so compareTo. – Windflower

The problem is BitSet does not implement compareTo, so you have to define your own ordering of BitSet. What is your desired ordering? – Motionless

I need ascending order of these BitSet objects. Is there any other way out than using TreeSet? – Windflower

Define ascending order. – Motionless

00011 < 00100 < 00110 – Windflower

Ok, now write a Comparator<BitSet> describing that logic. – Motionless

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

Motionless

The input to this SortedSet is coming through other part of programs. So what I receive is a stream of BitSet objects which I have to collect and sort and process. new CustomBitSetComparator() can't be implemented here! – Windflower

The CustomBitSetComparator() does not contain any BitSets. It compares them. It implemnts Comparator<BitSet>, which has a function compare(BitSet, BitSet) that the TreeSet uses to compare the incoming BitSets. You have to write this class yourself. – Motionless

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.

Whitecollar

Answer 3

I'm not sure why you want to put BitSet in a treeSet, while a workaround is to create a wrapper class which implements Comparable interface.

Public class CustomComparableBitSet implements Comparable{
   private BitSet bs;

   public int compareTo(T o){
      //your comparison logic goes here.
   }
}

then in the client code, add instance of CustomComparableBitSet into treeset.

Bastinado

I have these thousands of BitSet objects and I need to sort them first to process further (The processing requires them to be ascending order). So I thought TreeSet would be best data structure. If there is any other way out, please let me know. – Windflower

Ok if you have thousands of BitSet objects, creating wrapper objects might not be a good idea, because it will bring in some memory overhead. How about extends BitSet class and implements Comparable. public class CustomeComparableBitSet<T> extends BitSet implements Comparable<T> { public int compareTo(T arg0) { int i = 0; // TODO change i based on your comparison logic return i; } } – Bastinado