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

import scala.reflect.ClassTag

object AuD_07_06_SortWithPrioritiyQueue_App extends App {

  def PriorityQueueSort(a: Array[Int], l: Int, r: Int): Unit = {
    val Q = new PriorityQueue((r-l)+1)
    for  (i <- l to  r) {
      Q .push(a(i))
    }
    for  (i  <- l to  r) {
      a(i)  =  Q.extractMin()
    }
  }

  class PriorityQueue(size: Int) {
    // Position 0 bleibt frei

    val H = new Array[Int](size+1)

    var n: Int = 0 // Index des letzten Elements (0 ist unbelegt)

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


    def push(x: Int): Unit = {
      H(n+1)  =  x
      var i: Int =  n+1
      var break = false
      while (i > 1 && !break) {
        val p: Int  =  i/2
        if (H(i) >= H(p) ) {
          break = true
        } else {
          swap(i, p)
          i  =  p
        }
      }
      n = n+1 // !!
    }

    def extractMin(): Int = {
      val x  =  H(1)
      H(1)  =  H(n)
      var i =  1
      var break = false
      while (i <= n && !break) {
        var m = i
        if  ( (2*i < n) && (H(2*i) < H(m)) ) {
          m = 2*i
        }
        if ( (2*i+1 < n) && (H(2*i+1) < H(m)) ) {
          m = 2*i+1
        }
        if (m == i) {
          break = true
        } else {
          swap(m, i)
          i = m
        }
      }
      n = n-1 // !!
      x
    }
  }

  val aInt: Array[Int] = Array(6,8,0,2,3,9,7,5,1,4)

  PriorityQueueSort(aInt, 0, aInt.length-1)

  println(aInt.mkString(", "))


  // -------------------------------------------------------------------
  // Das geht auch generisch:

  def PriorityQueueSortG[A](a: Array[A], l: Int, r: Int)(implicit ord: Ordering[A], ct: ClassTag[A]): Unit = {

    val Q = new PriorityQueueG[A]((r-l)+1)
    for  (i <- l to  r) {
      Q.push(a(i))
    }
    for  (i  <- l to  r) {
      a(i)  =  Q.extractMin()
    }
  }

  class PriorityQueueG[A](size: Int)(implicit ord: Ordering[A], ct: ClassTag[A]) {
    // Position 0 bleibt frei

    val H = new Array[A](size+1)

    var n: Int = 0 // Index des letzten Elements (0 ist unbelegt)

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

    def push(x: A): Unit = {
      H(n+1)  =  x
      var i: Int =  n+1
      var break = false
      while (i > 1 && !break) {
        val p: Int  =  i/2
        if (ord.gteq(H(i), H(p))) {
          break = true
        } else {
          swap(i, p)
          i  =  p
        }
      }
      n = n+1 // !!
    }

    def extractMin(): A = {
      val x  =  H(1)
      H(1)  =  H(n)
      var i =  1
      var break = false
      while (i <= n && !break) {
        var m = i
        if  ( (2*i < n) && ord.lt(H(2*i), H(m)) ) {
          m = 2*i
        }
        if ( (2*i+1 < n) && ord.lt(H(2*i+1), H(m)) ) {
          m = 2*i+1
        }
        if (m == i) {
          break = true
        } else {
          swap(m, i)
          i = m
        }
      }
      n = n-1 // !!
      x
    }
  }

  // Klasse mit natuerlicher Ordnung
  case class Worker(name: String, weight: Int) extends Ordered[Worker] {
    override def compare(o: Worker): Int = this.weight - o.weight
  }

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

  PriorityQueueSortG(aWorker, 0, aWorker.length-1)//implicit: (Ordering[ConstrWorker], scala.reflect.classTag[ConstrWorker])
  println(aWorker.mkString(", "))

  // Klasse ohne natuerliche Ordnung
  case class Student(name: String, weight: Int)

  val aStudent = Array(
    Student("Alex", 77),
    Student("Bert", 72),
    Student("Claus", 96),
    Student("Dominik", 111),
    Student("Emil", 96),
    Student("Flo", 122),
    Student("Gerd", 75)
  )

  implicit val StudenttOrdering: Ordering[Student] =
    (x: Student, y: Student) => x.weight - y.weight

  PriorityQueueSortG[Student](aStudent, 0, aStudent.length-1)//implicit: (StudenttOrdering, scala.reflect.classTag[Student])
  println(aStudent.mkString(", "))

}