Let's say we have a balance binary tree and we want to yield (iterate) all the nodes in order.
Interface IBalancedTreeNode(Of T) ReadOnly Property Value As T Property Left As IBalancedTreeNode(Of T) Property Righ As IBalancedTreeNode(Of T) End Interface
Let's take the simple recursive approach
<Extension> Public Iterator YieldNode(Of T)( node As IBalancedTreeNode(Of T)) As IEnumerable(Of IBalancedTreeNode(Of T)) IF node Is Nothing Then Exit Function For Each node In node.Left.YieldNodes Yield node Next Yield node For Each node In node.Righ.YieldNodes Yield node Next End Function
Really simple to follow arithmetically , but has the issue that you are repeatedly yielding the same node(s).
A Solution would be that have some way of passing as parameter "the yield" when you do the recursion
extension public iterator function YieldNodes(of T) ( node As IBalancedTreeNode(Of T) ) As IEnumerable(Of IBalancedTreeNode(Of T)) return _YieldNodes(of T)( node, ThisMethod.Yielder ) end function extension private iterator function _YieldNodes (Of T)(Node As IBalancedTreeNode(of T), ByRef yielder As Yield(Of IEnumerable(Of IBalancedTreeNode(Of T)) ) ) As IEnumerable(Of IBalancedTreeNode(of T)) If node Is Nothing Then Exit Function If node.Left IsNot Nothing Then node.YieldNodes( yielder ) Yielder.Yield node If node.Righ IsNot Nothing Then Node.YieldNodes( yielder ) end function
Now the yield algorithm is Linear, but I have yet to find a way to implement this design.
So this means a change of algorithm to fit in with restrictions of the language.
<Extension> Iterator Function YieldNodes(Of T) ( Current As IBalancedTreeNode(Of T) ) As IEnumerable(Of IBalancedTreeNode(Of T)) If Current IsNot Nothing Then Exit Function Dim TheStack As New Stack(Of BalancedTreeNode(Of T) ) Do While Current IsNot Nothing TheStack.Put( Current ) Current = Current.Left End While If TheStack.Count > 0 Then Dim Popped = TheStack.Pop Yield Popped Current = Popped.Righ End If Loop Until (Current Is Nothing) AndAlso (TheStack.Count = 0) End Function
Slightly more complex algorithm to understand, but has the advantage of linearizing the yielding of nodes.
Think about how the programming language can effect the implementation of your algorithm.
Also think how the implementation can effect the running time of the algorithm.