Package org.apache.lucene.util.bkd

Class BKDReader.BKDPointTree

java.lang.Object

org.apache.lucene.util.bkd.BKDReader.BKDPointTree

All Implemented Interfaces:

java.lang.Cloneable, PointValues.PointTree

Enclosing class:

BKDReader

private static class BKDReader.BKDPointTree
extends java.lang.Object
implements PointValues.PointTree

Field Summary

Fields

Modifier and Type	Field	Description
private int[]	commonPrefixLengths
private BKDConfig	config
private DocIdsWriter	docIdsWriter
private IndexInput	innerNodes
private boolean	isTreeBalanced
private int	lastLeafNodePointCount
private long[]	leafBlockFPStack
private int	leafNodeOffset
private IndexInput	leafNodes
private int	level
private byte[]	maxPackedValue
private byte[]	minPackedValue
private boolean[]	negativeDeltas
private int	nodeID
private int	nodeRoot
(package private) long	pointCount
private int[]	readNodeDataPositions
private int	rightMostLeafNode
private int[]	rightNodePositions
private byte[]	scratchDataPackedValue
private BKDReader.BKDReaderDocIDSetIterator	scratchIterator
private byte[]	scratchMaxIndexPackedValue
private byte[]	scratchMinIndexPackedValue
private int[]	splitDimsPos
private byte[][]	splitDimValueStack
private byte[][]	splitValuesStack
private int	version

Constructor Summary

Constructors

Modifier	Constructor	Description
private	BKDPointTree(IndexInput innerNodes, IndexInput leafNodes, BKDConfig config, int numLeaves, int version, long pointCount, byte[] minPackedValue, byte[] maxPackedValue, boolean isTreeBalanced)
private	BKDPointTree(IndexInput innerNodes, IndexInput leafNodes, BKDConfig config, int numLeaves, int version, long pointCount, int nodeID, int level, byte[] minPackedValue, byte[] maxPackedValue, BKDReader.BKDReaderDocIDSetIterator scratchIterator, byte[] scratchDataPackedValue, byte[] scratchMinIndexPackedValue, byte[] scratchMaxIndexPackedValue, int[] commonPrefixLengths, boolean isTreeBalanced)

Method Summary

Modifier and Type	Method	Description
void	addAll(PointValues.IntersectVisitor visitor, boolean grown)
private int	balanceTreeNodePosition(int minNode, int maxNode, int node, int position, int level)
PointValues.PointTree	clone()	Clone, the current node becomes the root of the new tree.
private long	getLeafBlockFP()	Only valid after pushLeft or pushRight, not pop!
byte[]	getMaxPackedValue()	Return the maximum packed value of the current node.
byte[]	getMinPackedValue()	Return the minimum packed value of the current node.
private int	getNumLeavesSlow(int node)
private int	getTreeDepth(int numLeaves)
private boolean	isLeafNode()
private boolean	isLeftNode()
private boolean	isRootNode()
boolean	moveToChild()	Move to the first child node and return true upon success.
boolean	moveToParent()	Move to the parent node and return true upon success.
boolean	moveToSibling()	Move to the next sibling node and return true upon success.
private boolean	nodeExists()
private void	pop()
private void	popBounds(byte[] packedValue)
private void	pushBoundsLeft()
private void	pushBoundsRight()
private void	pushLeft()
private void	pushRight()
private void	readCommonPrefixes(int[] commonPrefixLengths, byte[] scratchPackedValue, IndexInput in)
private int	readCompressedDim(IndexInput in)
private int	readDocIDs(IndexInput in, long blockFP, BKDReader.BKDReaderDocIDSetIterator iterator)
private void	readMinMax(int[] commonPrefixLengths, byte[] minPackedValue, byte[] maxPackedValue, IndexInput in)
private void	readNodeData(boolean isLeft)
private void	resetNodeDataPosition()
long	size()	Return the number of points below the current node.
private long	sizeFromBalancedTree(int leftMostLeafNode, int rightMostLeafNode)
java.lang.String	toString()
private void	visitCompressedDocValues(int[] commonPrefixLengths, byte[] scratchPackedValue, IndexInput in, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor, int compressedDim)
void	visitDocIDs(PointValues.IntersectVisitor visitor)	Visit all the docs below the current node.
void	visitDocValues(PointValues.IntersectVisitor visitor)	Visit all the docs and values below the current node.
private void	visitDocValues(PointValues.IntersectVisitor visitor, long fp)
private void	visitDocValuesNoCardinality(int[] commonPrefixLengths, byte[] scratchDataPackedValue, byte[] scratchMinIndexPackedValue, byte[] scratchMaxIndexPackedValue, IndexInput in, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor)
private void	visitDocValuesWithCardinality(int[] commonPrefixLengths, byte[] scratchDataPackedValue, byte[] scratchMinIndexPackedValue, byte[] scratchMaxIndexPackedValue, IndexInput in, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor)
private void	visitLeavesOneByOne(PointValues.IntersectVisitor visitor)
private void	visitSparseRawDocValues(int[] commonPrefixLengths, byte[] scratchPackedValue, IndexInput in, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor)
private void	visitUniqueRawDocValues(byte[] scratchPackedValue, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor)

