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

  def digit(k: Int, n: Int): Int = {
    var nn = n
    var digits: List[Int] = Nil
    while (nn > 0) {
      digits = (nn % 10) :: digits
      nn = nn / 10
    }
    try {
      digits(digits.length - k)
    } catch {
      case _: IndexOutOfBoundsException => 0
    }
  }

  def SortByDigit(a: Array[Int], l: Int, r: Int, k: Int): Unit = {
    val R = 10
    val count: Array[Int] = Array.fill(R)(0)
    val pos: Array[Int] = Array.fill(10)(0)
    val b: Array[Int] = new Array[Int](a.length)

    var j: Int = 0

    for (i <- l to r) {
      j = digit(k, a(i))
      println(s"digit(2, ${a(i)} = $j")
      count(j) = count(j) + 1
    }

    println(count.mkString(", "))

    var i = l
    for (j <- 0 until R) {
      pos(j) = i
      i = i + count(j)
    }

    println(pos.mkString(", "))

    for (i <- l to r) {
      j = digit(k, a(i))
      b(pos(j)) = a(i)
      pos(j) = pos(j) + 1
    }

    for (i <- l to r)
      a(i) = b(i)
  }

  val a = Array(331, 401, 420, 30, 321, 220, 1, 402, 322, 343)

  SortByDigit(a, 0, a.length-1, 2)

  println(a.mkString(", "))

}