Permuting BitSet in Java

Question

I have this tool for permuting bits in BitSets:

com.stackexchange.codereview.util.BitPermutation.java:

package com.stackexchange.codereview.util;

import java.util.BitSet;
import java.util.Objects;

/**
 * This class is responsible for representing the bit permutations of 
 * {@code long} values. It, however, supports copying bits instead of strict 
 * permutations..
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 19, 2022)
 * @since 1.6 (Jan 19, 2022)
 */
public class BitPermutation {

    protected final int[] bitIndices;
    protected final int bitSetLength;
    
    public BitPermutation(BitSet bitSet) {
        this(Objects.requireNonNull(
                bitSet,
                "The input BitSet is null.").size());
    }
    
    public BitPermutation(int bits)  {
        checkNumberOfBits(bits);
        this.bitSetLength = bits;
        this.bitIndices = new int[bits];
        
        for (int bitIndex = 0; bitIndex < bits; ++bitIndex) {
            bitIndices[bitIndex] = bitIndex;
        }
    }
    
    public void swap(int index1, int index2) {
        checkIndex(index1);
        checkIndex(index2);
        
        int temp = bitIndices[index1];
        bitIndices[index1] = bitIndices[index2];
        bitIndices[index2] = temp;
    }
    
    public int getBitIndexAt(int index) {
        checkIndex(index);
        return bitIndices[index];
    }
    
    public void setBitIndex(int index, int value) {
        checkIndex(index);
        checkIndex(value);
        bitIndices[index] = value;
    }
    
    public int size() {
        return bitSetLength;
    }
    
    protected void checkIndex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException(
                    "index is not allowed to have negative values. (index = " 
                            + index + ")");
        }
        
        if (index >= bitSetLength) {
            throw new IllegalArgumentException(
                    "index is too large. (index = " 
                            + index 
                            + ") Must be at most " 
                            + (bitSetLength - 1));
        }
    }
    
    protected void checkNumberOfBits(int bits) {
        if (bits < 1) {
            throw new IllegalArgumentException(
                    "bits = " + bits + ". Must be at least 1.");
        }
    }
}

com.stackexchange.codereview.util.BitSetPermutator.java:

package com.stackexchange.codereview.util;

import java.util.BitSet;
import java.util.Objects;
import java.util.Random;

/**
 * This class provides the method for permuting bit sets.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 19, 2022)
 * @since 1.6 (Jan 19, 2022)
 */
public class BitSetPermutator {

    /**
     * Permutes the bits in {@code sourceBitSet} according to 
     * {@code bitPermutation}. The input bit set remains intact after the call 
     * to this method.
     * 
     * @param sourceBitSet the source bit set.
     * @param bitPermutation the bit permutation.
     * @return the result, permuted bit set.
     */
    public static BitSet permuteBitSet(BitSet sourceBitSet, 
                                       BitPermutation bitPermutation) {
        
        Objects.requireNonNull(sourceBitSet, 
                               "The input source BitSet is null.");
        
        Objects.requireNonNull(bitPermutation, 
                               "The input bit permutation is null.");
        
        int targetInts = sourceBitSet.size() / Integer.SIZE + 
                        (sourceBitSet.size() % Integer.SIZE != 0 ? 1 : 0);
        
        BitSet targetBitSet = new BitSet(targetInts);
        
        for (int sourceBitIndex = 0; 
                 sourceBitIndex < bitPermutation.size(); 
                 sourceBitIndex++) {
            
            int targetBitIndex = bitPermutation.getBitIndexAt(sourceBitIndex);
            
            setBits(sourceBitSet,
                    targetBitSet, 
                    sourceBitIndex, 
                    targetBitIndex);
        }
        
        return targetBitSet;
    }
    
    /**
     *
     * @param sourceBitSet
     * @param random
     * @return
     */
    public static BitSet shuffleBitSet(BitSet sourceBitSet, Random random) {
        Objects.requireNonNull(sourceBitSet, 
                               "The input source BitSet is null.");
        
        Objects.requireNonNull(random, "The random number generator is null.");
        
        BitPermutation bitPermutation = new BitPermutation(sourceBitSet);
        shuffleBitPermutation(bitPermutation, random);
        return permuteBitSet(sourceBitSet, bitPermutation);
    }
    
    // https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
    private static void shuffleBitPermutation(BitPermutation bitPermutation,
                                              Random random) {
        for (int i = bitPermutation.size() - 1; i > 0; --i) {
            int j = random.nextInt(i + 1);
            bitPermutation.swap(i, j);
        }
    }
    
    private static void setBits(BitSet sourceBitSet, 
                                BitSet targetBitSet,
                                int sourceBitIndex, 
                                int targetBitIndex) {
        boolean bit = readBit(sourceBitSet, sourceBitIndex);
        writeBit(targetBitSet, bit, targetBitIndex);
    }
    
    private static boolean readBit(BitSet sourceBitSet, int bitIndex) {
        return sourceBitSet.get(bitIndex);
    }
    
    private static void writeBit(BitSet targetBitSet, 
                                 boolean bit, 
                                 int bitIndex) {
        targetBitSet.set(bitIndex, bit);
    }
}

com.stackexchange.codereview.util.Demo.java:

package com.stackexchange.codereview.util;

import java.util.BitSet;
import java.util.Random;

public class Demo {
    
