Package org.basex.query.util.fingertree

Interface Node<N,E>

Type Parameters:
N - node type
E - element type
All Superinterfaces:
NodeLike<N,E>
public interface Node<N,E> extends NodeLike<N,E>
A node inside a digit.
Author:
BaseX Team 2005-21, BSD License, Leo Woerteler

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    arity()
    Number of children of this node.
    long
    checkInvariants()
    Checks that this node does not violate any invariants.
    N
    getSub(int pos)
    Returns the sub-node at the given position in this node.
    boolean
    insert(Node<N,E>[] siblings, long pos, E val)
    Inserts the given element at the given position in this node.
    NodeLike<N,E>[]
    remove(Node<N,E> l, Node<N,E> r, long pos)
    Removes the element at the given position in this node.
    Node<N,E>
    reverse()
    Creates a reversed version of this node.
    Node<N,E>
    set(long pos, E val)
    Replaces the element at the given position in this node with the given element.
    long
    size()
    Number of elements in this node.
    NodeLike<N,E>
    slice(long off, long len)
    Extracts a sub-tree containing the elements at positions off .. off + len - 1 from the tree rooted at this node.

    Methods inherited from interface org.basex.query.util.fingertree.NodeLike

    append

  • Method Details

    • size

      long size()
      Number of elements in this node.
      Returns:
      number of elements

    • arity

      int arity()
      Number of children of this node.
      Returns:
      number of children

    • getSub

      N getSub(int pos)
      Returns the sub-node at the given position in this node.
      Parameters:
      pos - index of the sub-node, must be between 0 and arity() - 1
      Returns:
      the sub-node

    • reverse

      Node<N,E> reverse()
      Creates a reversed version of this node.
      Returns:
      a node with the reverse order of contained elements

    • insert

      boolean insert(Node<N,E>[] siblings, long pos, E val)
      Inserts the given element at the given position in this node. The array siblings is used for input as well as output. It must contain the left and right sibling of this node (if existing) at positions 0 and 2 when calling the method. After the method returns, there are two cases to consider:
      • If the method returned true (i.e. this node was split), the array contains the left sibling at position 0, the split node at position 1 and 2 and the right sibling at 3.
      • Otherwise the array contains (possibly modified versions of) left sibling at position 0, this node at position 1 and the right sibling at position 2.
      Parameters:
      siblings - sibling array for input and output
      pos - insertion position
      val - value to insert
      Returns:
      true if the node was split, false otherwise

    • set

      Node<N,E> set(long pos, E val)
      Replaces the element at the given position in this node with the given element.
      Parameters:
      pos - position
      val - new value
      Returns:
      resulting node

    • remove

      NodeLike<N,E>[] remove(Node<N,E> l, Node<N,E> r, long pos)
      Removes the element at the given position in this node. If this node is merged with one of its neighbors, the middle element of the result array is null.
      Parameters:
      l - left neighbor, possibly null
      r - right neighbor, possibly null
      pos - position of the element to delete
      Returns:
      three-element array with the new left neighbor, node and right neighbor

    • slice

      NodeLike<N,E> slice(long off, long len)
      Extracts a sub-tree containing the elements at positions off .. off + len - 1 from the tree rooted at this node. This method is only called if len < this.size() holds.
      Parameters:
      off - offset of first element
      len - number of elements
      Returns:
      the sub-tree, possibly under-full

    • checkInvariants

      long checkInvariants()
      Checks that this node does not violate any invariants.
      Returns:
      this node's size
      Throws:
      AssertionError - if an invariant was violated