recursive GetEnumerator()

C

colin

Hi,
is it possible to have a recursive GetEnumerator for traversing a tree
structure ?

public IEnumerator<DType> GetEnumerator()

{

return GetEnumerator(root);

}

public IEnumerator<DType> GetEnumerator(node p)

{

if(p.low!=null)

GetEnumerator(p.low);

yield return p.val;

if(p.high!=null)

GetEnumerator(p.high);

}



compiles ok, but foreach only does 1 iteration.



Colin =^.^=
 
C

colin

colin said:
Hi,
is it possible to have a recursive GetEnumerator for traversing a tree
structure ?

public IEnumerator<DType> GetEnumerator()

{

return GetEnumerator(root);

}

public IEnumerator<DType> GetEnumerator(node p)

{

if(p.low!=null)

GetEnumerator(p.low);

yield return p.val;

if(p.high!=null)

GetEnumerator(p.high);

}



compiles ok, but foreach only does 1 iteration.



Colin =^.^=

ah not to worry, i did the recursion by using recursive foreach instead of
the function call.

Colin =^.^=
 
?

=?ISO-8859-1?Q?G=F6ran_Andersson?=

colin said:
Hi,
is it possible to have a recursive GetEnumerator for traversing a tree
structure ?

public IEnumerator<DType> GetEnumerator()

{

return GetEnumerator(root);

}

public IEnumerator<DType> GetEnumerator(node p)

{

if(p.low!=null)

GetEnumerator(p.low);

The GetEnumerator method returns an enumerator. If you just throw away
the return value, there is hardly any reason to make the call, is there.
yield return p.val;

Why is the code continuing after return? Did you ignore the compiler
warning about unreachable code?
if(p.high!=null)

GetEnumerator(p.high);

Once again, mind the return value.
}



compiles ok, but foreach only does 1 iteration.

You mean that it compiles, but with warnings...
 
C

colin

Göran Andersson said:
The GetEnumerator method returns an enumerator. If you just throw away the
return value, there is hardly any reason to make the call, is there.

I dont think in this case it actually returns anything, at least not thats
used.
if I try and return an IEnumerator it complains.
Why is the code continuing after return? Did you ignore the compiler
warning about unreachable code?

thats the nature of yield I beleive, however this is the first time ive used
it,
so im a bit unsure, but it seems it just yields control, doesnt actually
realy return.
ie when it comes accros a 'yield return expresion' it executs
the code inside the foreach loop with the value in expresion
when that code has executed, it continues after the 'yield return expresion'
statement
Once again, mind the return value.

its recursive so the value isnt used from the return as such, but from the
yield statement.
You mean that it compiles, but with warnings...

dont think there were any warnings at all,
however ive since used foreach instead of calling another GetEnumerator
and it works ok...

so getenumerator does foreach wich calls getenumerator and does foreach
recursivly for all the trees nodes.

Colin =^.^=
 
Y

Yuriy Solodkyy

Hi,

I had to implement in in C# 3.0. There is nothing very C# 3.0 special there,
so you can easily translate it back to C# 2.0.

public static IEnumerable<T> TraverseTree<T>(this IEnumerable<T> self,
Func<T, IEnumerable<T>> getChildren)
{
var parents = new Stack<IEnumerator<T>>();
var enumerator = self.GetEnumerator();
parents.Push(enumerator);
do
{
enumerator = parents.Pop();
while (enumerator.MoveNext())
{
var current = enumerator.Current;

yield return current;

parents.Push(enumerator);
enumerator = getChildren(current).GetEnumerator();
}
}
while (parents.Count > 0);
}

If you know your types you may replace getChildren with your actual method
that returns enumerator of node children.

-yuriy
http://couldbedone.blogspot.com
 
C

colin

Yuriy Solodkyy said:
Hi,

I had to implement in in C# 3.0. There is nothing very C# 3.0 special
there, so you can easily translate it back to C# 2.0.

public static IEnumerable<T> TraverseTree<T>(this IEnumerable<T>
self, Func<T, IEnumerable<T>> getChildren)
{
var parents = new Stack<IEnumerator<T>>();
var enumerator = self.GetEnumerator();
parents.Push(enumerator);
do
{
enumerator = parents.Pop();
while (enumerator.MoveNext())
{
var current = enumerator.Current; yield return current;

parents.Push(enumerator);
enumerator = getChildren(current).GetEnumerator();
}
}
while (parents.Count > 0);
}

