Module org.apache.arrow.algorithm

Package org.apache.arrow.algorithm.dictionary

Class SearchTreeBasedDictionaryBuilder<V extends ValueVector>

java.lang.Object

org.apache.arrow.algorithm.dictionary.SearchTreeBasedDictionaryBuilder<V>

Type Parameters:

V - the dictionary vector type.

All Implemented Interfaces:

DictionaryBuilder<V>

public class SearchTreeBasedDictionaryBuilder<V extends ValueVector>
extends Object
implements DictionaryBuilder<V>

This class builds the dictionary based on a binary search tree. Each add operation can be finished in O(log(n)) time, where n is the current dictionary size.

Field Summary

Fields

Modifier and Type	Field	Description
protected final VectorValueComparator<V>	comparator	The criteria for sorting in the search tree.

Constructor Summary

Constructors

Constructor	Description
SearchTreeBasedDictionaryBuilder(V dictionary, VectorValueComparator<V> comparator)	Construct a search tree-based dictionary builder.
SearchTreeBasedDictionaryBuilder(V dictionary, VectorValueComparator<V> comparator, boolean encodeNull)	Construct a search tree-based dictionary builder.

Method Summary

Modifier and Type	Method	Description
int	addValue(V targetVector, int targetIndex)	Try to add an element from the target vector to the dictionary.
int	addValues(V targetVector)	Try to add all values from the target vector to the dictionary.
V	getDictionary()	Gets the dictionary built.
void	populateSortedDictionary(V sortedDictionary)	Gets the sorted dictionary.

Methods inherited from class java.lang.Object

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

Field Details

comparator

protected final VectorValueComparator<V extends ValueVector> comparator

The criteria for sorting in the search tree.

Constructor Details

SearchTreeBasedDictionaryBuilder

public SearchTreeBasedDictionaryBuilder(V dictionary,
 VectorValueComparator<V> comparator)

Construct a search tree-based dictionary builder.

Parameters:

dictionary - the dictionary vector.

comparator - the criteria for value equality.

SearchTreeBasedDictionaryBuilder

public SearchTreeBasedDictionaryBuilder(V dictionary,
 VectorValueComparator<V> comparator,
 boolean encodeNull)

Construct a search tree-based dictionary builder.

Parameters:

dictionary - the dictionary vector.

comparator - the criteria for value equality.

encodeNull - if null values should be added to the dictionary.

Method Details

getDictionary

public V getDictionary()

Gets the dictionary built. Please note that the dictionary is not in sorted order. Instead, its order is determined by the order of element insertion. To get the dictionary in sorted order, please use populateSortedDictionary(ValueVector).

Specified by:

getDictionary in interface DictionaryBuilder<V extends ValueVector>

Returns:

the dictionary.

addValues

public int addValues(V targetVector)

Try to add all values from the target vector to the dictionary.

Specified by:

addValues in interface DictionaryBuilder<V extends ValueVector>

Parameters:

targetVector - the target vector containing values to probe.

Returns:

the number of values actually added to the dictionary.

addValue

public int addValue(V targetVector,
 int targetIndex)

Try to add an element from the target vector to the dictionary.

Specified by:

addValue in interface DictionaryBuilder<V extends ValueVector>

Parameters:

targetVector - the target vector containing new element.

targetIndex - the index of the new element in the target vector.

Returns:

the index of the new element in the dictionary.

populateSortedDictionary

public void populateSortedDictionary(V sortedDictionary)

Gets the sorted dictionary. Note that given the binary search tree, the sort can finish in O(n).