/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 5, Bäume: Immer einer über den anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_05_04_InorderProcess {

    enum BinTree<A> : CustomStringConvertible {
        case Empty
        indirect case Node(value:  A,
                           left:   BinTree,
                           right:  BinTree
        )
        var description : String {
            switch self {
            case .Empty: return "."
            case .Node(let v, let l, let r): return "[\(v), \(l.description), \(r.description) ]"
            }
        }
    }

    static func InOrderTraversalWithProcess<A>(tree: BinTree<A>, process: (A) -> ()) {

        func inorder(tree: BinTree<A>) {
            switch tree {
            case .Empty:
                return
            case .Node(let v, let l, let r):
                inorder(tree: l)
                process(v)
                inorder(tree: r)
            }
        }

        return inorder(tree: tree)
    }

    static func run() {
        let tree: BinTree<Int> =
                .Node(value: 1,
                        left: .Node(value: 2,
                                left: .Empty, right: .Empty),
                        right: .Node(value: 3,
                                left: .Node(value: 4, left: .Empty, right: .Empty),
                                right: .Node(value: 5,
                                        left: .Node(value: 6, left: .Empty, right: .Node(value: 7, left: .Empty, right: .Empty)),
                                        right: .Node(value: 8, left: .Empty, right: .Node(value: 9, left: .Empty, right: .Empty)))
                        )
                )

        InOrderTraversalWithProcess(tree: tree, process: { (x: Int) in print(x) } )
    }

}