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

    enum IntList : Sequence {
        case Nil
        indirect case Cons(first: Int, rest: IntList)

        func makeIterator() -> IntLstIterator {
            IntLstIterator(lst: self)
        }
    }

    struct IntLstIterator : IteratorProtocol {
        var lst: IntList
        init(lst: IntList) {
            self.lst = lst
        }
        mutating func next() -> Int? {
            switch lst {
            case .Nil: return nil
            case .Cons(let first, let rest):
                lst = rest
                return first
            }
        }
    }

    static func insert(a: IntList, v: Int) -> IntList {
        switch a {
        case .Nil:
            return .Cons(first: v, rest: .Nil)
        case .Cons(let x, let rest):
            if (v < x) {
                return .Cons(first: v, rest: a)
            } else {
                return .Cons(first: x, rest: insert(a: rest, v: v))
            }
        }
    }

    static func sort(a: IntList) -> IntList {
        switch a {
        case .Nil :
            return .Nil
        case .Cons(let v, let rest) :
            return insert(a: sort(a: rest), v: v)
        }
    }

    static func run() {
        let arr: [Int] = [1,-2,3,-4,5,-6,7]
        var lst: IntList = .Nil
        for i in arr {
            lst = .Cons(first: i, rest: lst)
        }
        let sortedList = sort(a: lst)
        print(Array(sortedList))
    }

}