/** This app generates all the sentences of grammar1.
  * Turning this into a function that would generate a *stream*
  * of sentences is left as an exercise for the reader.
  * Another, easier, exercise would be to read the grammar
  * from a file (using the syntax in the comment before
  * CFGparseTree in CFGaux.scala),  rather than having it wired in.
  * 
  * The app maintains a queue of pairs (T, L), where T is a tree with
  * one or more tips, and L is the path to the leftmost tip.  While
  * the queue is nonempty (as it should always be for an infinite
  * language), the app expands the next (T, L) pair,  shows the
  * sentences (from tipless trees) that result, puts the trees with
  * tips back on the queue, and asks the user if they want to
  * continue.  Does it generate all the sentences exactly once?
  * Not if the language is ambiguous, so that the same sentence
  * can come from more than one tree.
  */
object PS3Q2Demo extends App {
  import PS3Q2._
  import CFGexample1._
  import CFGaux._
  import collection.immutable.Queue
  import CFGutil._

  /** Unparse a tree with respect to grammar1.
    * "Unparsing" means generating an Sexp representation, which
    * is slightly clearer.  See the comment on CFGtreeUnparse in
    * CFGaux.scala .
    */
  def gram1Unparse(tr: CFGsyntaxTree): Sexp = CFGtreeUnparse(tr, grammar1)

  def treeExpansionsDisplayCollect(tr: CFGsyntaxTree, path: Path):
      (List[(CFGsyntaxTree, Path)], List[CFGsyntaxTree]) = {
    println("tr: " + gram1Unparse(tr) + "\n  path = " + path)
    val trExpansions: List[CFGsyntaxTree] = expandPath(tr, path, grammar1)
    println("trExpansions = " + trExpansions.map(gram1Unparse))
    val expansionTips: List[Option[Path]] = trExpansions.map(leftmostTip)
    // Collect expansions with a leftmost tip and those without --
    val partitions: (List[(CFGsyntaxTree, Option[Path])],
                     List[(CFGsyntaxTree, Option[Path])]) = 
      (trExpansions zip expansionTips).partition({
        case (_, Some(_)) => true
        case (_, None) => false
      })
    val (withTipOpt, withoutTipOpt) = partitions
    // -- `withTipOpt` and `withoutTip` are lists of pairs
    //   (CFGsyntaxTree, Option[Path])
    // Get rid of those pesky options --
    val withoutTip =  withoutTipOpt.map(_._1)
    println("  Without Tip = " + withoutTip.map(gram1Unparse))
    if (withoutTip.nonEmpty) {
      println("  Sentences:\n     " +
              withoutTip.map(tr =>
                "[ " + CFGtreeSentence(tr, " ") + " ]"
              ).mkString("\n     "))
    }
    val withTip = withTipOpt.map(pair => {
      val tr = pair._1
      val path =  pair._2.get
      (tr, path)
    })
    val withTipPrefix = "  With tip = List("
    println(withTipPrefix)
    // We want the close paren to line up with the open
    // paren, so we indent one space less --
    val indent = " " * (withTipPrefix.length - 1)
    for ((expansion, path) <- withTip) {
      println(indent + " (" + gram1Unparse(expansion) + ",\n" +
              indent + "  " + path.toString + ")")
    }
    println(indent + ")")
    (withTip, withoutTip)
  }

  // App starts here --

  var q: Queue[(CFGsyntaxTree, Path)] = Queue((tree1, List()))
  // For now, grammar is fixed to be grammar1
  var keepChugging: Boolean = true
  while (keepChugging) {
    val ((nextTree, nextPath), newQ) = q.dequeue
    //val pair: (CFGsyntaxTree, Path) = 
    q = newQ
    val (expansionsWithTips, expansionsWithoutTips) =
      treeExpansionsDisplayCollect(nextTree, nextPath)
    q = q ++ expansionsWithTips
    keepChugging = (q.nonEmpty && askUserYesOrNo("Continue?"))
  }
}