I coded this algorithm in order to have a generic backtracking algorithm. I expect the user to pass a POD for ELEMENT
, hopefully as small as possible. Any idea how I could improve this?
#ifndef BACKTRACK_H
#define BACKTRACK_H
#include <array>
#include <vector>
#include <assert.h>
template< class ELEMENT, unsigned MAX_CAPACITY >
class backtrack
{
public:
backtrack()
: m_grid()
, m_depth( 0 )
, m_finish( false )
{
}
virtual ~backtrack() {}
template< typename ForwardIterator >
backtrack( ForwardIterator begin, ForwardIterator end )
: m_grid()
, m_depth( 0 )
, m_finish( false )
{
std::copy( begin, end, m_grid.begin() );
}
void step()
{
if ( is_a_valid_solution( m_grid ) )
m_finish = process_solution( m_grid );
if ( m_depth == MAX_CAPACITY )
return;
const auto & candidates = generate_candidates( m_grid );
for( const auto & candidate : candidates )
{
push( candidate );
step();
pull();
}
}
private:
virtual
bool is_a_valid_solution( const std::array< ELEMENT, MAX_CAPACITY > & solution )
{
( void )solution;
return false;
}
virtual
bool process_solution( const std::array< ELEMENT, MAX_CAPACITY > & solution )
{
( void )solution;
return false;
}
virtual
std::vector<ELEMENT> generate_candidates( const
std::array< ELEMENT, MAX_CAPACITY > & partial_solution )
{
( void )partial_solution;
return std::vector<ELEMENT>();
}
void push( ELEMENT candidate )
{
assert( m_depth < MAX_CAPACITY );
m_grid[ m_depth++ ] = candidate;
}
void pull()
{
assert( m_depth <= MAX_CAPACITY );
assert( m_depth > 0 );
m_grid[ --m_depth ] = ELEMENT();
}
private:
std::array< ELEMENT, MAX_CAPACITY > m_grid;
unsigned m_depth;
bool m_finish;
};
requires PODType<ELEMENT>()
after thetemplate <XXX>
line. (Valid in C++17 but good as a comment now). – Loki Astari Mar 20 at 15:47static_assert( is_pod< ELEMENT>::type )
or sth like that – qdii Mar 20 at 15:48static_assert
that the type is POD, in the lack of C++17 concepts. – glampert Mar 20 at 18:02