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

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

    class BinSearchTree<K: Comparable, V> {
        private var tree: BinTree<(K, V)> = .Empty

        func insert(key: K, value: V) {
            tree = insertF(key: key, value: value, t: tree)
        }

        private func insertF(key: K, value: V, t: BinTree<(K, V)>) -> BinTree<(K, V)> {
            switch t {
            case .Empty:
                return .Node(value: (key, value), left: .Empty, right: .Empty)
            case .Node((let k, let v), let l, let r):
                if (k == key) {
                    return t
                } else if (k > key) {
                    return .Node(value: (k, v), left: insertF(key: key, value: value, t: l), right: r)
                } else if (k < key) {
                    return .Node(value: (k, v), left: l, right: insertF(key: key, value: value, t: r))
                }
            }
            return t // must not be reached
        }

        func lookup(key: K) -> V? {
            lookupF(key: key, t: tree)
        }

        private func lookupF(key: K, t: BinTree<(K, V)>) -> V? {
            switch t {
            case .Empty:
                return nil
            case .Node((let k, let v), let l, let r):
                if (k == key) {
                    return v
                } else if (k > key) {
                    return lookupF(key: key, t: l)
                } else if (k < key) {
                    return lookupF(key: key, t: r)
                }
            }
            return nil
        }
    }

    static func run() {
        let BST = BinSearchTree<Int, String>()
        BST.insert(key: 10, value: "J")

        for (k, v) in [(8, "H"), (1,"A"), (2, "B"), (5, "E"), (9, "I"), (6, "F"), (7, "G"), (3, "C"), (4, "D")] {
            BST.insert(key: k,value: v)
        }

        for i in 1 ... 10 {
            print("\(i) -> \(BST.lookup(key: i))")
        }
    }

}