Boost.Context アルゴリズムを中断可能にする

既存のアルゴリズム関数の実行を中断可能にしてみました。
対象は、Boost.Graphの最短経路計算アルゴリズムです。

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/assign/list_of.hpp>
#include <functional>
#include "continuation.hpp"

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int>                           Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

enum { S, A, B, C, D, E, F, Z, N };
const std::string Names = "SABCDEFZ";

class path_history_visitor {
    continuation& cont;
public:
    typedef boost::on_discover_vertex event_filter;

    path_history_visitor(continuation& cont) : cont(cont) {}

    template<typename Vertex, typename Graph>
    void operator()(Vertex v, const Graph&)
    {
        std::cout << Names[v] << ' ';
        cont.suspend();
    }
};

Graph make_graph()
{
    const std::vector<Edge> edges = boost::assign::list_of<Edge>
        (S, A)
        (A, B)
        (B, C)
        (B, D)
        (C, E)
        (C, F)
        (D, F)
        (E, D)
        (F, E)
        (E, Z)
        (F, Z)
    ;

    const std::vector<int> weights = boost::assign::list_of
        (3)
        (1)
        (2)
        (3)
        (7)
        (12)
        (2)
        (11)
        (3)
        (2)
        (2)
    ;

    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

int main()
{
    const Graph g = make_graph();
    const Vertex from = S;

    continuation cont = [&](continuation& cont) {
        path_history_visitor vis(cont);

        boost::dijkstra_shortest_paths(g, from,
               boost::visitor(boost::make_dijkstra_visitor(vis)));
    };

    while (!cont.is_complete()) {
        cont.resume();
    }
}

S A B C D E F Z 

ポイントは、Event Visitorとラムダ式です。
Boost.GraphのEvent Visitorは、アルゴリズムの各ポイントで呼び出す関数を指定することができます。ここでは、点が交差するたびに実行するEvent Visitorを使用しています。Event Visitor内でsuspendを呼ぶことにより、アルゴリズムを途中で中断することができます。
ラムダ式は、既存のアルゴリズムの呼び出しをBoost.Contextのコンテキストへと変換するのに使用できます。

Event Visitorは、アルゴリズムの関数オブジェクトでも代用できます。「nステップ実行したら中断する」というnを関数オブジェクトのコンストラクタで渡してメンバ関数に持っておくなどすれば便利だと思います。
中断可能なアルゴリズムを別途用意するのではなく、既存のアルゴリズムをそのまま使用できるのがいいところですね。

ゲームループで「重い処理は数フレームかけて処理を行う」といったことに使えそうです。