/*
Exercise 1
You have to create a data type for representing a person. A person has a firstName, a lastName and probably an age. A person can be a normal human or super hero. And a super hero have a nickName, eventually a "human" identity. A human is just a normal person ! A super hero has super power. Super power can be what you want !
 */

trait BST {
  // Add a value to a BST
  def add (value : Int) : BST
  // Test if a value is in a BST
  def in (value : Int) : Boolean
  // // How to print a BST
  //override def toString = "."
  // // The sum of all values in the BST
  def sum : Int
  // // Comparison of two BST (based on their sum)
  def <= (tree : BST) : Boolean = this.sum <= tree.sum
  // // How to merge two BST
  def merge (tree : BST) : BST
}

case class Node (value : Int, left : BST, right : BST) extends BST {

  def add(value: Int) : BST = {
    def aux(value: Int, tree: BST) : BST = {
      tree match {
        case Empty => Node(value, Empty, Empty)
        case Node(v, l, r) => {
          if (value < v) {
            Node(v, aux(value, l), r)
          } else if (value == v) {
            Node(v, l, r)
          } else {
            Node(v, l, aux(value, r))
          }
        }
      }
    }
    aux(value, this)
  }

  def in(value : Int) : Boolean = {
    def aux(value: Int, tree: BST) : Boolean = {
      tree match {
        case Empty => false
        case Node(v, l, r) => (v == value) || (value < v && aux(value, l)) || (value > v && aux(value, r))
      }
    }
    aux(value, this)
  }

  def sum : Int = {
    value + left.sum + right.sum
  }

  def merge (tree : BST) : BST = {
    
  }
}

object Empty extends BST {

  def add(value: Int) : BST = Node(value, Empty, Empty)

  def in(value : Int) : Boolean = false

  def sum = 0

  def merge (tree : BST) : BST = tree
}

object Week4 {
  def main (args: Array[String]): Unit = {
    val a = Empty.add(10).add(5).add(13).add(3).add(8)
    val b = a.add(7)
    val c = a.add(6)
    val d = Empty.add(1).add(2).add(3).add(3).add(4)

    println(b)
    println(d)

    println("10 in a " + a.in(10))
    println("8 in a " + a.in(8))
    println("13 in a " + a.in(13))
    println("42 in a " + a.in(42))

    println("sum a " + a.sum)
    println("sum b " + b.sum)

    println("a <= b " + (a <= b))

    // println(b.merge(d))
    // println(d.merge(b))
  }
}