I am designing a library for a hierarchical problem. At each stage of the hierarchy there are several "tools" at hand. If at a state N one tool succeeds, the solution is passed to the next (N+1) state. If all tools of stage N fails, it returns to the state N-1 (previous) and lets it handle the problem.

I have two possible ideas how to structure this problem. My question is, is any of these superior to the other (or are both flawed) and why?

The first solution uses templates to create a linked list of templated classes.

template <typename Input, typename Output>
struct BaseSolver
{
    virtual boost::optional<Output> run(const Input& _input) = 0;
};

template<typename Input>
struct BaseStage
{
    virtual bool runAndRecover(const Input &_input)
    {
        return true;
    }
};

template<typename Input, typename Output>
struct Stage1 : BaseStage<Input>
{
    bool run(const Input& _input)
    {
        for(const auto& solver : solvers_)
        {
            const auto currentResult = solver->run(_input);
            if(currentResult && nextStage->runAndRecover(currentResult.get()))
            {
                return true;
            }
        }
        return false;
    }

    std::vector<boost::shared_ptr<BaseSolver<Input, Output>>> solvers_;

    BaseStage<Output>* nextStage;
};

This is the other solution. It binds only to the run() function of the next stage

template<typename Input, typename Output>
struct Stage2
{
    typedef boost::function<boost::optional<Output> (Input)> SolverFunction;
    typedef boost::function<bool(Output)> NextStage;

    bool run(const Input& _input)
    {
        for(const auto& solver : solverFunctions_)
        {
            const auto solverResult = solver(_input);
            if(solverResult && nextStage_(solverResult.get()))
            {
                return true;
            }
        }
        return false;
    }

    std::vector<SolverFunction> solverFunctions_;
    // will be bind to the next stage::run
    NextStage nextStage_;
};