Methods inherited from class java.lang.Object

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

Field Detail

nodeID

private int nodeID

nodeRoot

private final int nodeRoot

level

private int level

innerNodes

private final IndexInput innerNodes

leafNodes

private final IndexInput leafNodes

leafBlockFPStack

private final long[] leafBlockFPStack

readNodeDataPositions

private final int[] readNodeDataPositions

rightNodePositions

private final int[] rightNodePositions

splitDimsPos

private final int[] splitDimsPos

negativeDeltas

private final boolean[] negativeDeltas

splitValuesStack

private final byte[][] splitValuesStack

minPackedValue

private final byte[] minPackedValue

maxPackedValue

private final byte[] maxPackedValue

splitDimValueStack

private final byte[][] splitDimValueStack

config

private final BKDConfig config

leafNodeOffset

private final int leafNodeOffset

version

private final int version

pointCount

final long pointCount

lastLeafNodePointCount

private final int lastLeafNodePointCount

rightMostLeafNode

private final int rightMostLeafNode

scratchDataPackedValue

private final byte[] scratchDataPackedValue

scratchMinIndexPackedValue

private final byte[] scratchMinIndexPackedValue

scratchMaxIndexPackedValue

private final byte[] scratchMaxIndexPackedValue

commonPrefixLengths

private final int[] commonPrefixLengths

scratchIterator

private final BKDReader.BKDReaderDocIDSetIterator scratchIterator

docIdsWriter

private final DocIdsWriter docIdsWriter

isTreeBalanced

private final boolean isTreeBalanced

Constructor Detail

BKDPointTree

private BKDPointTree(IndexInput innerNodes,
                     IndexInput leafNodes,
                     BKDConfig config,
                     int numLeaves,
                     int version,
                     long pointCount,
                     byte[] minPackedValue,
                     byte[] maxPackedValue,
                     boolean isTreeBalanced)
              throws java.io.IOException

Throws:

java.io.IOException

BKDPointTree

private BKDPointTree(IndexInput innerNodes,
                     IndexInput leafNodes,
                     BKDConfig config,
                     int numLeaves,
                     int version,
                     long pointCount,
                     int nodeID,
                     int level,
                     byte[] minPackedValue,
                     byte[] maxPackedValue,
                     BKDReader.BKDReaderDocIDSetIterator scratchIterator,
                     byte[] scratchDataPackedValue,
                     byte[] scratchMinIndexPackedValue,
                     byte[] scratchMaxIndexPackedValue,
                     int[] commonPrefixLengths,
                     boolean isTreeBalanced)

Method Detail

clone

public PointValues.PointTree clone()

Description copied from interface: PointValues.PointTree

Clone, the current node becomes the root of the new tree.

Specified by:

clone in interface PointValues.PointTree

Overrides:

clone in class java.lang.Object

getMinPackedValue

public byte[] getMinPackedValue()

Description copied from interface: PointValues.PointTree

Return the minimum packed value of the current node.

Specified by:

getMinPackedValue in interface PointValues.PointTree

getMaxPackedValue

public byte[] getMaxPackedValue()

Description copied from interface: PointValues.PointTree

Return the maximum packed value of the current node.

Specified by:

getMaxPackedValue in interface PointValues.PointTree

moveToChild

public boolean moveToChild()
                    throws java.io.IOException

Description copied from interface: PointValues.PointTree

Move to the first child node and return true upon success. Returns false for leaf nodes and true otherwise.

Specified by:

moveToChild in interface PointValues.PointTree

Throws:

java.io.IOException

resetNodeDataPosition

private void resetNodeDataPosition()
                            throws java.io.IOException

Throws:

java.io.IOException

pushBoundsLeft

private void pushBoundsLeft()

pushLeft

private void pushLeft()
               throws java.io.IOException

Throws:

java.io.IOException

pushBoundsRight

private void pushBoundsRight()

pushRight

private void pushRight()
                throws java.io.IOException

Throws:

java.io.IOException

moveToSibling

public boolean moveToSibling()
                      throws java.io.IOException

Description copied from interface: PointValues.PointTree

Move to the next sibling node and return true upon success. Returns false if the current node has no more siblings.

Specified by:

moveToSibling in interface PointValues.PointTree

Throws:

java.io.IOException

pop

private void pop()

popBounds

private void popBounds(byte[] packedValue)

moveToParent

public boolean moveToParent()

Description copied from interface: PointValues.PointTree

Move to the parent node and return true upon success. Returns false for the root node and true otherwise.

Specified by:

moveToParent in interface PointValues.PointTree

isRootNode

private boolean isRootNode()

isLeftNode

private boolean isLeftNode()

