recursive call returning a functor

[aaragon]

Hi guys,

Is there a way to return a functor from a recursive call that takes
different paths? Let's say that I have a tree structure like:

root
|
first child ---- nextSibling ----nextSibling ----nextSibling
---->0
| |
| |
0 |
0 0
firstChild -0
|
0

Now, I would like to create a function that executes a functor on leaf
objects. Is this possible???
In code, let's say we have a tree class:

template <class Object>
class Tree {

struct TreeNode {

TreeNode() : obj_(), firstChild_(NULL), nextSibling_(NULL),
parent_(NULL), depth_() {}

TreeNode(Object obj) : obj_(obj), firstChild_(NULL),
nextSibling_(NULL), parent_(NULL), depth_() {}

Object obj_;
size_t depth_;
TreeNode* firstChild_;
TreeNode* nextSibling_;
TreeNode* parent_;
};

TreeNode* root_; //!< The root of the tree
TreeNode* current_; //!< Helper pointer for searches
size_t size_; //!< Number of nodes in the tree
size_t height_; //!< Tree height

public:

typedef Object ValueType;
typedef Object& ReferenceType;
typedef Object* IteratorType;

//! Default constructor
Tree() : size_() { root_ = current_ = NULL; }

// more constructors, assignment operator and destructor...
// functions to return size and height...

template <class Functor>
Functor LeafExecute(Functor fn) {
//set current to root to start execution
current_ = root_;
//uses the private function FindObject
return LeafExecute(current_, fn);
}

private:

template <class Functor>
Functor LeafExecute(TreeNode* ptr, Functor fn) {

//recursively executes the rest of the tree
if (ptr->nextSibling_ != NULL)
LeafExecute(ptr->nextSibling_,fn);
if(ptr->firstChild_ != NULL)
LeafExecute(ptr->firstChild_,fn);
else if (ptr->firstChild_ == NULL) {
// execute functor
cout<<"executing functor at depth "<<ptr->depth_<<endl;
fn(ptr->obj_);
return fn;
}
}
};
I'm following the same behavior as the for_each algorithm in the
standard library:

template<typename _InputIterator, typename _Function>
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function
__f)
{
// concept requirements

__glibcxx_function_requires(_InputIteratorConcept< _InputIterator>)
__glibcxx_requires_valid_range(__first, __last);
for (; __first != __last; ++__first)
__f(*__first);
return __f;
}

except that it doesn't work as I expected and I don't know why. Maybe
because I'm calling the recursion on the siblings? Note that the
functor is passed by value to the function and returned by value (of
course)
I appreciate any feedback.

aa

[Kai-Uwe Bux]

aaragon wrote:

Hi guys,

Is there a way to return a functor from a recursive call that takes
different paths? Let's say that I have a tree structure like:

root
|
first child ---- nextSibling ----nextSibling ----nextSibling
---->0
| |
| |
0 |
0 0
firstChild -0
|
0

Now, I would like to create a function that executes a functor on leaf
objects. Is this possible???
In code, let's say we have a tree class:

template <class Object>
class Tree {

struct TreeNode {

TreeNode() : obj_(), firstChild_(NULL), nextSibling_(NULL),
parent_(NULL), depth_() {}

TreeNode(Object obj) : obj_(obj), firstChild_(NULL),
nextSibling_(NULL), parent_(NULL), depth_() {}

Object obj_;
size_t depth_;
TreeNode* firstChild_;
TreeNode* nextSibling_;
TreeNode* parent_;
};

TreeNode* root_; //!< The root of the tree
TreeNode* current_; //!< Helper pointer for searches
size_t size_; //!< Number of nodes in the tree
size_t height_; //!< Tree height

public:

typedef Object ValueType;
typedef Object& ReferenceType;
typedef Object* IteratorType;

//! Default constructor
Tree() : size_() { root_ = current_ = NULL; }

// more constructors, assignment operator and destructor...
// functions to return size and height...

template <class Functor>
Functor LeafExecute(Functor fn) {
//set current to root to start execution
current_ = root_;
//uses the private function FindObject
return LeafExecute(current_, fn);
}

private:

template <class Functor>
Functor LeafExecute(TreeNode* ptr, Functor fn) {

//recursively executes the rest of the tree
if (ptr->nextSibling_ != NULL)
LeafExecute(ptr->nextSibling_,fn);
if(ptr->firstChild_ != NULL)
LeafExecute(ptr->firstChild_,fn);
else if (ptr->firstChild_ == NULL) {
// execute functor
cout<<"executing functor at depth "<<ptr->depth_<<endl;
fn(ptr->obj_);
return fn;
}
}
};
I'm following the same behavior as the for_each algorithm in the
standard library:

template<typename _InputIterator, typename _Function>
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function
__f)
{
// concept requirements

__glibcxx_function_requires(_InputIteratorConcept< _InputIterator>)
__glibcxx_requires_valid_range(__first, __last);
for (; __first != __last; ++__first)
__f(*__first);
return __f;
}

except that it doesn't work as I expected and I don't know why.

What do you expect and where does it differ?

The only difference I is that you create copies of the functor object during
the execution and that many of the changes will be lost. E.g., when you
call

LeafExecute(ptr->nextSibling_,fn);

the current functor is passed by value, and any modification to its state
will be lost. As a consequence, if you try to count the number of leaves
using a stateful functor, you will miscount.

You could either replace those lines by

fn = LeafExecute( ptr->nextSibling_, fn );

or pass the functor by reference internally, e.g.:

