Package org.basex.query.util.fingertree

Class FingerTree<N,E>

java.lang.Object
org.basex.query.util.fingertree.FingerTree<N,E>
Type Parameters:
N - node type
E - element type
All Implemented Interfaces:
Iterable<E>
public abstract class FingerTree<N,E> extends Object implements Iterable<E>
A node of a FingerTree.
Author:
BaseX Team 2005-21, BSD License, Leo Woerteler

  • Constructor Details

    • FingerTree

      public FingerTree()

  • Method Details

    • empty

      public static <E> FingerTree<E,E> empty()
      Returns the empty finger tree.
      Type Parameters:
      E - element type
      Returns:
      empty finger tree

    • singleton

      public static <E> FingerTree<E,E> singleton(Node<E,E> leaf)
      Creates a singleton finger tree containing the given leaf node.
      Type Parameters:
      E - element type
      Parameters:
      leaf - the contained leaf
      Returns:
      the singleton finger tree

    • isEmpty

      public final boolean isEmpty()
      Checks if this node is empty.
      Returns:
      true if the node is empty, false otherwise

    • get

      public final E get(long index)
      Returns the element at the given position in this tree.
      Parameters:
      index - index of the element
      Returns:
      the element

    • set

      public abstract FingerTree<N,E> set(long pos, E val)
      Replaces the element at the given position in this tree.
      Parameters:
      pos - position
      val - element
      Returns:
      resulting tree

    • size

      public abstract long size()
      The size of this tree.
      Returns:
      number of elements in this tree

    • cons

      public abstract FingerTree<N,E> cons(Node<N,E> fst)
      Adds an element to the front of this tree.
      Parameters:
      fst - new first element
      Returns:
      updated tree

    • snoc

      public abstract FingerTree<N,E> snoc(Node<N,E> lst)
      Adds an element to the end of this tree.
      Parameters:
      lst - new last element
      Returns:
      updated tree

    • head

      public abstract Node<N,E> head()
      Returns the first element of this tree.
      Returns:
      first element
      Throws:
      NoSuchElementException - if the tree is empty

    • tail

      public abstract FingerTree<N,E> tail()
      Returns this tree removing the first element.
      Returns:
      updated tree

    • last

      public abstract Node<N,E> last()
      Returns the last element of this tree.
      Returns:
      last element
      Throws:
      NoSuchElementException - if the tree is empty

    • init

      public abstract FingerTree<N,E> init()
      Returns this tree removing the last element.
      Returns:
      updated tree

    • concat

      public abstract FingerTree<N,E> concat(Node<N,E>[] mid, long size, FingerTree<N,E> other)
      Concatenates this finger tree with the given one.
      Parameters:
      mid - nodes between the two trees
      size - sum of the sizes of all nodes in the middle array
      other - the other tree
      Returns:
      concatenation of both trees

    • reverse

      public abstract FingerTree<N,E> reverse(QueryContext qc)
      Creates a reversed version of this tree.
      Parameters:
      qc - query context
      Returns:
      reversed tree

    • insert

      public abstract FingerTree<N,E> insert(long pos, E val, QueryContext qc)
      Inserts the given value at the given position into this tree.
      Parameters:
      pos - position to insert at
      val - value to insert
      qc - query context
      Returns:
      resulting tree

    • remove

      public abstract TreeSlice<N,E> remove(long pos, QueryContext qc)
      Removes an element from this tree.
      Parameters:
      pos - position of the element to remove
      qc - query context
      Returns:
      resulting (potentially partial) tree
      Throws:
      AssertionError - if this tree is empty

    • slice

      public abstract TreeSlice<N,E> slice(long pos, long len)
      Extracts a slice from this tree containing the len elements starting with that at position pos.
      Parameters:
      pos - position of the first element
      len - number of elements
      Returns:
      resulting slice

    • replaceHead

      public abstract FingerTree<N,E> replaceHead(Node<N,E> head)
      Replaces the first node in this tree.
      Parameters:
      head - new first node
      Returns:
      resulting tree

    • replaceLast

      public abstract FingerTree<N,E> replaceLast(Node<N,E> last)
      Replaces the last node in this tree.
      Parameters:
      last - new last node
      Returns:
      resulting tree

    • toString

      public final String toString()
      Overrides:
      toString in class Object

    • checkInvariants

      public abstract long checkInvariants()
      Checks that this tree does not violate any invariants.
      Returns:
      number of elements in this tree
      Throws:
      AssertionError - if any invariant was violated

    • listIterator

      public final ListIterator<E> listIterator(long start)
      Creates a ListIterator over the elements in this tree.
      Parameters:
      start - starting position (i.e. the position initially returned by ListIterator.nextIndex())
      Returns:
      the list iterator

    • iterator

      public final ListIterator<E> iterator()
      Specified by:
      iterator in interface Iterable<N>