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

struct AuD_07_09_RadixSort {

    static func digit(k: Int, n: Int) -> Int {
        var nn = n
        var digits: [Int] = []
        while (nn > 0) {
            digits = [nn % 10] + digits
            nn = nn / 10
        }
        if (digits.count - k >= 0 && digits.count - k < digits.count) {
            return digits[digits.count - k]
        } else {
            return 0
        }
    }

    static func SortByDigit(a: inout [Int], l: Int, r: Int, k: Int) {
        let R = 10
        var count: [Int] = Array(repeating: 0, count: R)
        var pos: [Int] = Array(repeating: 0, count: R)
        var b: [Int] = Array(repeating: 0, count: a.count)

        var j: Int = 0

        for i in l ... r {
            j = digit(k: k, n: a[i])
            count[j] = count[j] + 1
        }

        var i = l
        for j in 0 ..< R {
            pos[j] = i
            i = i + count[j]
        }

        for i in l ... r {
            j = digit(k: k, n: a[i])
            b[pos[j]] = a[i]
            pos[j] = pos[j] + 1
        }

        for i in l ... r {
            a[i] = b[i]
        }
    }

    static func digitCount(n: Int, acc:Int = 1) -> Int {
        (n < 10) ? acc : digitCount(n: n/10, acc: acc+1)
    }

    static func RadixSort(a: inout [Int], l: Int, r: Int) {
        let kMax = digitCount(n: a.max(by: <)!)
        for i in 1 ... kMax {
            print(a.map({ (x) in String(x) }).joined(separator: ", "))
            SortByDigit(a: &a, l: l, r: r, k: i)
        }
    }

    static func run() {
        var a : [Int] = [4589, 3579, 3882, 2879, 5559, 4872, 2552, 5552, 3579, 3559]
        RadixSort(a: &a, l: 0, r: a.count-1)
        print(a.map({ (x) in String(x)} ).joined(separator: ", "))
    }
}