isLeafNode

private boolean isLeafNode()

nodeExists

private boolean nodeExists()

getLeafBlockFP

private long getLeafBlockFP()

Only valid after pushLeft or pushRight, not pop!

size

public long size()

Description copied from interface: PointValues.PointTree

Return the number of points below the current node.

Specified by:

size in interface PointValues.PointTree

sizeFromBalancedTree

private long sizeFromBalancedTree(int leftMostLeafNode,
                                  int rightMostLeafNode)

balanceTreeNodePosition

private int balanceTreeNodePosition(int minNode,
                                    int maxNode,
                                    int node,
                                    int position,
                                    int level)

visitDocIDs

public void visitDocIDs(PointValues.IntersectVisitor visitor)
                 throws java.io.IOException

Description copied from interface: PointValues.PointTree

Visit all the docs below the current node.

Specified by:

visitDocIDs in interface PointValues.PointTree

Throws:

java.io.IOException

addAll

public void addAll(PointValues.IntersectVisitor visitor,
                   boolean grown)
            throws java.io.IOException

Throws:

java.io.IOException

visitDocValues

public void visitDocValues(PointValues.IntersectVisitor visitor)
                    throws java.io.IOException

Description copied from interface: PointValues.PointTree

Visit all the docs and values below the current node.

Specified by:

visitDocValues in interface PointValues.PointTree

Throws:

java.io.IOException

visitLeavesOneByOne

private void visitLeavesOneByOne(PointValues.IntersectVisitor visitor)
                          throws java.io.IOException

Throws:

java.io.IOException

visitDocValues

private void visitDocValues(PointValues.IntersectVisitor visitor,
                            long fp)
                     throws java.io.IOException

Throws:

java.io.IOException

readDocIDs

private int readDocIDs(IndexInput in,
                       long blockFP,
                       BKDReader.BKDReaderDocIDSetIterator iterator)
                throws java.io.IOException

Throws:

java.io.IOException

getNumLeavesSlow

private int getNumLeavesSlow(int node)

readNodeData

private void readNodeData(boolean isLeft)
                   throws java.io.IOException

Throws:

java.io.IOException

getTreeDepth

private int getTreeDepth(int numLeaves)

visitDocValuesNoCardinality

private void visitDocValuesNoCardinality(int[] commonPrefixLengths,
                                         byte[] scratchDataPackedValue,
                                         byte[] scratchMinIndexPackedValue,
                                         byte[] scratchMaxIndexPackedValue,
                                         IndexInput in,
                                         BKDReader.BKDReaderDocIDSetIterator scratchIterator,
                                         int count,
                                         PointValues.IntersectVisitor visitor)
                                  throws java.io.IOException

Throws:

java.io.IOException

visitDocValuesWithCardinality

private void visitDocValuesWithCardinality(int[] commonPrefixLengths,
                                           byte[] scratchDataPackedValue,
                                           byte[] scratchMinIndexPackedValue,
                                           byte[] scratchMaxIndexPackedValue,
                                           IndexInput in,
                                           BKDReader.BKDReaderDocIDSetIterator scratchIterator,
                                           int count,
                                           PointValues.IntersectVisitor visitor)
                                    throws java.io.IOException

Throws:

java.io.IOException

readMinMax

private void readMinMax(int[] commonPrefixLengths,
                        byte[] minPackedValue,
                        byte[] maxPackedValue,
                        IndexInput in)
                 throws java.io.IOException

Throws:

java.io.IOException

visitSparseRawDocValues

private void visitSparseRawDocValues(int[] commonPrefixLengths,
                                     byte[] scratchPackedValue,
                                     IndexInput in,
                                     BKDReader.BKDReaderDocIDSetIterator scratchIterator,
                                     int count,
                                     PointValues.IntersectVisitor visitor)
                              throws java.io.IOException

Throws:

java.io.IOException

visitUniqueRawDocValues

private void visitUniqueRawDocValues(byte[] scratchPackedValue,
                                     BKDReader.BKDReaderDocIDSetIterator scratchIterator,
                                     int count,
                                     PointValues.IntersectVisitor visitor)
                              throws java.io.IOException

Throws:

java.io.IOException

visitCompressedDocValues

private void visitCompressedDocValues(int[] commonPrefixLengths,
                                      byte[] scratchPackedValue,
                                      IndexInput in,
                                      BKDReader.BKDReaderDocIDSetIterator scratchIterator,
                                      int count,
                                      PointValues.IntersectVisitor visitor,
                                      int compressedDim)
                               throws java.io.IOException

Throws:

java.io.IOException

readCompressedDim

private int readCompressedDim(IndexInput in)
                       throws java.io.IOException

Throws:

java.io.IOException

readCommonPrefixes

private void readCommonPrefixes(int[] commonPrefixLengths,
                                byte[] scratchPackedValue,
                                IndexInput in)
                         throws java.io.IOException

Throws:

java.io.IOException

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object