// A case of catastrophic backtracking in Swift
//---------------------------------------------
// example provided by Martin Mikusovic
//
// regex: (a*)*b
// strings: aa...a
//
// compile with
//
// swiftc catastrophic.swift
//
// run with for example
//
// time ./catastrophic 20

import Foundation

let args = CommandLine.arguments
if args.count >= 2, let count = Int(args[1]) {
    let s = String(repeating: "a", count: count)
    calculateTime {
        let _ = s ~= "(a*)*b"
    }
} else {
    print("Please enter a valid number argument.")
}

func calculateTime(block: () -> ()) {
    let start = DispatchTime.now()
    block()
    let end = DispatchTime.now()
    let nanoTime = end.uptimeNanoseconds - start.uptimeNanoseconds
    let timeInterval = Double(nanoTime) / 1_000_000_000
    print("\(timeInterval) s")
}

extension String {
    static func ~=(lhs: String, rhs: String) -> Bool {
        guard let regex = try? NSRegularExpression(pattern: rhs) else { return false }
        let range = NSRange(location: 0, length: lhs.utf16.count)
        return regex.firstMatch(in: lhs, options: [], range: range) != nil
    }
}