|
import static com.google.common.base.Preconditions.checkArgument; |
|
import static com.google.common.base.Preconditions.checkElementIndex; |
|
import static com.google.common.base.Preconditions.checkNotNull; |
|
|
|
import java.util.Arrays; |
|
import javax.annotation.concurrent.NotThreadSafe; |
|
|
|
/** |
|
* A long array that holds a fixed number of {@code ints} of a certain bit length. |
|
*/ |
|
@NotThreadSafe |
|
public final class CompactedArray { |
|
|
|
private static final int LONG_BITS = Long.BYTES * 8; |
|
// Position of 1 bit in LONG_BITS (which is always a power of 2) |
|
private static final int LONG_DIV_SHIFT = MathHelper.log2(LONG_BITS); |
|
private static final int LONG_MOD_MASK = LONG_BITS - 1; |
|
|
|
private static int getRawLengthFor(final int length, final int bitsPerInt) { |
|
// See Appendix 1 for ceilDiv implementation |
|
return MathHelper.ceilDiv(length * bitsPerInt, LONG_BITS); |
|
} |
|
|
|
private final long[] data; |
|
|
|
private final int length; |
|
private final int bitsPerValue; |
|
private final long bitmask; |
|
|
|
/** |
|
* Constructs an array that holds {@code length} integers with {@code bitsPerValue} bits each. |
|
* |
|
* @param length the number of values |
|
* @param bitsPerValue the bit-length of each value |
|
*/ |
|
public CompactedArray(final int length, final int bitsPerValue) { |
|
this(length, bitsPerValue, new long[getRawLengthFor(length, bitsPerValue)]); |
|
} |
|
|
|
/** |
|
* Constructs an array that holds {@code length} integers with {@code bitsPerValue} bits each |
|
* backed by the specified array. |
|
* |
|
* @param length the number of values |
|
* @param bitsPerValue the bit-length of each value |
|
* @param data the array by which this {@link CompactedArray} will be backed |
|
* @throws IllegalArgumentException if the array length is invalid |
|
*/ |
|
public CompactedArray(final int length, final int bitsPerValue, final long[] data) { |
|
this.data = checkNotNull(data, "packed"); |
|
// TODO Implement checkNonNegative |
|
this.length = checkNonNegative(length, "length"); |
|
this.bitsPerValue = checkNonNegative(bitsPerValue, "bitsPerInt"); |
|
this.bitmask = (1L << bitsPerValue) - 1; // e.g. bitsPerInt = 5 => bitmask = 0b11111 |
|
checkArgument(data.length == getRawLengthFor(length, bitsPerValue), |
|
"Invalid array length {} for {}", data.length, this); |
|
} |
|
|
|
// Division by LONG_BITS is equivalent to shifting by LONG_DIV_SHIFT. |
|
// Modulo LONG_BITS is equivalent to AND with LONG_MOD_MASK. |
|
|
|
/** |
|
* Returns the element at the specified position. |
|
* |
|
* @param index the index of the element to return |
|
* @return the element at the specified position |
|
* @throws IndexOutOfBoundsException if the index is out of range |
|
* ({@code index < 0 || index >= length()}) |
|
*/ |
|
public int get(final int index) { |
|
int bitOffset = checkElementIndex(index, length) * bitsPerValue; |
|
int offset = bitOffset >> LONG_DIV_SHIFT; |
|
int startBit = bitOffset & LONG_MOD_MASK; |
|
int nextOffset = (bitOffset + bitsPerValue - 1) >> LONG_DIV_SHIFT; |
|
|
|
long value = (data[offset] >>> startBit) & bitmask; |
|
|
|
if (offset != nextOffset) { |
|
int shiftBy = 64 - startBit; |
|
value |= (data[nextOffset] << shiftBy) & bitmask; |
|
} |
|
|
|
return (int) value; |
|
} |
|
|
|
/** |
|
* Replaces the element at the specified position with the given element. |
|
* |
|
* @param index the index of the element to replace |
|
* @param value the new element |
|
* @throws IndexOutOfBoundsException if index is out of range |
|
* ({@code index < 0 || index >= length()}) |
|
*/ |
|
public void set(final int index, final int value) { |
|
int bitOffset = checkElementIndex(index, length) * bitsPerValue; |
|
int offset = bitOffset >> LONG_DIV_SHIFT; |
|
int startBit = bitOffset & LONG_MOD_MASK; |
|
int nextOffset = (bitOffset + bitsPerValue - 1) >> LONG_DIV_SHIFT; |
|
long maskedValue = value & bitmask; |
|
|
|
data[offset] = (data[offset] & ~(bitmask << startBit)) | (maskedValue << startBit); |
|
|
|
if (offset != nextOffset) { |
|
int shiftBy = 64 - startBit; |
|
data[nextOffset] = |
|
(data[nextOffset] >>> shiftBy << shiftBy) | (maskedValue >> shiftBy); |
|
} |
|
} |
|
|
|
/** |
|
* Returns the fixed number of elements this array holds. |
|
* |
|
* @return the number of element this array holds |
|
*/ |
|
public int length() { |
|
return length; |
|
} |
|
|
|
/** |
|
* Gets the backing array of {@code longs}. |
|
* |
|
* @return the array by which this {@link CompactedArray} is backed |
|
*/ |
|
public long[] data() { |
|
return data; |
|
} |
|
|
|
@Override |
|
public int hashCode() { |
|
return Arrays.hashCode(data); |
|
} |
|
|
|
@Override |
|
public boolean equals(Object that) { |
|
return this == that || (that instanceof CompactedArray |
|
&& Arrays.equals(data, ((CompactedArray) that).data)); |
|
} |
|
} |