Package io.openml.gearbox.binarytree

Class BinaryTreeSerde<T>

java.lang.Object
io.openml.gearbox.binarytree.BinaryTreeSerde<T>
Type Parameters:
T - The type of value store in the tree node
public final class BinaryTreeSerde<T> extends Object
Serializes and deserializes a binary search tree.

Each BinaryTreeSerde instance has a pair of unique reserved characters - left delimiter & right delimiter. They are used to enclose a node value. For example, if left delimiter is '(' and right delimiter is ')', BinaryTreeSerde serializes and deserialzes back-and-forth in the following manner: 

      1
    /   \
   2     3   <--->   "1(2(4))(3)"
  /
 4

 ----------------------------------

    1
  /   \
 2     3     <--->   "1(2()(4))(3)"
  \
   4
Note how node values (1, 2, 3, 4) are delimited by "()". Serializations of node values must not contain the reserved delimiter characters (in the example, they are '(' and ')'), otherwise the behavior of BinaryTreeSerde is undefined.

To make serialization as compact as possible, BinaryTreeSerde avoids putting unnecessary empty right node in the serialization. For example, both "1(2(4))(3)" and "1(2(4)())(3)" represent the same tree, but the former one is actually used.

  • Method Details

    • usingParenthesesDelimiter

      public static <T> BinaryTreeSerde<T> usingParenthesesDelimiter()
      Creates a BinaryTreeSerde instance using '(' and ')' as the delimiter characters.
      Type Parameters:
      T - The type of value store in the tree node
      Returns:
      a new instance

    • usingDelimiterOf

      public static <T> BinaryTreeSerde<T> usingDelimiterOf(char leftDelimiter, char rightDelimiter)
      Creates a BinaryTreeSerde instance using the specified the delimiter characters.
      Type Parameters:
      T - The type of value store in the tree node
      Parameters:
      leftDelimiter - The provided left delimiter character, i.e. the char before the first node value char
      rightDelimiter - The provided right delimiter character, i.e. the char after the last node value char
      Returns:
      a new instance

    • serialize

      public String serialize(TreeNode<T> root)
      Returns a string representation of a binary tree by serializing each node value using the default Objects.toString(Object).
      Parameters:
      root - The root of the binary tree
      Returns:
      the string representation of the binary tree
      Throws:
      NullPointerException - if any root is null

    • serialize

      public String serialize(TreeNode<T> root, Function<T,String> serializer)
      Returns a string representation of a binary tree by serializing each node value using a specified strategy.
      Parameters:
      root - The root of the binary tree
      serializer - The provided node value serialization strategy
      Returns:
      the string representation of the binary tree
      Throws:
      NullPointerException - if any argument is null

    • deserialize

      public TreeNode<T> deserialize(String string, Function<String,T> deserializer)
      Deserializes a binary tree in string representation.

      This method serializes in O(n) time & space without recursion.

      The internal of this method first constructs a tree with mutable nodes and then makes an immutable copy of it.

      Parameters:
      string - The string representation of the tree
      deserializer - A strategy to transform a string representation to object
      Returns:
      the root of the deserialized tree
      Throws:
      NullPointerException - if string or deserializer is null