-
-
Save hugmanrique/debad817648dabb01b444aac851f0f92 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import static org.junit.jupiter.api.Assertions.assertEquals; | |
import static org.junit.jupiter.api.Assertions.assertThrows; | |
import org.junit.jupiter.api.Test; | |
public class CompactedArrayTests { | |
@Test | |
void testGet() { | |
long[] data = { 0x123456789ABCDEF0L, 0xABCDEF0123456789L}; | |
CompactedArray array = new CompactedArray(14, 9, data); | |
assertEquals(0b011110000, array.get(0)); | |
assertEquals(0b010101111, array.get(2)); | |
assertEquals(0b100010010, array.get(7)); | |
assertEquals(0b001001000, array.get(10)); | |
} | |
@Test | |
void testSetAndGet() { | |
CompactedArray array = new CompactedArray(20, 7); | |
array.set(0, 0b1011001); | |
assertEquals(0b1011001, array.get(0)); | |
assertEquals(0, array.get(1)); | |
array.set(9, 0b0110110); | |
assertEquals(0b0110110, array.get(9)); | |
assertEquals(0, array.get(8)); | |
assertEquals(0, array.get(10)); | |
array.set(12, 0b0001001); | |
assertEquals(0b0001001, array.get(12)); | |
assertEquals(0, array.get(11)); | |
assertEquals(0, array.get(13)); | |
array.set(19, 0b1101011); | |
assertEquals(0b1101011, array.get(19)); | |
assertEquals(0, array.get(18)); | |
} | |
@Test | |
void testLengthValidation() { | |
assertThrows(IllegalArgumentException.class, () -> { | |
long[] data = new long[0]; // Too small | |
new CompactedArray(2, 4, data); | |
}); | |
assertThrows(IllegalArgumentException.class, () -> { | |
long[] data = new long[2]; // Too big, can hold 14 words | |
new CompactedArray(6, 9, data); | |
}); | |
assertThrows(IllegalArgumentException.class, () -> { | |
long[] data = new long[5]; // Too small, can hold 320 words | |
new CompactedArray(21, 20, data); | |
}); | |
} | |
@Test | |
void testOutOfBounds() { | |
CompactedArray array = new CompactedArray(20, 7); | |
assertThrows(IndexOutOfBoundsException.class, () -> array.get(-2)); | |
assertThrows(IndexOutOfBoundsException.class, () -> array.get(20)); | |
assertThrows(IndexOutOfBoundsException.class, () -> array.get(451)); | |
assertThrows(IndexOutOfBoundsException.class, () -> array.set(-1, 3)); | |
assertThrows(IndexOutOfBoundsException.class, () -> array.set(20, 21)); | |
assertThrows(IndexOutOfBoundsException.class, () -> array.set(598, 43)); | |
} | |
@Test | |
void testEquality() { | |
long[] data = new long[1]; | |
CompactedArray numbers = new CompactedArray(4, 9, data); | |
CompactedArray sameNumbers = new CompactedArray(4, 9, data); | |
// Mutate backing array | |
numbers.set(1, 15); | |
assertEquals(numbers, sameNumbers); | |
assertEquals(sameNumbers, numbers); | |
assertEquals(numbers.get(1), sameNumbers.get(1)); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
MIT License | |
Copyright (c) 2020 Hugo Manrique | |
Permission is hereby granted, free of charge, to any person obtaining a copy | |
of this software and associated documentation files (the "Software"), to deal | |
in the Software without restriction, including without limitation the rights | |
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
copies of the Software, and to permit persons to whom the Software is | |
furnished to do so, subject to the following conditions: | |
The above copyright notice and this permission notice shall be included in all | |
copies or substantial portions of the Software. | |
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |
SOFTWARE. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment