// Part 2 about Regular Expression Matching

//==========================================

// copy over all code from re.scala

// (2a) Complete the function iterT which needs to

// be tail-recursive(!) and takes an integer n, a 

// function f and an x as arguments. This function 

// should iterate f n-times starting with the 

// argument x.

import scala.annotation.tailrec

@tailrec

def iterT[A](n: Int, f: A => A, x: A): A = ...

// (2b) Complete the size function for regular

// expressions 

def size(r: Rexp): Int = ...

// two testcases about the sizes of simplified and 

// un-simplified derivatives

//val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))

//size(iterT(20, (r: Rexp) => der('a', r), EVIL))        // should produce 7340068

//size(iterT(20, (r: Rexp) => simp(der('a', r)), EVIL))  // should produce 8

// (2c) Complete the fixpoint function below.

@tailrec

def fixpT[A](f: A => A, x: A): A = ...

/* testcases

//the Collatz function from CW 6 defined as fixpoint

def ctest(n: Long): Long =

  if (n == 1) 1 else

    if (n % 2 == 0) n / 2 else 3 * n + 1

// should all produce 1 

fixpT(ctest, 97L)

fixpT(ctest, 871L)

fixpT(ctest, 77031L)

*/

/*

// the same function on strings using the regular expression

// matcher

def foo(s: String): String = {

  if (matcher("a", s)) "a" else

  if (matcher("aa" ~ STAR("aa"), s)) s.take(s.length / 2) 

  else "a" ++ s * 3

}

// should all produce "a" 

fixpT(foo, "a" * 97)

fixpT(foo, "a" * 871)

*/