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

import Foundation

struct AuD_11_05_BinTreePaths {

    /*
     * Alle Pfade von der Wurzel zu einem Blatt in einem perfekten Baum der Tiefe n können mit einem
     * Algorithmus aufgezählt werden, der den Baum gar nicht sehen muss.
     * Es ist ja klar, welche Pfade es in einem solchem Baum gibt.
     * Wenn der Baum nicht so perfekt gebaut ist, dann muss man ihn ansehen, wenn man alle Pfade von
     * der Wurzel zu irgendeinem Blatt erzeugen will.
     */

    indirect enum BinTree<A> {
        case Empty
        case Node(value: A, left: BinTree<A>, right: BinTree<A>)
    }

    static func AllPaths<A>(_ t: BinTree<A>) -> [[String]] {
        var result: [[String]] = []

        func APR(_ t: BinTree<A>, _ path: [String]) {
            switch (t) {
            case .Empty:
                result = result + [path]
            case .Node(_, let l, let r):
                for d in ["l", "r"] {
                    APR(
                        { (s: String) -> BinTree<A> in
                            switch (s) {
                            case "l": return l
                            case "r": return r
                            default: return .Empty
                            }
                        }(d),
                        path + [d]
                    )
                }
            }
        }

        switch (t) {
        case .Empty:
            break
        case _:
            APR(t, [])
        }
        return result
    }

    // zur Vereinfachung des Baumaufbaus
    static func leaf<A>(_ a: A) -> BinTree<A> {
        .Node(value: a, left: .Empty, right: .Empty)
    }

    static func flatten<A: CustomStringConvertible>(_ t: BinTree<A>) -> String {
        switch (t) {
        case .Empty:
            return "."
        case .Node(let v, let l, let r):
            return "[\(v.description), \(flatten(l)), \(flatten(r))]"
        }
    }

    static let tree: BinTree<Int> =
        .Node( value: 7,
               left: .Node(value: 5, left: .Node(value: 1, left: .Empty, right: leaf(3)), right: leaf(6)),
               right: .Node(value: 12, left: .Empty, right: .Node(value: 19, left: leaf(15), right: leaf(66)))
        )

    static func run() {
        print(flatten(tree))
        print(AllPaths(tree).map( { (x) in x.joined() } ).joined(separator: ", "))
    }
}