Re: Access Data Items In Ancestor Stack Frames Safely (Dr.Dobb's article)

This version now starts to actually use ancestor stack data - still
options for improvement though. A bit hard to find the balance between
what to delegate to constructor, what to use still as function all
argument. Next try to merge again SortedList_Impl1 with
SortedList_Impl2.

========== StackAccess.h ========================

#ifndef STACKACCESS_H_
#define STACKACCESS_H_

#include <functional> // std::mem_fn

struct Nop
{

};

template <typename CALLER>
struct Func_Impl
{
      typedef CALLER caller_type;

      caller_type * caller;

};

template <typename IMPL, typename... ARGS>
struct FuncCore : virtual Func_Impl<typename IMPL::caller_type>
{
      typedef typename
      decltype(std::mem_fn(&IMPL::exec_impl))::result_type return_type;

      virtual return_type exec_wrap(ARGS...) = 0;

      virtual ~FuncCore() { }

      return_type exec(
              typename IMPL::caller_type * caller,
              ARGS... args)
      {
          Func_Impl<typename IMPL::caller_type>::caller = caller;
          return exec_wrap(args...);
      }

};

template <typename IMPL, typename... ARGS>
struct Func : public IMPL,
                 public FuncCore<IMPL, ARGS...>
{
      typedef typename FuncCore<IMPL>::return_type
          return_type;

      inline return_type exec_wrap(
              ARGS... args)
      {
          return this->exec_impl(args...);
      }

};
#endif /* STACKACCESS_H_ */

========== main.cpp =============================

#include <iostream>

#include "StackAccess.h"

struct ListNode
{
    int data;
    ListNode * next;

    ListNode(int data)
    : data(data),
      next(NULL)
    { }
};

struct BinaryTree
{
    int data;
    BinaryTree * left;
    BinaryTree * right;

    BinaryTree()
    : data(),
      left(NULL),
      right(NULL)
    { };

    BinaryTree(int data)
    : data(data),
      left(NULL),
      right(NULL)
    { }

    void print()
    {
        bool child(false);
        std::cout << data;
        if (NULL == left && NULL == right)
        {
            return;
        }
        std::cout << "{";
        if (NULL != left)
        {
            left->print();
            child = true;
        }
        if (NULL != right)
        {
            if (child)
            {
                std::cout << ",";
            }
            right->print();

        }
        std::cout << "}";
    }
};

BinaryTree* sortedListToBST(
        ListNode *& list,
        int start,
        int end)
{
   if (start > end) return NULL;
   // same as (start+end)/2, avoids overflow
   int mid = start + (end - start) / 2;
   BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
   BinaryTree *parent = new BinaryTree(list->data);
   parent->left = leftChild;
   list = list->next;
   parent->right = sortedListToBST(list, mid+1, end);
   return parent;
}

BinaryTree* sortedListToBST(
        ListNode *head,
        int n)
{
   return sortedListToBST(head, 0, n-1);
}

template <typename CALLER>
struct SortedList_Impl2 : virtual Func_Impl<CALLER>
{
    typedef SortedList_Impl2 type;

    int start;
    int end;
    int mid;
    BinaryTree *new_node;

    SortedList_Impl2()
    : new_node(new BinaryTree())
    { };

    SortedList_Impl2(
        int p_start,
        int p_end)
    : start(p_start),
      end(p_end),
      mid(start + (end - start) / 2),
      new_node((start > end)?NULL:new BinaryTree())
    { };

    void exec_left(
        type * caller,
        ListNode *& current_element)
    {
        if (NULL == new_node) return;

        type(start, mid-1).exec_left(this, current_element);

        new_node->data = current_element->data;
        current_element = current_element->next;

        caller->new_node->left = new_node;

        type(mid+1, end).exec_right(this, current_element);
    };

    void exec_right(
        type * caller,
        ListNode *& current_element)
    {
        if (NULL == new_node) return;

        type(start, mid-1).exec_left(this, current_element);

        new_node->data = current_element->data;
        current_element = current_element->next;

        caller->new_node->right = new_node;

        type(mid+1, end).exec_right(this, current_element);
    }

    BinaryTree* exec_impl(
            ListNode *& current_element,
            int p_start,
            int p_end)
    {
        start = p_start;
        end = p_end;
        mid = start + (end - start) / 2;

        type(start, mid-1).exec_left(this, current_element);

        new_node->data = current_element->data;
        current_element = current_element->next;

        type(mid+1, end).exec_right(this, current_element);

        return new_node;
    }
};

template <typename CALLER>
struct SortedList_Impl1 : virtual Func_Impl<CALLER>
{
      typedef SortedList_Impl1 type;

      BinaryTree* exec_impl(
             ListNode * head,
             int n)
      {
         // TODO: would like to pass 0, n-1 as arguments for constructor
         // not for the exec(...)
         // but it means we need a generic way to code the
SortedList_Impl2
         // specific constructor into Func(?!)
         return Func<SortedList_Impl2<type>, ListNode *&, int, int>().
          exec(this, head, 0, n-1);
      }
};
int
main(int, char**)
{
    const int no = 30;
    ListNode *root = NULL;
    ListNode *inserter = NULL;

    for (int i = 0; i < no; ++i)
    {
        ListNode *elem = new ListNode(i);
        if (NULL == inserter)
        {
            root = elem;
        }
        else
        {
            inserter->next = elem;
        }
        inserter = elem;
    }

    {
        BinaryTree *tree = sortedListToBST(root, no);
        tree->print();
        std::cout << std::endl;
    }

    {
        Nop nop;
        BinaryTree * tree = Func<SortedList_Impl1<Nop>, ListNode*, int>().
            exec(&nop, root, no);
        tree->print();
        std::cout << std::endl;
    }

    return 0;
}

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]