Sparse BitArray implementation in Java

SparseBitArray.java

package com.sangupta.jerry.ds.bitarray;

import java.io.IOException;

import com.sangupta.jerry.util.BitUtils;
import com.sangupta.jerry.util.ByteArrayUtils;

import net.jcip.annotations.NotThreadSafe;

@NotThreadSafe
public class SparseBitArray implements BitArray {
	
	/**
	 * Bits per element - we are using <code>long</code> for elements
	 * and thus 64 bits
	 */
	private final int BITS_PER_ELEMENT = Long.SIZE;
	
	/**
	 * Number of bytes per element
	 */
	private final int BYTES_PER_ELEMENT = BITS_PER_ELEMENT / 8;
	
	/**
	 * Number of buckets that we need to initialize
	 */
	private final int numBuckets;
	
	/**
	 * Bits held in one bucket
	 */
	private final int bitsPerBucket;
	
	/**
	 * Number of elements or long values per bucket
	 */
	private final int elementsNeededPerBucket;
	
	/**
	 * Maximum index that we can accomodate in this sparse array
	 */
	private final int maxIndex;
	
	/**
	 * The backing array
	 */
	private final long[][] array;
	
	/**
	 * Constructor
	 * 
	 * @param numBuckets
	 * @param bucketSize
	 */
	public SparseBitArray(int numBuckets, int bucketSize) {
		this.numBuckets = numBuckets;
		this.bitsPerBucket = bucketSize;
		
		this.maxIndex = bucketSize * numBuckets;
		
		int elements = this.bitsPerBucket / BITS_PER_ELEMENT;
		if(this.bitsPerBucket % BITS_PER_ELEMENT > 0) {
			elements++;
		}
		this.elementsNeededPerBucket = elements;
		
		this.array = new long[this.numBuckets][];
	}

	@Override
	public void close() throws IOException {
		// nothing to do here
	}

	@Override
	public boolean getBit(int index) {
		if(index < 0) {
			throw new IndexOutOfBoundsException("Index is out of range: " + index);
		}
		
		if(index > this.maxIndex) {
			throw new IndexOutOfBoundsException("Index is out of range: " + index);
		}
		
		int bucket = index / this.bitsPerBucket;
		if(this.array[bucket] == null) {
			return false;
		}
		
		int subIndex = index % this.bitsPerBucket;
		int element = subIndex / BITS_PER_ELEMENT;
		int bit = subIndex % BITS_PER_ELEMENT;
		
		long[] subArray = this.array[bucket];
		long value = subArray[element];
		
		return BitUtils.isBitSet(value, bit);
	}

	@Override
	public boolean setBit(int index) {
		if(index < 0) {
			throw new IndexOutOfBoundsException("Index is out of range: " + index);
		}
		
		if(index > this.maxIndex) {
			throw new IndexOutOfBoundsException("Index is out of range: " + index);
		}
		
		int bucket = index / this.bitsPerBucket;
		if(this.array[bucket] == null) {
			this.array[bucket] = new long[this.elementsNeededPerBucket];
		}
		
		int subIndex = index % this.bitsPerBucket;
		
		int element = subIndex / BITS_PER_ELEMENT;
		int bit = subIndex % BITS_PER_ELEMENT;
		
		long[] subArray = this.array[bucket];
		long value = subArray[element];
		long updated = BitUtils.setBit(value, bit);
		
		if(value != updated) {
			subArray[element] = updated;
			return true;
		}
		
		return false;
	}

	@Override
	public void clear() {
		for(int bucket = 0; bucket < this.numBuckets; bucket++) {
			this.array[bucket] = null;
		}
	}

	@Override
	public void clearBit(int index) {
		if(index < 0) {
			throw new IndexOutOfBoundsException("Index is out of range: " + index);
		}
		
		if(index > this.maxIndex) {
			throw new IndexOutOfBoundsException("Index is out of range: " + index);
		}
		
		int bucket = index / this.bitsPerBucket;
		if(this.array[bucket] == null) {
			return;
		}
		
		int subIndex = index % this.bitsPerBucket;
		int element = subIndex / BITS_PER_ELEMENT;
		int bit = subIndex % BITS_PER_ELEMENT;
		
		long[] subArray = this.array[bucket];
		long value = subArray[element];
		long updated = BitUtils.clearBit(value, bit);
		
		this.array[bucket][element] = updated;
	}

	@Override
	public boolean setBitIfUnset(int index) {
		if(index < 0) {
			throw new IndexOutOfBoundsException("Index is out of range: " + index);
		}
		
		if(index > this.maxIndex) {
			throw new IndexOutOfBoundsException("Index is out of range: " + index);
		}
		
		int bucket = index / this.bitsPerBucket;
		if(this.array[bucket] == null) {
			this.array[bucket] = new long[this.elementsNeededPerBucket];
		}
		
		int subIndex = index % this.bitsPerBucket;
		
		int element = subIndex / BITS_PER_ELEMENT;
		int bit = subIndex % BITS_PER_ELEMENT;
		
		long[] subArray = this.array[bucket];
		long value = subArray[element];
		long updated = BitUtils.setBit(value, bit);
		
		if(value != updated) {
			subArray[element] = updated;
			return true;
		}
		
		return false;
	}

	@Override
	public void or(BitArray bitArray) {
		throw new RuntimeException("not yet implemented");
	}

	@Override
	public void and(BitArray bitArray) {
		if(array == null) {
			throw new IllegalArgumentException("Array to be combined with cannot be null");
		}
		
		if(bitArray instanceof SparseBitArray) {
throw new RuntimeException("not yet implemented");
	}

	@Override
	public int bitSize() {
		return this.maxIndex;
	}

	@Override
	public int numBytes() {
		return this.numBuckets * this.elementsNeededPerBucket * (this.BITS_PER_ELEMENT / BYTES_PER_ELEMENT);
	}

	@Override
	public byte[] toByteArray() {
		throw new RuntimeException("not yet implemented");
	}

	@Override
	public int getHighestBitSet() {
		throw new RuntimeException("not yet implemented");
	}

	@Override
	public int getLowestBitSet() {
		throw new RuntimeException("not yet implemented");
	}

	@Override
	public int getNextSetBit(int fromIndex) {
		throw new RuntimeException("not yet implemented");
	}

}