To practice, one of the topics I'm familiarizing myself with again is trees. The thing about depth-first search and breadth-first search is that they differ only in the choice of the data structure that backs the algorithm.
I thought I could write a common tree search that I would feed either a stack (DFS) or a queue (BFS) using templates. stack and queue are nice enough that their adding and removing members have the same name. Unfortunately, the access function is once called top and front for the other. Because of this I did no quite arrive where I wanted. I didn't manage to do it without that lambda:
template<typename T, typename D, typename G>
bool ts(Tree<T> const & tree, T const value, D & ds, G getter)
{
if (empty(tree))
{
return false;
}
ds.push(tree.Root);
while (!ds.empty())
{
auto const current = getter();
ds.pop();
if (current->Value == value)
{
return true;
}
if (current->Left)
{
ds.push(current->Left);
}
if (current->Right)
{
ds.push(current->Right);
}
}
return false;
}
template<typename T>
bool dfs(Tree<T> const & tree, T const value)
{
stack<typename Tree<T>::Node const * const> ds;
return ts(tree, value, ds, [&ds](){ return ds.top(); });
}
template<typename T>
bool bfs(Tree<T> const & tree, T const value)
{
queue<typename Tree<T>::Node const * const> ds;
return ts(tree, value, ds, [&ds](){ return ds.front(); });
}
I though that I should be able to use mem_fun (or mem_fun_ref) to provide the respective access function. I tried
template<typename T>
bool dfs(Tree<T> const & tree, T const value)
{
typedef stack<typename Tree<T>::Node const * const> DataStructure;
return ts(tree, value, DataStructure(), mem_fun(&DataStructure::top));
}
But then the compiler complains about ambiguousity (between a const and a non-const version).
So I searched the internets and learned that I should provide the template type explicitly.
template<typename T>
bool dfs(Tree<T> const & tree, T const value)
{
typedef stack<typename Tree<T>::Node const * const> DataStructure;
return ts(tree, value, DataStructure(), mem_fun</*???*/>(&DataStructure::top));
}
Sadly, none of the many possibilities for ??? that I could come up with satisfied the compiler.
Can someone give me a hint?
Update: Here a full working example (except if you define NO_LAMBDA):
#include <iostream>
#include <stack>
#include <functional>
using namespace std;
template<typename T>
struct Tree
{
struct Node
{
T Value;
Node * Left;
Node * Right;
Node(T value) : Value(value), Left(nullptr), Right(nullptr) {}
virtual ~Node()
{
if (Left) delete Left;
if (Right) delete Right;
}
};
Node * Root;
Tree() : Root(nullptr) {}
virtual ~Tree() { if (Root) delete Root; }
};
template<typename T> void insert(typename Tree<T>::Node * node, T const & value)
{
typename Tree<T>::Node ** selected = &(value < node->Value ? node->Left : node->Right);
if (*selected)
insert(*selected, value);
else
*selected = new typename Tree<T>::Node(value);
}
template<typename T> void insert(Tree<T> & tree, T value)
{
if (!tree.Root)
tree.Root = new typename Tree<T>::Node(value);
else
insert(tree.Root, value);
}
template<typename T, typename D, typename G>
bool ts(Tree<T> const & tree, T const value, D & ds, G getter)
{
if (!tree.Root) return false;
ds.push(tree.Root);
while (!ds.empty())
{
auto const current = getter();
ds.pop();
if (current->Value == value) return true;
if (current->Left) ds.push(current->Left);
if (current->Right) ds.push(current->Right);
}
return false;
}
template<typename T>
bool dfs(Tree<T> const & tree, T const value)
{
typedef typename Tree<T>::Node const * DataStructureContent;
typedef stack<DataStructureContent> DataStructure;
#ifdef NO_LAMBDA // With this defined, it breaks.
return ts(tree, value, DataStructure(),
mem_fun(static_cast<DataStructureContent (DataStructure::*)() const>(&DataStructure::top)));
#else // This works.
DataStructure ds;
return ts(tree, value, ds, [&ds] () { return ds.top(); });
#endif
}
int main()
{
Tree<int> tree;
insert(tree, 5);
insert(tree, 2); insert(tree, 1); insert(tree, 3);
insert(tree, 7); insert(tree, 6); insert(tree, 9);
cout << "DFS(7) -> " << dfs(tree, 7) << endl;
cout << "DFS(8) -> " << dfs(tree, 8) << endl;
return 0;
}
You could cast the member function pointer to the type you need:
mem_fun( static_cast< R (DataStructure::*)( Args... ) >( &DataStructure::top ) )
or
mem_fun( static_cast< R (DataStructure::*)( Args... ) const >( &DataStructure::top ) )
with appropriate R for the result type and Args... for the arguments.
EDIT: You made two (three) mistakes in your complete example:
a) The cast needs to be exact, that is you need to provide the correct return type. Luckily, std::stack has typedefs to help you with that. In your case, you can cast with these two options:
typedef typename DataStructure::reference (DataStructure::*non_const_top)();
mem_fun( static_cast< non_const_top >( &DataStructure::top ) )
or
typedef typename DataStructure::const_reference (DataStructure::*const_top)() const;
mem_fun( static_cast< const_top >( &DataStructure::top ) )
b) You tried to bind a temporary to a reference when calling ts. Together with a), change the code to:
DataStructure ds;
typedef typename DataStructure::reference (DataStructure::*non_const_top)();
return ts(tree, value, ds, mem_fun(static_cast<non_const_top>(&DataStructure::top)));
c) In ts, you try to call the getter without an object. You need to change it to:
auto const current = getter( &ds );
With these changes, the code works for me.