# HG changeset patch
# User Christian Urban <christian.urban@kcl.ac.uk>
# Date 1601404511 -3600
# Node ID bdd12391d345d7fec696b041d83b90c51df56863
# Parent  e8402d8ec8e6392e9a7a6af7a05926d08f3e200f
updated

diff -r e8402d8ec8e6 -r bdd12391d345 data.sty
--- a/data.sty	Tue Sep 29 12:52:07 2020 +0100
+++ b/data.sty	Tue Sep 29 19:35:11 2020 +0100
@@ -88,6 +88,19 @@
 32  32.190
 \end{filecontents}
 
+% Swift, example (a*)*b  
+\begin{filecontents}{re-swift.data}
+5   0.001
+10  0.001
+15  0.009
+20  0.178
+23  1.399
+24  2.893
+25  5.671
+26  11.357
+27  22.430
+\end{filecontents}
+
 % Java 8, example (a*)*b  
 \begin{filecontents}{re-java.data}
 5  0.00298
diff -r e8402d8ec8e6 -r bdd12391d345 progs/catastrophic/catastrophic.swift
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic/catastrophic.swift	Tue Sep 29 19:35:11 2020 +0100
@@ -0,0 +1,43 @@
+// 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
+    }
+}
diff -r e8402d8ec8e6 -r bdd12391d345 progs/matcher/re2.sc
--- a/progs/matcher/re2.sc	Tue Sep 29 12:52:07 2020 +0100
+++ b/progs/matcher/re2.sc	Tue Sep 29 19:35:11 2020 +0100
@@ -90,7 +90,7 @@
 def test2() = {
   println("Test (a*)* b")
 
-  for (i <- 0 to 20 by 2) {
+  for (i <- 0 to 30 by 2) {
     println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f")
   }
 }
diff -r e8402d8ec8e6 -r bdd12391d345 slides/slides01.pdf
Binary file slides/slides01.pdf has changed
diff -r e8402d8ec8e6 -r bdd12391d345 slides/slides01.tex
--- a/slides/slides01.tex	Tue Sep 29 12:52:07 2020 +0100
+++ b/slides/slides01.tex	Tue Sep 29 19:35:11 2020 +0100
@@ -631,12 +631,13 @@
     axis lines=left,
     width=\textwidth,
     height=4cm, 
-    legend entries={Python, Java 8, JavaScript},  
+    legend entries={Python, Java 8, JavaScript, Swift},  
     legend pos=north west,
     legend cell align=left]
 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};   
 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
 \addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
 \end{axis}
 \end{tikzpicture}
 %
diff -r e8402d8ec8e6 -r bdd12391d345 slides/slides02.pdf
Binary file slides/slides02.pdf has changed
diff -r e8402d8ec8e6 -r bdd12391d345 slides/slides02.tex
--- a/slides/slides02.tex	Tue Sep 29 12:52:07 2020 +0100
+++ b/slides/slides02.tex	Tue Sep 29 19:35:11 2020 +0100
@@ -601,6 +601,7 @@
 
 \begin{center}
 \begin{tabular}{rl}
+0: & \bl{$\ONE$}\\    
 1: & \bl{$a$}\\
 2: & \bl{$a\cdot a$}\\
 3: & \bl{$a\cdot a\cdot a$}\\
@@ -773,12 +774,13 @@
     axis lines=left,
     width=9cm,
     height=5.5cm, 
-    legend entries={Java 8, Python, JavaScript},  
+    legend entries={Java 8, Python, JavaScript, Swift},  
     legend pos=north west,
     legend cell align=left]
 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
 \addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
 \end{axis}
 \end{tikzpicture}
 \end{center}