381 def flats(rs: List[ARexp]): List[ARexp] = rs match { |
381 def flats(rs: List[ARexp]): List[ARexp] = rs match { |
382 case Nil => Nil |
382 case Nil => Nil |
383 case AZERO :: rs1 => flats(rs1) |
383 case AZERO :: rs1 => flats(rs1) |
384 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
384 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
385 case r1 :: rs2 => r1 :: flats(rs2) |
385 case r1 :: rs2 => r1 :: flats(rs2) |
386 } |
386 } |
|
387 def remove(v: Val): Val = v match{ |
|
388 case Right(v1) => v1 |
|
389 case Left(v1) => v1 |
|
390 case _ => throw new Exception("Not removable") |
|
391 } |
|
392 def augment(v: Val, i: Int): Val = if(i > 1) augment(Right(v), i - 1) else Right(v) |
|
393 //an overly complex version |
|
394 /* |
|
395 if(rel_dist >0){//the regex we are dealing with is not what v points at |
|
396 rs match{ |
|
397 case Nil => throw new Exception("Trying to simplify a non-existent value") |
|
398 case AZERO :: rs1 => flats_vsimp(rs1, rel_dist - 1, remove(v)) |
|
399 case AALTS(bs, rs1) :: rs2 => flats_vsimp(rs2, rel_dist - 1, augment(v, rs1.length - 1))//rs1 is guaranteed to have a len geq 2 |
|
400 case r1 :: rs2 => flats_vsimp(rs2, rel_dist - 1, v) |
|
401 } |
|
402 } |
|
403 else if(rel_dist == 0){//we are dealing with regex v is pointing to -- "v->r itself" |
|
404 rs match{//r1 cannot be zero |
|
405 AALTS(bs, rs1) :: rs2 => flats_vsimp( ) |
|
406 AZERO::rs2 => throw new Exception("Value corresponds to zero") |
|
407 r1::rs2 => flats_vsimp(rs2, rel_dist - 1, v) |
|
408 } |
|
409 |
|
410 } |
|
411 else{ |
|
412 |
|
413 } |
|
414 */ |
|
415 def flats_vsimp(rs: List[ARexp], position: Int): Int = (rs, position) match { |
|
416 case (_, 0) => 0 |
|
417 case (Nil, _) => 0 |
|
418 case (ZERO :: rs1, _) => flats_vsimp(rs1, position - 1) - 1 |
|
419 case (AALTS(bs, rs1) :: rs2, _) => rs1.length - 1 + flats_vsimp(rs2, position - 1) |
|
420 case (r1 :: rs2, _) => flats_vsimp(rs2, position - 1) |
|
421 } |
387 def rflats(rs: List[Rexp]): List[Rexp] = rs match { |
422 def rflats(rs: List[Rexp]): List[Rexp] = rs match { |
388 case Nil => Nil |
423 case Nil => Nil |
389 case ZERO :: rs1 => rflats(rs1) |
424 case ZERO :: rs1 => rflats(rs1) |
390 case ALTS(rs1) :: rs2 => rs1 ::: rflats(rs2) |
425 case ALTS(rs1) :: rs2 => rs1 ::: rflats(rs2) |
391 case r1 :: rs2 => r1 :: rflats(rs2) |
426 case r1 :: rs2 => r1 :: rflats(rs2) |
410 case rs => AALTS(bs1, rs) |
445 case rs => AALTS(bs1, rs) |
411 } |
446 } |
412 } |
447 } |
413 //case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
448 //case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
414 case r => r |
449 case r => r |
|
450 } |
|
451 def find_pos(v: Val, rs: List[Rexp]): Int = (rs, v) match{ |
|
452 case (Right(v), r::Nil) => 1 |
|
453 case (Left(v), r::rs) => 0 |
|
454 case (Right(v), r::rs) => find_pos(v, rs) + 1 |
|
455 case (v, _) => 0 |
|
456 } |
|
457 def remove(v: Val, rs: List[Rexp]) : Val = (rs,v) match {//remove the outmost layer of ALTS's Left and Right |
|
458 case (Right(v), r::Nil) => v |
|
459 case (Left(v), r::rs) => v |
|
460 case (Right(v), r::rs) => remove(v, rs) |
|
461 } |
|
462 def simple_end(v: Value): Boolean = v match { |
|
463 case Left(v) => return false |
|
464 case Right(v) => return simple_end(v) |
|
465 case v => return true |
|
466 } |
|
467 def isend(v: Val, rs: List[Rexp], position: Int): Boolean = { |
|
468 val rsbh = rs.slice(position, rs.length) |
|
469 val out_end = if(flats(rsbh) == Nil) true else false |
|
470 val inner_end = simple_end(v) |
|
471 inner_end && out_end |
|
472 } |
|
473 def get_coat(v: Val, rs: List[Rexp], vs: Val): Val = (rs, v) match{//the dual operation of remove(so-called by myself) |
|
474 case (Right(v), r::Nil) => Right(vs) |
|
475 case (Left(v), r::rs) => Left(vs) |
|
476 case (Right(v), r::rs) => Right(get_coat(v, rs, vs)) |
|
477 } |
|
478 def coat(v: Val, i: Int) : Val = i match { |
|
479 case 0 => v |
|
480 case i => coat(Right(v), i - 1) |
|
481 } |
|
482 def bsimp2(r: ARexp, v: Val): (ARexp, Val => Val) = (r,v) match{ |
|
483 case (ASEQ(bs1, r1, r2), v) => (bsimp2(r1), bsimp2(r2)) match { |
|
484 case ((AZERO, _), (_, _) )=> (AZERO, undefined) |
|
485 case ((_, _), (AZERO, _)) => (AZERO, undefined) |
|
486 case ((AONE(bs2), f1) , (r2s, f2)) => (fuse(bs1 ++ bs2, r2s), lambda v => v match { case Sequ(_, v) => f2(v) } ) |
|
487 case ((r1s, f1), (r2s, f2)) => (ASEQ(bs1, r1s, r2s), lambda v => v match {case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))} |
|
488 } |
|
489 case AALTS(bs1, rs) => { |
|
490 val init_ind = find_pos(v, rs) |
|
491 val vs = bsimp2(rs[init_ind], remove(v, rs))//remove all the outer layers of left and right in v to match the regx rs[i] |
|
492 val rs_simp = rs.map(bsimp) |
|
493 val vs_kernel = rs_simp[init_ind] match { |
|
494 case AALTS(bs2, rs2) => remove(vs, rs_simp[init_ind])//remove the secondary layer of left and right |
|
495 case r => vs |
|
496 } |
|
497 val vs_for_coating = if(isend(vs, rs_simp, init_ind)) vs_kernel else Left(vs_kernel) |
|
498 |
|
499 val r_s = rs_simp[init_ind] |
|
500 val shift = flats_vsimp(vs, rs_simp, init_ind) + find_pos(vs, rs_simp[init_ind]) |
|
501 val vf = coat(vs_for_coating, shift + init_ind) |
|
502 |
|
503 val flat_res = flats(rs_simp)//flats2 returns a list of regex and a single v |
|
504 val dist_res = distinctBy(flat_res, erase) |
|
505 dist_res match { |
|
506 case Nil => AZERO |
|
507 case s :: Nil => fuse(bs1, s) |
|
508 case rs => AALTS(bs1, rs) |
|
509 } |
|
510 } |
|
511 //case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
512 case r => r |
415 } |
513 } |
416 def super_bsimp(r: ARexp): ARexp = r match { |
514 def super_bsimp(r: ARexp): ARexp = r match { |
417 case ASEQ(bs1, r1, r2) => (super_bsimp(r1), super_bsimp(r2)) match { |
515 case ASEQ(bs1, r1, r2) => (super_bsimp(r1), super_bsimp(r2)) match { |
418 case (AZERO, _) => AZERO |
516 case (AZERO, _) => AZERO |
419 case (_, AZERO) => AZERO |
517 case (_, AZERO) => AZERO |