"""
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]