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

import Foundation

struct AuD_02_01_Minimum_Methode_01 {

    /* Der Pseudocode von Methode 1 bringt ein spezielles Verfahren zum Ausdruck, mit dem der Leichteste gefunden
     * werden kann.
     * Für eine Implementierung müssen zusätzliche Entscheidungen getroffen werden, von denen einige
     * sprachabhängig sind. Am Verfahren ändert sich dabei aber nichts. Die Bewertung der Effizienz des Algorithmus kann
     * aber nicht völlig unbesehen auf jede Implementierung übertragen werden.
     * Eine Implementierung des Verfahrens könnte ein Array von Männern als Eingabe verarbeiten.
     * Ein Mann ist dabei ein Objekt das die Methode istSchwererAls implementiert.
     */

    static var counter: Int64 = 0 // Zaehlt die Vergelichsoperationen

    class Mann {
        private let gewicht: Int

        init(gewicht: Int) {
            self.gewicht = gewicht
        }

        func istSchwererAls(anderer: Mann) -> Bool {
            counter = counter + 1
            return self.gewicht > anderer.gewicht
        }
    }

    /*
     * Bei der Laufzeitanalyse geht es um den Zusammenhang zwischen der Eingabe und der Laufzeit des Algorithmus',
     * der diese Eingabe verarbeitet. Die Eingabe wird bei dieser Bewertung auf auf einen numerischen Wert
     * reduziert: die Eingabegröße} bzw.~Eingabelänge. In Beispiel ist offensichtlich, was damit
     * gemeint ist: Die Zahl der zu vergleichenden Männer.
     * Das ist aber nicht immer so völlig klar und hängt auch vom Algorithmus ab.
     * Statt der Anzahl der Männer könnte beispielsweise auch deren Gesamtgewicht die entscheidende Größe sein.
     * Beispielsweise weil der Vergleich von zwei Männern mit ist Leichter als von deren Gewicht abhängt.
     *
     * Das ist offensichtlich nicht der Fall. Nicht etwa weil so etwas prinzipiell ausgeschlossen wäre, sondern weil
     * im Pseudocode der Vergleich eine elementare Operation ist. Wenn das Gewicht eine Rolle spielen würde
     * dann müsste es im Algorithmus zum Ausdruck gebracht werden. Das ist nicht der Fall.
     *
     * Die Sache würde aber anders aussehen, wenn das Gewicht in folgender Art geprüft würde:
     */

    class MannMitLangsamenGewicht {
        let gewicht: Int

        init(gewicht: Int) {
            self.gewicht = gewicht
        }

        func istSchwererAls(anderer: MannMitLangsamenGewicht) -> Bool {
            var x = self.gewicht
            var y = anderer.gewicht
            while (x > 0 && y > 0) {
                x = x-1
                y = y-1
            }
            return (x == 0) && (y != 0)
        }

    }


    static func Methode1(maenner: [Mann]) ->  Int  {

        func istLeichtester(i: Int) -> Bool {
            for j in maenner.indices {
                if (maenner[i].istSchwererAls(anderer: maenner[j])) {
                    return false
                }
            }
            return true
        }

        for i in maenner.indices {
            if (istLeichtester(i: i)) {
                return i
            }
        }
        return -1 // falls kein Leichtester gefunden wird
    }

    /*
    * Um ein Gefühl für die Unterschiede zwischen worst case, best case und durchschnittlichen
    * Laufzeiten zu bekommen experimentieren wir mit Methode1. Der beste Fall ist, wenn die Männer der
    * Größe nach sortiert sind.
    * Dann ist der Leichteste schnell gefunden. Sind sie umgekehrt nach Gewicht sortiert, dann finden
    * wir den leichtesten als letzten.
    * Eine Zufallsverteilung sollte durchschnittliche Laufzeiten zur Folge haben.
    *
    * Die Zahl der Vergleiche ist ein gutes Maß für das Laufzeitverhalten.
    */


    static func run () {
        print("\nzufällig")
        for size in [100, 1000, 10000, 100000, 1000000, 10000000] {

            let a: [Int] = (0 ..< size).map( { (s:Int) -> Int in Int(arc4random_uniform(UInt32(size))) })

            // Männer mit zufälligem Gewicht
            let ms: [Mann] = a.map( { (i: Int) -> Mann in Mann(gewicht: i) } )

            counter = 0

            let nrLeichtester: Int = Methode1(maenner: ms)

            print("Der Leichteste Mann ist der Mann Nr. \(nrLeichtester)")

            print("Größe: \(size) -> Zahl der Vergleiche: \(counter)")
        }

        print("\nbeste Verteilung\"")
        for size in [100, 1000, 10000, 100000, 1000000, 10000000] {

            let a: [Int] = (0 ..< size).map( { (s:Int) -> Int in s })

            // Männer mit Gewicht
            let ms: [Mann] = a.map( { (i: Int) -> Mann in Mann(gewicht: i) } )

            counter = 0

            let nrLeichtester: Int = Methode1(maenner: ms)

            print("Der Leichteste Mann ist der Mann Nr. \(nrLeichtester)")

            print("Größe: \(size) -> Zahl der Vergleiche: \(counter)")
        }

        print("\nschlechteste Verteilung\"")
        for size in [100, 1000, 10000, 100000, 1000000, 10000000] {

            let a: [Int] = (0 ..< size).map( { (s:Int) -> Int in size - s })

            // Männer mit Gewicht
            let ms: [Mann] = a.map( { (i: Int) -> Mann in Mann(gewicht: i) } )

            counter = 0

            let nrLeichtester: Int = Methode1(maenner: ms)

            print("Der Leichteste Mann ist der Mann Nr. \(nrLeichtester)")

            print("Größe: \(size) -> Zahl der Vergleiche: \(counter)")
        }

    }

}