org.apache.arrow.algorithm.misc

Class PartialSumUtils

java.lang.Object

org.apache.arrow.algorithm.misc.PartialSumUtils

public class PartialSumUtils
extends Object

Partial sum related utilities.

Method Summary

Modifier and Type	Method and Description
static int	findPositionInPartialSumVector(BaseIntVector partialSumVector, long value) Given a value and a partial sum vector, finds its position in the partial sum vector.
static void	toDeltaVector(BaseIntVector partialSumVector, BaseIntVector deltaVector) Converts an input vector to the delta vector.
static void	toPartialSumVector(BaseIntVector deltaVector, BaseIntVector partialSumVector, long sumBase) Converts an input vector to a partial sum vector.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

toPartialSumVector

public static void toPartialSumVector(BaseIntVector deltaVector,
                                      BaseIntVector partialSumVector,
                                      long sumBase)

Converts an input vector to a partial sum vector. This is an inverse operation of toDeltaVector(BaseIntVector, BaseIntVector). Suppose we have input vector a and output vector b. Then we have b(0) = sumBase; b(i + 1) = b(i) + a(i) (i = 0, 1, 2, ...).

Parameters:

deltaVector - the input vector.

partialSumVector - the output vector.

sumBase - the base of the partial sums.

toDeltaVector

public static void toDeltaVector(BaseIntVector partialSumVector,
                                 BaseIntVector deltaVector)

Converts an input vector to the delta vector. This is an inverse operation of toPartialSumVector(BaseIntVector, BaseIntVector, long). Suppose we have input vector a and output vector b. Then we have b(i) = a(i + 1) - a(i) (i = 0, 1, 2, ...).

Parameters:

partialSumVector - the input vector.

deltaVector - the output vector.

findPositionInPartialSumVector

public static int findPositionInPartialSumVector(BaseIntVector partialSumVector,
                                                 long value)

Given a value and a partial sum vector, finds its position in the partial sum vector. In particular, given an integer value a and partial sum vector v, we try to find a position i, so that v(i) <= a < v(i + 1). The algorithm is based on binary search, so it takes O(log(n)) time, where n is the length of the partial sum vector.

Parameters:

partialSumVector - the input partial sum vector.

value - the value to search.

Returns:

the position in the partial sum vector, if any, or -1, if none is found.