package test

object Main {
    trait BSTree[+A] {
    def value: Option[A] = this match {
        case n: Node[A] => Some(n.v)
        case l: Leaf[A] => Some(l.v)
        case Empty      => None
    }

    def left: Option[BSTree[A]] = this match {
        case n: Node[A] => Some(n.l)
        case l: Leaf[A] => None
        case Empty      => None
    }

    def right: Option[BSTree[A]] = this match {
        case n: Node[A] => Some(n.r)
        case l: Leaf[A] => None
        case Empty      => None
    }
    }

    case class Node[A](v: A, l: BSTree[A], r: BSTree[A]) extends BSTree[A]
    case class Leaf[A](v: A) extends BSTree[A]
    case object Empty extends BSTree[Nothing]

    implicit class MyArrayExtentions(val x:Seq[Int]) {
         def moa:Int = if (x.length > 0) x.length/2 else -1
    }

    def splitArrayLRM(arr:Seq[Int]) = (
        if (arr.moa>=0) arr.slice(0,arr.moa) else Seq[Int](), 
        if (arr.length>0) arr.slice(arr.moa,arr.moa+1) else Seq[Int](),
        if (arr.moa>=0) arr.slice(arr.moa+1, arr.length) else Seq[Int]()
        )
     
    def listToTree(arr:Seq[Int]):Node[Int] = {
        val (l,c,r) = splitArrayLRM(arr)
        Node(c(0),
            if (l.length>0) listToTree(l) else Empty,
            if (r.length>0) listToTree(r) else Empty)
    }

    def main(args:Array[String]) = {
        val a0 = Seq[Int]()
        val a1 = 1 :: Nil
        val a2 = 1 :: 2 :: Nil
        val a3 = 1 :: 2 :: 3 :: Nil
        val a4 = 1 :: 2 :: 3 :: 4 :: Nil
        val a5 = 1 :: 2 :: 3 :: 4 :: 5 :: Nil
        println(s"${a0.moa}, ${a1.moa}, ${a2.moa}, ${a3.moa}, ${a4.moa}")
        println(s"${splitArrayLRM(a0)}, ${splitArrayLRM(a1)}, ${splitArrayLRM(a2)}, ${splitArrayLRM(a3)}, ${splitArrayLRM(a4)}, ${splitArrayLRM(a5)}")
        
        val n1 = listToTree(a1)
    }
}