import scala.language.implicitConversions
import scala.language.reflectiveCalls

/* Note, in the lectures I did not show the type consraint
 * I <% Seq[_] , which means that the input type I can be
 * treated, or seen, as a sequence. */

abstract class Parser[I <% Seq[_], T] {
  def parse(ts: I): Set[(T, I)]

  def parse_all(ts: I) : Set[T] =
    for ((head, tail) <- parse(ts); 
        if (tail.isEmpty)) yield head
}

class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], 
                                   q: => Parser[I, S]) extends Parser[I, (T, S)] {
  def parse(sb: I) = 
    for ((head1, tail1) <- p.parse(sb); 
         (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)
}

class AltParser[I <% Seq[_], T](p: => Parser[I, T], 
                                q: => Parser[I, T]) extends Parser[I, T] {
  def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   
}

class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], 
                                   f: T => S) extends Parser[I, S] {
  def parse(sb: I) = 
    for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
}

// atomic parsers  
case class CharParser(c: Char) extends Parser[String, Char] {
  def parse(sb: String) = 
    if (sb != "" && sb.head == c) Set((c, sb.tail)) else Set()
}

import scala.util.matching.Regex
case class RegexParser(reg: Regex) extends Parser[String, String] {
  def parse(sb: String) = reg.findPrefixMatchOf(sb) match {
    case None => Set()
    case Some(m) => Set((m.matched, m.after.toString))  
  }
}

val NumParser = RegexParser("[0-9]+".r)
def StringParser(s: String) = RegexParser(s.r)


// convenience
implicit def string2parser(s: String) = StringParser(s)
implicit def char2parser(c: Char) = CharParser(c)

implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
  def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
  def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
  def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
}

implicit def StringOps(s: String) = new {
  def || (q : => Parser[String, String]) = new AltParser[String, String](s, q)
  def || (r: String) = new AltParser[String, String](s, r)
  def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f)
  def ~[S] (q : => Parser[String, S]) = 
    new SeqParser[String, String, S](s, q)
  def ~ (r: String) = 
    new SeqParser[String, String, String](s, r)
}

val c = new CharParser('c')
lazy val cn = c ==> (c => c.toInt)
val f = (c: Char) => c.toInt

c.parse("cb")
(c ==> f).parse("cb")

// a parse palindromes
lazy val Pal : Parser[String, String] = 
  (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
   ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "a" || "b" || "")

Pal.parse_all("abaaaba")

println("Palindrome: " + Pal.parse_all("abaaaba"))

// well-nested parenthesis parser
lazy val P : Parser[String, String] = 
  "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || ""

P.parse_all("(((()()))())")
P.parse_all("(((()()))()))")
P.parse_all(")(")
P.parse_all("()")

// arithmetic expressions

lazy val E: Parser[String, Int] = 
  (T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } ||
  (T ~ "-" ~ E) ==> { case ((x, y), z) => x - z } || T 
lazy val T: Parser[String, Int] = 
  ((F ~ "*" ~ T) ==> { case ((x, y), z) => x * z } || F)
lazy val F: Parser[String, Int] = 
  ("(" ~ E ~ ")") ==> { case ((x, y), z) => y } || NumParser


println(E.parse("4*2+3"))
println(E.parse_all("4/2+3"))
println(E.parse("1 + 2 * 3"))
println(E.parse_all("(1+2)+3"))
println(E.parse_all("1+2+3"))  



// no left-recursion allowed, otherwise will loop
lazy val EL: Parser[String, Int] = 
  ((EL ~ "+" ~ EL) ==> { case ((x, y), z) => x + z} || 
   (EL ~ "*" ~ EL) ==> { case ((x, y), z) => x * z} ||
   ("(" ~ EL ~ ")") ==> { case ((x, y), z) => y} ||
   NumParser)

//println(E.parse_all("1+2+3"))


// a repetition parser

def RepParser[I  <% Seq[_], T](p: => Parser[I, T]): Parser[I, List[T]] = {
  p ==> { case x => x :: Nil } ||
  p ~ RepParser(p) ==> { case (x, y) => x :: y }   
}


// a repetition parser
lazy val R : Parser[String, List[Char]] = RepParser('a') 
println(R.parse_all("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"))



// non-ambiguous vs ambiguous grammars
lazy val S : Parser[String, String] =
  ("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || ""

S.parse("1" * 15)

lazy val U : Parser[String, String] =
  ("1" ~ U) ==> { case (x, y) => x + y  } || ""

U.parse("1" * 15)

U.parse("11")
U.parse("11111")
U.parse("11011")

U.parse_all("1" * 100)
U.parse_all("1" * 100 + "0")

lazy val UCount : Parser[String, Int] =
  ("1" ~ UCount) ==> { case (x, y) => y + 1 } || 
  "" ==> { (x) => 0 }

UCount.parse("11111")
UCount.parse_all("11111")




// Single Character parser
lazy val One : Parser[String, String] = "1"
lazy val Two : Parser[String, String] = "2"

One.parse("1")
One.parse("111")

(One ~ One).parse("111")
(One ~ One ~ One).parse("111")
(One ~ One ~ One ~ One).parse("1111")

(One || Two).parse("111")


for (x <- List(1, 2, 3, 4)) println(x)
for (x <- List(1, 2, 3, 4); if (2 < x)) yield (x.toString + x.toString)
for (x <- List("2", "1", "3", "4", "1")) yield (x + x + x)

(1, "one", '1')._3
for ((x, y) <- List((1, "one"), (2, "two"), (3, "three"), (4,"many")); if (y == "many"))
  yield (x.toString + y)



// Example section for lazy evaluation
def square(n: Int) = {
  n * n
}

square(4 + 3 + 5)

def bar(): Int = {
  bar()
  3
}

//would loop
square(bar())

// lazy
def foo(n: => Int) = {
  print("finished")
}

foo(bar())