package exercises

object Exercise {

  // 0. Вам нужно реализовать ADT дерева. Трейт для декомпозиции: Derevo. Наследники: Listok и Vetka.

  // 1 Вам нужно реализовать вспомогательный конструктор для тестов.
  // 2. Напишите функцию вычисления размера, которая подсчитывает количество узлов (листьев и ветвей) в дереве.
  // 3. Напишите функцию вычисления максимума, которая возвращает максимальный элемент в дереве(тип [Int]).
  // 4. Напишите функцию вычисления глубины, которая возвращает максимальную длину пути от корня дерева до любого листа.
  // 5. Напишите функцию map, которая изменяет сопоставляет каждый элемент дерева с заданной функцией.

  // 6. Напишите функцию вычисления размера(sizeF), которая подсчитывает количество узлов (листьев и ветвей)
  // в дереве через fold.
  // 7. Напишите функцию вычисления максимума(maximumF), которая возвращает максимальный элемент в дереве [Int]. (Заметка:
  //В Scala вы можете использовать x.max (y) или x max y, чтобы вычислить максимум двух целых чисел x
  //и у.) через fold
  // 8. Напишите функцию вычисления глубины (depthF), которая возвращает максимальную длину пути от корня
  // дерева до любого листа через fold
  // 9. Напишите функцию mapF, которая изменяет сопоставляет каждый элемент дерева с заданной функцией через fold.

  //Подсказка
  //Вы можете использовать x.max (y) или x max y, чтобы вычислить максимум двух целых чисел x и у.

  trait Derevo[A]

  case class Vetka[A](lft: Derevo[A], rgt: Derevo[A]) extends Derevo[A]

  case class Listok[A](a: A) extends Derevo[A]

  object Derevo {
    def vetka[A](lft: Derevo[A], rgt: Derevo[A]): Derevo[A] = Vetka[A](lft, rgt)

    def listok[A](a: A): Derevo[A] = Listok[A](a)
  }

  def size[A](t: Derevo[A]): Int = t match {
    case t: Listok[A] => 1
    case t: Vetka[A] => size(t.lft) + size(t.rgt)
  }

  def maximum(t: Derevo[Int]): Int = t match {
    case t: Listok[Int] => t.a
    case t: Vetka[Int] => math.max(maximum(t.lft), maximum(t.rgt))
  }

  def depth[A](t: Derevo[A]): Int = t match {
    case t: Vetka[A] => math.max(depth(t.lft) + 1, depth(t.rgt) + 1)
    case t: Listok[A] => 1
  }

  def map[A, B](t: Derevo[A])(f: A => B): Derevo[B] = t match {
    case t: Listok[A] => Listok(f(t.a))
    case t: Vetka[A] => Vetka(map(t.lft)(f), map(t.rgt)(f))
  }

  def fold[A, B](t: Derevo[A])(f: A => B)(g: (B, B) => B): B = t match {
    case t: Listok[A] => f(t.a)
    case t: Vetka[A] => g(fold(t.lft)(f)(g), fold(t.rgt)(f)(g))
  }

  def depthF[A](t: Derevo[A]): Int = t match {
    case t: Vetka[A] => fold(t)((m: A) => 1)((m: Int, n: Int) => (m max n) + 1)
    case t: Listok[A] => 1
  }

  def sizeF[A](t: Derevo[A]): Int = t match {
    case t: Listok[A] => 1
    case t: Vetka[A] => fold(t)((m: A) => 1)((m: Int, n: Int) => m + n)
  }

  def maximumF(t: Derevo[Int]): Int = t match {
    case t: Listok[Int] => t.a
    case t: Vetka[Int] => fold(t)((m: Int) => m)((m: Int, n: Int) => m max n)
  }

  def mapF[A, B](t: Derevo[A])(f: A => B): Derevo[B] = {
    fold(t)(a => Listok(f(a)): Derevo[B])((left, right) => Vetka(left, right))
  }
}