package kapitel_04

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 4, Listen: Immer einer nach dem anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_04_09_QueueFunctional_App extends App {

  sealed abstract class QueueRep
  case object Empty extends QueueRep
  case class Entries(x: Int, r: QueueRep) extends QueueRep

  case class Queue(private val queueRep: QueueRep = Empty) {

    def Enqueue(x: Int): Queue =
      Queue(AddToTail(x, queueRep))

    def Dequeue(): (Int, Queue) = {
      val (first, rest) = RemoveFirst(queueRep)
      (first, Queue(rest))
    }

    def RemoveFirst(queueRep: QueueRep): (Int, QueueRep) = queueRep match {
      case Empty => throw new IllegalArgumentException("queue is empty")
      case Entries(first, rest) =>
        (first, rest)
    }

    def AddToTail(x: Int, queueRep: QueueRep): QueueRep = queueRep match {
      case Empty =>
        Entries(x, Empty)
      case Entries(y, rest) =>
        Entries(y, AddToTail(x, rest))
    }
  }


  case class QueueA(private val queueIn: QueueRep = Empty,
                    private val queueOut: QueueRep = Empty) {

    def Enqueue(x: Int): QueueA =
      QueueA(Entries(x, queueIn), queueOut)

    def Dequeue(): (Int, QueueA) = {
      queueOut match {
        case Entries(x, rest) =>
          (x, QueueA(queueIn, rest))
        case Empty =>
          val newQueueOut = reverse(queueIn, Empty)
          newQueueOut match {
            case Entries(x, rest) =>
              (x, QueueA(Empty, rest))
            case Empty =>
              throw new IllegalMonitorStateException("Queue empty")
          }
      }
    }

    def reverse(queueRep: QueueRep, acc: QueueRep): QueueRep = queueRep match {
      case Empty =>
        acc
      case Entries(x, rest) =>
        reverse(rest, Entries(x, acc))
    }
  }

  var queue: QueueA = QueueA()

  for (i <- 0 until 4) {
    println("pre: " + queue)
    queue = queue.Enqueue(i)
    println("post: " + queue)
  }

  println()

  for (i <- 0 until 4) {
    println("pre: " + queue)
    val (value, newQueue) = queue.Dequeue()
    queue = newQueue
    println(s"post:  value= $value, queue= $queue")
  }

}