pep-material: marking/re2b_test.scala@ae4708c851ee (annotated)

94 ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	1	import scala.concurrent._
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	2	import scala.concurrent.duration._
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	3	import ExecutionContext.Implicits.global
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	4	import scala.language.postfixOps
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	5
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	6	val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	7
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	8	def nullable_urban (r: Rexp) : Boolean = r match {
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	9	case ZERO => false
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	10	case ONE => true
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	11	case CHAR(_) => false
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	12	case ALT(r1, r2) => nullable_urban(r1) \|\| nullable_urban(r2)
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	13	case SEQ(r1, r2) => nullable_urban(r1) && nullable_urban(r2)
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	14	case STAR(_) => true
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	15	}
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	16
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	17	def der_urban (c: Char, r: Rexp) : Rexp = r match {
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	18	case ZERO => ZERO
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	19	case ONE => ZERO
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	20	case CHAR(d) => if (c == d) ONE else ZERO
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	21	case ALT(r1, r2) => ALT(der_urban(c, r1), der_urban(c, r2))
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	22	case SEQ(r1, r2) =>
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	23	if (nullable(r1)) ALT(SEQ(der_urban(c, r1), r2), der_urban(c, r2))
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	24	else SEQ(der_urban(c, r1), r2)
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	25	case STAR(r1) => SEQ(der_urban(c, r1), STAR(r1))
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	26	}
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	27
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	28	def simp_urban(r: Rexp) : Rexp = r match {
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	29	case ALT(r1, r2) => (simp_urban(r1), simp_urban(r2)) match {
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	30	case (ZERO, r2s) => r2s
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	31	case (r1s, ZERO) => r1s
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	32	case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	33	}
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	34	case SEQ(r1, r2) => (simp_urban(r1), simp_urban(r2)) match {
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	35	case (ZERO, _) => ZERO
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	36	case (_, ZERO) => ZERO
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	37	case (ONE, r2s) => r2s
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	38	case (r1s, ONE) => r1s
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	39	case (r1s, r2s) => SEQ(r1s, r2s)
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	40	}
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	41	case r => r
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	42	}
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	43
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	44
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	45	lazy val f = Future {
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	46	assert(size(iterT(20, (r: Rexp) => der_urban('a', r), EVIL_urban)) == 7340068)
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	47	assert(size(iterT(20, (r: Rexp) => simp_urban(der_urban('a', r)), EVIL_urban)) == 8)
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	48	}
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	49
ae4708c851ee updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	50	Await.result(f, 120 second)

author	Christian Urban <christian dot urban at kcl dot ac dot uk>
	Wed, 21 Dec 2016 03:06:18 +0000
changeset 94	ae4708c851ee
child 95	4fa7231fede7
permissions	-rw-r--r--