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_02_SelectionSortOrdering_App extends App {

  /* Zum Sortieren benötigt man eine Ordnung nach der sortiert wird.
   * Wenn die zu sortierenden Dinge keine natürliche Ordnung haben, oder wenn man
   * nicht nach der natürlichen Ordnung sortieren will, dann beötigt man einen
   * Vergleicher.
   * In Java ist das ein Objekt, das das Interface Comparator implementiert.
   * In Scala wird diese Rolle von [[scala.math.Ordering]] übernommen.
   */

  /**
   * Sortiert ein Array mit von Werten entsprechend einem [[scala.math.Ordering]].
   * Alle Werte des Typs A können mit der Methode compare der des [[scala.math.Ordering]]s verglichen werden.
   * @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_ordering[A](a: Array[A], l: Int, r: Int)(implicit ordering: Ordering[A]): Unit = {

    @inline
    def argmin(i: Int, r: Int): Int = {
      var m = i
      if (r > i)
        for (j <- i+1 to r) {
          if (ordering.lt(a(j), a(m))) // 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)
    }
  }


  /**
   * Bauarbeiter ohne natürliche Ordnung.
   * @param name    der Name des Bauarbeiters
   * @param weight  sein Gewicht
   */
  case class Worker(name: String, weight: Int)

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

  // nach Gewicht sortieren:
  SelectionSort_ordering(workers, 0, workers.length-1)((w1: Worker, w2: Worker) => w1.weight - w2.weight)
  println(workers.mkString(", "))

  // nach Name sortieren:
  SelectionSort_ordering(workers, 0, workers.length-1)((w1: Worker, w2: Worker) => w1.name.compareTo(w2.name))
  println(workers.mkString(", "))

  // noch mal nach Gewicht sortieren:
  SelectionSort_ordering(workers, 0, workers.length-1)(Ordering.by(w => w.weight))
  println(workers.mkString(", "))

  implicit val nameOrdering: Ordering[Worker] = (x: Worker, y: Worker) => x.name.compareTo(y.name)

  // mit implizitem Ordering noch wieder nach Name sortieren:
  SelectionSort_ordering(workers, 0, workers.length-1)
  println(workers.mkString(", "))


  /**
   * 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)
  )

  // Bauarbeiter mit einer natürlichen Ordnung können auch soriert werden.
  // Ordered wird implizit in ein Ordering tramsformiert.
  // Nach natürlicher Ordnung sortieren:
  SelectionSort_ordering(orderedWorkers, 0, orderedWorkers.length-1)// implizit: (Ordering.ordered)
  println(orderedWorkers.mkString(", "))

  // abweichend von der natürlichen Ordnung sortieren:
  SelectionSort_ordering(orderedWorkers, 0, orderedWorkers.length-1)(Ordering.by( w => w.name))
  println(orderedWorkers.mkString(", "))

  // natürlich kann man auch Zahlen sortieren:
  val intArray = Array(77, 72, 96, 111, 96, 122, 75)
  SelectionSort_ordering(intArray, 0, intArray.length-1)
  println(intArray.mkString(", "))

  // .. auch absteigend
  SelectionSort_ordering(intArray, 0, intArray.length-1)( (i, j) => j-i )
  println(intArray.mkString(", "))



}