package kapitel_09

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

object AuD_09_07_RedBlackTree_App extends App {

  import scala.language.implicitConversions

  class RBT[A](implicit ordering: Ordering[A]) {

    object Color extends Enumeration {
      type Color = Value
      val Red, Black = Value
    }
    import Color._

    sealed abstract class RBTree
    case object Nil extends RBTree
    case class Node(color: Color, left: RBTree, value: A, right: RBTree) extends RBTree

    // Vergleichsoperatoren wie < und >, können verwendet werden:
    implicit def ToOrdered(a: A): Ordered[A] = Ordered.orderingToOrdered(a)

    def member(x: A, rbTree: RBTree): Boolean = rbTree match {
      case Nil =>
        false
      case Node(_, _, v, _) if x == v =>
        true
      case Node(_, left, v, _) if x < v =>
        member(x, left)
      case Node(_, _, v, right) if x > v =>
        member(x, right)
    }

    def paintBlack(t: RBTree): RBTree = t match {
      case Nil =>
        Nil
      case Node(_, l, v, r) =>
        Node(Black, l, v, r)
    }

    def insertRB(x: A, t: RBTree): RBTree =
      paintBlack(insR(x, t))

    def insR(x: A, s: RBTree): RBTree = s match {
      case Nil =>
        Node(Red, Nil, x, Nil)
      case Node(c, left, v, right) if x < v =>
        balance(c, insR(x, left), v, right)
      case Node(_, _, v, _) if x == v =>
        s
      case Node(c, left, v, right) if x > v =>
        balance(c, left, v, insR(x, right))
    }

    def balance(color: Color, tree1: RBTree, value: A, tree2: RBTree): RBTree =
      (color, tree1, value, tree2) match {
        case (Black, Node(Red, Node(Red, a, x, b), y, c), z, d) =>
          Node(Red, Node(Black, a, x, b), y, Node(Black, c, z, d))
        case (Black, a, x, Node(Red, b, y, Node(Red, c, z, d))) =>
          Node(Red, Node(Black, a, x, b), y, Node(Black, c, z, d))
        case (Black, Node(Red, a, x, Node(Red, b, y, c) ), z, d) =>
          Node(Red, Node(Black, a, x, b), y, Node(Black, c, z, d))
        case (Black, a, x, Node(Red, Node(Red, b, y, c), z, d)) =>
          Node(Red, Node(Black, a, x, b), y, Node(Black, c, z, d))
        case (_, _, _, _) =>
          Node(color, tree1, value, tree2)
      }

    var tree: RBTree = Nil

    def Member(x: A): Boolean = member(x, tree)

    def Insert(x: A): Unit = {
      tree = insertRB(x, tree)
    }

  }

  val tableInt = new RBT[Int]

  for (x <- List(3,4,5,0,7,9,4,7)) {
    tableInt.Insert(x)
  }

  for (x <- 0 to 10) {
    println(s"$x -> ${tableInt.Member(x)}")
  }

  case class Rabbit(name: String, weight: Int)

  val rabbits = List(Rabbit("Egon", 12), Rabbit("Sisi", 2), Rabbit("Gotthold", 7))

  // implizite gewichtsbasierte Ordnung der Kaninchen
  implicit object WeightOrdering extends Ordering[Rabbit] {
    override def compare(r1: Rabbit, r2: Rabbit): Int = r1.weight - r2.weight
  }

  val tableRabbit_weightSorted = new RBT[Rabbit]

  for(r <- rabbits) {
    tableRabbit_weightSorted.Insert(r)
  }
  for(r <- List(Rabbit("Egon", 12), Rabbit("Sisi", 2), Rabbit("Gotthold", 7), Rabbit("Roger", 5))) {
    println(s"$r -> ${tableRabbit_weightSorted.Member(r)}")
  }

  // mit expliziter lexikographischer Ordnung der Kaninchen
  val tableRabbit_lexSorted = new RBT[Rabbit]()(
    (x: Rabbit, y: Rabbit) => x.name.compareTo(y.name)
  )

  for(r <- rabbits) {
    tableRabbit_lexSorted.Insert(r)
  }

  for(r <- List(Rabbit("Egon", 12), Rabbit("Sisi", 2), Rabbit("Gotthold", 7), Rabbit("Roger", 5))) {
    println(s"$r -> ${tableRabbit_weightSorted.Member(r)}")
  }

}