sealed trait BT[+A]
case object Empty extends BT[Nothing]
case class Node[+A](elem: (A, A), left: BT[A], right: BT[A]) extends BT[A]

object DictionaryTree{

  def main(args: Array[String]): Unit = {
    val bt = stworzSlownik()
     println(tlumacz(bt, "słońce"))
     println(tlumacz(dodaj(bt, "ogień", "fire"), "ogień"))
     inorder(bt)
  }

  //Z1
  def stworzSlownik(): BT[String] =
    Node(("woda", "water"), Node(("słońce", "sun"), Node(("księżyc", "moon"), Empty, Empty),
      Node(("drzewo", "tree"), Empty, Empty)), Node(("głowa", "head"),
      Node(("telefon", "phone"), Empty, Empty), Empty))

  //Z2
  def tlumacz(slownik: BT[String], slowo: String): String =
    slownik match {
      case Empty => throw new Exception("Brak slowa w slowniku!")
      case Node((pol, ang), l, r) =>
        if (pol == slowo) ang
        else if (slowo < pol) tlumacz(l, slowo) else tlumacz(r, slowo)
    }

  //Z3
  def dodaj(slownik: BT[String], pol: String, ang: String): BT[String] =
    slownik match {
      case Empty => Node((pol, ang), Empty, Empty)
      case Node((pl, en), l, r) =>
        if (pl == pol) {
          if (en == ang) throw new Exception("Podane slowo wraz z podanym tlumaczeniem istnieje juz w slowniku!")
          else if (en.length() < ang.length()) Node((pl, en), l, r)
          else Node((pl, ang), l, r)
        }
        else if (pol < pl) Node((pl, en), dodaj(l, pol, ang), r)
        else Node((pl, en), l, dodaj(r, pol, ang))
    }

  //Z4
  def inorder[A](bt: BT[A]): List[(A, A)] =
    {
      def inord(p: (BT[A], List[(A, A)])): List[(A, A)] = p match {
        case (Empty, labels) => labels
        case (Node(v, t1, t2), labels) => inord(t1, v :: inord(t2, labels))
      }
      inord(bt, Nil)
    }

  //Z5
  def sort(list: List[(String, String)]): List[(String, String)] = {

    val porz = (a: (String, String), b: (String, String)) => {
      val (_, en1) = a
      val (_, en2) = b
      if (en1 < en2) true else false
    }

    def insert(list: List[(String, String)], t: (String, String)): List[(String, String)] = list match {
      case Nil => List[(String, String)](t)
      case x :: r => if (porz(x, t)) x :: insert(r, t)
      else t :: x :: r
    }

    (list :\ List[(String, String)]())((h, posortowana) => insert(posortowana, h))
  }

  //Z6
  def stworzDrzewo(list: List[(String,String)]): BT[String] = {
    def drzewo(list: List[(String,String)], acc: BT[String]): BT[String] =
      list match {
        case Nil => acc
        case (pl,en) :: t => drzewo(t, dodaj(acc, en, pl))
      }
    drzewo(list, Empty)
  }

  def stworzDrzewoWywazone(list: List[(String,String)]):BT[String] = {
    def drzewo(list: List[(String,String)], acc: BT[String]): BT[String] =
      if(list==Nil) acc
      else {
        val (list1,list2) = list.splitAt(list.length/2-1)
        if(list2==Nil) {
          val (pl,en) = list1.head
          dodaj(acc,en,pl)
        }
        else {
        val (pl,en) = list2.head
        val tree1 = dodaj(acc,en,pl)
        val tree2 = drzewo(list1,tree1)
        drzewo(list2.tail,tree2)
        }
      }
    drzewo(list, Empty)
  }

}