import Foundation

func machToNanoseconds(_ mach: UInt64) -> Double {
    struct Static {
        static var info: mach_timebase_info = {
            var info = mach_timebase_info()
            mach_timebase_info(&info)
            return info
        }()
    }
    return Double(mach) * Double(Static.info.numer) / Double(Static.info.denom)
}

func Test() {
    for threadCount in 1 ... 6 {
        let threadCountString = "* Thread count: \(threadCount) *"
        let surround = "".padding(toLength: threadCountString.count, withPad: "*", startingAt: 0)
        print(surround)
        print(threadCountString)
        print(surround)

        let iterations: UInt64 = 1000000
        let interval = iterations / 20

        var times: [UInt64] = []
        let cond = NSCondition()

        var runningThreads = threadCount
        for _ in 0 ..< threadCount {
            Thread.detachNewThread({
                let oneTimes = ThreadFunc(iterations: iterations, interval: interval)

                cond.lock()
                times.append(contentsOf: oneTimes)
                runningThreads -= 1
                cond.signal()
                cond.unlock()
            })
        }

        cond.lock()
        while runningThreads > 0 {
            cond.wait()
        }
        cond.unlock()

        let nanoseconds = times.map({ machToNanoseconds($0) })

        for threshold in [0.01, 0.02, 0.03, 0.04, 0.05, 0.1] {
            print("Threshold: \(threshold)")
            let clusters = cluster(nanoseconds, threshold: threshold)
            for cluster in clusters {
                let mean = cluster.reduce(0, +) / Double(cluster.count)
                let median = cluster[cluster.count / 2]
                let stddev = sqrt(cluster.map({ ($0 - mean) * ($0 - mean) }).reduce(0, +) / Double(cluster.count))

                print("count: \(cluster.count) - mean: \(mean) - median: \(median) - stddev: \(stddev)")
            }
            print("----------")
        }

        print("")
        print("")
    }

    print("********")
    print("* DONE *")
    print("********")
}

func ThreadFunc(iterations: UInt64, interval: UInt64) -> [UInt64] {
    var times: [UInt64] = []

    for i in 1 ... iterations {
        let start = mach_absolute_time()

        let x = Int64(i)
        var guess = x
        for _ in 0 ... 1024 {
            guess = (guess + x / guess) / 2
        }
        if abs(guess * guess - x) > 1000000000 {
            print("Found a really inexact square root! \(guess * guess) \(x)")
        }

        let end = mach_absolute_time()

        if i % interval == 0 {
            times.append(end - start)
        }
    }
    return times
}

func cluster(_ values: [Double], threshold: Double) -> [[Double]] {
    var result: [[Double]] = []
    var current: [Double] = []

    for n in values.sorted() {
        if let last = current.last, (n - last) / n <= threshold {
            current.append(n)
        } else {
            if !current.isEmpty {
                result.append(current)
            }
            current = [n]
        }
    }

    if !current.isEmpty {
        result.append(current)
    }

    return result
}