How to create SortedSet (e.g. TreeSet) for element

问题:

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?

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

回答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.

回答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.