* Instances of this class represent in a highly compacted form a nondecreasing sequence of natural * numbers. Instances are built by providing either an iterator returning the (nondecreasing) * sequence, or an {@linkplain Iterable iterable object} that provides such an iterator. In the * first case, you must also provide in advance the number of elements that will be returned and an * upper bound to their values (see below), and at the end of the construction the iterator will be * exhausted. * *
* An additional {@linkplain #get(long, long[], int, int) bulk method} makes it possible to extract * several consecutive entries at high speed, and {@link #getDelta(long)} computes directly the * difference between two consecutive elements. Moreover, the * {@link EliasFanoMonotoneLongBigListIterator#nextLong() nextLong()} method of an * {@linkplain #listIterator(long) iterator} will read read consecutive data much faster than * repeated calls to {@link #getLong(long)}. * *
* Methods to not usually perform bound checks on the arguments. Bounds checks can be enabled, * however, by enabling assertions. * *
* Because Java array are limited in size, it might not be possible to build certain instances: you * can use the {@link #fits(long, long)} methods to check is this might happen. In this case, please * use {@link EliasFanoMonotoneBigLongBigList}, which is slightly slower but has no such * limitations. * *
* This class is thread safe. * *
* Instances of this class can be {@linkplain #dump(String, ByteOrder) dumped} and then loaded uses * {@link MappedEliasFanoMonotoneLongBigList}. * *
* Given a monotone sequence 0 ≤ x0 ≤ x1 ≤ * … ≤ xn − 1 < u, where * u is a given upper bound (the size of the universe), the Elias–Fano * representation makes it possible to store it using at most 2 + log(u/n) * bits per element, which is very close to the information-theoretical lower bound ≈ log * e + log(u/n). A typical example is a list of pointer into records of * a large file: instead of using, for each pointer, a number of bit sufficient to express the * length of the file, the Elias–Fano representation makes it possible to use, for each * pointer, a number of bits roughly equal to the logarithm of the average length of a record. The * representation was introduced in Peter Elias, “Efficient storage and retrieval by content * and address of static files”, J. Assoc. Comput. Mach., 21(2):246−260, 1974, * and also independently by Robert Fano, “On the number of bits required to implement an * associative memory”, Memorandum 61, Computer Structures Group, Project MAC, MIT, Cambridge, * Mass., n.d., 1971. * *
* The elements of the sequence are recorded by storing separately the lower s = * ⌊log(u/n)⌋ bits and the remaining upper bits. The lower bits * are stored contiguously, whereas the upper bits are stored in an array of n + * u / 2s bits by setting, for each 0 ≤ i < * n, the bit of index xi / 2s + * i; the value can then be recovered by selecting the i-th bit of the * resulting bit array and subtracting i (note that this will work because the upper bits * are nondecreasing). * *
* This implementation uses {@link SimpleSelect} to support selection inside the upper-bits array, * and exploits {@link SimpleSelect#select(long, long[], int, int)} to implement * {@link #get(long, long[], int, int)}. * * @see EliasFanoMonotoneBigLongBigList * @see EliasFanoIndexedMonotoneLongBigList */ public class EliasFanoMonotoneLongBigList extends AbstractLongBigList implements Serializable { private static final long serialVersionUID = 4L; /** The length of the sequence. */ protected final long length; /** The number of lower bits. */ protected final int l; /** The upper bits, stored as unary gaps. */ protected transient long[] upperBits; /** The list of lower bits of each element, stored explicitly. */ protected long[] lowerBits; /** The select structure used to extract the upper bits. */ protected final SimpleSelect selectUpper; /** The mask for the lower bits. */ protected final long lowerBitsMask; /** Returns true if this class can accommodate a list with the given number of elements and upper bound. * * @param length the length of the list. * @param upperBound a strict upper bound to the values of the list. * @return true if this class can accommodate a list with the given number of elements and upper bound. */ public static boolean fits(final long length, final long upperBound) { final int l = length == 0 ? 0 : Math.max(0, Fast.mostSignificantBit(upperBound / length)); return (length + 1) * l < bits(MAX_ARRAY_SIZE); } protected EliasFanoMonotoneLongBigList(final long length, final int l, final long[] upperBits, final long[] lowerBits, final SimpleSelect selectUpper) { this.length = length; this.l = l; this.upperBits = upperBits; this.lowerBits = lowerBits; this.selectUpper = selectUpper; this.lowerBitsMask = (1L << l) - 1; } /** * Creates an Elias–Fano representation of the values returned by the given * {@linkplain Iterable iterable object}. * * @param list an iterable object returning nondecreasing natural numbers. */ public EliasFanoMonotoneLongBigList(final IntIterable list) { this((LongIterable) () -> LongIterators.wrap(list.iterator())); } /** * Creates an Elias–Fano representation of the values returned by the given * {@linkplain Iterable iterable object}. * * @param list an iterable object returning nondecreasing natural numbers. */ public EliasFanoMonotoneLongBigList(final ShortIterable list) { this((LongIterable) () -> LongIterators.wrap(list.iterator())); } /** * Creates an Elias–Fano representation of the values returned by the given * {@linkplain Iterable iterable object}. * * @param list an iterable object returning nondecreasing natural numbers. */ public EliasFanoMonotoneLongBigList(final ByteIterable list) { this((LongIterable) () -> LongIterators.wrap(list.iterator())); } /** * Creates an Elias–Fano representation of the values returned by the given * {@linkplain Iterable iterable object}. * * @param list an iterable object returning nondecreasing natural numbers. */ public EliasFanoMonotoneLongBigList(final LongIterable list) { this(computeParameters(list.iterator()), list.iterator()); } /** * Computes the number of elements and the last element returned by the given iterator. * * * @param iterator an iterator returning nondecreasing natural numbers. * @return a two-element array of longs containing the number of elements returned by the iterator * and the last returned element, respectively. */ private static long[] computeParameters(final LongIterator iterator) { long v = -1, prev = -1, c = 0; while(iterator.hasNext()) { v = iterator.nextLong(); if (prev > v) throw new IllegalArgumentException("The list of values is not monotone: " + prev + " > " + v); prev = v; c++; } return new long[] { c, v }; } /** * Creates an Elias–Fano representation of the values returned by an iterator, given that the * overall number of elements and an upper bound are provided, too. * *
* This constructor is particularly useful if the elements of the iterator are provided by some
* sequential source.
*
* @param n the number of elements returned by iterator.
* @param upperBound a strict upper bound to the values returned by iterator (note that
* it used to be non-strict).
* @param iterator an iterator returning nondecreasing natural numbers.
*/
public EliasFanoMonotoneLongBigList(final long n, final long upperBound, final ByteIterator iterator) {
this(new long[] { n, upperBound }, LongIterators.wrap(iterator));
}
/**
* Creates an Elias–Fano representation of the values returned by an iterator, given that the
* overall number of elements and an upper bound are provided, too.
*
*
* This constructor is particularly useful if the elements of the iterator are provided by some
* sequential source.
*
* @param n the number of elements returned by iterator.
* @param upperBound a strict upper bound to the values returned by iterator (note that
* it used to be non-strict).
* @param iterator an iterator returning nondecreasing natural numbers.
*/
public EliasFanoMonotoneLongBigList(final long n, final long upperBound, final ShortIterator iterator) {
this(new long[] { n, upperBound }, LongIterators.wrap(iterator));
}
/**
* Creates an Elias–Fano representation of the values returned by an iterator, given that the
* overall number of elements and an upper bound are provided, too.
*
*
* This constructor is particularly useful if the elements of the iterator are provided by some
* sequential source.
*
* @param n the number of elements returned by iterator.
* @param upperBound a strict upper bound to the values returned by iterator (note that
* it used to be non-strict).
* @param iterator an iterator returning nondecreasing natural numbers.
*/
public EliasFanoMonotoneLongBigList(final long n, final long upperBound, final IntIterator iterator) {
this(new long[] { n, upperBound }, LongIterators.wrap(iterator));
}
/**
* Creates an Elias–Fano representation of the values returned by an iterator, given that the
* overall number of elements and an upper bound are provided, too.
*
*
* This constructor is particularly useful if the elements of the iterator are provided by some
* sequential source.
*
* @param n the number of elements returned by iterator.
* @param upperBound a strict upper bound to the values returned by iterator (note that
* it used to be non-strict).
* @param iterator an iterator returning nondecreasing natural numbers.
*/
public EliasFanoMonotoneLongBigList(final long n, final long upperBound, final LongIterator iterator) {
this(new long[] { n, upperBound }, iterator);
}
/**
* Creates an Elias–Fano representation of the values returned by an iterator, given that the
* overall number of elements and an upper bound are provided, too.
*
*
* This constructor is used only internally, to work around the usual problems caused by the
* obligation to call this() before anything else.
*
* @param a an array containing the number of elements returned by iterator and a
* strict upper bound to the values returned by iterator (note that it used
* to be non-strict).
* @param iterator an iterator returning nondecreasing natural numbers.
*/
protected EliasFanoMonotoneLongBigList(final long[] a, final LongIterator iterator) {
length = a[0];
long v = -1;
final long upperBound = a[1];
l = length == 0 ? 0 : Math.max(0, Fast.mostSignificantBit(upperBound / length));
lowerBitsMask = (1L << l) - 1;
final long lowerBitsMask = (1L << l) - 1;
final LongArrayBitVector lowerBitsVector = LongArrayBitVector.getInstance();
final LongBigList lowerBitsList = lowerBitsVector.asLongBigList(l);
if ((length + 1) * l >= bits(MAX_ARRAY_SIZE)) throw new IllegalArgumentException("Lower-bits array is too large: please use EliasFanoMonotoneBigLongBigList");
lowerBitsList.size(length + 1);
final BitVector upperBits = LongArrayBitVector.getInstance().length(length + (upperBound >>> l) + 2);
long last = -1;
long finalUpperBound = upperBound;
for(long i = 0; i < length; i++) {
v = iterator.nextLong();
if (v > upperBound) throw new IllegalArgumentException("Too large value: " + v + " > " + upperBound);
// Correct for users of previous versions, where upperBound was non-strict
if (v == finalUpperBound) upperBits.length(length + (++finalUpperBound >>> l) + 2);
if (v < last) throw new IllegalArgumentException("Values are not nondecreasing: " + v + " < " + last);
if (l != 0) lowerBitsList.set(i, v & lowerBitsMask);
upperBits.set((v >>> l) + i);
last = v;
}
// Sentinel value; if the user provided a non-strict upper bound, finalUpperBound will be fixed in
// the loop above.
if (l != 0) lowerBitsList.set(length, finalUpperBound & lowerBitsMask);
upperBits.set((finalUpperBound >>> l) + length);
if (iterator.hasNext()) throw new IllegalArgumentException("There are more than " + length + " values in the provided iterator");
// The initialization for l == 0 avoids tests for l == 0 throughout the code.
this.lowerBits = l == 0 ? new long[1] : lowerBitsVector.bits();
this.upperBits = upperBits.bits();
selectUpper = new SimpleSelect(upperBits);
}
public long numBits() {
return selectUpper.numBits() + selectUpper.bitVector().length() + bits(lowerBits.length);
}
/**
* Returns the element at the specified position.
*
* @param index a position in the list.
* @return the element at the specified position; if {@code index} is out of bounds, behavior is
* undefined.
*/
@Override
public long getLong(final long index) {
assert index >= 0;
assert index < length;
final int l = this.l;
final long upperBits = selectUpper.select(index) - index;
final long position = index * l;
final int startWord = word(position);
final int startBit = bit(position);
final long result = lowerBits[startWord] >>> startBit;
return upperBits << l | (startBit + l <= Long.SIZE ? result : result | lowerBits[startWord + 1] << -startBit) & lowerBitsMask;
}
/**
* Returns the difference between two consecutive elements of the sequence.
*
* @param index the index of an element (smaller then {@link #size64()} - 1).
* @return the difference between the element of position {@code index + 1} and that of position
* {@code index}; if {@code index} is out of bounds, behavior is undefined.
* @see #get(long, long[])
*/
public long getDelta(long index) {
assert index >= 0;
assert index < length - 1;
final long[] dest = new long[2];
selectUpper.select(index, dest, 0, 2);
final int l = this.l;
final long[] lowerBits = this.lowerBits;
long position = index * l;
int startWord = word(position);
int startBit = bit(position);
long first = lowerBits[startWord] >>> startBit;
first = dest[0] - index++ << l | (startBit + l <= Long.SIZE ? first : first | lowerBits[startWord + 1] << -startBit) & lowerBitsMask;
position += l;
startWord = word(position);
startBit = bit(position);
long second = lowerBits[startWord] >>> startBit;
second = dest[1] - index << l | (startBit + l <= Long.SIZE ? second : second | lowerBits[startWord + 1] << -startBit) & lowerBitsMask;
return second - first;
}
/**
* Extracts a number of consecutive entries into a given array fragment.
*
* @param index the index of the first entry returned.
* @param dest the destination array; it will be filled with {@code length} consecutive entries
* starting at position {@code offset}; must be of length greater than {@code offset}.
* @param offset the first position written in {@code dest}.
* @param length the number of elements written in {@code dest} starting at {@code offset}.
* @return {@code dest}; if the arguments are out of bounds, behavior is undefined.
* @see #get(long, long[])
*/
public long[] get(long index, final long dest[], final int offset, final int length) {
assert index >= 0;
assert index < this.length;
assert offset >= 0;
assert offset < dest.length;
assert length >= 0;
assert offset + length <= dest.length;
selectUpper.select(index, dest, offset, length);
final int l = this.l;
final long lowerBitsMask = this.lowerBitsMask;
final long[] lowerBits = this.lowerBits;
long position = index * l;
for (int i = 0; i < length; i++) {
final int startWord = word(position);
final int startBit = bit(position);
final long result = lowerBits[startWord] >>> startBit;
dest[offset + i] = dest[offset + i] - index++ << l | (startBit + l <= Long.SIZE ? result : result | lowerBits[startWord + 1] << -startBit) & lowerBitsMask;
position += l;
}
return dest;
}
/**
* Extracts a number of consecutive entries into a given array.
*
* @param index the index of the first entry returned.
* @param dest the destination array, of nonzero length; it will be filled with consecutive entries.
* @return {@code dest}; if {@code index} is out of bounds or {@code dest} has length zero, behavior
* is undefined.
* @see #get(long, long[], int, int)
*/
public long[] get(final long index, final long dest[]) {
return get(index, dest, 0, dest.length);
}
/**
* A list iterator over the values of this {@link EliasFanoMonotoneLongBigList}.
*
*
* {@linkplain #nextLong() Forward iteration} will be faster than iterated calls to * {@link EliasFanoMonotoneLongBigList#getLong(long) getLong()}. Backward iteration is available, * but it will perform similarly to {@link EliasFanoMonotoneLongBigList#getLong(long) getLong()}. * *
* Additional unsafe methods {@link #nextLongUnsafe()} and {@link #previousLongUnsafe()} * iterate without checking for the existence of a next element. */ public class EliasFanoMonotoneLongBigListIterator implements LongBigListIterator { /** The index of the next element to return. */ protected long index; /** The current word in the array of upper bits. */ protected int word; /** The current window. */ protected long window; /** The current position in the array of lower bits. */ protected long lowerBitsPosition; protected EliasFanoMonotoneLongBigListIterator(final long from) { index = from; final long position = selectUpper.select(from); window = upperBits[word = word(position)] & -1L << position; lowerBitsPosition = index * l; } private long getNextUpperBits() { while (window == 0) window = upperBits[++word]; final long upperBits = bits(word) + Long.numberOfTrailingZeros(window) - index++; window &= window - 1; return upperBits; } @Override public long previousIndex() { return index - 1; } @Override public long nextIndex() { return index; } @Override public boolean hasPrevious() { return index > 0; } @Override public boolean hasNext() { return index < length; } @Override public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); return nextLongUnsafe(); } /** * Returns the same element as {@link #nextLong()}, if {@link #hasNext()} is true; otherwise, * behavior is undefined. * * @return the same element as {@link #nextLong()}, if {@link #hasNext()} is true; otherwise, * behavior is undefined. */ public long nextLongUnsafe() { final int l = EliasFanoMonotoneLongBigList.this.l; final int startWord = word(lowerBitsPosition); final int startBit = bit(lowerBitsPosition); long lower = lowerBits[startWord] >>> startBit; if (startBit + l > Long.SIZE) lower |= lowerBits[startWord + 1] << -startBit; lowerBitsPosition += l; return getNextUpperBits() << l | lower & lowerBitsMask; } @Override public long previousLong() { if (!hasPrevious()) throw new NoSuchElementException(); return previousLongUnsafe(); } /** * Returns the same element as {@link #previousLong()}, if {@link #hasPrevious()} is true; * otherwise, behavior is undefined. * * @return the same element as {@link #previousLong()}, if {@link #hasPrevious()} is true; * otherwise, behavior is undefined. */ public long previousLongUnsafe() { final int l = EliasFanoMonotoneLongBigList.this.l; --index; final long position = selectUpper.select(index); window = upperBits[word = word(position)] & -1L << position; lowerBitsPosition = index * l; final int startWord = word(lowerBitsPosition); final int startBit = bit(lowerBitsPosition); long lower = lowerBits[startWord] >>> startBit; if (startBit + l > Long.SIZE) lower |= lowerBits[startWord + 1] << -startBit; return (position - index) << l | lower & lowerBitsMask; } } /** * Returns a list iterator over the values of this {@link EliasFanoMonotoneLongBigList}. * *
* Forward iteration will be faster than iterated calls to * {@link EliasFanoMonotoneLongBigList#getLong(long) getLong()}. Backward iteration is available, * but it will perform similarly to {@link EliasFanoMonotoneLongBigList#getLong(long) getLong()}. * * @param from the starting position in the sequence. * @return a list iterator over the values of this {@link EliasFanoMonotoneLongBigList}. * @see EliasFanoMonotoneLongBigListIterator */ @Override public EliasFanoMonotoneLongBigListIterator listIterator(final long from) { return new EliasFanoMonotoneLongBigListIterator(from); } /** * Returns a list iterator over the values of this {@link EliasFanoMonotoneLongBigList}. * *
* Forward iteration will be faster than iterated calls to * {@link EliasFanoMonotoneLongBigList#getLong(long) getLong()}. Backward iteration is available, * but it will perform similarly to {@link EliasFanoMonotoneLongBigList#getLong(long) getLong()}. * * @return a list iterator over the values of this {@link EliasFanoMonotoneLongBigList}. * @see EliasFanoMonotoneLongBigListIterator */ @Override public EliasFanoMonotoneLongBigListIterator listIterator() { return new EliasFanoMonotoneLongBigListIterator(0); } /** * Returns a list iterator over the values of this {@link EliasFanoMonotoneLongBigList}. * *
* Forward iteration will be faster than iterated calls to * {@link EliasFanoMonotoneLongBigList#getLong(long) getLong()}. Backward iteration is available, * but it will perform similarly to {@link EliasFanoMonotoneLongBigList#getLong(long) getLong()}. * * @return a list iterator over the values of this {@link EliasFanoMonotoneLongBigList}. * @see EliasFanoMonotoneLongBigListIterator */ @Override public EliasFanoMonotoneLongBigListIterator iterator() { return listIterator(); } @Override public long size64() { return length; } /** * Dumps this list's lower bits in {@linkplain ByteOrder#nativeOrder() native order} so that it can * be used with {@link MappedEliasFanoMonotoneLongBigList}. * * @param basename the basename of the generated files. */ public void dump(final String basename) throws IOException { dump(basename, ByteOrder.nativeOrder()); } /** * Dumps this list's lower bits so that it can be used with * {@link MappedEliasFanoMonotoneLongBigList}. * *
* Two files will be generated: a serialized object with extension * {@link MappedEliasFanoMonotoneLongBigList#OBJECT_EXTENSION} and a list of longs in the specified * {@linkplain ByteOrder byte order} with extension * {@link MappedEliasFanoMonotoneLongBigList#LOWER_BITS_EXTENSION}. * * @param basename the basename of the generated files. * @param byteOrder the desired byte order. */ public void dump(final String basename, final ByteOrder byteOrder) throws IOException { final long[][] upperBitsBig = BigArrays.wrap(upperBits); BinIO.storeObject(new MappedEliasFanoMonotoneLongBigList(length, l, upperBitsBig, new SimpleBigSelect(upperBitsBig, selectUpper.bitVector().length()), byteOrder == ByteOrder.LITTLE_ENDIAN), basename + MappedEliasFanoMonotoneLongBigList.OBJECT_EXTENSION); final FileChannel fileChannel = FileChannel.open(new File(basename + MappedEliasFanoMonotoneLongBigList.LOWER_BITS_EXTENSION).toPath(), StandardOpenOption.WRITE, StandardOpenOption.CREATE); final ByteBuffer byteBuffer = ByteBuffer.allocateDirect(1024); byteBuffer.order(byteOrder); for (final long l : lowerBits) { byteBuffer.putLong(l); if (!byteBuffer.hasRemaining()) { byteBuffer.flip(); fileChannel.write(byteBuffer); byteBuffer.clear(); } } byteBuffer.flip(); fileChannel.write(byteBuffer); fileChannel.close(); } private void readObject(final ObjectInputStream s) throws IOException, ClassNotFoundException { s.defaultReadObject(); upperBits = selectUpper.bitVector().bits(); // A fix that avoids bumping the serial id from 4L if (lowerBits.length == 0) lowerBits = new long[1]; } }