--- a/templates4/re.scala Wed Nov 28 17:13:40 2018 +0000
+++ b/templates4/re.scala Wed Nov 28 23:26:47 2018 +0000
@@ -1,7 +1,7 @@
// Part 1 about Regular Expression Matching
//==========================================
-
+// Regular Expressions
abstract class Rexp
case object ZERO extends Rexp
case object ONE extends Rexp
@@ -11,7 +11,7 @@
case class STAR(r: Rexp) extends Rexp // star
-// some convenience for typing in regular expressions
+// some convenience for typing regular expressions
import scala.language.implicitConversions
import scala.language.reflectiveCalls
@@ -102,11 +102,13 @@
size(simp(der('a', der('a', EVIL)))) // => 8
size(simp(der('a', der('a', der('a', EVIL))))) // => 8
-// Java needs around 30 seconds for matching 28 a's with EVIL.
+// Python needs around 30 seconds for matching 28 a's with EVIL.
+// Java 9 and later increase this to an "astonishing" 40000 a's in
+// 30 seconds.
//
// Lets see how long it really takes to match strings with
-// 0.5 Million a's...it should be in the range of some
-// seconds.
+// 5 Million a's...it should be in the range of a couple
+// of seconds.
def time_needed[T](i: Int, code: => T) = {
val start = System.nanoTime()
@@ -119,5 +121,14 @@
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))))
}
+// another "power" test case
+simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE
+
+// the Iterator produces the rexp
+//
+// SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)
+//
+// where SEQ is nested 50 times.
+
*/