Class Node

java.lang.Object
org.roaringbitmap.art.Node
Direct Known Subclasses:
LeafNode, Node16, Node256, Node4, Node48

public abstract class Node extends Object
  • Field Details

    • nodeType

      protected NodeType 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

      public Node(NodeType nodeType, int compressedPrefixSize)
      constructor
      Parameters:
      nodeType - the node type
      compressedPrefixSize - the prefix byte array size,less than or equal to 6
  • Method Details

    • sortSmallByteArray

      protected static byte[] sortSmallByteArray(byte[] key, Node[] children, int left, int right)
      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

      public 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 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

      public abstract Node getChild(int pos)
      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

      public abstract void replaceNode(int pos, Node freshOne)
      replace the position child to the fresh one
      Parameters:
      pos - the position
      freshOne - 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

      public abstract Node remove(int pos)
      remove the specified position child
      Parameters:
      pos - the position to remove
      Returns:
      an adaptive changed fresh node of the current node
    • serialize

      public void serialize(DataOutput dataOutput) throws IOException
      serialize
      Parameters:
      dataOutput - the DataOutput
      Throws:
      IOException - signal a exception happened while the serialization
    • serialize

      public void serialize(ByteBuffer byteBuffer) throws IOException
      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

      public static Node deserialize(DataInput dataInput) throws IOException
      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

      public static Node deserialize(ByteBuffer byteBuffer) throws IOException
      deserialize into a typed node
      Parameters:
      byteBuffer - the ByteBuffer
      Returns:
      the typed node
      Throws:
      IOException - indicate a exception happened
    • replaceChildren

      abstract void replaceChildren(Node[] children)
      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

      abstract void serializeNodeBody(DataOutput dataOutput) throws IOException
      serialize the node's body content
      Parameters:
      dataOutput - the DataOutput
      Throws:
      IOException - exception indicates serialization errors
    • serializeNodeBody

      abstract void serializeNodeBody(ByteBuffer byteBuffer) throws IOException
      serialize the node's body content
      Parameters:
      byteBuffer - the ByteBuffer
      Throws:
      IOException - exception indicates serialization errors
    • deserializeNodeBody

      abstract void deserializeNodeBody(DataInput dataInput) throws IOException
      deserialize the node's body content
      Parameters:
      dataInput - the DataInput
      Throws:
      IOException - exception indicates deserialization errors
    • deserializeNodeBody

      abstract void deserializeNodeBody(ByteBuffer byteBuffer) throws IOException
      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

      public static Node insertLeaf(Node current, LeafNode childNode, byte key)
      insert the LeafNode as a child of the current internal node
      Parameters:
      current - current internal node
      childNode - the leaf node
      key - the key byte reference to the child leaf node
      Returns:
      an adaptive changed node of the input 'current' node
    • copyPrefix

      public static void copyPrefix(Node src, Node dst)
      copy the prefix between two nodes
      Parameters:
      src - the source node
      dst - 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 array
      fromIndex - inclusive
      toIndex - exclusive
      k - the target key byte value
      Returns:
      the array offset of the target input key 'k' or -1 to not found
    • binarySearchWithResult

      static SearchResult binarySearchWithResult(byte[] key, int fromIndex, int toIndex, byte k)
    • serializeHeader

      private void serializeHeader(DataOutput dataOutput) throws IOException
      Throws:
      IOException
    • serializeHeader

      private void serializeHeader(ByteBuffer byteBuffer) throws IOException
      Throws:
      IOException
    • serializeHeaderSizeInBytes

      private int serializeHeaderSizeInBytes()
    • deserializeHeader

      private static Node deserializeHeader(DataInput dataInput) throws IOException
      Throws:
      IOException
    • deserializeHeader

      private static Node deserializeHeader(ByteBuffer byteBuffer) throws IOException
      Throws:
      IOException