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

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	DoublePgmIndex.DoubleBuilder Builds a `DoublePgmIndex` on a provided sorted list of keys.
private static class	DoublePgmIndex.DoubleEmptyPgmIndex Empty immutable PGM Index.
protected static class	DoublePgmIndex.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 DoublePgmIndex	EMPTY Empty immutable DoublePgmIndex.
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 double	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 DoubleArrayList	keys The list of keys for which this index is built.
public final double	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	DoublePgmIndex(DoubleArrayList keys, int size, int epsilon, int epsilonRecursive, int[] levelOffsets, int[] segmentData)
private	DoublePgmIndex() Empty set constructor.

Method Summary

Modifier and Type	Method and Description
private int	approximateIndex(double key, int segmentDataIndex, int[] segmentData)
public boolean	contains(double key) Returns whether this key set contains the given key.
private int	Returns: the segment data index; or -1 if none. findSegment(double key) Finds the segment responsible for a given key, that is, the rightmost segment having its first key <= the searched key.
public <T extends DoubleProcedure> T	forEachInRange(T procedure, double minKey, double 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 double	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(double 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(double minKey, double 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<DoubleCursor>	rangeIterator(double minKey, double 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(double 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 DoublePgmIndex EMPTY Empty immutable DoublePgmIndex.

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 double 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 DoubleArrayList 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 double 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`.

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

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

Method Detail

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

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

findSegment	back to summary
private int findSegment(double 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(double 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 DoubleProcedure> T forEachInRange(T procedure, double minKey, double 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 double 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(double 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(double 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(double minKey, double 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<DoubleCursor> rangeIterator(double minKey, double 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(double 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(double 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 DoublePgmIndex.DoubleBuilder

Class Inheritance

extends Object
implements SegmentConsumer, Accountable

java.lang.Object
com.carrotsearch.hppc.DoublePgmIndex.DoubleBuilder

All Implemented Interfaces

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

Builds a DoublePgmIndex on a provided sorted list of keys.

Field Summary

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

Constructor Summary

Access	Constructor and Description
public	DoubleBuilder()

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 DoublePgmIndex	build() Builds the `DoublePgmIndex`; or `EMPTY` if there are no keys in the list.
private int	buildFirstLevel()
private int	buildUpperLevel(int levelOffset, int levelNumSegments)
private double	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 DoublePgmIndex.DoubleBuilder	setEpsilon(int epsilon) Sets the epsilon range to use when learning the segments for the list of keys.
public DoublePgmIndex.DoubleBuilder	setEpsilonRecursive(int epsilonRecursive) Sets the recursive epsilon range to use when learning the segments for the segment levels.
public DoublePgmIndex.DoubleBuilder	setSortedKeys(DoubleArrayList keys) Sets the sorted list of keys to build the index for; duplicate elements are allowed.
public DoublePgmIndex.DoubleBuilder	setSortedKeys(double[] 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 DoubleArrayList 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

DoubleBuilder	back to summary
public DoubleBuilder()

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 DoublePgmIndex build() Builds the `DoublePgmIndex`; 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 double 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 DoublePgmIndex.DoubleBuilder setEpsilon(int epsilon) Sets the epsilon range to use when learning the segments for the list of keys.

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

setSortedKeys	back to summary
public DoublePgmIndex.DoubleBuilder setSortedKeys(DoubleArrayList keys) Sets the sorted list of keys to build the index for; duplicate elements are allowed.

setSortedKeys	back to summary
public DoublePgmIndex.DoubleBuilder setSortedKeys(double[] 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 DoublePgmIndex.DoubleEmptyPgmIndex

Class Inheritance

extends DoublePgmIndex

java.lang.Object
com.carrotsearch.hppc.DoublePgmIndex
com.carrotsearch.hppc.DoublePgmIndex.DoubleEmptyPgmIndex

Empty immutable PGM Index.

Nested and Inner Type Summary

Modifier and Type	Class and Description
private static class	DoublePgmIndex.DoubleEmptyPgmIndex.DoubleEmptyIterator

Field Summary

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

Inherited from com.carrotsearch.hppc.DoublePgmIndex:: 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	DoubleEmptyPgmIndex()

Method Summary

Modifier and Type	Method and Description
public <T extends DoubleProcedure> T	forEachInRange(T procedure, double minKey, double maxKey) Overrides com.carrotsearch.hppc.DoublePgmIndex.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(double key) Overrides com.carrotsearch.hppc.DoublePgmIndex.indexOf. Searches the specified key, and returns its index in the element list.
public Iterator<DoubleCursor>	rangeIterator(double minKey, double maxKey) Overrides com.carrotsearch.hppc.DoublePgmIndex.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.DoublePgmIndex:: contains isEmpty ramBytesAllocated ramBytesUsed rangeCardinality rank size

Field Detail

emptyIterator	back to summary
private final Iterator<DoubleCursor> emptyIterator

Constructor Detail

DoubleEmptyPgmIndex	back to summary
private DoubleEmptyPgmIndex()

Method Detail

forEachInRange back to summary

public <T extends DoubleProcedure> T forEachInRange(T procedure, double minKey, double maxKey)

Overrides com.carrotsearch.hppc.DoublePgmIndex.forEachInRange.

Doc from com.carrotsearch.hppc.DoublePgmIndex.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(double key)

Overrides com.carrotsearch.hppc.DoublePgmIndex.indexOf.

Doc from com.carrotsearch.hppc.DoublePgmIndex.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<DoubleCursor> rangeIterator(double minKey, double maxKey)

Overrides com.carrotsearch.hppc.DoublePgmIndex.rangeIterator.

Doc from com.carrotsearch.hppc.DoublePgmIndex.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 DoublePgmIndex.DoubleEmptyPgmIndex.DoubleEmptyIterator

Class Inheritance

extends AbstractIterator<DoubleCursor>

java.lang.Object
com.carrotsearch.hppc.AbstractIterator
com.carrotsearch.hppc.DoublePgmIndex.DoubleEmptyPgmIndex.DoubleEmptyIterator

Constructor Summary

Access	Constructor and Description
private	DoubleEmptyIterator()

Method Summary

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

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

Constructor Detail

DoubleEmptyIterator	back to summary
private DoubleEmptyIterator()

Method Detail

fetch back to summary

protected DoubleCursor 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:DoubleCursor

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

Annotations

@Override

com.carrotsearch.hppc back to summary

protected Class DoublePgmIndex.RangeIterator

Class Inheritance

extends AbstractIterator<DoubleCursor>

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

Iterator over a range of elements in a sorted array.

Field Summary

Modifier and Type	Field and Description
private final double[]	buffer
private final DoubleCursor	cursor
private final double	maxKey
private final int	size

Constructor Summary

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

Method Summary

Modifier and Type	Method and Description
protected DoubleCursor	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 double[] buffer

cursor	back to summary
private final DoubleCursor cursor

maxKey	back to summary
private final double maxKey

size	back to summary
private final int size

Constructor Detail

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

Method Detail

fetch back to summary

protected DoubleCursor 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:DoubleCursor

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

Annotations

@Override