Re: recursive call returning a functor

From:

aaragon <alejandro.aragon@gmail.com>

Newsgroups:

comp.lang.c++

Date:

Wed, 30 Apr 2008 09:32:10 -0700 (PDT)

Message-ID:

<fcb7822a-9504-4070-b17e-11b1276ef2ae@k13g2000hse.googlegroups.com>

On Apr 30, 1:37 am, Kai-Uwe Bux <jkherci...@gmx.net> 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