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.

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

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.

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

On 2018-06-14 11:46:04 +0000, 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

On 6/14/18 8:35 AM, Robert M. Münch wrote:
> On 2018-06-14 11:46:04 +0000, 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 &this + 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

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.

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"