binary tree creation|building|deserialization|unmarshalling, traversal, representation, serialization|marshalling

binary_Tree__Build_N_Print.scala

#!/usr/bin/env scala
// for The `bash` `shell script` './script.sh'
//
//import scala.math.{log, ceil}
import io.AnsiColor._
// or
//import Console.{GREEN, RED, RESET, YELLOW_B, UNDERLINED}
//
//
// ? Is something wrong with:
// SubTree.toString ?
trait Binary_Tree {
  //override def toString() = "{}"
  // unimplemented interface
  def to_Brackets_Str: String
  def node_Label: String
  def subSize: Int
  def tier: Int
}
//
object Empty_Tree extends Binary_Tree {
  //
  override def toString() = "{}"
  // warning: 
  // a pure expression does nothing in statement position; 
  // you may be omitting necessary parentheses
  def to_Brackets_Str = "{}"
  def node_Label: String = ""
  def subSize: Int = 0
  def tier: Int = 0
}
//
case class SubTree(
  var left: Binary_Tree = Empty_Tree,
  var right: Binary_Tree = Empty_Tree,
  // recursive ?
  // immutable ?
  var parent: Binary_Tree = Empty_Tree,
  var node_Label: String//,
  //tier: Int = 1//,
  // recursive ?
  //var subSize: Int = 1
) extends Binary_Tree {
  //
  override def toString() = s"${left}<" +
  s"n:${node_Label}" +
  s"(${subSize})^[${parent.node_Label}]t:${tier}" +
  s">${right}"
  // invalid escape '\{'
  def to_Brackets_Str = s"""{${left.to_Brackets_Str}""" + 
  s"""${node_Label}""" + 
  s"""${right.to_Brackets_Str}}"""
  def subSize: Int = 1 + left.subSize + right.subSize
  def tier: Int = parent.tier + 1
}
//
// Done?: implement 'tree_From_Brackets_String'
/*
 testing:
 tree_From_Brackets_String(
   tree_Str = "{{{{{}l8L{}}l4{{}r9L{}}}l2{{}r5L{}}}1*{{{}l6L{}}r3{{}r7L{}}}}",
   is_DeBug_Mode = 1 == 0
 )
*/
/** it must|expected|suppose to
 * build a 'Binary_Tree'
 * from the appropriate formatted string
 * like this: 
 *  "{{{{{}l8L{}}l4{{}r9L{}}}l2{{}r5L{}}}1*{{{}l6L{}}r3{{}r7L{}}}}"
 */
