Module roaringbitmap
Package org.roaringbitmap.art

Class BranchNode

java.lang.Object
org.roaringbitmap.art.Node
org.roaringbitmap.art.BranchNode
Direct Known Subclasses:
Node16, Node256, Node4, Node48
public abstract class BranchNode extends Node

  • Field Details

    • prefix

      protected byte[] prefix

    • count

      protected short count

    • ILLEGAL_IDX

      public static final int ILLEGAL_IDX
      See Also:

  • Constructor Details

    • BranchNode

      public BranchNode(int compressedPrefixSize)
      constructor
      Parameters:
      compressedPrefixSize - the prefix byte array size,less than or equal to 6

  • Method Details

    • postClone

      public void postClone(BranchNode newlyCloned, Node[] oldChildren, Node[] newChildren)

    • nodeType

      protected abstract NodeType nodeType()

    • prefixLength

      protected byte prefixLength()

    • 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

    • insert

      protected abstract BranchNode insert(Node childNode, byte key)
      insert the LeafNode as a child of the current internal node
      Parameters:
      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(BranchNode src, BranchNode dst)
      copy the prefix between two nodes
      Parameters:
      src - the source node
      dst - the destination node

    • 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 org.roaringbitmap.art.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

    • getChildAtKey

      public abstract Node getChildAtKey(byte key)
      get the child at the specified key in the node. the behavior is equivalent to int pos = getChildPos(key); return (pos != ILLEGAL_IDX) ? getChild(pos) : null; but subclasses may be able to provide a more efficient implementation
      Parameters:
      key - the position
      Returns:
      a Node corresponding to the input position, or null if not found

    • 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

    • serializeHeader

      protected void serializeHeader(DataOutput dataOutput) throws IOException
      Specified by:
      serializeHeader in class Node
      Throws:
      IOException

    • serializeHeader

      protected void serializeHeader(ByteBuffer byteBuffer) throws IOException
      Specified by:
      serializeHeader in class Node
      Throws:
      IOException

    • serializeHeaderSizeInBytes

      protected int serializeHeaderSizeInBytes()
      Overrides:
      serializeHeaderSizeInBytes in class Node