/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 3, Daten und ihre Struktur
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_03_08_StructuralRecursion {

    enum IntList {
        case Nil
        indirect case Cons (head: Int, tail: IntList)
    }

    static func ListSum(lst: IntList) -> Int {
        switch lst {
        case .Nil: return 0
        case .Cons(let first, let rest): return first + ListSum(lst: rest)
        }
    }

    enum IntTree {
        case Leaf(v: Int)
        indirect case Node(left: IntTree, right: IntTree)
    }

    static func treeToList(tree: IntTree) -> IntList {
        switch tree {
        case .Leaf(let v):
            return .Cons(head: v, tail: .Nil)
        case .Node(let left, let right):
            return append(lst1: treeToList(tree: left), lst2: treeToList(tree: right))
        }
    }

    static func append(lst1: IntList, lst2:IntList) -> IntList {
        switch lst1 {
        case .Nil :
            return lst2
        case .Cons(let head, let tail) :
            return .Cons(head: head, tail: append(lst1: tail, lst2: lst2))
        }
    }

}