package kapitel_07

import scala.annotation.tailrec

object AuD_07_09_RadixSort_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))
      count(j) = count(j) + 1
    }

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

    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)
  }

  @tailrec
  def digitCount(n: Int, acc:Int = 1): Int =
    if (n < 10) acc else digitCount(n/10, acc+1)

  def RadixSort(a: Array[Int], l: Int, r: Int): Unit = {
    val kMax = digitCount(a.max)

    for (i <- 1 to kMax) {
      println(a.mkString(", "))
      SortByDigit(a, l, r, i)
    }
  }


  val a = Array(4589, 3579, 3882, 2879, 5559, 4872, 2552, 5552, 3579, 3559)

  RadixSort(a, 0, a.length-1)

  println(a.mkString(", "))

}