using iterator in a binaryTree

[Tony Johansson]

Hello!

At the end I have a complete working program that creates a Binary Tree
using the generic class Tree<T>.
The generic class Tree<T> is implemneting the generic interface
IEnumerable<T> so we can use
foreach on the Binary tree. We use a iterator to implement the
IEnumerator<T>(Current,MoveNext).

Now to my question can somebody explain this code GetEnumerator(). I know it
uses recursion because I have run it through
the debugger. I find it hard to understand how recursion is used in the
code.
If I look at the method WalkTree below that is using recursion. It much more
easy to understand the code that use WalkTree
then to understand the code GetEnumerator. Both is using recursion but I can
see directly that WalkTree is using recursion
but it's not possible to see that GetEnumerator is using recursion.

public IEnumerator<T> GetEnumerator()
{
if (this.left != null)
{
foreach (T item in this.left)
{
yield return item;
}
}
yield return this.data;

if (this.right != null)
{
foreach (T item in this.right)
{
yield return item;
}
}
}


public void WalkTree()
{
if (this.LeftTree != null)
{
this.LeftTree.WalkTree();
}

Console.WriteLine(this.NodeData);

if (this.RightTree != null)
{
this.RightTree.WalkTree();
}
}



using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

public class Tree<T> : IEnumerable<T> where T : IComparable<T>,
IComparable
{
private T data;
private Tree<T> left;
private Tree<T> right;

public Tree(T data)
{
this.data = data;
left = null;
right = null;
}

public Tree<T> RightTree
{
get { return right; }
set { right = value; }
}

public Tree<T> LeftTree
{
get { return left; }
set { left = value; }
}

public T NodeData
{
get { return data; }
set { data = value; }
}

public void Insert(T newItem)
{
T currentItem = this.NodeData;

if (currentItem.CompareTo(newItem) > 0)
{
if (this.LeftTree == null)
{
this.LeftTree = new Tree<T>(newItem);
}
else
{
this.LeftTree.Insert(newItem);
}
}
else
{
if (this.RightTree == null)
{
this.RightTree = new Tree<T>(newItem);
}
else
{
this.RightTree.Insert(newItem);
}
}
}

public void WalkTree()
{
if (this.LeftTree != null)
{
this.LeftTree.WalkTree();
}

Console.WriteLine(this.NodeData);

if (this.RightTree != null)
{
this.RightTree.WalkTree();
}
}

public IEnumerator<T> GetEnumerator()
{
if (this.left != null)
{
foreach (T item in this.left)
{
yield return item;
}
}
yield return this.data;

if (this.right != null)
{
foreach (T item in this.right)
{
yield return item;
}
}
}


IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}

class Program
{
private static Tree<T> BuildTree<T>(params T[] data) where T :
IComparable<T>, IComparable
{
Tree<T> sortTree = new Tree<T>(data[0]);

for (int i = 1; i < data.Length; i++)
{
sortTree.Insert(data);
}
return sortTree;
}

static void Main(string[] args)
{
Tree<int> intTree = BuildTree<int>(1, 5, 3, 2, 45, 7, 8, 9, 0, 12,
65, 566, 11, 44, 66, 77);

foreach (int item in intTree)
Console.WriteLine(item);
}
}


//Tony

 

[Peter Duniho]

[...]
Now to my question can somebody explain this code GetEnumerator(). I know it
uses recursion because I have run it through
the debugger. I find it hard to understand how recursion is used in the
code.

Recursion happens any time a method calls itself, directly or indirectly.

If I look at the method WalkTree below that is using recursion. It much more
easy to understand the code that use WalkTree
then to understand the code GetEnumerator. Both is using recursion but I can
see directly that WalkTree is using recursion
but it's not possible to see that GetEnumerator is using recursion.

It's not only possible to see, it's easy:

public IEnumerator<T> GetEnumerator()
{
if (this.left != null)
{
foreach (T item in this.left)

The above statement is one site in which this GetEnumerator() method
calls itself.

{
yield return item;
}
}
yield return this.data;

if (this.right != null)
{
foreach (T item in this.right)

The above statement is another site in which this GetEnumerator() method
calls itself.

{
yield return item;
}
}
}

