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

    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() -> BFTreeIterator<A> {
            BFTreeIterator(tree: self)
        }
    }

    struct BFTreeIterator<A: Equatable> : IteratorProtocol {
        private var queue : [BinTree<A>] = []
        private var treeV: BinTree<A>

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

        mutating func next() -> A? {
            if (treeV == .Empty && queue.isEmpty) {
                return nil
            }

            if (treeV == .Empty) {
                treeV = queue.removeFirst()
            }
            switch treeV {
            case .Node(let v, let l, let r) :
                if (l != .Empty) { queue.append(l) }
                if (r != .Empty) { queue.append(r) }
                treeV = .Empty
                return v
            case .Empty:
                return nil // must not be reached
            }
        }
    }

    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: 1,
                        left: .Node(value: 2,
                                left: .Node(value: 4,
                                        left: leaf(v: 8),
                                        right: leaf(v: 9)),
                                right: leaf(v: 5)),
                        right: .Node(value: 3,
                                left: .Node(value: 6,
                                        left: leaf(v: 10),
                                        right: leaf(v: 11)),
                                right: leaf(v: 7))
                )

        for v in tree {
            print(v)
        }
    }

}