Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > recursive call returning a functor

Reply
Thread Tools

recursive call returning a functor

 
 
aaragon
Guest
Posts: n/a
 
      04-30-2008
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
 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      04-30-2008
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
 
Reply With Quote
 
 
 
 
aaragon
Guest
Posts: n/a
 
      04-30-2008
On Apr 30, 1:37 am, Kai-Uwe Bux <(E-Mail Removed)> wrote:
> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recursive functions Vs Non-recursive functions - performance aspect vamsi C Programming 21 03-09-2009 10:53 PM
Two recursive calls inside of a recursive function n00m C++ 12 03-13-2008 03:18 PM
Does recursive call able to print in same page as main call Yohan N. Leder Perl Misc 19 07-02-2006 11:45 AM
defined? for recursive function call v/s defined? for function call stack Alok Ruby 3 04-13-2006 11:53 AM
Scope resolution in needed to call a functor maker Howard Gardner C++ 0 02-05-2005 02:31 PM



Advertisments