package kapitel_05

import scala.annotation.tailrec

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 5, Bäume: Immer einer über den anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_05_10_ArrayHeap_App extends App {

  /* start bei Index 0 */
  val capacity: Int = 10
  var lastPos: Int = -1 // last position occupied by a value
  val h: Array[Int] = Array.ofDim(capacity)

  def swap(i: Int, j: Int): Unit = {
    val t = h(i)
    h(i) = h(j)
    h(j) = t
  }

  def remove(): Int = {
    assert(lastPos > -1)
    val result = h(0)
    h(0) = h(lastPos)
    lastPos = lastPos-1
    bubbleDown(0)
    result
  }

  @tailrec
  def bubbleDown(i: Int): Unit = {
    var m: Int = 2*i
    if (2*i+1 <= lastPos) {
      if (2*i + 2 > lastPos || h(2*i+1) >= h(2*i+2))
        m = 2*i+1
      else
        m = 2*i + 2
      if (h(i) < h(m)) {
        swap(i, m)
        bubbleDown(m)
      }
    }
  }

  def insert(e: Int): Unit = {
    assert(lastPos < capacity)
    lastPos = lastPos+1
    h(lastPos) = e
    bubbleUp(lastPos)
  }

  @tailrec
  def bubbleUp(i: Int): Unit =
    if (i > 0 && h((i-1)/2) <= h(i)) {
      swap(i, (i-1)/2)
      bubbleUp((i-1)/2)
    }

  println(s"[${h.mkString(", ")}], $lastPos")
  for (x <- List(2, 9, 7, 6, 5, 8, 1, 3, 10, 4)) {
    insert(x)
    println(s"[${h.mkString(", ")}], $lastPos")
  }

  println("=============")

  println(s"[${h.mkString(", ")}], $lastPos")
  try {
    while (true) {
      println(s"-> ${remove()}")
      println(s"[${h.mkString(", ")}], $lastPos")
    }
  } catch {
    case _ : AssertionError  =>
  }

}