"""
Iterate Through Recursive Data With Yield

If you study the _scanInOrder method below you will see that implementing it with `yield` is very
straightforward. Without `yield` the alternative is to write a helper class that implements
IEnumerator<of T> and maintains state variables to track its current position in between calls to
.moveNext. Yuck!

This example was adapted from http://msdn.microsoft.com/msdnmag/issues/06/00/C20/default.aspx
"""


class Node<of T> where T must be IComparable<of T>

    cue init(item as T)
        .init(item, nil, nil)

    cue init(item as T, left as Node<of T>?, right as Node<of T>?)
        base.init
        _item = item
        _left = left
        _right = right

    pro left from var as Node<of T>?

    pro right from var as Node<of T>?

    get item from var as T

    def compareTo(node as Node<of T>) as int
        # this method enables comparison operators in Cobra like "a < b" where a and b are Nodes
        return .item.compareTo(node.item)

    def toString as String is override
        return '[.typeOf.name](item=[.item])'

    def dump
        print this stop
        if _left, print ' left:', _left stop
        if _right, print ' right:', _right stop
        print
        if _left, _left.dump
        if _right, _right.dump


class BinaryTree<of T> where T must be IComparable<of T>

    cue init(root as Node<of T>)
        base.init
        _root = root

    pro root from var as Node<of T>
    
    def add(items as vari T)
        for item in items, .add(item)
    
    def add(item as T)
        _add(Node<of T>(item), _root)
    
    def _add(newNode as Node<of T>, root as Node<of T>)
        if newNode > root
            right = root.right
            if right
                _add(newNode, right)
            else
                root.right = newNode
        else if newNode < root
            left = root.left
            if left
                _add(newNode, left)
            else
                root.left = newNode

    get inOrder as IEnumerable<of T>
        return _scanInOrder(_root, 0)

    def _scanInOrder(node as Node<of T>?, level) as IEnumerable<of T>
        if node
            if node.left
                for item in _scanInOrder(node.left to !, level+1)
                    yield item
            yield node.item
            if node.right
                for item in _scanInOrder(node.right to !, level+1)
                    yield item


class Program

    def main
        tree = BinaryTree<of int>(Node<of int>(0))
        tree.add(4, 6, 2, 7, 5, 3, 1)
        values = List<of int>()
        for value in tree.inOrder
            # print value
            values.add(value)
        assert values == [0, 1, 2, 3, 4, 5, 6, 7]