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

Well, my first attempt to turn some recursive algorithm into this data
access model is harder that i thought. I took this one: "Convert
Sorted List to Balanced Binary Search Tree (BST)" (http://leetcode.com/
2010/11/convert-sorted-list-to-balanced-binary.html). And tried first
to transmogrify it into this model, before actually changing the code
and making use of access to ancestor data. However what happened, the
compilation didn't stop. Because i turned the recursive function call
execution into some recursive template compilation. I didn't yet
manage to break this template recursion. Can someone please help be
for that? It's in SortedList_Impl2::exec_impl().

Here's the code:
============= 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(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 A, typename B, typename C, typename D>
struct IfEqual
{
    typedef D type;
};

template <typename A, typename C, typename D>
struct IfEqual<A, A, C, D>
{
    typedef C type;
};

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

    // avoid template recursion for function call recursion
    typedef typename IfEqual<
        // 2nd level ancestor?
        typename CALLER::caller_type,
        // is NOP? - TODO: should not depend on that!
        Nop,
        // derive one level more
        Func<SortedList_Impl2<type>, ListNode *&, int, int>,
        // don't create another level, use current
        Func<SortedList_Impl2<CALLER>, ListNode *&, int, int>>
        ::type recursion_type;

    BinaryTree* exec_impl(
        ListNode *& list,
        int start,
        int end)
    {
        // this does not compile(?!)
        // recursion_type recursion;

        // this compiles but endlessly
        Func<SortedList_Impl2<type>, ListNode *&, int, int>
recursion;

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

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

     BinaryTree* exec_impl(
             ListNode * head,
             int n)
     {
         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! ]