def tree_From_Brackets_String(
  tree_Str: String, 
  // <- go 1 tier|level down|start|add new subTree
  open_Tree_Char: Char = '{',
  // <- go 1 tier|level up|close|complete last subTree
  close_Tree_Char: Char = '}',
  is_DeBug_Mode: Boolean = 1 == 0
): Binary_Tree = if (
  tree_Str.isEmpty ||
  tree_Str.size < 3
) {
  // return
  Empty_Tree
} else {
  // interesting case
  // except format correctness check
  //
  //@scala.annotation.tailrec
  def inner_Loop(  
    str_To_Parse_Left: String,
    // previous state -> empty|open|close|label part
    //previous_Char: Option[Char] = None,
    //previous_Char: String = "",
    node_Label: String = "",
    // path|address|selector in a tree
    // like function combinations|composition|chain
    //insert_Pointer: Binary_Tree,
    // changing main tree placeholder
    // or complete tree so far
    //result_Accum: Binary_Tree = Empty_Tree,
    trees_List: List[Binary_Tree] = List(),
    is_DeBug_Mode: Boolean = 1 == 0
  ): Binary_Tree = if (
    str_To_Parse_Left.isEmpty ||
    str_To_Parse_Left.size < 2
  ) {
    // base case
    if (trees_List.isEmpty) {
      // guard
      Empty_Tree
    } else {
      // expected to be|contain exactly one item
      trees_List.head
    }
  } else {
    // recursive step
    val next_Str_To_Parse: String = str_To_Parse_Left.tail
    val curr_Chr: Char = str_To_Parse_Left.head
    // Done: add|isert proper 'parent'
    val (next_Label, next_Trees) = curr_Chr match {
      // <- go 1 tier|level down|start|add new subTree
      // use `backticks`
      case `open_Tree_Char` => if (node_Label.isEmpty) {
        // append current deepest subTree
        (node_Label, Empty_Tree :: trees_List)
      } else {
        // reset|side effects|mutation
        trees_List.head match {
          case st @ SubTree(lT, rT, p, nL) => st.node_Label = node_Label
          case _ => println("unexpected 'Empty_Tree' for `node_Label` change")
        }
        // return
        ("", Empty_Tree :: trees_List)
      }
      // <- go 1 tier|level up|close|complete last subTree
      // insert last && completed into previous last (if any)
      // current last|first.isComplete == true
      // expected trees_List.tail.nonEmpty == true 
      case `close_Tree_Char` => if (
          trees_List.isEmpty
        ) {
          println("unexpected empty `trees_List`")
          // return
          (node_Label, trees_List)
        } else {
          //
          if (trees_List.tail.isEmpty) {
            // it is fine if it is the last closing char '}'
            if (1 == 1 && is_DeBug_Mode) {
              Console.err.println(
                /*
                unexpected `head` only in `trees_List`(1):List(
                {}<n:l8L(1)^[]t:1>{}<n:l4(3)^[]t:1>{}<n:r9L(1)^[]t:1>{}<n:l2(5)^[]t:1>{}<n:r5L(1)^[]t:1>{}<n:1*(9)^[]t:1>{}<n:l6L(1)^[]t:1>{}<n:r3(3)^[]t:1>{}<n:r7L(1)^[]t:1>{}
                ), curr_Chr:}, next_Str_To_Parse:
                */
                "unexpected `head` only in `trees_List`" + 
                s"(${trees_List.size}):${trees_List}" +
                s""", curr_Chr:'${curr_Chr}'""" +
                s""", next_Str_To_Parse:\"${next_Str_To_Parse}\""""
              )
            }
            // return
            (node_Label, trees_List)
          } else {// if (trees_List.tail.nonEmpty) {
            //
            trees_List.tail.head match {
              // add|insert right subT 
              //case st @ SubTree(lT, rT, p, nL) => 
              case st @ SubTree(_, _, _, _) => {
                // reset|side effects|mutation
                trees_List.head match {
                  case rST @ SubTree(_, _, p, _) => {
                    rST.parent = st
                    // error: reassignment to val
                    //p = st
                  }  
                  case _ => ()// <- skip
                }  
                // reset|side effects|mutation
                st.right = trees_List.head
                // return
                // drop last|first
                (node_Label, trees_List.tail)
              }
              // add|insert left subT 
              // to the new subT replacing previous last|next first
              //case eT: Empty_Tree.type => {}
              case _ => trees_List.head match {
                case lST @ SubTree(_, _, p, _) => {
                  // ? default ?
                  val subT = SubTree(left = lST, node_Label = "")
                  // reset|side effects|mutation
                  // error: reassignment to val
                  //p = subT
                  lST.parent = subT
                  // return
                  (node_Label, subT :: trees_List.tail.tail)
                }
                case _ => (
                  node_Label, 
                  SubTree(
                    //left = trees_List.head,// Empty_Tree
                    node_Label = node_Label
                  ) :: trees_List.tail.tail
                )
              }
            }
            // return
            // drop last|first
            //(node_Label, trees_List.tail)
          }
      }
      case _ => (node_Label + curr_Chr, trees_List)
    }
    /* cases for 'tree so far' 
    considering left -> root -> right traversal
    - '{'|"{...{"|"{}" -> Empty_Tree
    - Empty_Tree + label -> SubTree(
      left = Empty_Tree|default, node_Label = "label", right = default)
    right subTree progress 
    ? is more complicated ?  
    ? is List needed 
    to merge|add current|recent complete tree
    to the last stored incomplete tree
    with incompletre|empty right child|subTree ?
    and list (size) must always contain at least one (?possibly empty?) tree 
    - SubTree + '{' -> same SubTree 
    */
    // return
    // resume|continue iteration
    inner_Loop(  
      str_To_Parse_Left = next_Str_To_Parse,
      node_Label = next_Label,
      trees_List = next_Trees,
      is_DeBug_Mode = is_DeBug_Mode
    )
  }
  //
  /// ### initialize ### ///
  // main placeholder
  /*val tree_Skeleton = SubTree(
    //parent = Empty_Tree,
    node_Label = "?"
  )*/
  // return
  inner_Loop(  
    str_To_Parse_Left = tree_Str,
    //previous_Char = "",
    //insert_Pointer = tree_Skeleton.left,
    //result_Accum = tree_Skeleton,
    is_DeBug_Mode = is_DeBug_Mode
  )
}
//  
/** it must|expected|suppose to return
 * nodes as label + tier + size
 * in some tree traversal order(ing)
 * 
 * test: 
 * res41: List[String] = List(1*, 1*, "")
 * some_Order_Treversal(bin_Tree = tree_1)
 * Done?: fix it & refactor to @tailrec
 *       add inner loop or somthing
*/
//@scala.annotation.tailrec
def some_Order_Treversal(
  bin_Tree: Binary_Tree, 
  is_DeBug_Mode: Boolean = 1 == 0
): List[(String, Int, Int)] = {
  //
  @scala.annotation.tailrec
  def inner_Loop(  
    // ? it must be 'stack|queue' here
    // to iterate through ?
    roots_Stack: List[Binary_Tree],
    result_Accum: List[(String, Int, Int)] = List(),
    is_DeBug_Mode: Boolean = 1 == 0
  ): List[(String, Int, Int)] = if (roots_Stack.isEmpty) {
    // base case
    // return
    result_Accum
  } else {
    // recursive step
    val sub_Tree = roots_Stack.head
    val (next_Stack, next_Accum) = sub_Tree match {
      case eT: Empty_Tree.type => {
      //error: identifier expected but 'type' found.
      //case Empty_Tree.type => {
        // base case
        // stop treversing (down)
        // just reduce stack to converge to the base case|stop condition
        (roots_Stack.tail, result_Accum)
        //left_Result ++ right_Result
      }
      case st @ SubTree(lT, rT, p, nL) => {
        // recursive step
        // ? it must be known|tracked 
        // what roots|subTrees was already proccesed traversed ?
        // ? to distinguish|choose between left|root|right ?
        // <- actually no (need for that)
        // ? scan 'result_Accum' ?
        // ? or use dedicated Set ?
        // ? merge ?
        // ? is it 'tailrec' ?
        /* cases:
        - 'root' in
        - 'left' in <- & what if it is an 'Empty_Tree' ?
        - 'right' in <- & what if it is an 'Empty_Tree' ?
        - nothing in yet, 1-st encounter|occurence
        */
        // return
        (
          // reducing stack to converge to the base case|stop condition
          // managing|maintaining|creating appropriate ordering
          // for: {{{}l2{}}1*{{}r3{}}}
          // -> List(r3, l2, 1*)
          //lT :: (rT :: roots_Stack.tail), 
          // -> List(l2, r3, 1*)
          rT :: (lT :: roots_Stack.tail), 
          (nL, st.tier, st.subSize) :: result_Accum
        )
      }
    }
    // return
    inner_Loop(  
      roots_Stack = next_Stack, 
      result_Accum = next_Accum,
      is_DeBug_Mode = is_DeBug_Mode
    )
  }
  /// ### initialize ### ///
  // return
  inner_Loop(  
    roots_Stack = List(bin_Tree),
    result_Accum = List(),
    is_DeBug_Mode = is_DeBug_Mode
  )
}
//
// Done?: implement `print_Tier_By_Tier`
/** testing:
 * print_Tier_By_Tier(bin_Tree = tree_1, is_DeBug_Mode = 1 == 1)
 */
