On Apr 30, 1:37 am, KaiUwe Bux <(EMail 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
>
> KaiUwe 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
