package kapitel_11

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

import scala.language.implicitConversions

object AuD_11_01_PermutationSortRabbits_App extends App {

  /*
   * Permutationen sind ein wichtiges kombinatorisches Objekt.
   */

  def Perm[T](l: List[T]): List[List[T]] = l match {
    case Nil =>
      Nil :: Nil
    case x :: rest =>
      Ins(x, Perm(rest))
  }

  def Ins[T](x: T, L: List[List[T]]): List[List[T]] =
    L.flatMap(l => InsH(x, l))

  def InsH[T](x: T, l: List[T]): List[List[T]] = l match {
    case Nil =>
      (x :: Nil) :: Nil
    case h :: t =>
      (x :: l) :: InsH(x, t).map(l1 => h :: l1)
  }

  def isSorted[A](l: List[A])(implicit ordering: Ordering[A]): Boolean = {
    implicit def toOrdered(a:A): Ordered[A] = Ordered.orderingToOrdered(a)
    !l.dropRight(1).zip(l.tail).exists {
      case (x, y) =>
        x > y
    }
  }

  /*
   * Kanainchen Kaninchen generisch und mit roher Kraft sortieren:
   */
  def PermSort[A](l: List[A])(implicit ordering: Ordering[A]): List[A] = {
    for (p <- Perm(l)) {
      if (isSorted(p))
        return p
    }
    throw new IllegalArgumentException("List can not be sorted")
  }

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

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

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

  println(PermSort(rabbits))

}