/**
 * 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
 */

import Foundation


struct AuD_04_09_QueueFunctional {

    enum QueueRep {
        case Empty
        indirect case Entries(x: Int, r: QueueRep)
    }

    enum QueueError: Error {
        case QueueEmpty
        case QueueFull
    }

    class Queue {
        private let queueRep: QueueRep

        init (queueRep: QueueRep = .Empty) {
            self.queueRep = queueRep
        }

        func Enqueue (x: Int) -> Queue {
            Queue(queueRep: AddToTail(x: x, queueRep: queueRep))
        }

        func Dequeue() throws -> (Int, Queue) {
            let (first, rest) = try RemoveFirst(queueRep: queueRep)
            return (first, Queue(queueRep: rest))
        }

        func RemoveFirst(queueRep: QueueRep) throws -> (Int, QueueRep) {
            switch queueRep {
            case .Empty :
                throw QueueError.QueueEmpty
            case .Entries(let first, let rest) :
                return (first, rest)
            }
        }

        func AddToTail(x: Int, queueRep: QueueRep) -> QueueRep {
            switch queueRep {
            case .Empty :
                return .Entries(x: x, r: .Empty)
            case .Entries(let y, let rest) :
                return .Entries(x: y, r: AddToTail(x: x, queueRep: rest))
            }
        }
    }

    class QueueA {
        private let queueIn: QueueRep
        private let queueOut: QueueRep

        init (queueIn: QueueRep = .Empty, queueOut: QueueRep = .Empty) {
            self.queueIn = queueIn
            self.queueOut = queueOut
        }

        func Enqueue(x: Int) -> QueueA {
            QueueA(queueIn: .Entries(x: x, r: queueIn), queueOut: queueOut)
        }

        func Dequeue() throws -> (Int, QueueA) {
            switch queueOut {
            case .Entries(let x, let rest) :
                return (x, QueueA(queueIn: queueIn, queueOut: rest))
            case .Empty :
                let newQueueOut = reverse(queueRep: queueIn, acc: .Empty)
                switch newQueueOut {
                case .Entries(let x, let rest) :
                    return (x, QueueA(queueIn: .Empty, queueOut: rest))
                case .Empty :
                    throw QueueError.QueueEmpty
                }
            }
        }

        func reverse(queueRep: QueueRep, acc: QueueRep) -> QueueRep {
            switch queueRep {
            case .Empty:
                return acc
            case .Entries(let x, let rest):
                return reverse(queueRep: rest, acc: .Entries(x: x, r: acc))
            }
        }
    }

    static func run() {
        var queue: QueueA = QueueA()

        for i in 0 ..< 4 {
            queue = queue.Enqueue(x: i)
        }

        print()

        for _ in 0 ..< 4 {
            do {
                let (value, newQueue) = try queue.Dequeue()
                queue = newQueue
                print("value= \(value)")
            } catch {
                print("Failed")
            }
        }

    }
}