Re: foreach DFS/BFS for tree data-structure?

[Timoses via Digitalmars-d-learn]

On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. Münch wrote:

I have a simple tree C data-structure that looks like this:

node {
node parent:
vector[node] children;
}

I would like to create two foreach algorthims, one follwing the 
breadth first search pattern and one the depth first search 
pattern.


Is this possible? I read about Inputranges, took a look at the 
RBTree code etc. but don't relly know/understand where to start.


What I found really interesting when reading Ali Çehreli's book 
'Programming in D' was using fibers for tree iteration.


Check out http://ddili.org/ders/d.en/fibers.html and skip to the 
section "Fibers in range implementations"

Re: foreach DFS/BFS for tree data-structure?

[Meta via Digitalmars-d-learn]

On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. Münch wrote:

I have a simple tree C data-structure that looks like this:

node {
node parent:
vector[node] children;
}

I would like to create two foreach algorthims, one follwing the 
breadth first search pattern and one the depth first search 
pattern.


Is this possible? I read about Inputranges, took a look at the 
RBTree code etc. but don't relly know/understand where to start.


While it's possible to do with input ranges, it's not pretty and 
I'm not sure that it's as performant as the traditional method. I 
would recommend going with one of the other suggestions in this 
thread.

Re: foreach DFS/BFS for tree data-structure?

[Steven Schveighoffer via Digitalmars-d-learn]

On 6/14/18 8:35 AM, Robert M. Münch wrote:

On 2018-06-14 11:46:04 +, Dennis said:


On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. Münch wrote:
Is this possible? I read about Inputranges, took a look at the RBTree 
code etc. but don't relly know/understand where to start.


You can also use opApply to iterate over a tree using foreach, see:
https://tour.dlang.org/tour/en/gems/opdispatch-opapply


Ah... that looks very good. Need to dig a bit deeper on how to use it. 
Thanks.




Just to clarify, RBTree can easily do DFS without a real stack because 
there are a finite number of children (2) for each node, and it's an 
O(1) operation to figure out which child the current node is in relation 
to the parent (am I a left child or right child?).


Now, with your C version, if your children are stored in the array 
itself, figuring out the "next" child is a matter of doing  + 1. 
But if you are storing pointers instead, then figuring out the next 
child would be an O(n) operation.


Using the stack to track where you are (via opApply) is a valid way as 
well. You could also unroll that into a malloc'd stack, but the code is 
not as pretty of course.


-Steve

Re: foreach DFS/BFS for tree data-structure?

[Robert M. Münch via Digitalmars-d-learn]

On 2018-06-14 11:46:04 +, Dennis said:


On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. Münch wrote:
Is this possible? I read about Inputranges, took a look at the RBTree 
code etc. but don't relly know/understand where to start.


You can also use opApply to iterate over a tree using foreach, see:
https://tour.dlang.org/tour/en/gems/opdispatch-opapply


Ah... that looks very good. Need to dig a bit deeper on how to use it. Thanks.

--
Robert M. Münch
http://www.saphirion.com
smarter | better | faster

Re: foreach DFS/BFS for tree data-structure?

[Dennis via Digitalmars-d-learn]

On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. Münch wrote:
Is this possible? I read about Inputranges, took a look at the 
RBTree code etc. but don't relly know/understand where to start.


You can also use opApply to iterate over a tree using foreach, 
see:

https://tour.dlang.org/tour/en/gems/opdispatch-opapply

Re: foreach DFS/BFS for tree data-structure?

[rikki cattermole via Digitalmars-d-learn]

On 14/06/2018 11:31 PM, Robert M. Münch wrote:

I have a simple tree C data-structure that looks like this:

node {


struct Node {


 node parent:


Node* parent;


 vector[node] children;


Node[] children;


}

I would like to create two foreach algorthims, one follwing the breadth 
first search pattern and one the depth first search pattern.


Here is (very roughly breadth):

auto search(Method method) {
struct Voldermort {
Node parent;
size_t offset;

@property {
Node front() {
return parent.children[offset];
}

bool empty() {
return offset == parent.children.length;
}
}

void popFront() {
offset++;
}
}

return Voldermort(this);
}

Depth will be a bit of a pain since you'll need to know where you have 
been at each set of children.