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! ]