def print_Tier_By_Tier(
  bin_Tree: Binary_Tree,
  is_DeBug_Mode: Boolean = 1 == 0
): Unit = {
  //
  import scala.math.{log, ceil}
  import io.AnsiColor._
  // or
  //import Console.{GREEN, RED, RESET, YELLOW_B, UNDERLINED}
  //
  // log(a)(x) = log(b)(x) / log(b)(a)
  //scala> (0 to 8 by 1).map(i => (i, math.ceil(log_2(i)).toInt))
  //res20: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector(
  //  (0,-2147483648), (1,0), (2,1), (3,1), (4,2), (5,2), (6,2), (7,2), (8,3))
  //scala> (0 to 8 by 1).map(i => (i, log_2(i)))
  //res21: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector(
  //  (0,-2147483648), (1,0), (2,1), (3,1), (4,2), (5,2), (6,2), (7,2), (8,3))
  def log_2(x: Int): Int = (math.log(x) / math.log(2)).toInt
  //
  //error: value subSize is not a member of Binary_Tree ??? WTF !!!
  val max_Tier: Int = log_2(bin_Tree.subSize) + 1
  val triers = Array.fill(max_Tier)(List[String]())
  if (is_DeBug_Mode) {
    Console.err.println(
      s"triers(${triers.size}):" + 
      s"${RESET}${YELLOW_B}${RED}${UNDERLINED}${triers.mkString(",")}${RESET}"
    )
  }
  // traverse
  var nodes_Stack = List(bin_Tree)
  //
  for(node <- 1 to bin_Tree.subSize){
    //
    val current_Node = nodes_Stack.head
    //
    nodes_Stack = nodes_Stack.tail
    //
    current_Node match {
      case s: SubTree => {
        //print("SubTree")
        //java.lang.ArrayIndexOutOfBoundsException: 2
        triers(s.tier - 1) = s.node_Label :: triers(s.tier - 1)
        if (1 == 1 && is_DeBug_Mode) {
          Console.err.println(
            s"s.tier:${RESET}${YELLOW_B}${RED}${UNDERLINED}${s.tier}${RESET}" + 
            s"s.subSize:${RESET}${YELLOW_B}${RED}${UNDERLINED}${s.subSize}${RESET}" + 
            s"s.node_Label:${RESET}${YELLOW_B}${RED}${UNDERLINED}${s.node_Label}${RESET}"     
          )
        }
        s.left match {
          case lT: SubTree => {// prepend
            nodes_Stack = lT :: nodes_Stack}
          case _ => ()  
        }
        s.right match {
          case rT: SubTree => {// prepend
            nodes_Stack = rT :: nodes_Stack}
          case _ => ()  
        }
      }
      case e: Empty_Tree.type => {
        //print("Empty_Tree")
      }
      case _ => print("!!! unexpected undefined!!!")
    }
    //
    if (1 == 0 && current_Node.isInstanceOf[SubTree]) {
      /* scala> tree_1.getClass()
      res24: Class[_ <: SubTree] = class SubTree
      scala> tree_1.parent.getClass()
      res25: Class[_ <: Binary_Tree] = class Empty_Tree$
      scala> tree_1.parent.isInstanceOf[Empty_Tree.type]
      res29: Boolean = true
      scala> tree_1.parent.isInstanceOf[SubTree.type]
      <console>:17: warning: 
      fruitless type test: 
        a value of type Binary_Tree 
        cannot also be a SubTree.type (the underlying of SubTree.type)
             tree_1.parent.isInstanceOf[SubTree.type]                               ^
      res30: Boolean = false
      scala> tree_1.parent.isInstanceOf[SubTree]
      res31: Boolean = false
      scala> tree_1.isInstanceOf[SubTree]
      res32: Boolean = true
      scala> tree_1.isInstanceOf[Empty_Tree.type]
      <console>:17: warning: 
        fruitless type test: 
          a value of type SubTree 
          cannot also be a Empty_Tree.type (the underlying of Empty_Tree.type)
             tree_1.isInstanceOf[Empty_Tree.type]
                                ^
      res33: Boolean = false
      */
      // error: value left is not a member of Binary_Tree
      /*if (current_Node.left.isInstanceOf[SubTree]) {
        // prepend
        nodes_Stack = current_Node.left :: nodes_Stack
      }
      if (current_Node.right.isInstanceOf[SubTree]) {
        // prepend
        nodes_Stack = current_Node.right :: nodes_Stack
      }
      //
      triers(current_Node.subSize - 1) = current_Node.node_Label :: triers(
        current_Node.subSize - 1)*/
    }
  }
  // store nodes by levels|triers
  //println(bin_Tree)
  triers.foreach(t => println(t.mkString(" ")))
}
//
def hierarchical_Drop_Down(
  ordered_Nodes: List[(String, Int, Int)]
): Unit = {
  println("hierarchical drop down")
  for ((label, tier, t_Size) <- ordered_Nodes.reverseIterator) {
    println(
      s"""${tier}:|${UNDERLINED}${"\t" * (tier - 1)}""" +
      s"""${label}(${t_Size})${RESET}"""
    )
  }
}
//
//
/// ### >>> unit test <<< ### ///
// that kind of invocation (instead of 'App.main()') works for `script`
val is_DeBug_Mode: Boolean = 1 == 1
val open_Tree = '{'
val close_Tree = '}'
val tree_Str_1 = "{{{{{}l8L{}}l4{{}r9L{}}}l2{{}r5L{}}}1*{{{}l6L{}}r3{{}r7L{}}}}"
val tree_1 = SubTree(
  //parent = Empty_Tree,
  node_Label = "1*"//,
  //tier = 1//,
  //subSize = 1//3//9
)
val subTree_2 = SubTree(
  parent = tree_1,
  node_Label = "l2"//,
  //tier = 2,
  //subSize = 1
)
val subTree_3 = SubTree(
  parent = tree_1,
  node_Label = "r3"//,
  //tier = 2,
  //subSize = 1
)
//
//tree_1.subSize += subTree_2.subSize + subTree_3.subSize
tree_1.left = subTree_2
tree_1.right = subTree_3
//
println(tree_1)
println(tree_1.to_Brackets_Str)
//res41: List[String] = List(1*, 1*, "")
val ordered_Nodes_1 = some_Order_Treversal(
  bin_Tree = tree_1, 
  is_DeBug_Mode = 1 == 0
)
println(
  "`some_Order_Treversal`:\n" +
  ordered_Nodes_1
)
print_Tier_By_Tier(bin_Tree = tree_1, is_DeBug_Mode = 1 == 1)
//
println("`tree_From_Brackets_String` ...")
println(tree_Str_1)
val tree_2 = tree_From_Brackets_String(
  tree_Str = tree_Str_1, 
  open_Tree_Char = open_Tree,//'{',
  close_Tree_Char = close_Tree,//'}',
  is_DeBug_Mode = is_DeBug_Mode
)
println(tree_2)
println(tree_2.to_Brackets_Str)
val ordered_Nodes_2 = some_Order_Treversal(
  bin_Tree = tree_2, 
  is_DeBug_Mode = 1 == 0
)
println(
  "`some_Order_Treversal`:\n" +
  ordered_Nodes_2
)
print_Tier_By_Tier(bin_Tree = tree_2, is_DeBug_Mode = 1 == 1)
hierarchical_Drop_Down(ordered_Nodes_2)