/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 11, Probleme totschlagen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_11_01_PermutationSortRabbits {

    static func Perm<T>(_ l: [T]) -> [[T]] {
        if (l.count == 0) {
            return [[]]
        } else {
            return Ins(l.first!, Perm(Array(l.dropFirst())))
        }
    }

    static func Ins<T>(_ x: T, _ L: [[T]]) -> [[T]] {
        return L.flatMap( { (l) in InsH(x, l) } )
    }

    static func InsH<T>(_ x: T, _ l: [T]) -> [[T]] {
        if (l.count == 0) {
            return [[x]]
        } else {
            let xl: [[T]] = [[x] + l]
            return xl + InsH(x, Array(l.dropFirst())).map({ (l1) in [l.first!] + l1 })
        }
    }

    static func isSorted<A: Comparable>(_ l: [A]) -> Bool {
        let missarragedPairs = zip(
            Array(l.dropLast()),
            Array(l.dropFirst())).filter( { (x, y) in x > y } )
        return missarragedPairs.count == 0
    }

    enum SortError: Error {
        case mayNotOccur
    }

    static func PermSort<A: Comparable>(_ l: [A]) throws -> [A]  {
        for p in Perm(l) {
            if (isSorted(p)) {
                return p
            }
        }
        throw SortError.mayNotOccur
    }

    struct Rabbit : Comparable, CustomStringConvertible {
        let name: String
        let weight: Int

        static func < (lhs: Rabbit, rhs: Rabbit) -> Bool {
            lhs.weight < rhs.weight
        }
        var description: String {
            "(\(name), \(weight))"
        }

    }

    static let rabbits: [Rabbit] = [
        Rabbit(name: "Egon", weight: 12),
        Rabbit(name: "Sisi", weight: 2),
        Rabbit(name: "Gotthold", weight: 7),
        Rabbit(name: "Roger", weight: 5)]

    static func run () {
        do {
            try print(PermSort(rabbits).map(({ (rabbit) in rabbit.description}) ).joined(separator: ", "))
        } catch {
        }
    }

}