package kapitel_07


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

object AuD_07_01_SelectionSortOrdered_App extends App {

  /* Zum Sortieren benötigt man eine Ordnung nach der sortiert wird.
   * Manchmal bringen die zu sortierenden Dinge schon eine eigene
   * Ordnung mit, die dann als Sortierkriterium genutzt werden kann.
   * In Java und Scala wird das als natürliche Ordnung bezeichnet.
   * Die natürliche Ordnung basiert in Java auf dem Interface Comparable.
   * Scale erweitert es zu [[scala.math.Ordered]].
   */



  /**
   * Sortiert ein Array mit natürlich geordneteten Werten entsprechend [[java.lang.Comparable]].
   * Alle Werte des Typs A sind mit compareTo vergleichbar.
   * @param a   das Array
   * @param l   die Untergenze des zu sorierenden Bereichs
   * @param r   die Obergrenze des zu sortierenden Bereichs
   * @tparam A  der typ der Array-Elemente
   */
  def SelectionSort_natOrderComparable[A <: Comparable[A]](a: Array[A], l: Int, r: Int): Unit = {

    @inline
    def argmin(i: Int, r: Int): Int = {
      var m = i
      if (r > i)
        for (j <- i+1 to r) {
          if (a(j).compareTo(a(m)) < 0) // a(j) < a(m)
            m = j
        }
      m
    }

    @inline
    def swap(i: Int, j: Int): Unit = {
      val t = a(i)
      a(i) = a(j)
      a(j) = t
    }

    for (i <- l until r) {
      val m = argmin(i, r)
      swap(i, m)
    }
  }

  /**
   * Vergleichbare Bauarbeiter. Bauarbeiter mit einer (Java-artigen) natürlichen Ordnung
   * die auf ihrem ihr Gewicht basiert.
   * @param name    der Name des Bauarbeiters
   * @param weight  sein Gewicht
   */
  case class ComparableWorker(name: String, weight: Int) extends Comparable[ComparableWorker] {
    override def compareTo(o: ComparableWorker): Int = this.weight - o.weight
  }

  val comparableWorkers = Array(
    ComparableWorker("Alex", 77),   ComparableWorker("Bert", 72),
    ComparableWorker("Klausi", 96), ComparableWorker("Dominik", 111),
    ComparableWorker("Emil", 96),   ComparableWorker("Flo", 122),
    ComparableWorker("Gerd", 75)
  )

  SelectionSort_natOrderComparable(comparableWorkers, 0, comparableWorkers.length-1)
  println(comparableWorkers.mkString(", "))

  //==================================================================================

  /**
   * Sortiert ein Array mit natürlich geordneteten Werten entsprechend [[scala.math.Ordered]].
   * Der Trait [[scala.math.Ordered]] ist eine Erweiterung von [[java.lang.Comparable]]
   * * in dem neben compareTo auch die üblichen Vergleichsoperationen definiert sind.
   *
   * @param a   das Array
   * @param l   die Untergenze des zu sorierenden Bereichs
   * @param r   die Obergrenze des zu sortierenden Bereichs
   * @tparam A  der typ der Array-Elemente
   */
  def SelectionSort_natOrderOrdered[A <: Ordered[A]](a: Array[A], l: Int, r: Int): Unit = {

    @inline
    def swap(i: Int, j: Int): Unit = {
      val t = a(i)
      a(i) = a(j)
      a(j) = t
    }

    @inline
    def argmin(i: Int, r: Int): Int = {
      var m = i
      if (r > i)
        for (j <- i + 1 to r) {
          if (a(j) < a(m)) // !!
            m = j
        }
      m
    }

    for (i <- l until r) {
      val m = argmin(i, r)
      swap(i, m)
    }
  }

  /**
   * Geordnete Bauarbeiter.
   * @param name    der Name des Bauarbeiters
   * @param weight  sein Gewicht
   */
  case class OrderedWorker(name: String, weight: Int) extends Ordered[OrderedWorker] {
    override def compare(o: OrderedWorker): Int = this.weight - o.weight
  }

  val orderedWorkers = Array(
    OrderedWorker("Alex", 77),    OrderedWorker("Bert", 72),
    OrderedWorker("Klausi", 96),  OrderedWorker("Dominik", 111),
    OrderedWorker("Emil", 96),    OrderedWorker("Flo", 122),
    OrderedWorker("Gerd", 75)
  )

  SelectionSort_natOrderOrdered(orderedWorkers, 0, orderedWorkers.length-1)
  println(orderedWorkers.mkString(", "))

  // Ordered kann als Comparable verwendet werden
  // (Umgekehrt geht das natürich nicht einfach so.)
  SelectionSort_natOrderComparable(orderedWorkers, 0, orderedWorkers.length-1)
  println(orderedWorkers.mkString(", "))


}