package kapitel_03

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 3, Daten und ihre Struktur
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_03_08_StructuralRecursion_App extends App {

  sealed abstract class IntList
  case object Nil extends IntList
  case class Cons(head: Int, tail: IntList) extends IntList

  def ListSum(lst: IntList): Int = lst match {
    case Nil => 0
    case Cons(first, rest) => first + ListSum(rest)
  }

  sealed abstract class IntTree
  case class Leaf(v: Int) extends IntTree
  case class Node(left: IntTree, right: IntTree) extends IntTree

  def TreeSum(tree: IntTree): Int = tree match {
    case Leaf(v) => v
    case Node(left, right) => TreeSum(left) + TreeSum(right)
  }

  def InsSort(lst: IntList): IntList = lst match {
    case Nil =>
      Nil
    case Cons(first, rest) =>
      insert(first, InsSort(rest))
  }

  def insert(x: Int, lst: IntList): IntList = lst match {
    case Nil =>
      Cons(x, Nil)
    case Cons(first, rest) =>
      if (x < first) Cons(x, lst)
      else Cons(x, insert(x, rest))
  }


  def treeToList(tree: IntTree): IntList = tree match {
    case Leaf(v) =>
      Cons(v, Nil)
    case Node(left, right) =>
      append(treeToList(left), treeToList(right))
  }

  def append(lst1: IntList, lst2:IntList): IntList = lst1 match {
    case Nil => lst2
    case Cons(first1, rest1) =>
      Cons(first1, append(rest1, lst2))
  }

}