Space-efficient index that enables fast rank/range search operations on a sorted sequence of long.

Implementation of the PGM-Index described at https://pgm.di.unipi.it/, based on the paper

  Paolo Ferragina and Giorgio Vinciguerra.
  The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds.
  PVLDB, 13(8): 1162-1175, 2020.

It provides rank and range search operations. indexOf() is faster than B+Tree, and the index is much more compact. contains() is between 4x to 7x slower than IntHashSet#contains(), but between 2.5x to 3x faster than Arrays#binarySearch.

Its compactness (40KB for 200MB of keys) makes it efficient for very large collections, the index fitting easily in the L2 cache. The epsilon parameter should be set according to the desired space-time trade-off. A smaller value makes the estimation more precise and the range smaller but at the cost of increased space usage. In practice, epsilon 64 is a good sweet spot.

Internally the index uses an optimal piecewise linear mapping from keys to their position in the sorted order. This mapping is represented as a sequence of linear models (segments) which are themselves recursively indexed by other piecewise linear mappings.

Nested and Inner Type Summary

Modifier and Type	Class and Description
public static class	LongPgmIndex.LongBuilder Builds a `LongPgmIndex` on a provided sorted list of keys.
private static class	LongPgmIndex.LongEmptyPgmIndex Empty immutable PGM Index.
protected static class	LongPgmIndex.RangeIterator Iterator over a range of elements in a sorted array.

Field Summary

Modifier and Type	Field and Description
public static final int	BEYOND_EPSILON_JUMP Initial value of the exponential jump when scanning out of the epsilon range.
public static final int	DOUBLE_KEY_SIZE 2x `KEY_SIZE`.
public static final LongPgmIndex	EMPTY Empty immutable LongPgmIndex.
public static final int	EPSILON Epsilon approximation range when searching the list of keys.
public final int	epsilon The epsilon range used to build this index.
public static final int	EPSILON_RECURSIVE Epsilon approximation range for the segments layers.
public final int	epsilonRecursive The recursive epsilon range used to build this index.
public final long	firstKey The lowest key in `keys`.
public static final int	KEY_SIZE Size of a key, measured in `Integer#BYTES` because the key is stored in an int[].
public final LongArrayList	keys The list of keys for which this index is built.
public final long	lastKey The highest key in `keys`.
public final int[]	levelOffsets The offsets in `segmentData` of the first segment of each segment level.
public static final int	SEGMENT_DATA_SIZE Data size of a segment, measured in `Integer#BYTES`, because segments are stored in an int[].
public final int[]	segmentData The index data.
public final int	size The size of the key set.

Access	Constructor and Description
private	LongPgmIndex(LongArrayList keys, int size, int epsilon, int epsilonRecursive, int[] levelOffsets, int[] segmentData)
private	LongPgmIndex() Empty set constructor.

Method Summary

Modifier and Type	Method and Description
private int	approximateIndex(long key, int segmentDataIndex, int[] segmentData)
public boolean	contains(long key) Returns whether this key set contains the given key.
private int	Returns: the segment data index; or -1 if none. findSegment(long key) Finds the segment responsible for a given key, that is, the rightmost segment having its first key <= the searched key.
public <T extends LongProcedure> T	forEachInRange(T procedure, long minKey, long maxKey) Applies `procedure` to the keys in the list that are greater than or equal to `minKey` (inclusive), and less than or equal to `maxKey` (inclusive).
private static long	getIntercept(int segmentDataIndex, int[] segmentData)
private long	getKey(int segmentDataIndex, int[] segmentData)
private static double	getSlope(int segmentDataIndex, int[] segmentData)
public int	Returns: The index of the searched key if it is present; otherwise, `(-(<i>insertion point</i>) - 1)`. The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or `keys`#`size()` if all the elements are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found. indexOf(long key) Searches the specified key, and returns its index in the element list.
public boolean	isEmpty() Returns whether this key set is empty.
public long	ramBytesAllocated() Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated. Estimates the allocated memory.
public long	ramBytesUsed() Implements com.carrotsearch.hppc.Accountable.ramBytesUsed. Estimates the bytes that are actually used.
public int	rangeCardinality(long minKey, long maxKey) Returns the number of keys in the list that are greater than or equal to `minKey` (inclusive), and less than or equal to `maxKey` (inclusive).
public Iterator<LongCursor>	rangeIterator(long minKey, long maxKey) Returns an iterator over the keys in the list that are greater than or equal to `minKey` (inclusive), and less than or equal to `maxKey` (inclusive).
public int	Returns: The index of the searched key if it is present; otherwise, the `insertion point`. The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or `keys`#`size()` if all the elements are less than the specified key. Note that this method always returns a value >= 0. rank(long x) Returns, for any value `x`, the number of keys in the sorted list which are smaller than `x`.
public int	size() Returns the size of the key set.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

