recursive call returning a functor

Discussion in 'C++' started by aaragon, Apr 30, 2008.

  1. aaragon

    aaragon Guest

    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
    aaragon, Apr 30, 2008
    #1
    1. Advertising

  2. aaragon

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Apr 30, 2008
    #2
    1. Advertising

  3. aaragon

    aaragon Guest

    On Apr 30, 1:37 am, Kai-Uwe Bux <> 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
    aaragon, Apr 30, 2008
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Howard Gardner
    Replies:
    0
    Views:
    361
    Howard Gardner
    Feb 5, 2005
  2. n00m
    Replies:
    12
    Views:
    1,111
  3. Alok
    Replies:
    3
    Views:
    246
  4. Yohan N. Leder
    Replies:
    19
    Views:
    238
    Yohan N. Leder
    Jul 2, 2006
  5. A
    Replies:
    4
    Views:
    112
Loading...

Share This Page