package kapitel_02

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 2, Qualität von Algorithmen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */
object AuD_02_01_Minimum_Methode_01_App extends App {

  /* Bei einer Implementierung von Methode_2 hat man die Wahl bei der Datenstruktur,
   * in der die Männer zu finden sind. Wir nehmen ein Array mit Objekten der
   * Klasse Mann. Diesmal unterstützen sie eine Methode istLeichterAls
   *
   * Dieser Algorithmus basiert auf einer Teilen und Herrschen Strategie, oder genauer einer Reduzieren und Herrschen
   * Strategie, bei der das gegebene Problem auf ein kleineres Problem der gleichen Art reduziert wird.
   * Die Lösung wird das nach den Prinzipien der dynamischen Programmierung optimiert.
   */

  case class Mann(gewicht: Int) {
    def istSchwererAls(anderer: Mann): Boolean = {
      Mann.counter = Mann.counter + 1  // noch ein Vergleich mehr
      this.gewicht > anderer.gewicht
    }
  }

  /*
   * Bei der Laufzeitanalyse geht es um den Zusammenhang zwischen der Eingabe und der Laufzeit des Algorithmus',
   * der diese Eingabe verarbeitet. Die Eingabe wird bei dieser Bewertung auf auf einen numerischen Wert
   * reduziert: die Eingabegröße} bzw.~Eingabelänge. In Beispiel ist offensichtlich, was damit
   * gemeint ist: Die Zahl der zu vergleichenden Männer.
   * Das ist aber nicht immer so völlig klar und hängt auch vom Algorithmus ab.
   * Statt der Anzahl der Männer könnte beispielsweise auch deren Gesamtgewicht die entscheidende Größe sein.
   * Beispielsweise weil der Vergleich von zwei Männern mit ist Leichter als von deren Gewicht abhängt.
   *
   * Das ist offensichtlich nicht der Fall. Nicht etwa weil so etwas prinzipiell ausgeschlossen wäre, sondern weil
   * im Pseudocode der Vergleich eine elementare Operation ist. Wenn das Gewicht eine Rolle spielen würde
   * dann müsste es im Algorithmus zum Ausdruck gebracht werden. Das ist nicht der Fall.
   *
   * Die Sache sieht aber anders aus, wenn das Gewicht in folgender Art geprüft würde:
   */

  case class MannMitLangsamenGewicht(gewicht: Int) {
    def istLeichterAls(anderer: Mann): Boolean = {
      var x = this.gewicht
      var y = anderer.gewicht
      while (x > 0 && y > 0) {
        x = x-1
        y = y-1
      }
      (x == 0) && (y != 0)
    }
  }

  /*
  * Um ein Gefühl für die Unterschiede zwischen worst case, best case und durchschnittlichen
  * Laufzeiten zu bekommen experimentieren wir mit Methode1. Der beste Fall ist, wenn die Männer der
  * Größe nach sortiert sind.
  * Dann ist der Leichteste schnell gefunden. Sind sie umgekehrt nach Gewicht sortiert, dann finden
  * wir den leichtesten als letzten.
  * Eine Zufallsverteilung sollte durchschnittliche Laufzeiten zur Folge haben.
  *
  * Die Zahl der Vergleiche ist ein gutes Maß für das Laufzeitverhalten. Wie zählen sie:
  */

  object Mann {
    var counter: Long = 0 // Zahl der Vergleiche
  }

  def Methode1(maenner: Array[Mann]): Int = {

    def istLeichtester(i: Int): Boolean = {
      for (j <- maenner.indices)
        if (maenner(i).istSchwererAls(maenner(j)))
          return false
      true
    }

    for (i <- maenner.indices) {
      if (istLeichtester(i))
        return i
    }
    -1 // falls kein Leichtester gefunden wird
  }

  println("\nzufällig")
  for (size <- List(100, 1000, 10000, 100000, 1000000, 10000000)) {

    val r = scala.util.Random
    val a = for (_ <- 0 to size) yield r.nextInt(size)

    // Männer mit zufälligem Gewicht
    val maenner: Array[Mann] = a.map(i => Mann(i)).toArray
    Mann.counter = 0
    val leichtester = Methode1(maenner)
    println(s"Der Leichteste Mann ist der Mann Nr. $leichtester")
    println(s"Größe: $size -> Zahl der Vergleiche: ${Mann.counter}")
  }


  println("\nbeste Verteilung")
  for (size <- List(100, 1000, 10000, 100000, 1000000, 10000000)) {
    val a = for (i <- 0 to size) yield i
    val maenner: Array[Mann] = a.map(i => Mann(i)).toArray
    Mann.counter = 0
    println(s"Der Leichteste Mann ist der Mann Nr. ${Methode1(maenner)}")
    println(s"Größe: $size -> Zahl der Vergleiche: ${Mann.counter}")
  }

  println("\nschlechteste Verteilung")
  for (size <- List(100, 1000, 10000, 100000, 1000000, 10000000)) {
    val a = for (i <- 0 to size) yield size - i
    val maenner: Array[Mann] = a.map(i => Mann(i)).toArray
    Mann.counter = 0
    println(s"Der Leichteste Mann ist der Mann Nr. ${Methode1(maenner)}")
    println(s"Größe: $size -> Zahl der Vergleiche: ${Mann.counter}")
  }

}