Resizing a java BitSet

Question

Hi,

I sub classed the BitSet class to add some additional methods. One of the is called "fold". It splits the BitSet in 2 halves and "combines" them with an or. (increases Information density)

This works but the size (1024) of the folded BitSet is still the original size.

Code:

    BitSet firstHalf;
    BitSet secondHalf;
    for(int i = nrOfTimes; i > 0; i-- ){
        firstHalf = this.get(0, this.size()/2);
        secondHalf = this.get(this.size()/2, this.size());
        firstHalf.or(secondHalf);
        this.clear();
        this.or(firstHalf);
    }

It's probably doable to return a new BitSet of desired length but only by creating a new smaller one for each iteration but still you would need to re-assign it (myClass = myClass.fold()). If you fold, there is no interest in the original version. The idea is to save space (memory and DB).

Is there a way to reduce the size of the current BitSet? (a "trick" I'm not seeing?)

Answer 1

I think it's okay to do myClass = myClass.fold(), you don't have to worry about "saving space".

If there is no interest in the old object (i.e., no one has a reference to it) the garbage collector will clean up the memory for you anyway. It is well optimized for these kind of use cases.

This pattern is found in all immutable classes in the java library. Take for instance str = str.substring(i); or bigInt = bigInt.multiply(BigInteger.TEN); etc.

Answer 2

Indeed you are correct, the clear method will clear all the bits but will not release any internal memory used to hold the bits.

For what it's worth: If you look at the source code of BitSet. The bits are hold in an internal array called words. The only place where this array is downsize is in the private trimToSize() method. This in turn is only called from clone() and writeObject(), but only if the size is not sticky -- i.e. if the BitSet was not created by calling the BitSet(int nbits) constructor.

Your suggested approach of creating a new BitSet and reassigning it is perfectly OK. The original version will be garbage collected anyway. The modified method could look like this:

public static BitSet fold(BitSet bs, int nrOfTimes)
{
    BitSet temp;
    while (nrOfTimes-- > 0)
    {
        temp = bs.get(0, bs.size()/2);
        temp.or ( bs.get(bs.size()/2, bs.size()) );
        bs.clear();
        bs.or(temp);
    }
    return temp;
}