    public static void main(String[] args) {
        BitSet bs = new BitSet();
        bs.set(1);
        bs.set(2);
        bs.set(4);
        bs.set(10);
        bs.set(12);
        
        System.out.println("Before: " + bs);
        Random random = new Random();
        bs = BitSetPermutator.shuffleBitSet(bs, random);
        
        System.out.println("After:  " + bs);
    }
}

com.stackexchange.codereview.util.BitPermutationTest.java:

package com.stackexchange.codereview.util;

import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.*;

public class BitPermutationTest {
    
    private BitPermutation bitPermutation;
    
    @Before
    public void before() {
        bitPermutation = new BitPermutation(Long.SIZE);
    }
    
    @Test
    public void testSwap() {
        assertEquals(2, bitPermutation.getBitIndexAt(2));
        assertEquals(5, bitPermutation.getBitIndexAt(5));
        bitPermutation.swap(5, 2);
        assertEquals(5, bitPermutation.getBitIndexAt(2));
        assertEquals(2, bitPermutation.getBitIndexAt(5));
    }

    @Test
    public void testGetBitIndexAt() {
        for (int i = 0; i < bitPermutation.size(); ++i) {
            assertEquals(i, bitPermutation.getBitIndexAt(i));
        }
    }
    
    @Test
    public void testSetBitIndex() {
        bitPermutation.setBitIndex(26, 29);
        assertEquals(29, bitPermutation.getBitIndexAt(26));
        bitPermutation.setBitIndex(26, 30);
        assertEquals(30, bitPermutation.getBitIndexAt(26));
    }
}

com.stackexchange.codereview.util.BitSetPermutatorTest.java:

package com.stackexchange.codereview.util;

import java.util.BitSet;
import org.junit.Test;
import static org.junit.Assert.*;

public class BitSetPermutatorTest {
    
    @Test
    public void testPermuteBitSet() {
        BitSet bs = new BitSet();
        bs.set(0);
        bs.set(2);
        bs.set(3);
        bs.set(7);
        
        // Here, bs = 10001101.
        
        BitPermutation bp = new BitPermutation(8);
        
        for (int i = 0, j = bp.size() - 1; i < j; ++i, --j) {
            bp.swap(i, j);
        }
        
        BitSet permutedBitSet = BitSetPermutator.permuteBitSet(bs, bp);
        
        BitSet expectedBitSet = new BitSet();
        expectedBitSet.set(0);
        expectedBitSet.set(4);
        expectedBitSet.set(5);
        expectedBitSet.set(7);
        
        assertEquals(expectedBitSet, permutedBitSet);
    }
    
}

Critique request

My most concern here is the API design (naming, packaging, etc.), but, please, let me hear your thoughts whatever they might be.

Answer 1

Apart form the package name com.stackexchange.codereview that, unless the code is developed for codereview.stackexchange.com, might seem odd here are a couple of implementation details that stood out at a first glance:

Although I'm aware is only a personal preference, since there are high chances the java compiler optimises such details, the check for sourceBitSet's size oddity from BitSetPermutator#permuteBitSet method

int targetInts = sourceBitSet.size() / Integer.SIZE + 
                    (sourceBitSet.size() % Integer.SIZE != 0 ? 1 : 0);

I would switch it to a check for "eventy"

int targetInts = sourceBitSet.size() / Integer.SIZE + 
                    (sourceBitSet.size() % Integer.SIZE == 0 ? 0 : 1);

The shuffle algorithmic efficiency could be improved if the shuffle would be done only for the second half of the size while the random is generated for the first half of the size. Following implementation is just an example:

private static void shuffleBitPermutation(BitPermutation bitPermutation
                                        , Random random) {
        int size = bitPermutation.size();
        int halfSize = (int) Math.ceil(size/2);
        for (int i = size - 1; i > halfSize; --i) {
            int j = random.nextInt(halfSize);
            bitPermutation.swap(i, j);
        }
    }

Answer 2

BitPermutation follows single responsibility principle to the point where your API stops being object oriented and becomes procedural. Instead of having static utility methods that operate on simple data objects, put the responsibility of providing permutations into to BitPermutation class (the permuteBitSet method). You now get a functional interface from that. Then you have the data and the algorithm that requires the data together (this would be different if the algorithm took advantage of a generic type implemented by BitPermutation).

Your setBitIndex method allows repeating an index, which breaks the API promise. You can set all indices to 0 and the result is no longer a permutation. I haven't had enough coffe this morning, but it seems that the only safe way to manipulate the permutation so that it never breaks the internal data structure is to either swap two indices or set every index in a single operation. Or to provide a complex "permutation builder".

Answer 3

One remark on package naming:

package com.stackexchange.codereview.util;

This doesn't follow the recommendation to use some domain/identity that belongs to you as a person or organisation. If every StackExchange.CodeReview user were to follow your naming scheme, you'd get a package clash, as a .util subpackage is very likely to be created by more than one developer.

Your package name would be valid only for the StackExchange owners.

My recommendation would be something like

package com.stackexchange.coderodde.util;

including your StackExchange user name.

Answer 4

From the package structure it seems the unit tests are in the same folder with the tested code; if that's the case the tests should be kept in test dedicated folder, check unit test literature for details. If the tests and the tested code are in different folders probably the code is maintained with a build automation tool, detail that might worth mentioning from the perspective of least astonishment principle.