//:load matcher.scala

//:load parser3.scala

abstract class Token

case object T_ONE extends Token

val lexing_rules : List[Rule[Token]] =

  List(("1", (s: List[Char]) => T_ONE))

val T = Tokenizer(lexing_rules)

case class TokParser(tok: Token) extends Parser[List[Token], Token] {

  def parse(ts: List[Token]) = ts match {

    case t::ts if (t == tok) => Set((t, ts)) 

    case _ => Set ()

  }

}

implicit def token2tokparser(t: Token) = TokParser(t)

case object EmpParser extends Parser[List[Token], String] {

  def parse(ts: List[Token]) = Set(("", ts))

}

lazy val Su: Parser[List[Token], String] = 

  (T_ONE ~ Su) ==> { case (x, y) => "1" + y} || EmpParser  

def time_needed[T](i: Int, code: => T) = {

  val start = System.nanoTime()

  for (j <- 1 to i) code

  val end = System.nanoTime()

  (end - start)/(i * 1.0e9)

}

def test(i: Int) = {

  val result = Su.parse_all(T.fromString("1" * i))

  //print(result.size + " ")

}

for (i <- 1 to 1000 by 50) {

  print(i + " ")

  print("%.5f".format(time_needed(1, test(i))))

  print("\n")

}