Package io.openml.gearbox.binarytree.pathvisitor

Class Path<T>

java.lang.Object
io.openml.gearbox.binarytree.pathvisitor.Path<T>
Type Parameters:
T - The type of value store in the TreeNode
public class Path<T> extends Object
A Path represents a one-way path between two TreeNodes in a binary tree.

The Path can be root-to-leaf or node-to-node. The internal of Path is a doubly linked list, with each list node wrapping a TreeNode as list node value.

Path is designed for enhancing the performance of path-traversing algorithm. For example, we can cut a Path in the middle using trim(TreeNode) in constant time, instead of iteratively removing path tails(O(n) time). In the meantime, we can also get the length of the Path in constant time.

  • Constructor Details

    • Path

      public Path()

  • Method Details

    • emptyPath

      public static <T> Path<T> emptyPath()
      Creates a Path with no path elements(TreeNode) yet.
      Type Parameters:
      T - The type of value store in the TreeNode
      Returns:
      a new Path instance

    • deepCopyOf

      public static <T> Path<T> deepCopyOf(Path<T> other)
      Constructs a Path containing the path elements of the specified Path, in the order they are contained in the specified Path.
      Type Parameters:
      T - The type of value store in the TreeNode
      Parameters:
      other - The Path whose path elements are to be placed into the new Path
      Returns:
      a new Path instance
      Throws:
      NullPointerException - if the other is null

    • view

      public List<TreeNode<T>> view()
      Returns an immutable view of all path elements in this Path at the time of calling this method.

      Adding or removing elements in either the view or the original Path is not reflected on the other side. In other words, since a binary tree is immutable(because TreeNode is immutable), mutating the tree(or a path of it) must result in a new view.

      Generating the view takes O(n) time where n is the length of the list.

      Returns:
      a List of current path elements of a binary tree path

    • trim

      public void trim(TreeNode<T> expectedTail)
      Keeps removing TreeNode elements from end of an under-construction path (last, 2nd last, 3rd last ...) until the element to be removed equals to a specified element.

      Path is assumed not to be empty.

      This method executes in constant time.

      Parameters:
      expectedTail - The specified element that signals the stop of the trimming process

    • addLast

      public void addLast(TreeNode<T> pathElement)
      Appends a TreeNode to the end of this path.
      Parameters:
      pathElement - The TreeNode to append

    • getLast

      public TreeNode<T> getLast()
      Returns the tail of this path.
      Returns:
      a TreeNode reference
      Throws:
      NoSuchElementException - if the path is empty

    • isEmpty

      public boolean isEmpty()
      Returns whether there are any TreeNode already been added to the path yet.
      Returns:
      true is path is empty or false, otherwise

    • removeLast

      public TreeNode<T> removeLast()
      Deletes the tail of this path.
      Returns:
      the element that has been removed from this path
      Throws:
      NoSuchElementException - if the path is empty

    • length

      public int length()
      Returns the length of this path.
      Returns:
      the number of TreeNodes in this path

    • toString

      public String toString()
      Overrides:
      toString in class Object