import scala.collection.mutable.Stack
import scala.collection.mutable.ListBuffer
import scala.io.Source
import java.io._

case class Input(
  letter: Char,
  left: Char,
  right: List[Char]
)
case class Data(
  input: List[Input],
  alphabet: List[Char],
  word: List[Char]
)
case class Graph(
  nodes: Map[Char, List[Int]],
  relation: List[(Char, Char)]
)

object Main {
  val lowerCase: List[Char] = "zxcvbnmasdfghjklqwertyuiop".toList


  def main(args: Array[String]): Unit = {
    val Data(list, alphabet, word) = parse("test.txt")

    val dr = Relations.dependency(list)
    println("Dependency Relation:\t" + dr)
    val idr = Relations.complementary(dr,alphabet)
    println("Independency Relation:\t" + idr)
    val fclasses = Foata.calculate(dr,word,alphabet)
    println("Foata classes:\t\t\t" + fclasses)

    GraphOperations.dumpToFile(GraphOperations.createGraph(dr,word))
  }

  def parse(fileName: String): Data = {
    var exp: List[Char] = List()
    var alphabet: List[Char] = List()
    val file = Source.fromFile(fileName).getLines
    val buffer: ListBuffer[Input] = new ListBuffer()

    file.foreach(line => {
      if(line.startsWith("(")){
        val letter = line.charAt(1)
        val left  = line.charAt(4)
        val right = line.substring(7).filter(lowerCase.contains).toList
        buffer += Input(letter,left,right)
      }
      if(line.startsWith("w"))
        exp = line.substring(4).toList
      if(line.startsWith("A"))
        alphabet = lowerCase.filter(c => line.contains(c))
    })
    Data(buffer.toList, alphabet, exp)
  }
}

object Relations{
  import cats.instances.list._
  import cats.syntax.all._

  def dependency(inList: List[Input]): List[(Char, Char)] ={
    val relation = for{
      input <- inList
      right <- input.right
      x <- inList.filter{ case Input(_,left,_) => left == right}
    } yield (input.letter, x.letter)
    makeSymmetric(relation)
  }

  def complementary[T](relation: List[(T, T)], alphabet: List[T]): List[(T, T)] =
    (alphabet |@| alphabet).tupled.filterNot(relation.contains)

  def makeSymmetric[T](relation: List[(T, T)]): List[(T, T)] = {
    val buffer: ListBuffer[(T, T)] = new ListBuffer()
    relation.foreach{
      case (l: T, r: T) =>
        buffer += l -> r
        if(!relation.contains(r -> l))
          buffer += r -> l
    }
    buffer.toList
  }

  def removeSymmetric[T](relation: List[(T,T)]): List[(T,T)] = {
    val buffer: ListBuffer[(T,T)] = new ListBuffer()
    relation.foreach{case (left,right) =>
      if(!buffer.contains(right -> left))
        buffer += left -> right
    }
    buffer.toList
  }


  def removeReflexive[T](relation: List[(T,T)]): List[(T,T)] =
    relation.filterNot{case (l,r) => l ==r }
}

object Foata{

  def calculate(dr: List[(Char, Char)], word: List[Char], alphabet: List[Char]): List[List[Char]] ={
    val r = Relations.removeReflexive(dr)
    val stacks = alphabet.map(letter => letter -> new Stack[Char]()).toMap

    word.reverse.foreach( x => {
      stacks(x).push(x)
      r.filter{ case (l, _) => l == x }
        .map(_._2)
        .foreach(stacks(_).push('*'))
    })

    val fb: ListBuffer[List[Char]] = new ListBuffer()
    var max = stacks.map(s => s._2.length).max

    while (max > 0){
      val buffer: ListBuffer[Char] = new ListBuffer()
      stacks.foreach(s =>
        if(s._2.length == max)
          buffer += s._2.pop()
      )
      max -= 1
      val done = buffer.filterNot(_ == '*').sorted.toList
      if(done.nonEmpty)
        fb += done
    }
    fb.toList
  }
}

object GraphOperations{
  import cats.instances.list._
  import cats.syntax.all._

  def createGraph(dr: List[(Char, Char)], word: List[Char]): Graph = {
    var nodes: Map[Char, List[Int]] = Map()

    word.zipWithIndex.foreach{ case (c, i) =>
      nodes = if(nodes.contains(c)) nodes + (c -> (i :: nodes(c))) else nodes + (c -> List(i))
    }

    val r = dr.filter{ case (left, right) =>
      val different = left != right && word.contains(left) && word.contains(right)
      val reflective = left == right && word.count(_ == left) >= 2
      different || reflective
    }

    Graph(nodes,Relations.removeSymmetric(r))
  }

  def dumpToFile(graph: Graph): Unit ={
    val pw = new PrintWriter(new File("graph.dot"))

    pw.write("digraph g{\n")

    graph.relation.foreach{case (left, right) =>
      val r0 = (graph.nodes(left) |@| graph.nodes(right)).tupled
      val r1 = Relations.removeReflexive(r0)
      val r2 = Relations.removeSymmetric(r1)
      r2.foreach{
        case (i,j) => pw.write("\t"+i.toString +" -> " + j.toString + "\n")
      }
    }

    graph.nodes.foreach{case(c, nums) =>
      nums.foreach(i =>
        pw.write("\t"+ i.toString +"[label="+c+"]\n")
      )
    }

    pw.write("}\n")
    pw.close()
  }
}