Package org.roaringbitmap.art
Class Node
java.lang.Object
org.roaringbitmap.art.Node
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected short
static final int
protected NodeType
protected byte[]
protected byte
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic int
binarySearch
(byte[] key, int fromIndex, int toIndex, byte k) search the position of the input byte key in the node's key byte array part(package private) static SearchResult
binarySearchWithResult
(byte[] key, int fromIndex, int toIndex, byte k) static void
copyPrefix
(Node src, Node dst) copy the prefix between two nodesstatic Node
deserialize
(DataInput dataInput) deserialize into a typed node from the byte streamstatic Node
deserialize
(ByteBuffer byteBuffer) deserialize into a typed nodeprivate static Node
deserializeHeader
(DataInput dataInput) private static Node
deserializeHeader
(ByteBuffer byteBuffer) (package private) abstract void
deserializeNodeBody
(DataInput dataInput) deserialize the node's body content(package private) abstract void
deserializeNodeBody
(ByteBuffer byteBuffer) deserialize the node's body contentabstract Node
getChild
(int pos) get the child at the specified position in the node, the 'pos' range from 0 to countabstract byte
getChildKey
(int pos) get the corresponding key byte of the requested positionabstract int
getChildPos
(byte k) get the position of a child corresponding to the input key 'k'abstract int
get the max child's positionabstract int
get the position of the min element in current node.abstract SearchResult
getNearestChildPos
(byte key) get the position of a child corresponding to the input key 'k' if present if 'k' is not in the child, return the positions of the neighbouring nodes insteadabstract int
getNextLargerPos
(int pos) get the next position in the nodeabstract int
getNextSmallerPos
(int pos) get the next smaller element's positionstatic Node
insertLeaf
(Node current, LeafNode childNode, byte key) insert the LeafNode as a child of the current internal nodeabstract Node
remove
(int pos) remove the specified position child(package private) abstract void
replaceChildren
(Node[] children) replace the node's children according to the given children parameter while doing the deserialization phase.abstract void
replaceNode
(int pos, Node freshOne) replace the position child to the fresh onevoid
serialize
(DataOutput dataOutput) serializevoid
serialize
(ByteBuffer byteBuffer) serializeprivate void
serializeHeader
(DataOutput dataOutput) private void
serializeHeader
(ByteBuffer byteBuffer) private int
(package private) abstract void
serializeNodeBody
(DataOutput dataOutput) serialize the node's body content(package private) abstract void
serializeNodeBody
(ByteBuffer byteBuffer) serialize the node's body contentabstract int
the serialized size except the common node header partint
the serialized size in bytes of this nodeprotected static byte[]
sortSmallByteArray
(byte[] key, Node[] children, int left, int right) sort the small arrays through the insertion sort alg.
-
Field Details
-
nodeType
-
prefixLength
protected byte prefixLength -
prefix
protected byte[] prefix -
count
protected short count -
ILLEGAL_IDX
public static final int ILLEGAL_IDX- See Also:
-
-
Constructor Details
-
Node
constructor- Parameters:
nodeType
- the node typecompressedPrefixSize
- the prefix byte array size,less than or equal to 6
-
-
Method Details
-
sortSmallByteArray
sort the small arrays through the insertion sort alg. -
getChildPos
public abstract int getChildPos(byte k) get the position of a child corresponding to the input key 'k'- Parameters:
k
- a key value of the byte range- Returns:
- the child position corresponding to the key 'k'
-
getNearestChildPos
get the position of a child corresponding to the input key 'k' if present if 'k' is not in the child, return the positions of the neighbouring nodes instead- Parameters:
key
- a key value of the byte range- Returns:
- a result indicating whether or not the key was found and the positions of the child corresponding to it or its neighbours
-
getChildKey
public abstract byte getChildKey(int pos) get the corresponding key byte of the requested position- Parameters:
pos
- the position- Returns:
- the corresponding key byte
-
getChild
get the child at the specified position in the node, the 'pos' range from 0 to count- Parameters:
pos
- the position- Returns:
- a Node corresponding to the input position
-
replaceNode
replace the position child to the fresh one- Parameters:
pos
- the positionfreshOne
- the fresh node to replace the old one
-
getMinPos
public abstract int getMinPos()get the position of the min element in current node.- Returns:
- the minimum key's position
-
getNextLargerPos
public abstract int getNextLargerPos(int pos) get the next position in the node- Parameters:
pos
- current position,-1 to start from the min one- Returns:
- the next larger byte key's position which is close to 'pos' position,-1 for end
-
getMaxPos
public abstract int getMaxPos()get the max child's position- Returns:
- the max byte key's position
-
getNextSmallerPos
public abstract int getNextSmallerPos(int pos) get the next smaller element's position- Parameters:
pos
- the position,-1 to start from the largest one- Returns:
- the next smaller key's position which is close to input 'pos' position,-1 for end
-
remove
remove the specified position child- Parameters:
pos
- the position to remove- Returns:
- an adaptive changed fresh node of the current node
-
serialize
serialize- Parameters:
dataOutput
- the DataOutput- Throws:
IOException
- signal a exception happened while the serialization
-
serialize
serialize- Parameters:
byteBuffer
- the ByteBuffer- Throws:
IOException
- signal a exception happened while the serialization
-
serializeSizeInBytes
public int serializeSizeInBytes()the serialized size in bytes of this node- Returns:
- the size in bytes
-
deserialize
deserialize into a typed node from the byte stream- Parameters:
dataInput
- the input byte stream- Returns:
- the typed node
- Throws:
IOException
- indicate a exception happened
-
deserialize
deserialize into a typed node- Parameters:
byteBuffer
- the ByteBuffer- Returns:
- the typed node
- Throws:
IOException
- indicate a exception happened
-
replaceChildren
replace the node's children according to the given children parameter while doing the deserialization phase.- Parameters:
children
- all the not null children nodes in key byte ascending order,no null element
-
serializeNodeBody
serialize the node's body content- Parameters:
dataOutput
- the DataOutput- Throws:
IOException
- exception indicates serialization errors
-
serializeNodeBody
serialize the node's body content- Parameters:
byteBuffer
- the ByteBuffer- Throws:
IOException
- exception indicates serialization errors
-
deserializeNodeBody
deserialize the node's body content- Parameters:
dataInput
- the DataInput- Throws:
IOException
- exception indicates deserialization errors
-
deserializeNodeBody
deserialize the node's body content- Parameters:
byteBuffer
- the ByteBuffer- Throws:
IOException
- exception indicates deserialization errors
-
serializeNodeBodySizeInBytes
public abstract int serializeNodeBodySizeInBytes()the serialized size except the common node header part- Returns:
- the size in bytes
-
insertLeaf
insert the LeafNode as a child of the current internal node- Parameters:
current
- current internal nodechildNode
- the leaf nodekey
- the key byte reference to the child leaf node- Returns:
- an adaptive changed node of the input 'current' node
-
copyPrefix
copy the prefix between two nodes- Parameters:
src
- the source nodedst
- the destination node
-
binarySearch
public static int binarySearch(byte[] key, int fromIndex, int toIndex, byte k) search the position of the input byte key in the node's key byte array part- Parameters:
key
- the input key byte arrayfromIndex
- inclusivetoIndex
- exclusivek
- the target key byte value- Returns:
- the array offset of the target input key 'k' or -1 to not found
-
binarySearchWithResult
-
serializeHeader
- Throws:
IOException
-
serializeHeader
- Throws:
IOException
-
serializeHeaderSizeInBytes
private int serializeHeaderSizeInBytes() -
deserializeHeader
- Throws:
IOException
-
deserializeHeader
- Throws:
IOException
-