If you know your types you may replace getChildren with your actual method
that returns enumerator of node children.

I was hoping to do it recursivly rather than remember all the parent nodes
for each entry.
I think its a bit simpler and could be faster,
however ive no idea how this looks in actual implementaion.

I made the nodes themselves enumerable thus :-

public IEnumerator<DType> GetEnumerator()
{
if (low != null)
foreach (DType x in low)
yield return x;
yield return val;
if (high != null)
foreach (DType x in high)
yield return x;
}

sp the main class GetEnumerator just calls foreach on the root node.

I confess to not fully understanding what im doing however,
I picked up a bit from examples, although the recursive took a while to
figure out.
ive ignored the MoveNext and Current as it doesnt fit with doing it
recursivly.
im not sure if Il need it anyway, but it seems to work ok.

I got realy confused with the difference between interfaces and
generic/non-generic bases etc.

Colin =^.^=
 
?

=?ISO-8859-1?Q?G=F6ran_Andersson?=

colin said:
I dont think in this case it actually returns anything, at least not thats
used.
if I try and return an IEnumerator it complains.

Yes, it does return an enumerator. (Or, at least, it works as if it
returns an enumerator. I don't know exactly how it's implemented.)
thats the nature of yield I beleive,

Yes, you are right. The code continues at that point for the next step
in the enumeration.
 
C

colin

Göran Andersson said:
Yes, it does return an enumerator. (Or, at least, it works as if it
returns an enumerator. I don't know exactly how it's implemented.)

it seems to actually return the data not the enumerator,
well it complains if you do,
I gues IEnumerator is just a sort of keyword to say its not a normal
function.

im not sure what happens if you actually return data without yield,
wether it gets called for each element, I gues thats what the Next and
Current would be for.

Colin =^.^=
 
J

