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

    enum BinTree<A: Equatable> : Sequence, Equatable {
        static func == (lhs: BinTree<A>, rhs: BinTree<A>) -> Bool {
            switch lhs {
            case .Empty :
                switch rhs {
                case .Empty :
                    return true
                default :
                    return false
                }
            case .Node(let vl, let ll, let rl) :
                switch rhs {
                case .Empty :
                    return false
                case .Node(let vr, let lr, let rr) :
                    return (vl == vr) && (ll == lr) && (rl == rr)
                }

            }
        }

        case Empty
        indirect case Node(value:  A,
                           left:   BinTree,
                           right:  BinTree
        )

        func makeIterator() -> TreeIterator<A> {
            TreeIterator(tree: self)
        }
    }


    struct TreeIterator<A: Equatable> : IteratorProtocol {
        typealias Element = A

        private var stack: [BinTree<A>] = []
        var treeV: BinTree<A>

        init(tree: BinTree<A>) {
            self.treeV = tree
        }

        mutating func next() -> A? {
            while (treeV != .Empty) {
                switch treeV {
                case .Node(_, let l, _) :
                    stack = [treeV] + stack
                    treeV = l
                default :
                    assertionFailure("Must not be reached")
                    return nil
                }
            }
            assert(treeV == .Empty)
            if (stack.count == 0) {
                return nil
            } else {
                let head = stack[0]
                switch head {
                case .Node(let v, _, let r) :
                    stack = Array(stack.dropFirst())
                    let result = v
                    treeV = r
                    return result
                default :
                    assertionFailure("Must not be reached")
                    return nil
                }
            }
        }
    }

    static func leaf<A: Equatable>(v: A) -> BinTree<A> {
        .Node(value: v, left: .Empty, right: .Empty)
    }

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

        for v in tree {
            print(v)
        }
    }

}