BEYOND_EPSILON_JUMP	back to summary
public static final int BEYOND_EPSILON_JUMP Initial value of the exponential jump when scanning out of the epsilon range.

DOUBLE_KEY_SIZE	back to summary
public static final int DOUBLE_KEY_SIZE 2x `KEY_SIZE`.

EMPTY	back to summary
public static final LongPgmIndex EMPTY Empty immutable LongPgmIndex.

EPSILON	back to summary
public static final int EPSILON Epsilon approximation range when searching the list of keys. Controls the size of the returned search range, strictly greater than 0. It should be set according to the desired space-time trade-off. A smaller value makes the estimation more precise and the range smaller but at the cost of increased space usage. With EPSILON=64 the benchmark with 200MB of keys shows that this PGM index requires only 2% additional memory on average (40KB). It depends on the distribution of the keys. This epsilon value is good even for 2MB of keys. With EPSILON=32: +5% speed, but 4x space (160KB).

EPSILON

back to summary

public static final int EPSILON

Epsilon approximation range when searching the list of keys. Controls the size of the returned search range, strictly greater than 0. It should be set according to the desired space-time trade-off. A smaller value makes the estimation more precise and the range smaller but at the cost of increased space usage.

With EPSILON=64 the benchmark with 200MB of keys shows that this PGM index requires only 2% additional memory on average (40KB). It depends on the distribution of the keys. This epsilon value is good even for 2MB of keys. With EPSILON=32: +5% speed, but 4x space (160KB).

epsilon	back to summary
public final int epsilon The epsilon range used to build this index.

EPSILON_RECURSIVE	back to summary
public static final int EPSILON_RECURSIVE Epsilon approximation range for the segments layers. Controls the size of the search range in the hierarchical segment lists, strictly greater than 0.

epsilonRecursive	back to summary
public final int epsilonRecursive The recursive epsilon range used to build this index.

firstKey	back to summary
public final long firstKey The lowest key in `keys`.

KEY_SIZE	back to summary
public static final int KEY_SIZE Size of a key, measured in `Integer#BYTES` because the key is stored in an int[].

keys	back to summary
public final LongArrayList keys The list of keys for which this index is built. It is sorted and may contain duplicate elements.

lastKey	back to summary
public final long lastKey The highest key in `keys`.

levelOffsets	back to summary
public final int[] levelOffsets The offsets in `segmentData` of the first segment of each segment level.

SEGMENT_DATA_SIZE	back to summary
public static final int SEGMENT_DATA_SIZE Data size of a segment, measured in `Integer#BYTES`, because segments are stored in an int[].

segmentData	back to summary
public final int[] segmentData The index data. It contains all the segments for all the levels.

size	back to summary
public final int size The size of the key set. That is, the number of distinct elements in `keys`.

LongPgmIndex	back to summary
private LongPgmIndex(LongArrayList keys, int size, int epsilon, int epsilonRecursive, int[] levelOffsets, int[] segmentData)

LongPgmIndex	back to summary
private LongPgmIndex() Empty set constructor.

Method Detail

approximateIndex	back to summary
private int approximateIndex(long key, int segmentDataIndex, int[] segmentData)

contains	back to summary
public boolean contains(long key) Returns whether this key set contains the given key.

findSegment	back to summary
private int findSegment(long key) Finds the segment responsible for a given key, that is, the rightmost segment having its first key <= the searched key. Returns:int the segment data index; or -1 if none.