Jon Skeet [C# MVP]

it seems to actually return the data not the enumerator,
well it complains if you do,
I gues IEnumerator is just a sort of keyword to say its not a normal
function.

No, not at all. GetEnumerator returns an enumerator. That enumerator
is then used to fetch an IEnumerable, which has the MoveNext and
Current members.

foreach does all this for you under the hood.
im not sure what happens if you actually return data without yield,
wether it gets called for each element, I gues thats what the Next and
Current would be for.

yield return is just smart syntactic sugar which builds an IEnumerator/
IEnumerable.
You can use ildasm or reflector to see what types are in your compiled
code.

It's worth understanding what foreach does before you embark on C# 2's
iterator-building features.

Jon
 
C

colin

Jon Skeet said:
No, not at all. GetEnumerator returns an enumerator. That enumerator
is then used to fetch an IEnumerable, which has the MoveNext and
Current members.

foreach does all this for you under the hood.


yield return is just smart syntactic sugar which builds an IEnumerator/
IEnumerable.
You can use ildasm or reflector to see what types are in your compiled
code.

It's worth understanding what foreach does before you embark on C# 2's
iterator-building features.

thanks,

well im only using foreach on this tree to check the rest of it is working,
so I dont intend to make it too elaborate,
like i said before, the current and move next arnt very usefull in a tree,
unless the parent nodes are stored as well wich is messy.
with recursive calls they are stored but on the call stack.

I dont think I will be needing to use the iterator outside a foreach loop,
so I think im safe.

I think its realy quite neat you can use foreach to iterate a list like
this,
before in c++ I had to pass a function and all other data it needed to an
iterator,
and wich made it a bit more limited.
the complexity of the many different types that have to do with collections
however has overflowed my brain for now,
im not even sure if I realy need to inherit any of them,
the complexities of extracting nodes in a tree
and balancing it is enough to cope with for 1 day.

Colin =^.^=
 
J

Jon Skeet [C# MVP]

well im only using foreach on this tree to check the rest of it is working,
so I dont intend to make it too elaborate,
like i said before, the current and move next arnt very usefull in a tree,
unless the parent nodes are stored as well wich is messy.
with recursive calls they are stored but on the call stack.

Current and MoveNext() are the way that iterators work though - that's
the *only* way they work. There's no way of getting data out of a
I dont think I will be needing to use the iterator outside a foreach loop,
so I think im safe.

It's not a case of being safe or not - you're already using MoveNext()
and Current, and the enumerator that your code returns is implementing
MoveNext() and Current appropriately.

Jon
 
C

colin

Jon Skeet said:
Current and MoveNext() are the way that iterators work though - that's
the *only* way they work. There's no way of getting data out of a


It's not a case of being safe or not - you're already using MoveNext()
and Current, and the enumerator that your code returns is implementing
MoveNext() and Current appropriately.

wel I dont understand entirly then, as I have no implmentation of current
and next,
and the foreach does work without them. Ive even removed the inherited
collection classes.
im not sure there can be default implementations of them as the next node is
not easily known from the current node.

maybe using yield for all the iterations means it al gets done ok.

I could reduce the code to the essentials to show if you like.

Colin =^.^=
 
J

Jon Skeet [C# MVP]

wel I dont understand entirly then, as I have no implmentation of current
and next,

Yes you do. The compiler has created them for you.
and the foreach does work without them.

No, the foreach statement *cannot* work without MoveNext() and
Current.
Ive even removed the inherited collection classes.

Irrelevant - if you use "yield return" style code, the compiler will
generate a lot of stuff for you.
im not sure there can be default implementations of them as the next node is
not easily known from the current node.

maybe using yield for all the iterations means it al gets done ok.

I could reduce the code to the essentials to show if you like.

No, I understand the code - but I don't think you understand what the
compiler is doing for you. I *strongly* recommend that you run ildasm
or Reflector on your code to see what's being generated.

See http://www.yoda.arachsys.com/csharp/csharp2/iterators.html for
some more information on this, by the way.

Jon
 
C

colin

Jon Skeet said:
Yes you do. The compiler has created them for you.


No, the foreach statement *cannot* work without MoveNext() and
Current.


Irrelevant - if you use "yield return" style code, the compiler will
generate a lot of stuff for you.


No, I understand the code - but I don't think you understand what the
compiler is doing for you. I *strongly* recommend that you run ildasm
or Reflector on your code to see what's being generated.

See http://www.yoda.arachsys.com/csharp/csharp2/iterators.html for
some more information on this, by the way.

Jon

thanks Jon, thats quite a usefully concise info about what ive been doing,
I think I at least understand fairly well whats going on at the code level
now.
the 'yield return expresion' does make for a bit of confusion over flow of
control at first.

I think I understand that movenext is like moving to the next statemnt in
the GetEnumerator function if yield is used, and current would be like
storing the state information of the functions stack.
although I had assumed it just put the code inline or something,
and put the code inside the foreach block at each yeild statement.

Ive not tried using reflection or looking at the code directly,
im not sure I want to atm lol, I might not understand or like what I see.

maybe its not as fast as I would like if its actually storing the stack
info,
but then this isnt a method that will be used intensivly to access the list.
my original implementation was written partly in assembler many years ago
when CPU power wasnt so plentifull.
before that I also had a microcode version for a bit slice processor,
before content addressable ram made it obsolete.

heres the minimum code wich just builds up the list and dumps it to the
console.
its hardly finished, rebalancing wil be done when excessive time spent in
searching is detected.

:-------

using System.Collections.Generic;

namespace WindowsApplication1
{
public class stree<DType>
{
public class node
{
public node(DType x)
{
val=x;
}
public IEnumerator<DType> GetEnumerator() // recursive
iterator.
{
if (low != null)
foreach (DType x in low)
yield return x;
yield return val;
if (high != null)
foreach (DType x in high)
yield return x;
}
public DType val;
public node high,low;
}
public System.Collections.Comparer compare =
System.Collections.Comparer.DefaultInvariant;
public node root;
public void Add(DType x)
{
Add(ref root, x);
}
public bool Add(ref node p,DType x)
{
if (p == null)
{
p = new node(x);
return true;
}
int r = compare.Compare(x, p.val);
if (r > 0)
return Add(ref p.high, x);
if(r<0)
return Add(ref p.low, x);
return false;
}
public IEnumerator<DType> GetEnumerator()
{
if(root!=null)
foreach (DType x in root)
yield return x;
}
}
}


main()
{
stree<double> tree = new stree<double>();
tree.Add(4.1);
tree.Add(4.3);
tree.Add(4.9);
tree.Add(2.1);
foreach (double y in tree)
System.Console.WriteLine(y);
}


Colin =^.^=
 
J

Jon Skeet [C# MVP]

colin said:
thanks Jon, thats quite a usefully concise info about what ive been doing,
I think I at least understand fairly well whats going on at the code level
now.
the 'yield return expresion' does make for a bit of confusion over flow of
control at first.

Yes. It's a lot easier than implementing IEnumerator/IEnumerable
yourself though :)
I think I understand that movenext is like moving to the next statemnt in
the GetEnumerator function if yield is used, and current would be like
storing the state information of the functions stack.

Not quite. The context information is stored within a newly generated
type, but Current has to return the current element within the
enumerated data.
although I had assumed it just put the code inline or something,
and put the code inside the foreach block at each yeild statement.

No, it couldn't do that - don't forget that foreach could be in one
type, and the iterator in a completely different one.
Ive not tried using reflection or looking at the code directly,
im not sure I want to atm lol, I might not understand or like what I see.

There's a big difference between Reflector and reflection... if you
haven't used Reflector before, it's well worth downloading (just Google
for it).
maybe its not as fast as I would like if its actually storing the stack
info,
but then this isnt a method that will be used intensivly to access the list.
my original implementation was written partly in assembler many years ago
when CPU power wasnt so plentifull.
before that I also had a microcode version for a bit slice processor,
before content addressable ram made it obsolete.

Indeed - I wouldn't worry about speed until you've definitely got a
problem. It's not likely to be particularly slow, although using it
recursively can be a bit more of a hit than might be ideal:

http://blogs.msdn.com/toub/archive/2004/10/29/249858.aspx
 
C

colin

Jon Skeet said:
No, it couldn't do that - don't forget that foreach could be in one
type, and the iterator in a completely different one.

The way I implemented it before in c was to pass a function to the iterator,
it might of been simpler to use if the iterator was like a macro.
I had hoped it would expand the iterator in the code where the foreach
was used, but obviously this isnt so... too much to hope for ;)
I gues if the type isnt completly fixed at compile time this isnt possible
anyway.
There's a big difference between Reflector and reflection... if you
haven't used Reflector before, it's well worth downloading (just Google
for it).

thanks, Il have a look sometime, I think the important thing is that the
binary searching is fast and I havnt heard anything yet to think otherwise.

Ive not realy had any problems where I realy needed to see what was going on
underneath the code.
although I had to do a bit of work to get memory usage down to <2gb.
Indeed - I wouldn't worry about speed until you've definitely got a
problem. It's not likely to be particularly slow, although using it
recursively can be a bit more of a hit than might be ideal:

http://blogs.msdn.com/toub/archive/2004/10/29/249858.aspx

thanks thats quite interesting read, ofc a tree is very good for searches,
and isnt so likely to be used like this often,
but it might be worth considering dumping it to an array,
wich could be quite quick and easy,
and iterating that, this might be quicker if the whole list was iterated.
in fact this might lead to an easy way of balancing the tree.

Colin =^.^=
 
J

Jon Skeet [C# MVP]

The way I implemented it before in c was to pass a function to the iterator,
it might of been simpler to use if the iterator was like a macro.
I had hoped it would expand the iterator in the code where the foreach
was used, but obviously this isnt so... too much to hope for ;)
I gues if the type isnt completly fixed at compile time this isnt possible
anyway.

That couldn't work anyway, as the type using "foreach" often won't
have access to all the members used within the iterator block.
thanks, Il have a look sometime, I think the important thing is that the
binary searching is fast and I havnt heard anything yet to think otherwise.

Ive not realy had any problems where I realy needed to see what was going on
underneath the code.
although I had to do a bit of work to get memory usage down to <2gb.

I think it's useful to see what's going on under the hood to get
*some* idea of the state machine that the compiler builds for you -
you don't need a detailed understanding of it though.
thanks thats quite interesting read, ofc a tree is very good for searches,
and isnt so likely to be used like this often,
but it might be worth considering dumping it to an array,
wich could be quite quick and easy,
and iterating that, this might be quicker if the whole list was iterated.
in fact this might lead to an easy way of balancing the tree.

I think I'll have to let you ponder on that :)

Jon
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top