Is there an ImmutableBitSet in Java?

Question

Is there any Java library offering an ImmutableBitSet? I didn't find any, neither Guava nor using Google.

Answer 1

You could use BigInteger, since it has setBit, testBit and clearBit.

Answer 2

It's easy to make a practically immutable BitSet from a java.util.BitSet by extending it and knock out modifier methods with throws UnsupportedException or empty block.

However, since BitSet's field which stores effective data isn't final, you have to apply one of the safe publication idioms to achieve thread-safety (copied from here):

• Initializing an object reference from a static initializer;
• Storing a reference to it into a volatile field or AtomicReference;
• Storing a reference to it into a final field of a properly constructed object
• Storing a reference to it into a field that is properly guarded by a lock.

Another solution could be to make a new ImmutableBitSet class, embed a BitSet into it as a field (with final modifier) and delegate the embedded object's reader methods to the new class.

Note that the latter solution doesn't break Liskow Substitution Principle while the first one does.

Answer 3

A workaround:

store the BitSet in a private field and expose it with a cloning public method:

private final BitSet bits;
public BitSet bits(){
    return (BitSet) bits.clone();
}

or:

private final BitSet bits;
public BitSet bits(){
    BitSet clone = new BitSet();
    clone.or(bits);
    return clone;
}

Answer 4

I decided to make a summary of all the answers:

I see no way to get everything perfect, i.e., to get an immutable subclass of BitSet, so that equals works in an thread-safe manner. I admit that I didn't state all my requirements in the question.

Inheriting from BitSet and letting all the mutator methods throw an exception is easy and works. The only problem is that equals called from BitSet itself is not thread-safe since it accesses the non-final inherited fields directly. All other methods can be made thread-safe by a trick described below.

Delegating to BitSet is also easy and works, and its only problem is that a BitSet can't be equal to an ImmutableBitSet. Note that for thread safety the delegate must be stored in a final field.

Combining inheritance and delegation looks promising:

public class ImmutableBitSet extends BitSet {
    private final ImmutableBitSet delegate;

    public ImmutableBitSet(BitSet original) {
        or(original); // copy original to this
        delegate = this; // initialize a final reference for thread safety
    }

    @Override // example mutator method
    public void and(BitSet set) {
        throw new UnsupportedOperationException();
    }

    @Override // example non-mutator method
    public boolean get(int bitIndex) {
        return delegate.getPrivate(bitIndex);
    }

    // needed in order to avoid endless recursion
    private boolean getPrivate(int bitIndex) {
        super.get(bitIndex);
    }

    ...
}

It looks strange, but works nearly perfect. Call to bitSet.equals(immutableBitSet) are not thread-safe, because of them accessing the non-final fields directly. So it was just a fruitless exercise.

Using a BitInteger is quite a lot of work if one wants to implement all the methods and conversion to and from the mutable BitSet. So I'd recommend either delegation or inheritance, depending on the desired behavior of equals and on the need for thread safety.

Answer 5

You could maybe use BigInteger. It is immutable, and has bit manipulation methods.

Answer 6

Personally, I prefer an EnumSet over a BitSet. It is implemented as a bit field, but has the API of a set with strong naming. Really this is the best of both worlds. Guava does provide an ImmutableEnumSet

Answer 7

I have implemented such based on org.apache.lucene.util.OpenBitSet from the Apache Lucene project here

http://www.dishevelled.org/bitset

http://www.dishevelled.org/bitset/apidocs/index.html