findSegment

back to summary

private int findSegment(long key)

Finds the segment responsible for a given key, that is, the rightmost segment having its first key <= the searched key.

Returns:int: the segment data index; or -1 if none.

forEachInRange	back to summary
public <T extends LongProcedure> T forEachInRange(T procedure, long minKey, long maxKey) Applies `procedure` to the keys in the list that are greater than or equal to `minKey` (inclusive), and less than or equal to `maxKey` (inclusive).

getIntercept	back to summary
private static long getIntercept(int segmentDataIndex, int[] segmentData)

getKey	back to summary
private long getKey(int segmentDataIndex, int[] segmentData)

getSlope	back to summary
private static double getSlope(int segmentDataIndex, int[] segmentData)

indexOf back to summary

indexOf	back to summary
public int indexOf(long key) Searches the specified key, and returns its index in the element list. If multiple elements are equal to the specified key, there is no guarantee which one will be found. Returns:int The index of the searched key if it is present; otherwise, `(-(<i>insertion point</i>) - 1)`. The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or `keys`#`size()` if all the elements are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

public int indexOf(long key)

Searches the specified key, and returns its index in the element list. If multiple elements are equal to the specified key, there is no guarantee which one will be found.

Returns:int: The index of the searched key if it is present; otherwise, (-(<i>insertion point</i>) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or keys#size() if all the elements are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

isEmpty	back to summary
public boolean isEmpty() Returns whether this key set is empty.

ramBytesAllocated	back to summary
public long ramBytesAllocated() Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated. Estimates the allocated memory. It does not count the memory for the list of keys, only for the index itself. Returns:long Doc from com.carrotsearch.hppc.Accountable.ramBytesAllocated. Ram allocated in bytes Annotations @Override

ramBytesAllocated

back to summary

public long ramBytesAllocated()

Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated.

Estimates the allocated memory. It does not count the memory for the list of keys, only for the index itself.

Returns:long

Doc from com.carrotsearch.hppc.Accountable.ramBytesAllocated.

Ram allocated in bytes

Annotations

@Override

ramBytesUsed	back to summary
public long ramBytesUsed() Implements com.carrotsearch.hppc.Accountable.ramBytesUsed. Estimates the bytes that are actually used. It does not count the memory for the list of keys, only for the index itself. Returns:long Doc from com.carrotsearch.hppc.Accountable.ramBytesUsed. Ram used in bytes Annotations @Override

ramBytesUsed

back to summary

public long ramBytesUsed()

Implements com.carrotsearch.hppc.Accountable.ramBytesUsed.

Estimates the bytes that are actually used. It does not count the memory for the list of keys, only for the index itself.

Returns:long

Doc from com.carrotsearch.hppc.Accountable.ramBytesUsed.

Ram used in bytes

Annotations

@Override

rangeCardinality	back to summary
public int rangeCardinality(long minKey, long maxKey) Returns the number of keys in the list that are greater than or equal to `minKey` (inclusive), and less than or equal to `maxKey` (inclusive).

rangeIterator	back to summary
public Iterator<LongCursor> rangeIterator(long minKey, long maxKey) Returns an iterator over the keys in the list that are greater than or equal to `minKey` (inclusive), and less than or equal to `maxKey` (inclusive).

rank back to summary

rank	back to summary
public int rank(long x) Returns, for any value `x`, the number of keys in the sorted list which are smaller than `x`. It is equal to `indexOf` if `x` belongs to the list, or -`indexOf`-1 otherwise. If multiple elements are equal to the specified key, there is no guarantee which one will be found. Returns:int The index of the searched key if it is present; otherwise, the `insertion point`. The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or `keys`#`size()` if all the elements are less than the specified key. Note that this method always returns a value >= 0.

public int rank(long x)

Returns, for any value x, the number of keys in the sorted list which are smaller than x. It is equal to indexOf if x belongs to the list, or -indexOf-1 otherwise.

If multiple elements are equal to the specified key, there is no guarantee which one will be found.

Returns:int: The index of the searched key if it is present; otherwise, the insertion point. The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or keys#size() if all the elements are less than the specified key. Note that this method always returns a value >= 0.

size	back to summary
public int size() Returns the size of the key set. That is, the number of distinct elements in `keys`.

com.carrotsearch.hppc back to summary

public Class LongPgmIndex.LongBuilder

Class Inheritance

extends Object
implements SegmentConsumer, Accountable

java.lang.Object
com.carrotsearch.hppc.LongPgmIndex.LongBuilder

All Implemented Interfaces

com.carrotsearch.hppc.Accountable, com.carrotsearch.hppc.PlaModel.SegmentConsumer

Builds a LongPgmIndex on a provided sorted list of keys.

Field Summary

Modifier and Type	Field and Description
protected int	epsilon
protected int	epsilonRecursive
protected LongArrayList	keys
protected int	numSegments
protected PlaModel	plam
protected IntArrayList	segmentData
protected int	size

Constructor Summary

Access	Constructor and Description
public	LongBuilder()

Method Summary

Modifier and Type	Method and Description
public void	accept(double The first key of the segment. firstKey, double The segment slope. slope, long The segment intercept. intercept) Implements com.carrotsearch.hppc.PlaModel.SegmentConsumer.accept. Consumes a new segment.
private void	addSentinelSegment(int endIndex) Adds a sentinel segment that is used to give a limit for the position approximation, but does not count in the number of segments per level.
public LongPgmIndex	build() Builds the `LongPgmIndex`; or `EMPTY` if there are no keys in the list.
private int	buildFirstLevel()
private int	buildUpperLevel(int levelOffset, int levelNumSegments)
private long	getKey(int segmentDataIndex, int[] segmentData)
public long	ramBytesAllocated() Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated. Estimates the allocated memory.
public long	ramBytesUsed() Implements com.carrotsearch.hppc.Accountable.ramBytesUsed. Estimates the bytes that are actually used.
public LongPgmIndex.LongBuilder	setEpsilon(int epsilon) Sets the epsilon range to use when learning the segments for the list of keys.
public LongPgmIndex.LongBuilder	setEpsilonRecursive(int epsilonRecursive) Sets the recursive epsilon range to use when learning the segments for the segment levels.
public LongPgmIndex.LongBuilder	setSortedKeys(LongArrayList keys) Sets the sorted list of keys to build the index for; duplicate elements are allowed.
public LongPgmIndex.LongBuilder	setSortedKeys(long[] keys, int length) Sets the sorted array of keys to build the index for; duplicate elements are allowed.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

epsilon	back to summary
protected int epsilon

epsilonRecursive	back to summary
protected int epsilonRecursive

keys	back to summary
protected LongArrayList keys

numSegments	back to summary
protected int numSegments

plam	back to summary
protected PlaModel plam

segmentData	back to summary
protected IntArrayList segmentData

size	back to summary
protected int size

Constructor Detail

LongBuilder	back to summary
public LongBuilder()

Method Detail

accept	back to summary
public void accept(double firstKey, double slope, long intercept) Implements com.carrotsearch.hppc.PlaModel.SegmentConsumer.accept. Doc from com.carrotsearch.hppc.PlaModel.SegmentConsumer.accept. Consumes a new segment. The segment is defined by the epsilon-approximation function fs(k) = k × slope + intercept. Parameters firstKey:double The first key of the segment. slope:double The segment slope. intercept:long The segment intercept. Annotations @Override

back to summary

public void accept(double firstKey, double slope, long intercept)

Implements com.carrotsearch.hppc.PlaModel.SegmentConsumer.accept.

Doc from com.carrotsearch.hppc.PlaModel.SegmentConsumer.accept.

Consumes a new segment. The segment is defined by the epsilon-approximation function fs(k) = k × slope + intercept.

Parameters

firstKey:double: The first key of the segment.
slope:double: The segment slope.
intercept:long: The segment intercept.

Annotations

@Override

addSentinelSegment	back to summary
private void addSentinelSegment(int endIndex) Adds a sentinel segment that is used to give a limit for the position approximation, but does not count in the number of segments per level.

build	back to summary
public LongPgmIndex build() Builds the `LongPgmIndex`; or `EMPTY` if there are no keys in the list.

buildFirstLevel	back to summary
private int buildFirstLevel()

buildUpperLevel	back to summary
private int buildUpperLevel(int levelOffset, int levelNumSegments)

getKey	back to summary
private long getKey(int segmentDataIndex, int[] segmentData)

ramBytesAllocated

back to summary

public long ramBytesAllocated()

Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated.

Estimates the allocated memory. It does not count the memory for the list of keys, only for the builder itself.

Returns:long

Doc from com.carrotsearch.hppc.Accountable.ramBytesAllocated.

Ram allocated in bytes

Annotations

@Override

ramBytesUsed

back to summary

public long ramBytesUsed()

Implements com.carrotsearch.hppc.Accountable.ramBytesUsed.

Estimates the bytes that are actually used. It does not count the memory for the list of keys, only for the builder itself.

Returns:long

Doc from com.carrotsearch.hppc.Accountable.ramBytesUsed.

Ram used in bytes

Annotations

@Override

setEpsilon	back to summary
public LongPgmIndex.LongBuilder setEpsilon(int epsilon) Sets the epsilon range to use when learning the segments for the list of keys.

setEpsilonRecursive	back to summary
public LongPgmIndex.LongBuilder setEpsilonRecursive(int epsilonRecursive) Sets the recursive epsilon range to use when learning the segments for the segment levels.

setSortedKeys	back to summary
public LongPgmIndex.LongBuilder setSortedKeys(LongArrayList keys) Sets the sorted list of keys to build the index for; duplicate elements are allowed.

setSortedKeys	back to summary
public LongPgmIndex.LongBuilder setSortedKeys(long[] keys, int length) Sets the sorted array of keys to build the index for; duplicate elements are allowed.

com.carrotsearch.hppc back to summary

private Class LongPgmIndex.LongEmptyPgmIndex

Class Inheritance

extends LongPgmIndex

java.lang.Object
com.carrotsearch.hppc.LongPgmIndex
com.carrotsearch.hppc.LongPgmIndex.LongEmptyPgmIndex

Empty immutable PGM Index.

Nested and Inner Type Summary

Modifier and Type	Class and Description
private static class	LongPgmIndex.LongEmptyPgmIndex.LongEmptyIterator

Field Summary

Modifier and Type	Field and Description
private final Iterator<LongCursor>	emptyIterator

Inherited from com.carrotsearch.hppc.LongPgmIndex:: BEYOND_EPSILON_JUMP DOUBLE_KEY_SIZE EMPTY EPSILON epsilon EPSILON_RECURSIVE epsilonRecursive firstKey KEY_SIZE keys lastKey levelOffsets SEGMENT_DATA_SIZE segmentData size

Constructor Summary

Access	Constructor and Description
private	LongEmptyPgmIndex()

Method Summary

Modifier and Type	Method and Description
public <T extends LongProcedure> T	forEachInRange(T procedure, long minKey, long maxKey) Overrides com.carrotsearch.hppc.LongPgmIndex.forEachInRange. Applies `procedure` to the keys in the list that are greater than or equal to `minKey` (inclusive), and less than or equal to `maxKey` (inclusive).
public int	indexOf(long key) Overrides com.carrotsearch.hppc.LongPgmIndex.indexOf. Searches the specified key, and returns its index in the element list.
public Iterator<LongCursor>	rangeIterator(long minKey, long maxKey) Overrides com.carrotsearch.hppc.LongPgmIndex.rangeIterator. Returns an iterator over the keys in the list that are greater than or equal to `minKey` (inclusive), and less than or equal to `maxKey` (inclusive).

Inherited from com.carrotsearch.hppc.LongPgmIndex:: contains isEmpty ramBytesAllocated ramBytesUsed rangeCardinality rank size

Field Detail

emptyIterator	back to summary
private final Iterator<LongCursor> emptyIterator

Constructor Detail

LongEmptyPgmIndex	back to summary
private LongEmptyPgmIndex()

Method Detail

forEachInRange back to summary

public <T extends LongProcedure> T forEachInRange(T procedure, long minKey, long maxKey)

Overrides com.carrotsearch.hppc.LongPgmIndex.forEachInRange.

Doc from com.carrotsearch.hppc.LongPgmIndex.forEachInRange.

Applies procedure to the keys in the list that are greater than or equal to minKey (inclusive), and less than or equal to maxKey (inclusive).

Annotations

@Override

indexOf back to summary

public int indexOf(long key)

Overrides com.carrotsearch.hppc.LongPgmIndex.indexOf.

Doc from com.carrotsearch.hppc.LongPgmIndex.indexOf.

Searches the specified key, and returns its index in the element list. If multiple elements are equal to the specified key, there is no guarantee which one will be found.

Returns:int

The index of the searched key if it is present; otherwise, (-(<i>insertion point</i>) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or keys#size() if all the elements are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Annotations

@Override

rangeIterator back to summary

public Iterator<LongCursor> rangeIterator(long minKey, long maxKey)

Overrides com.carrotsearch.hppc.LongPgmIndex.rangeIterator.

Doc from com.carrotsearch.hppc.LongPgmIndex.rangeIterator.

Returns an iterator over the keys in the list that are greater than or equal to minKey (inclusive), and less than or equal to maxKey (inclusive).

Annotations

@Override

com.carrotsearch.hppc back to summary

private Class LongPgmIndex.LongEmptyPgmIndex.LongEmptyIterator

Class Inheritance

extends AbstractIterator<LongCursor>

java.lang.Object
com.carrotsearch.hppc.AbstractIterator
com.carrotsearch.hppc.LongPgmIndex.LongEmptyPgmIndex.LongEmptyIterator

Constructor Summary

Access	Constructor and Description
private	LongEmptyIterator()

Method Summary

Modifier and Type	Method and Description
protected LongCursor	fetch() Implements abstract com.carrotsearch.hppc.AbstractIterator.fetch. Fetch next element.

Inherited from com.carrotsearch.hppc.AbstractIterator:: done hasNext next remove

Constructor Detail

LongEmptyIterator	back to summary
private LongEmptyIterator()

Method Detail

fetch back to summary

protected LongCursor fetch()

Implements abstract com.carrotsearch.hppc.AbstractIterator.fetch.

Doc from com.carrotsearch.hppc.AbstractIterator.fetch.

Fetch next element. The implementation must return done() when all elements have been fetched.

Returns:LongCursor

Returns the next value for the iterator or chain-calls done().

Annotations

@Override

com.carrotsearch.hppc back to summary

protected Class LongPgmIndex.RangeIterator

Class Inheritance

extends AbstractIterator<LongCursor>

java.lang.Object
com.carrotsearch.hppc.AbstractIterator
com.carrotsearch.hppc.LongPgmIndex.RangeIterator

Iterator over a range of elements in a sorted array.

Field Summary

Modifier and Type	Field and Description
private final long[]	buffer
private final LongCursor	cursor
private final long	maxKey
private final int	size

Constructor Summary

Access	Constructor and Description
protected	RangeIterator(LongArrayList keys, int fromIndex, long maxKey) Range iterator from `fromIndex` (inclusive) to `maxKey` (inclusive).

Method Summary

Modifier and Type	Method and Description
protected LongCursor	fetch() Implements abstract com.carrotsearch.hppc.AbstractIterator.fetch. Fetch next element.

Inherited from com.carrotsearch.hppc.AbstractIterator:: done hasNext next remove

Field Detail

buffer	back to summary
private final long[] buffer

cursor	back to summary
private final LongCursor cursor

maxKey	back to summary
private final long maxKey

size	back to summary
private final int size

Constructor Detail

RangeIterator	back to summary
protected RangeIterator(LongArrayList keys, int fromIndex, long maxKey) Range iterator from `fromIndex` (inclusive) to `maxKey` (inclusive).

Method Detail

fetch back to summary

protected LongCursor fetch()

Implements abstract com.carrotsearch.hppc.AbstractIterator.fetch.

Doc from com.carrotsearch.hppc.AbstractIterator.fetch.

Fetch next element. The implementation must return done() when all elements have been fetched.

Returns:LongCursor

Returns the next value for the iterator or chain-calls done().

Annotations

@Override