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

    struct Trie<T> {
        var info: T? // nil = unmarked node
        var succ: Dictionary<Character, Trie<T>>
    }

    static func insert<T>(t: inout Trie<T>, v: [Character], info: T) {
        if (v.count == 1) {
            let head = v[0]
            let next: Trie<T>? = t.succ[head]
            switch next {
            case nil :
                t.succ.updateValue(Trie<T>(info: info, succ: Dictionary<Character, Trie<T>>()), forKey: head)
            default :
                t.succ[head]!.info = info
            }
        } else if (v.count > 1) {
            let head = v[0]
            let tail = Array(v.dropFirst())
            let next = t.succ[head]
            switch next {
            case nil :
                var nt = Trie<T>(info: nil, succ: [:])
                insert(t: &nt, v: tail, info: info)
                t.succ.updateValue(nt, forKey: head)
            case _ :
                insert(t: &(t.succ[head]!), v: tail, info: info)
            }
        }
    }

    static func find<T>(t: Trie<T>, l: [Character]) -> T? {
        let next: Trie<T>? = t.succ[l[0]]
        switch next {
        case nil:
            return nil
        default :
            if (l.count == 1) {
                return next?.info
            } else {
                return find(t: next!, l: Array(l.dropFirst()))
            }
        }
    }

    static func run() {
        var t = Trie<String>( info: nil, succ: [:])
        let words = ["der", "dampf", "dauer", "da", "daumen"]
        for word in words {
            insert(t: &t, v: [Character](word), info: word)
        }
        for word in words {
            print(find(t: t, l: [Character](word)))
        }
    }
}