Geek Answers Handbook

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

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

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

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

How to implement a comparable interface? Or is there any other way to sort these BitSet type BitSet ?

+4
source share
3 answers

There are two ways to use TreeSet .

  • It has objects that implement Comparable
  • Create a custom Comparator object that compares the elements of your TreeSet .

Since you want your TreeSet contain BitSet s and BitSet not to implement Comparable , you need to tell TreeSet to TreeSet custom Comparator . How you implement this, Comparator up to you.

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

The comparator might 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; } } }
+8
source

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

+1
source

I'm not sure why you want to put a BitSet in a treeSet, while the workaround is to create a wrapper class that implements the 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 an instance of CustomComparableBitSet to the treeet .

-1
source

More articles:


All Articles