template <class Functor>
Functor LeafExecute(Functor fn) {
assert( root_ != NULL );
LeafExecute(root_, fn);
return( fn );
}

private:

template <class Functor>
void LeafExecute(TreeNode* ptr, Functor & fn) {

//recursively executes the rest of the tree
if (ptr->nextSibling_ != NULL) {
LeafExecute(ptr->nextSibling_,fn);
}
if(ptr->firstChild_ != NULL) {
LeafExecute(ptr->firstChild_,fn);
} else {
// leaf: execute functor
fn(ptr->obj_);
}
}

Maybe
because I'm calling the recursion on the siblings? Note that the
functor is passed by value to the function and returned by value (of
course)
I appreciate any feedback.

aa

Best

Kai-Uwe Bux

[aaragon]

On Apr 30, 1:37 am, Kai-Uwe Bux <[e-mail]:

aaragon wrote:

Hi guys,

Is there a way to return a functor from a recursive call that takes
different paths? Let's say that I have a tree structure like:

root
|
first child ---- nextSibling ----nextSibling ----nextSibling
---->0
| |
| |
0 |
0 0
firstChild -0
|
0

Now, I would like to create a function that executes a functor on leaf
objects. Is this possible???
In code, let's say we have a tree class:

template <class Object>
class Tree {

struct TreeNode {

TreeNode() : obj_(), firstChild_(NULL), nextSibling_(NULL),
parent_(NULL), depth_() {}

TreeNode(Object obj) : obj_(obj), firstChild_(NULL),
nextSibling_(NULL), parent_(NULL), depth_() {}

Object obj_;
size_t depth_;
TreeNode* firstChild_;
TreeNode* nextSibling_;
TreeNode* parent_;
};

TreeNode* root_; //!< The root of the tree
TreeNode* current_; //!< Helper pointer for searches
size_t size_; //!< Number of nodes in the tree
size_t height_; //!< Tree height

public:

typedef Object ValueType;
typedef Object& ReferenceType;
typedef Object* IteratorType;

//! Default constructor
Tree() : size_() { root_ = current_ = NULL; }

// more constructors, assignment operator and destructor...
// functions to return size and height...

template <class Functor>
Functor LeafExecute(Functor fn) {
//set current to root to start execution
current_ = root_;
//uses the private function FindObject
return LeafExecute(current_, fn);
}

private:

template <class Functor>
Functor LeafExecute(TreeNode* ptr, Functor fn) {

//recursively executes the rest of the tree
if (ptr->nextSibling_ != NULL)
LeafExecute(ptr->nextSibling_,fn);
if(ptr->firstChild_ != NULL)
LeafExecute(ptr->firstChild_,fn);
else if (ptr->firstChild_ == NULL) {
// execute functor
cout<<"executing functor at depth "<<ptr->depth_<<endl;
fn(ptr->obj_);
return fn;
}
}
};

I'm following the same behavior as the for_each algorithm in the
standard library:

template<typename _InputIterator, typename _Function>
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function
__f)
{
// concept requirements

__glibcxx_function_requires(_InputIteratorConcept< _InputIterator>)
__glibcxx_requires_valid_range(__first, __last);
for (; __first != __last; ++__first)
__f(*__first);
return __f;
}

except that it doesn't work as I expected and I don't know why.

What do you expect and where does it differ?

The only difference I is that you create copies of the functor object during
the execution and that many of the changes will be lost. E.g., when you
call

LeafExecute(ptr->nextSibling_,fn);

the current functor is passed by value, and any modification to its state
will be lost. As a consequence, if you try to count the number of leaves
using a stateful functor, you will miscount.

You could either replace those lines by

fn = LeafExecute( ptr->nextSibling_, fn );

or pass the functor by reference internally, e.g.:

template <class Functor>
Functor LeafExecute(Functor fn) {
assert( root_ != NULL );
LeafExecute(root_, fn);
return( fn );
}

private:

template <class Functor>
void LeafExecute(TreeNode* ptr, Functor & fn) {

//recursively executes the rest of the tree
if (ptr->nextSibling_ != NULL) {
LeafExecute(ptr->nextSibling_,fn);
}
if(ptr->firstChild_ != NULL) {
LeafExecute(ptr->firstChild_,fn);
} else {
// leaf: execute functor
fn(ptr->obj_);
}
}

Maybe
because I'm calling the recursion on the siblings? Note that the
functor is passed by value to the function and returned by value (of
course)
I appreciate any feedback.

aa

Best

Kai-Uwe Bux

Thanks for replying to my post. I tried the first approach and it
didn't work, so I ended up passing internally by reference as you
suggested. That solved the problem. The final code for the function
looks like this:

template <class Functor>
Functor LeafExecute(Functor fn) {
assert(root_ != NULL);
//set current to root to start execution
current_ = root_;
//uses the private function FindObject
LeafExecute(current_, fn);
return fn;
}

template <class Functor>
Functor& LeafExecute(TreeNode* ptr, Functor& fn) {

//recursively executes the rest of the tree
if (ptr->nextSibling_ != NULL)
LeafExecute(ptr->nextSibling_,fn);
if(ptr->firstChild_ != NULL)
LeafExecute(ptr->firstChild_,fn);
else if (ptr->firstChild_ == NULL) {
// execute functor
cout<<"executing functor at depth "<<ptr->depth_<<endl;
fn(ptr->obj_);
return fn;
}
}

where this time I return by reference in the private function.
Once again, thanks!

aa