As you can see, GetEnumerator() calls itself two different places, hence
the recursion. It's trivial to see this in the debugger if you simply
put a break-point on the GetEnumerator() method: you'll see during the
enumeration where it's being called recursively.

From an analytical point of view, the thing you need to remember is
that a "foreach" statement includes an implicit call to the
GetEnumerator() method. That's how it gets the IEnumerable<T> it uses
to do the enumeration.

Note also that a method with the "yield" keyword in it is a special kind
of method called an "iterator". It's automatically packed into an
anonymous implementation of IEnumerable<T> that includes the necessary
MoveNext(), Current, etc. members to be use for that interface.

So in reality, the iterator method you've shown implements the iteration
in three parts: a loop iteration the left descendants, a single return
of the object itself, and a loop iteration of the right descendants.
With each call to the implicitly created MoveNext() method, the iterator
code progresses through those three sections of its own code exactly as
specified in the method by the "yield" statement.

For more details see:
http://msdn.microsoft.com/en-us/library/dscyy5s0.aspx
http://msdn.microsoft.com/en-us/library/ttw7t8t6.aspx

Pete

 

[Tony Johansson]

Hello!

Now I think I understand. So as you mentioned whatever I have after the
keyword "in" in a foreach clause that objects GetEnumerator is called.
In this case we have foreach (T item in this.left)
this.left is a Tree<T> so the GetEnumerator of the Tree<T> object is called.
which is this code. Does that sounds reasonable correct ?

//Tony

[...]
Now to my question can somebody explain this code GetEnumerator(). I know
it uses recursion because I have run it through
the debugger. I find it hard to understand how recursion is used in the
code.

Recursion happens any time a method calls itself, directly or indirectly.

If I look at the method WalkTree below that is using recursion. It much
more easy to understand the code that use WalkTree
then to understand the code GetEnumerator. Both is using recursion but I
can see directly that WalkTree is using recursion
but it's not possible to see that GetEnumerator is using recursion.

It's not only possible to see, it's easy:

public IEnumerator<T> GetEnumerator()
{
if (this.left != null)
{
foreach (T item in this.left)

The above statement is one site in which this GetEnumerator() method calls
itself.

{
yield return item;
}
}
yield return this.data;

if (this.right != null)
{
foreach (T item in this.right)

The above statement is another site in which this GetEnumerator() method
calls itself.

{
yield return item;
}
}
}

As you can see, GetEnumerator() calls itself two different places, hence
the recursion. It's trivial to see this in the debugger if you simply put
a break-point on the GetEnumerator() method: you'll see during the
enumeration where it's being called recursively.

From an analytical point of view, the thing you need to remember is that a
"foreach" statement includes an implicit call to the GetEnumerator()
method. That's how it gets the IEnumerable<T> it uses to do the
enumeration.

Note also that a method with the "yield" keyword in it is a special kind
of method called an "iterator". It's automatically packed into an
anonymous implementation of IEnumerable<T> that includes the necessary
MoveNext(), Current, etc. members to be use for that interface.

So in reality, the iterator method you've shown implements the iteration
in three parts: a loop iteration the left descendants, a single return of
the object itself, and a loop iteration of the right descendants. With
each call to the implicitly created MoveNext() method, the iterator code
progresses through those three sections of its own code exactly as
specified in the method by the "yield" statement.

For more details see:
http://msdn.microsoft.com/en-us/library/dscyy5s0.aspx
http://msdn.microsoft.com/en-us/library/ttw7t8t6.aspx

Pete

 

[Peter Duniho]

Hello!

Now I think I understand. So as you mentioned whatever I have after the
keyword "in" in a foreach clause that objects GetEnumerator is called.
In this case we have foreach (T item in this.left)
this.left is a Tree<T> so the GetEnumerator of the Tree<T> object is called.
which is this code. Does that sounds reasonable correct ?

Yes, that is basically exactly what's going on.