再帰呼び出しとスタック | Programming Place Plus 新C++編

トップページ新C++編

先頭へ戻る

このページの概要

このページでは、ある関数がそれと同じ関数を呼び出すという再帰呼び出しについて取り上げます。また、関数呼び出しの仕組みと関わりが深い、スタックと呼ばれるデータ構造の存在についても触れています。

以下は目次です。要点だけをさっと確認したい方は、「まとめ」をご覧ください。



塗りつぶしコマンドを作る

前のページで、ペイントスクリプトは最低限動作する状態になりましたが、いつものように、ここから少し改造を加えたり、補足の解説を行ったりしていきます。

このページでは、「塗りつぶし」のコマンドを追加することを題材にして、関数の再帰呼び出しを解説します。ここで追加する塗りつぶしコマンドは、指定した座標を起点として、同じ色のピクセルを上下左右に探していき、一斉に指定の色で塗り替えるというものです。キャンバス全面を強制的に塗りつぶすコマンドに fill という名前を使ってしまったので、ここで作るコマンドは bucket(バケツ)にしておきます(ペイントソフトによっては、こういう機能はバケツツールと呼ばれています)。

bucket X座標 Y座標

さっそく実装を始めてもいいですが、動作確認のために、線で囲まれた領域を作りやすくしておいたほうがよさそうです。rectコマンドで四角形の枠は作れますが、四角形の内側を塗ることしか試せないので、直線と円を描くコマンドを作っておきましょう。

line 開始X座標 開始Y座標 終端X座標 終端Y座標
circle 中心X座標 中心Y座標 半径

直線や円を描くには少々知識が必要ですが、ここは本題ではないので詳しい説明は省きます。

興味があれば「ブレゼンハムのアルゴリズム」を調べてみてください。

// canvas.cpp

namespace paint_script {
    void Canvas::paint_line(int x1, int y1, int x2, int y2, Pen& pen)
    {
        const int dx {std::abs(x2 - x1)};
        const int dy {std::abs(y2 - y1)};
        const int sx {x1 < x2 ? 1 : -1};
        const int sy {y1 < y2 ? 1 : -1};
        int e {dx - dy};

        while (true) {
            paint_dot(x1, y1, pen);
            if (x1 == x2 && y1 == y2) {
                break;
            }

            int e2 {2 * e};
            if (e2 > -dy) {
                e -= dy;
                x1 += sx;
            }
            if (e2 < dx) {
                e += dx;
                y1 += sy;
            }
        }
    }

    void Canvas::paint_circle(int center_x, int center_y, int radius, Pen& pen)
    {
        int x {radius};
        int y {0};
        int d {3 - 2 * radius};

        while (x >= y) {
            paint_dot(center_x + x, center_y + y, pen);
            paint_dot(center_x - x, center_y + y, pen);
            paint_dot(center_x + x, center_y - y, pen);
            paint_dot(center_x - x, center_y - y, pen);
            paint_dot(center_x + y, center_y + x, pen);
            paint_dot(center_x - y, center_y + x, pen);
            paint_dot(center_x + y, center_y - x, pen);
            paint_dot(center_x - y, center_y - x, pen);

            if (d >= 0) {
                --x;
                d -= 4 * x;
            }
            ++y;
            d += 4 * y + 2;
        }
    }
}

ペイントスクリプトのプログラムの全体像は、このページのほかの解説をすべて終えたあとで掲載します

これまでに解説していない std::abs関数1が使われていますが、これは引数に渡した値の絶対値を返す関数です。オーバーロードされた宣言が複数あり、整数型のものは &lt:cstdlib> あるいは <cmath> に、浮動小数点型のものは <cmath> にあります。

【C言語プログラマー】C++ では型ごとに関数を使い分ける必要はないですが、labs、llabs といった型ごとの名前の関数も使えるようになっています。

内部を塗りつぶした四角形を描画する filled_rectコマンドにならって、内部を塗りつぶした円を描画する filled_circleコマンドも作ってしまいます。

// canvas.cpp

namespace paint_script {
    void Canvas::paint_filled_circle(int center_x, int center_y, int radius, Pen& pen)
    {
        int x {radius};
        int y {0};
        int d {3 - 2 * radius};

        while (x >= y) {
            paint_dot(center_x + x, center_y + y, pen);
            paint_dot(center_x - x, center_y + y, pen);
            paint_dot(center_x + x, center_y - y, pen);
            paint_dot(center_x - x, center_y - y, pen);
            paint_dot(center_x + y, center_y + x, pen);
            paint_dot(center_x - y, center_y + x, pen);
            paint_dot(center_x + y, center_y - x, pen);
            paint_dot(center_x - y, center_y - x, pen);

            for (int dx {-x + 1}; dx <= x; dx++) {
                paint_dot(center_x + dx, center_y + y, pen);
                paint_dot(center_x + dx, center_y - y, pen);
                paint_dot(center_x + y, center_y + dx, pen);
                paint_dot(center_x - y, center_y + dx, pen);
            }

            if (d >= 0) {
                --x;
                d -= 4 * x;
            }
            ++y;
            d += 4 * y + 2;
        }
    }
}

再帰呼び出し

では、bucketコマンドの実装を考えていきます。

まず、あるピクセルを起点にして、上下左右のピクセルを塗るにはどうすればいいでしょう。単純にはこうなるはずです。

namespace paint_script {
    void Canvas::bucket_drawing(int x, int y, Pen& pen)
    {
        paint_dot(x, y, pen);     // 指定されたピクセルを塗る
        paint_dot(x, y - 1, pen); // 1つ上のピクセルを塗る
        paint_dot(x, y + 1, pen); // 1つ下のピクセルを塗る
        paint_dot(x - 1, y, pen); // 1つ左のピクセルを塗る
        paint_dot(x + 1, y, pen); // 1つ右のピクセルを塗る
    }
}

実際には起点と同じ色のときにだけ塗るようにする必要があるので、その判定が必要です。

namespace paint_script {
    void Canvas::bucket_drawing(int x, int y, Pen& pen)
    {
        if (!is_inside(x, y)) {
            return;
        }

        // 起点の色
        const Color target_color {get_pixel(x, y)};

        // 起点の色と同じ色で塗ろうとしているなら、何もせず終了する
        if (is_equal_color(target_color, pen.get_color())) {
            return;
        }

        // 起点を塗る
        paint_dot(x, y, pen);

        // 隣接ピクセルは、起点の色と同じ場合に塗る
        if (is_inside(x, y - 1) && is_equal_color(target_color, get_pixel(x, y - 1))) {
            paint_dot(x, y - 1, pen);
        }
        if (is_inside(x, y + 1) && is_equal_color(target_color, get_pixel(x, y + 1))) {
            paint_dot(x, y + 1, pen);
        }
        if (is_inside(x - 1, y) && is_equal_color(target_color, get_pixel(x - 1, y))) {
            paint_dot(x - 1, y, pen);
        }
        if (is_inside(x + 1, y) && is_equal_color(target_color, get_pixel(x + 1, y))) {
            paint_dot(x + 1, y, pen);
        }
    }

    Color Canvas::get_pixel(int x, int y) const
    {
        assert(is_inside(x, y));
        return m_pixels[y][x];
    }
}
// color.h

namespace paint_script {

    // 同じ色かどうか
    inline bool is_equal_color(const Color& color1, const Color& color2)
    {
        return color1.red == color2.red
            && color1.green == color2.green
            && color1.blue == color2.blue
            ;
    }
}

この時点で塗りつぶしの対象になっているのは、起点のピクセルと、その上下左右のピクセルの計5ピクセルだけです。backetコマンドとしては、さらにその上下左右にあるピクセルへと対象を拡げていかなければいけません。これまでの知識だけでやろうとするならループを駆使するしかないですが(そして結局そのほうが良いという結論に戻るのですが)、まずはこのページのテーマである、再帰呼び出し (recursive call) を試してみます。

再帰呼び出しとは、いま実行している関数と同じ関数を呼び出すということです。特別な構文があるわけではなく、ほかの関数を呼び出すのと同じように書けばいいだけです。たとえば “Hello” を指定回数だけ出力する関数を、再帰呼び出しを駆使して書くと次のようになります。

#include <iostream>

void print_hello(int times)
{
    if (times <= 0) {
        return;
    }

    std::cout << "Hello\n";
    print_hello(times - 1);  // 再帰呼び出し
}

int main()
{
    print_hello(5);
}

実行結果:

Hello
Hello
Hello
Hello
Hello

main関数だけは例外で、再帰呼び出しできないことになっています2が、Visual Studio でも gcc でも動作します。

【C言語プログラマ】C言語では main関数を例外扱いするルールはなく、再帰呼び出しできると考えられます。

再帰呼び出しを使うときには、いつか初回の呼び出し元に戻ってこられるようにしなければいけません。さもないと、無限に呼び出しを続けてしまうことになり、一向に処理が先に進まないプログラムになったり、異常終了に至ったりします(この件はあとで改めて取り上げます)。このサンプルプログラムの場合、print_hello関数の引数が “Hello” を出力する回数を表しているわけですが、再帰呼び出しのたびに実引数を 1 ずつ減らしていき、渡された値が 0以下の場合には何もせずに return するようにしています。

再帰呼び出しを使って、bucket_drawing関数を作り変えてみます。

namespace paint_script {
    void Canvas::bucket_drawing(int x, int y, Pen& pen)
    {
        if (!is_inside(x, y)) {
            return;
        }

        const Color target_color {get_pixel(x, y)};
        if (is_equal_color(target_color, pen.get_color())) {
            return;
        }

        // 起点のピクセルを指定して、再帰呼び出しの初回を開始
        bucket_drawing_recursive(x, y, target_color, pen);
    }

    void Canvas::bucket_drawing_recursive(int x, int y, const Color& target_color, Pen& pen)
    {
        if (!is_inside(x, y)) {
            return;
        }
        if (!is_equal_color(get_pixel(x, y), target_color)) {
            return;
        }

        // 指定のピクセルを塗る
        paint_dot(x, y, pen);

        // 上下左右のピクセルへ(再帰呼び出し)
        bucket_drawing_recursive(x, y - 1, target_color, pen);
        bucket_drawing_recursive(x, y + 1, target_color, pen);
        bucket_drawing_recursive(x - 1, y, target_color, pen);
        bucket_drawing_recursive(x + 1, y, target_color, pen);
    }
}

これで、Canvas::bucket_drawingメンバ関数に指定した起点のピクセルから開始して、周囲の同じ色のピクセルにどこまでも塗りつぶし処理を展開していけるようになりました。is_insideメンバ関数によるチェックもあるので、キャンバスの端を突き抜けてしまうこともありません。

たとえば次のようにコマンドを実行すると、以下のような結果が得られます。

pen RED
circle 100 100 30
pen GREEN
bucket 100 100
save test.bmp
bucketコマンドの実行結果

スタックオーバーフロー

ここまでの実装でうまくいっているわけではありますが、じつは問題があります。さきほどのコマンドの中で、circleコマンドの3つ目のパラメータを大きくしてから実行してみます。

pen RED
circle 100 100 100
pen GREEN
bucket 100 100
save test.bmp

すると、bucketコマンドの実行時に異常終了します。

もし正常に動いてしまったら、さらに大きくして試してみてください。

何が起きているか簡単にいえば、実行中にメモリが足らなくなってしまったということです。さきほど実行した一連のコマンドは、circleコマンドで描いた、半径100pixel の円の内側のピクセルを塗りつぶすということですが、円の内側にあるすべてのピクセルを塗りつぶすには、相当な回数の再帰呼び出しを繰り返さなければなりません。

ここで、関数を呼び出す仕組みについて知っておく必要があります。関数を呼び出すとき、その関数のコードがあるメモリアドレスへ移動すればいいわけですが(「関数ポインタとラムダ式」のページを参照)、関数内のコードの実行が終わったあとの戻り先についても管理しなければなりません。「関数A -> B -> Aに戻る」のような単純な経路だけでなく、「関数A -> B -> C -> Bに戻る -> D -> Bに戻る -> Aに戻る」のような複雑な経路を辿ることもありますから、今いるところから一番最初のところにまできちんと戻ってこられるようなかたちで記憶しておく必要があります。

そこで、コールスタック (call stack) やプログラムスタック (program stack) などと呼ばれるデータ構造がメモリ上に構築されています。関数を呼び出すたびにコールスタックに情報を格納し、呼び出し元に戻るときに(あるいは戻ったあと)、その分の情報が取り除かれるということを繰り返します。コールスタックに格納する情報には、戻り先を示す情報のほか、自動ストレージ期間を持つように宣言されたローカル変数や、引数の値などが含まれていることがあります。

【上級】コンピュータの命令セットアーキテクチャが定める呼び出し規約によって、コールスタックに情報を格納したり取り除いたりする処理を、関数の呼び出し側で行うのか、呼び出された側で行うのかという違いがあります。

このような仕組みで動いているため、関数がなかなか呼び出し元に帰らず、次の関数へ次の関数へと掘り進んでいくような作りになっていると、コールスタックは大量の情報を抱え込むことになります。コールスタックは std::vector のように自動的に増えるものではなく、固定的な大きさで確保されているため、いつか限界が来て溢れ出すことになります。コールスタックが溢れてしまうことを、スタックオーバーフロー (stack overflow) と呼びます。

Visual Studio では、コールスタックの規定の大きさは 1MByte です3。大きさを変更する方法については Visual Studio編>「コールスタックの大きさ」 を参照してください。

gcc (MinGW-w64) では、コールスタックの規定の大きさは 2MByte です。コンパイラオプションで -Wl,--stack=バイト数 のように指定することで大きさを変更できます。

さきほどの bucketコマンドの実行時に異常終了したのは、スタックオーバーフローが起きたためです。塗りつぶす範囲が広範囲にわたっていると、呼び出し元に帰らない再帰呼び出しが繰り返し行われ、コールスタックの容量の限界に達します。

スタックオーバーフローを避けて bucketコマンドを実装する方策については、あとで取り上げます


ところで、コールスタックの「スタック (stack)」の部分ですが、これは非常に重要なデータ構造の名前でもあります。スタックは、本を積み重ねていくかのようなイメージでデータを登録し、取り出すときには必ず最後に登録されたデータ(一番上に積んだ本)が選ばれるという特徴を持っています。言い換えると、後で入れたデータから先に取り出されるというルール(後入れ先出し (LIFO: Last-In First-Out))が課せられた、特殊化されたデータ構造です。このようなデータ構造は、配列を使って実装することができるほか、C++ の標準ライブラリにある std::stack を使うことでも利用できます(このあと取り上げます)。

配列を使ってスタックを実装する方法については、アルゴリズムとデータ構造編でも解説しています。

std::stack

std::stack4 はスタックを実装したクラスで、<stack> をインクルードすると使用できます。

【上級】正確にはクラステンプレートです。

スタックというデータ構造にとって最低限必要な機能は、データを追加する操作と、取り出す操作です。この2つの操作にはそれぞれ、プッシュ (push) と、ポップ (pop) という呼び名があります。後入れ先出しのデータ構造なので、ポップで取り出されるデータは、最後にプッシュされたデータです。

std::stack は std::vector と同じく、型名に <int> のような記述を付けて、要素の型を指定します。

std::stack<int> stack1 {};        // 空のスタック
std::stack<int> stack2 {stack1};  // ほかのスタックからコピー

プッシュは pushメンバ関数で行います。

stack1.push(100);

【C++23】push_rangeメンバ関数が追加され、Range(C++20 の機能)を指定した方法でまとめて追加できるようになっています5

ポップは popメンバ関数で行います。最後にプッシュしたデータが削除されますが、その値が返ってくることはなく、戻り値は void です。

stack1.pop();

ポップで削除される値が必要なら、先に topメンバ関数を使って受け取っておく必要があります。topメンバ関数が返すものは、std::stack の内側にあるデータへの参照なので、コピーを受け取らないと危険です。

auto v = stack1.top();  // int& が返される。参照のまま受け取ると、pop で削除されるので危険
stack1.pop();

std::stack が空の状態で popメンバ関数、topメンバ関数を呼び出してはいけません。

【上級】std::stack は実装にほかのコンテナを用いており(テンプレートパラメータにより取り換えできる)、popメンバ関数は pop_back関数を、topメンバ関数は pop関数を呼び出すことで実現されます。そのため、std::stack が空の場合の動作も、それぞれの関数がどのように実装されているかに左右されることになります。デフォルトで用いられるコンテナは std::deque であり、この場合(C++標準のほかのコンテナに取り換えた場合も結局は同様に)は未定義の動作です6

空かどうかは emptyメンバ関数を使って調べられます。

if (!stack1.empty()) {
    stack1.pop();  // 安全
}

sizeメンバ関数を使って、現在格納されているデータの個数を調べることもできます。

auto size = stack1.size();

再帰呼び出しを避けた実装

Canvas::bucket_drawing_recursiveメンバ関数の実装を見直してみると、たとえば起点から1つ上のピクセルに処理を進めたあと、そのピクセルが再び上下左右を確認するので、下に戻ってきてしまうことが分かります。また、起点から上–>右と進むことと、起点から右–>上と進むことは、結局同じピクセルを確認することになります。現状の実装にはこのように多大な無駄があります。この無駄によって、再帰呼び出しの回数がよけいに増加しています。

この無駄をなくすには、すでに処理済みのピクセルを除外する仕組みが必要です。処理を終えたピクセルの情報を std::vector に保存していけば、すでに処理済みのピクセルかどうかを判断することに使えますが、これだとかなり非効率になります(1ピクセルごとに std::vector の中身を総ざらいして確認しなければならないので)。

そこで考え方を逆転して、処理しなければならないピクセルの座標情報を保存していくようにします。この情報管理のために std::stack を使います。

#include <stack>
#include <tuple>

namespace paint_script {
    void Canvas::bucket_drawing(int x, int y, Pen& pen)
    {
        if (!is_inside(x, y)) {
            return;
        }

        const Color target_color {get_pixel(x, y)};
        if (is_equal_color(target_color, pen.get_color())) {
            return;
        }

        std::stack<std::pair<int, int>> pixel_stack {};

        // 起点のピクセルを登録
        pixel_stack.push({x, y});

        // スタックが空になるまで繰り返すループ(再帰呼び出しをしない)
        while (!pixel_stack.empty()) {

            // スタックから1つ取り出す
            std::tie(x, y) = pixel_stack.top();
            pixel_stack.pop();

            // 取り出された座標のピクセルを塗る
            paint_dot(x, y, pen);

            // 上下左右のピクセルが target_color と一致するなら、その座標情報をスタックに入れる。
            // キャンバスの端を越えないようにチェック。
            if (is_inside(x, y - 1) && is_equal_color(target_color, get_pixel(x, y - 1))) {
                pixel_stack.push({x, y - 1});
            }
            if (is_inside(x, y + 1) && is_equal_color(target_color, get_pixel(x, y + 1))) {
                pixel_stack.push({x, y + 1});
            }
            if (is_inside(x - 1, y) && is_equal_color(target_color, get_pixel(x - 1, y))) {
                pixel_stack.push({x - 1, y});
            }
            if (is_inside(x + 1, y) && is_equal_color(target_color, get_pixel(x + 1, y))) {
                pixel_stack.push({x + 1, y});
            }
        }
    }
}

このような実装にすることで再帰呼び出しに頼る必要がなくなり、コールスタックの大量消費を避けられます。以下のようにコマンドを実行しても、スタックオーバーフローを起こさなくなりました。

pen RED
circle 100 100 100
pen GREEN
bucket 100 100
save test.bmp
bucketコマンドの実行結果

最終的にペイントスクリプトの全体像は次のようになりました。

//main.cpp
#include <iostream>
#include "canvas.h"
#include "command_executor.h"
#include "command_history.h"
#include "macro.h"
#include "string_util.h"

int main()
{
    std::cout << "コマンドを入力してください。\n"
              << "help と入力すると、コマンドの一覧を表示します。\n"
              << "exit と入力すると、プログラムを終了します。\n";

    paint_script::Canvas canvas {};
    paint_script::CommandHistory history {};
    paint_script::CommandExecutor executor {canvas, history};

    while (true) {
        std::string input_string {};
        std::getline(std::cin, input_string);

        // 入力履歴を保存
        history.add(input_string);

        // マクロを置換する
        paint_script::Macro::replace(input_string);
        
        // 空白文字ごとに分割して、std::vector に格納する
        const auto command_vec = str_util::split(input_string, " ");
        if (command_vec.empty()) {
            continue;
        }
        
        // 該当するコマンドを探して実行
        if (executor.exec(command_vec) == paint_script::CommandExecutor::ExecResult::exit_program) {
            break;
        }
    }
}
// string_util.cpp
#include "string_util.h"

namespace str_util {

    // 文字列を分割する
    std::vector<std::string> split(const std::string& str, const std::string& delim)
    {
        const auto delimLen = delim.size();
        if (delimLen == 0) {
            return {str};
        }

        std::string::size_type current {0};
        std::string::size_type found {};
        std::vector<std::string> result {};

        // 区切り文字を探しながら、その位置の手前までの文字列を追加することを繰り返す
        while ((found = str.find(delim, current)) != std::string::npos) {
            result.push_back(str.substr(current, found - current));
            current = found + delimLen;
        }

        // 残った部分を追加
        result.push_back(str.substr(current, str.size() - current));

        return result;
    }

    // 指定文字列をすべて探して置き換える
    std::string& find_replace_all(std::string& str, const std::string& search_str, const std::string& replace_str)
    {
        if (search_str.empty()) {
            return str;
        }

        std::string::size_type pos {};
        while ((pos = str.find(search_str)) != std::string::npos) {
            str.replace(pos, search_str.length(), replace_str);
            pos += search_str.length();
        }

        return str;
    }
}
// string_util.h
#ifndef STRING_UTIL_H_INCLUDED
#define STRING_UTIL_H_INCLUDED

#include <string>
#include <vector>


namespace str_util {

    // 文字列を分割する
    //
    // str:   対象の文字列
    // delim: 区切り文字列
    // 戻り値: str を delim で区切った部分文字列を格納した vector
    std::vector<std::string> split(const std::string& str, const std::string& delim);

    // 指定文字列をすべて探して置き換える
    //
    // str:         対象の文字列
    // search_str:  探す文字列
    // replace_str: 置換文字列
    // 戻り値:      str を返す
    std::string& find_replace_all(std::string& str, const std::string& search_str, const std::string& replace_str);

}

#endif
// canvas.cpp
#include "canvas.h"
#include "bmp.h"
#include "pen.h"
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <stack>
#include <tuple>

namespace paint_script {

    Canvas::Canvas(unsigned int width, unsigned int height, Color color) :
        m_pixels {},
        m_width {0},
        m_height {0}
    {
        resize(width, height, color);
    }

    void Canvas::resize(unsigned int width, unsigned int height, Color color)
    {
        assert(1 <= width);
        assert(1 <= height);

        m_pixels.resize(height);
        for (auto& row : m_pixels) {
            row.resize(width);
        }

        m_width = width;
        m_height = height;

        fill(color);
    }

    void Canvas::fill(Color color)
    {
        for (auto& row : m_pixels) {
            std::fill(std::begin(row), std::end(row), color);
        }
    }

    void Canvas::bucket_drawing(int x, int y, Pen& pen)
    {
        if (!is_inside(x, y)) {
            return;
        }

        const Color target_color {get_pixel(x, y)};
        if (is_equal_color(target_color, pen.get_color())) {
            return;
        }

        std::stack<std::pair<int, int>> pixel_stack {};

        // 起点のピクセルを登録
        pixel_stack.push({x, y});

        // スタックが空になるまで繰り返すループ(再帰呼び出しをしない)
        while (!pixel_stack.empty()) {

            // スタックから1つ取り出す
            std::tie(x, y) = pixel_stack.top();
            pixel_stack.pop();

            // 取り出された座標のピクセルを塗る
            paint_dot(x, y, pen);

            // 上下左右のピクセルが target_color と一致するなら、その座標情報をスタックに入れる。
            // キャンバスの端を越えないようにチェック。
            if (is_inside(x, y - 1) && is_equal_color(target_color, get_pixel(x, y - 1))) {
                pixel_stack.push({x, y - 1});
            }
            if (is_inside(x, y + 1) && is_equal_color(target_color, get_pixel(x, y + 1))) {
                pixel_stack.push({x, y + 1});
            }
            if (is_inside(x - 1, y) && is_equal_color(target_color, get_pixel(x - 1, y))) {
                pixel_stack.push({x - 1, y});
            }
            if (is_inside(x + 1, y) && is_equal_color(target_color, get_pixel(x + 1, y))) {
                pixel_stack.push({x + 1, y});
            }
        }
    }

    void Canvas::paint_dot(int x, int y, Pen& pen)
    {
        if (!is_inside(x, y)) {
            return;
        }

        m_pixels[y][x] = pen.get_color();
    }

    void Canvas::paint_line(int x1, int y1, int x2, int y2, Pen& pen)
    {
        const int dx {std::abs(x2 - x1)};
        const int dy {std::abs(y2 - y1)};
        const int sx {x1 < x2 ? 1 : -1};
        const int sy {y1 < y2 ? 1 : -1};
        int e {dx - dy};

        while (true) {
            paint_dot(x1, y1, pen);
            if (x1 == x2 && y1 == y2) {
                break;
            }

            int e2 {2 * e};
            if (e2 > -dy) {
                e -= dy;
                x1 += sx;
            }
            if (e2 < dx) {
                e += dx;
                y1 += sy;
            }
        }
    }

    void Canvas::paint_rect(int left, int top, int right, int bottom, Pen& pen)
    {
        // 上辺
        for (int x {left}; x <= right; ++x) {
            paint_dot(x, top, pen);
        }

        // 左辺
        for (int y {top + 1}; y < bottom; ++y) {
            paint_dot(left, y, pen);
        }

        // 右辺
        for (int y {top + 1}; y < bottom; ++y) {
            paint_dot(right, y, pen);
        }

        // 下辺
        for (int x {left}; x <= right; ++x) {
            paint_dot(x, bottom, pen);
        }
    }

    void Canvas::paint_filled_rect(int left, int top, int right, int bottom, Pen& pen)
    {
        for (int y {top}; y <= bottom; ++y) {
            for (int x {left}; x <= right; ++x) {
                paint_dot(x, y, pen);
            }
        }
    }

    void Canvas::paint_circle(int center_x, int center_y, int radius, Pen& pen)
    {
        int x {radius};
        int y {0};
        int d {3 - 2 * radius};

        while (x >= y) {
            paint_dot(center_x + x, center_y + y, pen);
            paint_dot(center_x - x, center_y + y, pen);
            paint_dot(center_x + x, center_y - y, pen);
            paint_dot(center_x - x, center_y - y, pen);
            paint_dot(center_x + y, center_y + x, pen);
            paint_dot(center_x - y, center_y + x, pen);
            paint_dot(center_x + y, center_y - x, pen);
            paint_dot(center_x - y, center_y - x, pen);

            if (d >= 0) {
                --x;
                d -= 4 * x;
            }
            ++y;
            d += 4 * y + 2;
        }
    }

    void Canvas::paint_filled_circle(int center_x, int center_y, int radius, Pen& pen)
    {
        int x {radius};
        int y {0};
        int d {3 - 2 * radius};

        while (x >= y) {
            paint_dot(center_x + x, center_y + y, pen);
            paint_dot(center_x - x, center_y + y, pen);
            paint_dot(center_x + x, center_y - y, pen);
            paint_dot(center_x - x, center_y - y, pen);
            paint_dot(center_x + y, center_y + x, pen);
            paint_dot(center_x - y, center_y + x, pen);
            paint_dot(center_x + y, center_y - x, pen);
            paint_dot(center_x - y, center_y - x, pen);

            for (int dx {-x + 1}; dx <= x; dx++) {
                paint_dot(center_x + dx, center_y + y, pen);
                paint_dot(center_x + dx, center_y - y, pen);
                paint_dot(center_x + y, center_y + dx, pen);
                paint_dot(center_x - y, center_y + dx, pen);
            }

            if (d >= 0) {
                --x;
                d -= 4 * x;
            }
            ++y;
            d += 4 * y + 2;
        }
    }

    bool Canvas::load_from_bitmap_file(const std::string& path)
    {
        if (!Bmp::load(path, &m_width, &m_height, &m_pixels)) {
            return false;
        }

        return true;
    }

    bool Canvas::save_to_bitmap_file(const std::string& path)
    {
        return Bmp::save(path, m_width, m_height, m_pixels);
    }

    bool Canvas::is_inside(int x, int y) const
    {
        if (x < 0 || static_cast<int>(m_width) <= x) {
            return false;
        }
        if (y < 0 || static_cast<int>(m_height) <= y) {
            return false;
        }
        return true;
    }

    Color Canvas::get_pixel(int x, int y) const
    {
        assert(is_inside(x, y));
        return m_pixels[y][x];
    }

}
// canvas.h
#ifndef CANVAS_H_INCLUDED
#define CANVAS_H_INCLUDED

#include <string>
#include <vector>
#include "color.h"

namespace paint_script {

    class Pen;

    class Canvas {
    public:
        static constexpr unsigned int default_width {320};
        static constexpr unsigned int default_height {240};

    public:
        // コンストラクタ
        //
        // width: 横方向のピクセル数。省略時は default_width
        // height: 縦方向のピクセル数。省略時は default_height
        // color: 初期状態の色。省略時は白
        Canvas(unsigned int width = default_width, unsigned int height = default_height, Color color = {255, 255, 255});

    public:
        // キャンバスの大きさを変更する
        // 
        // これまでのキャンバスに描かれていた内容は失われ、
        // color の色で塗りつぶされる。
        //
        // width: 横方向のピクセル数 (1~WidthMax)
        // height: 縦方向のピクセル数 (1~HeightMax)
        // color: 色。省略時は白
        void resize(unsigned int width, unsigned int height, Color color = {255, 255, 255});


        // 全面を塗りつぶす
        //
        // color: 色
        void fill(Color color);

        // 指定座標を起点に、同一色の隣接ピクセルを塗りつぶす
        //
        // x: 起点になるピクセルの X座標
        // y: 起点になるピクセルの Y座標
        // pen: ペン
        void bucket_drawing(int x, int y, Pen& pen);


        // 点を描画する
        //
        // x: X座標
        // y: Y座標
        // pen: ペン
        void paint_dot(int x, int y, Pen& pen);

        // 直線を描画する
        //
        // x1: X座標
        // y1: Y座標
        // x2: X座標
        // y2: Y座標
        // pen: ペン
        void paint_line(int x1, int y1, int x2, int y2, Pen& pen);

        // 矩形を描画する
        //
        // left: 左端X座標
        // top: 上端Y座標
        // right: 右端X座標
        // bottom: 下端Y座標
        // pen: ペン
        void paint_rect(int left, int top, int right, int bottom, Pen& pen);

        // 内側を塗りつぶした矩形を描画する
        //
        // left: 左端X座標
        // top: 上端Y座標
        // right: 右端X座標
        // bottom: 下端Y座標
        // pen: ペン
        void paint_filled_rect(int left, int top, int right, int bottom, Pen& pen);

        // 円を描画する
        //
        // center_x: 中心X座標
        // center_y: 中心Y座標
        // radius: 半径
        // pen: ペン
        void paint_circle(int center_x, int center_y, int radius, Pen& pen);

        // 内側を塗りつぶした円を描画する
        //
        // center_x: 中心X座標
        // center_y: 中心Y座標
        // radius: 半径
        // pen: ペン
        void paint_filled_circle(int center_x, int center_y, int radius, Pen& pen);


        // ビットマップファイルから読み込む
        //
        // path: ビットマップファイルのパス
        // 戻り値: 成否
        bool load_from_bitmap_file(const std::string& path);

        // ビットマップファイルとして書き出す
        //
        // path: 出力先のビットマップファイルのパス
        // 戻り値: 成否
        bool save_to_bitmap_file(const std::string& path);



        // 横方向のピクセル数を返す
        //
        // 戻り値: 横方向のピクセル数
        inline unsigned int get_width() const
        {
            return m_width;
        }
        
        // 縦方向のピクセル数を返す
        //
        // 戻り値: 縦方向のピクセル数
        inline unsigned int get_height() const
        {
            return m_height;
        }

        // 座標がキャンバスの範囲内かどうか調べる
        //
        // x: X座標
        // y: Y座標
        // 戻り値: キャンバス内の座標なら true。そうでなければ false
        bool is_inside(int x, int y) const;

        // 指定座標の色を返す
        //
        // x: X座標
        // y: Y座標
        // 戻り値: 指定座標の色
        Color get_pixel(int x, int y) const;

    private:
        std::vector<std::vector<Color>>     m_pixels;
        unsigned int                        m_width;
        unsigned int                        m_height;
    };

}

#endif
// command_executor.cpp
#include "command_executor.h"
#include "canvas.h"
#include "command_history.h"
#include "macro.h"
#include "string_util.h"
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <iterator>


namespace paint_script {

    const CommandExecutor::CommandData CommandExecutor::CommandMap[] {
        {"help", &help, &print_help_help},
        {"exit", &exit, &print_help_exit},
        {"resize", &resize, &print_help_resize},
        {"fill", &fill, &print_help_fill},
        {"bucket", &bucket, &print_help_bucket},
        {"pen", &pen, &print_help_pen},
        {"dot", &dot, &print_help_dot},
        {"line", &line, &print_help_line},
        {"rect", &rect, &print_help_rect},
        {"filled_rect", &filled_rect, &print_help_filled_rect},
        {"circle", &circle, &print_help_circle},
        {"filled_circle", &filled_circle, &print_help_filled_circle},
        {"load", &load, &print_help_load},
        {"save", &save, &print_help_save},
        {"load_script", &load_script, &print_help_load_script},
        {"save_script", &save_script, &print_help_save_script},
    };



    CommandExecutor::CommandExecutor(Canvas& canvas, CommandHistory& history) :
        m_canvas {canvas}, m_history {history},
        m_is_load_script {false}
    {

    }

    CommandExecutor::ExecResult CommandExecutor::exec(const command_params_t& command_vec)
    {
        const std::string command_name {command_vec.at(0)};

        // コマンドを探す
        const auto command_it = std::find_if(
            std::cbegin(CommandMap),
            std::cend(CommandMap),
            [command_name](const CommandData& data) { return data.name == command_name; });
        if (command_it == std::cend(CommandMap)) {
            return ExecResult::not_found;
        }
        
        // 実行
        try {
            return command_it->impl(this, command_vec);
        }
        catch (const std::invalid_argument&) {
            std::cout << "入力に間違いがあります。\n";
        }
        catch (const std::out_of_range&) {
            std::cout << "有効範囲を越えた入力があります。\n";
        }
        return ExecResult::failed;
    }


    // ヘルプ
    CommandExecutor::ExecResult CommandExecutor::help(const command_params_t&)
    {
        print_help();
        return ExecResult::successd;
    }

    // 終了
    CommandExecutor::ExecResult CommandExecutor::exit(const command_params_t&)
    {
        return ExecResult::exit_program;
    }

    // キャンバスの大きさを変更する
    CommandExecutor::ExecResult CommandExecutor::resize(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 3) {
            std::cout << "resize コマンドには2つのパラメータが必要です。\n";
            print_help_resize();
            return ExecResult::failed;
        }

        const int width {std::stoi(cmd_vec.at(1))};
        if (width < 1) {
            std::cout << "横方向のピクセル数は 1 以上でなければなりません。\n";
            print_help_resize();
            return ExecResult::failed;
        }

        const int height {std::stoi(cmd_vec.at(2))};
        if (height < 1) {
            std::cout << "縦方向のピクセル数は 1 以上でなければなりません。\n";
            print_help_resize();
            return ExecResult::failed;
        }

        m_canvas.resize(static_cast<unsigned int>(width), static_cast<unsigned int>(height));
        return ExecResult::successd;
    }
        
    // キャンバスを塗りつぶす
    CommandExecutor::ExecResult CommandExecutor::fill(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 4) {
            std::cout << "fill コマンドには3つのパラメータが必要です。\n";
            print_help_fill();
            return ExecResult::failed;
        }

        const int red {std::stoi(cmd_vec.at(1))};
        if (red < 0 || 255 < red) {
            std::cout << "赤成分の強さは 0 から 255 の範囲でなければなりません。\n";
            print_help_fill();
            return ExecResult::failed;
        }

        const int green {std::stoi(cmd_vec.at(2))};
        if (green < 0 || 255 < green) {
            std::cout << "緑成分の強さは 0 から 255 の範囲でなければなりません。\n";
            print_help_fill();
            return ExecResult::failed;
        }

        const int blue {std::stoi(cmd_vec.at(3))};
        if (blue < 0 || 255 < blue) {
            std::cout << "青成分の強さは 0 から 255 の範囲でなければなりません。\n";
            print_help_fill();
            return ExecResult::failed;
        }

        m_canvas.fill({static_cast<unsigned char>(red), static_cast<unsigned char>(green), static_cast<unsigned char>(blue)});
        return ExecResult::successd;
    }

    // 指定座標を起点に、同一色の隣接ピクセルを塗りつぶす
    CommandExecutor::ExecResult CommandExecutor::bucket(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 3) {
            std::cout << "( コマンドには2つのパラメータが必要です。\n";
            print_help_bucket();
            return ExecResult::failed;
        }

        const int x {std::stoi(cmd_vec.at(1))};
        const int y {std::stoi(cmd_vec.at(2))};

        m_canvas.bucket_drawing(x, y, m_pen);
        return ExecResult::successd;
    }

    // ペンを変更する
    CommandExecutor::ExecResult CommandExecutor::pen(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 4) {
            std::cout << "pen コマンドには3つのパラメータが必要です。\n";
            print_help_pen();
            return ExecResult::failed;
        }

        const int red {std::stoi(cmd_vec.at(1))};
        if (red < 0 || 255 < red) {
            std::cout << "赤成分の強さは 0 から 255 の範囲でなければなりません。\n";
            print_help_pen();
            return ExecResult::failed;
        }

        const int green {std::stoi(cmd_vec.at(2))};
        if (green < 0 || 255 < green) {
            std::cout << "緑成分の強さは 0 から 255 の範囲でなければなりません。\n";
            print_help_pen();
            return ExecResult::failed;
        }

        const int blue {std::stoi(cmd_vec.at(3))};
        if (blue < 0 || 255 < blue) {
            std::cout << "青成分の強さは 0 から 255 の範囲でなければなりません。\n";
            print_help_pen();
            return ExecResult::failed;
        }

        const Pen pen({static_cast<unsigned char>(red), static_cast<unsigned char>(green), static_cast<unsigned char>(blue)});
        m_pen = pen;
        return ExecResult::successd;
    }

    // 点を描画する
    CommandExecutor::ExecResult CommandExecutor::dot(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 3) {
            std::cout << "dot コマンドには2つのパラメータが必要です。\n";
            print_help_dot();
            return ExecResult::failed;
        }

        const int x {std::stoi(cmd_vec.at(1))};
        const int y {std::stoi(cmd_vec.at(2))};

        m_canvas.paint_dot(x, y, m_pen);
        return ExecResult::successd;
    }

    // 直線を描画する
    CommandExecutor::ExecResult CommandExecutor::line(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 5) {
            std::cout << "line コマンドには4つのパラメータが必要です。\n";
            print_help_line();
            return ExecResult::failed;
        }

        const int x1 {std::stoi(cmd_vec.at(1))};
        const int y1 {std::stoi(cmd_vec.at(2))};
        const int x2 {std::stoi(cmd_vec.at(3))};
        const int y2 {std::stoi(cmd_vec.at(4))};

        m_canvas.paint_line(x1, y1, x2, y2, m_pen);
        return ExecResult::successd;
    }

    // 矩形を描画する
    CommandExecutor::ExecResult CommandExecutor::rect(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 5) {
            std::cout << "rect コマンドには4つのパラメータが必要です。\n";
            print_help_rect();
            return ExecResult::failed;
        }

        const int left {std::stoi(cmd_vec.at(1))};
        const int top {std::stoi(cmd_vec.at(2))};
        const int right {std::stoi(cmd_vec.at(3))};
        const int bottom {std::stoi(cmd_vec.at(4))};

        if (left > right) {
            std::cout << "left は right より左になければなりません。\n";
            return ExecResult::failed;
        }
        if (top > bottom) {
            std::cout << "top は bottom より上になければなりません。\n";
            return ExecResult::failed;
        }

        m_canvas.paint_rect(left, top, right, bottom, m_pen);
        return ExecResult::successd;
    }

    // 矩形を描画し、内側を塗りつぶす
    CommandExecutor::ExecResult CommandExecutor::filled_rect(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 5) {
            std::cout << "filled_rect コマンドには4つのパラメータが必要です。\n";
            print_help_filled_rect();
            return ExecResult::failed;
        }

        const int left {std::stoi(cmd_vec.at(1))};
        const int top {std::stoi(cmd_vec.at(2))};
        const int right {std::stoi(cmd_vec.at(3))};
        const int bottom {std::stoi(cmd_vec.at(4))};

        if (left > right) {
            std::cout << "left は right より左になければなりません。\n";
            return ExecResult::failed;
        }
        if (top > bottom) {
            std::cout << "top は bottom より上になければなりません。\n";
            return ExecResult::failed;
        }

        m_canvas.paint_filled_rect(left, top, right, bottom, m_pen);
        return ExecResult::successd;
    }

    // 円を描画する
    CommandExecutor::ExecResult CommandExecutor::circle(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 4) {
            std::cout << "circle コマンドには3つのパラメータが必要です。\n";
            print_help_circle();
            return ExecResult::failed;
        }

        const int center_x {std::stoi(cmd_vec.at(1))};
        const int center_y {std::stoi(cmd_vec.at(2))};
        const int radius {std::stoi(cmd_vec.at(3))};

        m_canvas.paint_circle(center_x, center_y, radius, m_pen);
        return ExecResult::successd;
    }

    // 円を描画し、内部を塗りつぶす
    CommandExecutor::ExecResult CommandExecutor::filled_circle(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 4) {
            std::cout << "filled_circle コマンドには3つのパラメータが必要です。\n";
            print_help_filled_circle();
            return ExecResult::failed;
        }

        const int center_x {std::stoi(cmd_vec.at(1))};
        const int center_y {std::stoi(cmd_vec.at(2))};
        const int radius {std::stoi(cmd_vec.at(3))};

        m_canvas.paint_filled_circle(center_x, center_y, radius, m_pen);
        return ExecResult::successd;
    }

    // ビットマップファイルから読み込む
    CommandExecutor::ExecResult CommandExecutor::load(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 2) {
            std::cout << "load コマンドには1つのパラメータが必要です。\n";
            print_help_load();
            return ExecResult::failed;
        }

        const std::string path {cmd_vec.at(1)};

        if (!m_canvas.load_from_bitmap_file(path)) {
            std::cout << "path " << "の読み込みに失敗しました。\n";
            return ExecResult::failed;
        }
        return ExecResult::successd;
    }

    // ビットマップファイルに保存する
    CommandExecutor::ExecResult CommandExecutor::save(const command_params_t& cmd_vec)
    {
        if (cmd_vec.size() < 2) {
            std::cout << "save コマンドには1つのパラメータが必要です。\n";
            print_help_save();
            return ExecResult::failed;
        }

        const std::string path {cmd_vec.at(1)};

        if (!m_canvas.save_to_bitmap_file(path)) {
            std::cout << "path " << "への保存に失敗しました。\n";
            return ExecResult::failed;
        }
        return ExecResult::successd;
    }

    // スクリプトが保存されたファイルから実行する
    CommandExecutor::ExecResult CommandExecutor::load_script(const command_params_t& cmd_vec)
    {
        if (m_is_load_script) {
            return ExecResult::successd;
        }

        if (cmd_vec.size() < 2) {
            std::cout << "load_script コマンドには1つのパラメータが必要です。\n";
            print_help_load_script();
            return ExecResult::failed;
        }

        const std::string path {cmd_vec.at(1)};

        // スクリプトを読み込んで、履歴情報として復元する
        auto it = m_history.load_from_file(path);
        if (it == m_history.end()) {
            std::cout << path << " の読み込みに失敗しました。\n";
            return ExecResult::failed;
        }


        auto result = ExecResult::successd;

        // スクリプトのロード実行中であることを表すフラグを立てる
        m_is_load_script = true;

        // 履歴情報を辿りながら、1つずつ実行していく
        for ( /**/; it != m_history.end(); ++it) {
            std::string cmd {*it};

            // マクロを置換する
            paint_script::Macro::replace(cmd);

            // 空白文字ごとに分割して、std::vector に格納する
            const auto command_vec = str_util::split(cmd, " ");
            if (command_vec.empty()) {
                continue;
            }

            // 実行。途中でエラーが起きたら、以降の実行は止める
            auto exec_result = exec(command_vec);
            if (exec_result == ExecResult::failed || exec_result == ExecResult::exit_program) {
                result = exec_result;
                break;
            }
        }

        m_is_load_script = false;
        return result;
    }

    // スクリプトを保存する
    CommandExecutor::ExecResult CommandExecutor::save_script(const command_params_t& cmd_vec)
    {
        if (m_is_load_script) {
            return ExecResult::successd;
        }

        if (cmd_vec.size() < 2) {
            std::cout << "save_script コマンドには1つのパラメータが必要です。\n";
            print_help_save();
            return ExecResult::failed;
        }

        const std::string path {cmd_vec.at(1)};

        if (!m_history.save_to_file(path)) {
            std::cout << "path " << "への保存に失敗しました。\n";
            return ExecResult::failed;
        }

        return ExecResult::successd;
    }

    void CommandExecutor::print_help() const
    {
        std::cout << "以下のコマンドがあります。\n"
                  << "対応するパラメータがある場合は、その順番どおりに、正しい値をスペースで区切って入力してください。\n"
                  << std::endl;

        for (const auto& data : CommandMap) {
            data.help(this);
        }

        Macro::print_help();
    }

    void CommandExecutor::print_help_help() const
    {
        std::cout << "help\n"
                  << "ヘルプメッセージを出力します。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_exit() const
    {
        std::cout << "exit\n"
                  << "スクリプトの実行を終了します。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_resize() const
    {
        std::cout << "resize width height\n"
                  << "キャンバスの大きさを変更します。\n"
                  << "  width:  横方向のピクセル数を 1 以上の大きさで指定します。\n"
                  << "  height: 縦方向のピクセル数を 1 以上の大きさで指定します。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_fill() const
    {
        std::cout << "fill red green blue\n"
                  << "キャンバスを1色で塗りつぶします。\n"
                  << "  red:   赤成分の強さを 0 から 255 の範囲で指定します。\n"
                  << "  green: 緑成分の強さを 0 から 255 の範囲で指定します。\n"
                  << "  blue:  青成分の強さを 0 から 255 の範囲で指定します。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_bucket() const
    {
        std::cout << "bucket x y\n"
                  << "指定座標を起点に、その位置のピクセルと同じ色で隣接しているピクセルを塗りつぶします。\n"
                  << "  x: 起点の X座標。\n"
                  << "  y: 起点の Y座標。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_pen() const
    {
        std::cout << "pen red green blue\n"
                  << "点や線を描くときに使うペンを変更します。\n"
                  << "  red:   赤成分の強さを 0 から 255 の範囲で指定します。\n"
                  << "  green: 緑成分の強さを 0 から 255 の範囲で指定します。\n"
                  << "  blue:  青成分の強さを 0 から 255 の範囲で指定します。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_dot() const
    {
        std::cout << "dot x y\n"
                  << "現在のペンを使って、点を描画します。\n"
                  << "  x: X座標を指定します。キャンバスの範囲外の場合は何も描かれません。\n"
                  << "  y: Y座標を指定します。キャンバスの範囲外の場合は何も描かれません。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_line() const
    {
        std::cout << "line x1 y1 x2 y2\n"
                  << "現在のペンを使って、指定した2つの座標を結ぶ直線を描画します。\n"
                  << "  x1: 片側の端点のX座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  y1: 片側の端点のY座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  x2: 他方の端点のX座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  y2: 他方の端点のY座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_rect() const
    {
        std::cout << "rect left top right bottom\n"
                  << "現在のペンを使って、矩形を描画します。\n"
                  << "内側は塗られません。内側を塗る場合は、filled_rect コマンドを使用してください。\n"
                  << "  left:   左端のX座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  top:    上端のY座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  right:  右端のX座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  bottom: 下端のY座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_filled_rect() const
    {
        std::cout << "filled_rect left top right bottom\n"
                  << "現在のペンを使って、矩形を描画します。\n"
                  << "内側を塗りつぶします。内側を塗らない場合は、rect コマンドを使用してください。\n"
                  << "  left:   左端のX座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  top:    上端のY座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  right:  右端のX座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  bottom: 下端のY座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_circle() const
    {
        std::cout << "circle cx cy radius\n"
                  << "現在のペンを使って、円を描画します。\n"
                  << "内側は塗られません。内側を塗る場合は、filled_circle コマンドを使用してください。\n"
                  << "  cx:     円の中心のX座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  cy:     円の中心のY座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  radius: 円の半径を指定します。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_filled_circle() const
    {
        std::cout << "filled_circle cx cy radius\n"
                  << "現在のペンを使って、円を描画します。\n"
                  << "内側を塗りつぶします。内側を塗らない場合は、circle コマンドを使用してください。\n"
                  << "  cx:     円の中心のX座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  cy:     円の中心のY座標を指定します。キャンバスの範囲外も指定できます。\n"
                  << "  radius: 円の半径を指定します。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_load() const
    {
        std::cout << "load path\n"
                  << ".bmpファイルを指定して、キャンバスを作成します。\n"
                  << "  path: 読み込む .bmpファイルのパス。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_save() const
    {
        std::cout << "save path\n"
                  << "現在のキャンバスの状態を .bmp ファイルに保存します。\n"
                  << "  path: 出力する .bmpファイルのパス。すでに存在する場合は上書きします。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_load_script() const
    {
        std::cout << "load_script path\n"
                  << "スクリプトが書き込まれたテキストファイルを読み込んで、その内容を実行します。\n"
                  << "  path: テキストファイルのパス。\n"
                  << std::endl;
    }

    void CommandExecutor::print_help_save_script() const
    {
        std::cout << "save_script path\n"
                  << "現在までに入力したコマンドとパラメータの履歴をテキストファイルに保存します。\n"
                  << "  path: 出力するテキストファイルのパス。すでに存在する場合は上書きします。\n"
                  << std::endl;
    }
}
// command_executor.h
#ifndef COMMAND_EXECUTOR_H_INCLUDED
#define COMMAND_EXECUTOR_H_INCLUDED

#include <functional>
#include <string>
#include <vector>
#include "pen.h"

namespace paint_script {

    class Canvas;
    class CommandHistory;

    class CommandExecutor {
    public:
        using command_params_t = std::vector<std::string>;  // コマンドとパラメータの型

        // 結果
        enum class ExecResult {
            successd,       // 成功
            failed,         // 失敗
            not_found,      // コマンドが見つからない
            exit_program,   // 成功。プログラムを終了させる
        };

    public:
        // コンストラクタ
        //
        // canvas:  キャンバスの参照
        // history: 履歴管理オブジェクトの参照
        explicit CommandExecutor(Canvas& canvas, CommandHistory& history);

    public:
        // コマンドを実行する
        //
        // command_vec: コマンドとパラメータを含んだ配列
        // 戻り値: 結果
        ExecResult exec(const command_params_t& command_vec);

    private:
        using CommandImpl_t = std::function<ExecResult (CommandExecutor*, const command_params_t&)>;    // 実装関数の型   
        using CommandHelp_t = std::function<void (const CommandExecutor*)>;                     // ヘルプ出力関数の型

        // コマンドデータ
        struct CommandData {
            const char*     name;   // コマンド名
            CommandImpl_t   impl;   // コマンドの実装関数
            CommandHelp_t   help;   // コマンドのヘルプを出力する関数
        };
        static const CommandData CommandMap[];

    private:
        ExecResult help(const command_params_t& cmd_vec);
        ExecResult exit(const command_params_t& cmd_vec);
        ExecResult resize(const command_params_t& cmd_vec);
        ExecResult fill(const command_params_t& cmd_vec);
        ExecResult bucket(const command_params_t& cmd_vec);
        ExecResult pen(const command_params_t& cmd_vec);
        ExecResult dot(const command_params_t& cmd_vec);
        ExecResult line(const command_params_t& cmd_vec);
        ExecResult rect(const command_params_t& cmd_vec);
        ExecResult filled_rect(const command_params_t& cmd_vec);
        ExecResult circle(const command_params_t& cmd_vec);
        ExecResult filled_circle(const command_params_t& cmd_vec);
        ExecResult load(const command_params_t& cmd_vec);
        ExecResult save(const command_params_t& cmd_vec);
        ExecResult load_script(const command_params_t& cmd_vec);
        ExecResult save_script(const command_params_t& cmd_vec);

        void print_help() const;
        void print_help_help() const;
        void print_help_exit() const;
        void print_help_resize() const;
        void print_help_fill() const;
        void print_help_bucket() const;
        void print_help_pen() const;
        void print_help_dot() const;
        void print_help_line() const;
        void print_help_rect() const;
        void print_help_filled_rect() const;
        void print_help_circle() const;
        void print_help_filled_circle() const;
        void print_help_load() const;
        void print_help_save() const;
        void print_help_load_script() const;
        void print_help_save_script() const;

    private:
        Canvas&                 m_canvas;
        CommandHistory&         m_history;
        Pen                     m_pen {{0, 0, 0}};

        bool                    m_is_load_script;
    };

}

#endif
// command_history.cpp
#include "command_history.h"
#include <fstream>

namespace paint_script {

    // 履歴を追加する
    void CommandHistory::add(const std::string& command)
    {
        m_commands.push_back(command);
    }

    // 最初の履歴を指すイテレータを返す
    std::vector<std::string>::const_iterator CommandHistory::begin() const
    {
        return std::cbegin(m_commands);
    }

    // 最後の履歴の後ろを指すイテレータを返す
    std::vector<std::string>::const_iterator CommandHistory::end() const
    {
        return std::cend(m_commands);
    }

    // テキストファイルから履歴を読み込む
    std::vector<std::string>::const_iterator CommandHistory::load_from_file(const std::string& path)
    {
        std::ifstream ifs {path};
        if (!ifs) {
            return end();
        }

        // 追加前の一番後ろのインデックスを保存
        // [!] このあと std::vector への追加を行うと、イテレータや参照、ポインタは無効化される可能性があるので、
        //     添字で保存しておく。
        auto start_index = m_commands.size();

        // 1行ずつ読み込みながら、履歴に追加
        while (!ifs.eof()) {
            std::string s {};
            std::getline(ifs, s);
            add(s);
        }

        return std::begin(m_commands) + start_index;
    }

    // 履歴をテキストファイルへ書き出す
    bool CommandHistory::save_to_file(const std::string& path)
    {
        std::ofstream ofs {path, std::ios_base::out};
        if (!ofs) {
            return false;
        }

        for (const std::string& str : m_commands) {
            ofs << str << "\n";
        }

        return true;
    }
}
// command_history.h
#ifndef COMMAND_HISTORY_H_INCLUDED
#define COMMAND_HISTORY_H_INCLUDED

#include <string>
#include <vector>

namespace paint_script {

    class CommandHistory {
    public:
        // 履歴を追加する
        //
        // command: 追加するコマンドおよびパラメータの文字列
        void add(const std::string& command);


        // 最初の履歴を指すイテレータを返す
        std::vector<std::string>::const_iterator begin() const;

        // 最後の履歴の後ろを指すイテレータを返す
        std::vector<std::string>::const_iterator end() const;


        // テキストファイルから履歴を読み込む
        //
        // path: テキストファイルのパス
        // 戻り値: 読み込まれた最初の履歴を指すイテレータ。
        //         読み込みに失敗した場合は、end() が返すイテレータ。
        std::vector<std::string>::const_iterator load_from_file(const std::string& path);

        // 履歴をテキストファイルへ書き出す
        //
        // path: 出力先のテキストファイルのパス
        // 戻り値: 成否
        bool save_to_file(const std::string& path);

    private:
        std::vector<std::string>    m_commands;
    };

}

#endif
// macro.cpp
#include "macro.h"
#include <iostream>
#include "string_util.h"

namespace paint_script {

    const std::pair<std::string, std::string> Macro::MacroTable[]{
        {"RED", "255 0 0"},
        {"GREEN", "0 255 0"},
        {"BLUE", "0 0 255"},
        {"WHITE", "255 255 255"},
        {"BLACK", "0 0 0"},
    };



    // マクロ置換を行う
    std::string& Macro::replace(std::string& str)
    {
        for (const auto& macro : MacroTable) {
            str_util::find_replace_all(str, macro.first, macro.second);
        }

        return str;
    }

    // マクロの一覧を出力する
    void Macro::print_help()
    {
        std::cout << "以下のマクロがあります。\n"
                  << std::endl;

        for (const auto& macro : MacroTable) {
            std::cout << macro.first << "\n"
                      << "置換結果: " << macro.second << "\n"
                      << std::endl;
        }
    }
}
// macro.h
#ifndef MACRO_H_INCLUDED
#define MACRO_H_INCLUDED

#include <string>
#include <utility>

namespace paint_script {

    class Macro {
    public:
        Macro() = delete;

        // マクロ置換を行う
        //
        // str: 対象の文字列
        // 戻り値: str を返す
        static std::string& replace(std::string& str);

        // マクロの一覧を出力する
        static void print_help();

    private:
        static const std::pair<std::string, std::string> MacroTable[];
    };

}

#endif
// pen.cpp
#include "pen.h"

namespace paint_script {

    Pen::Pen(Color color) :
        m_color {color}
    {

    }

}
// pen.h
#ifndef PEN_H_INCLUDED
#define PEN_H_INCLUDED

#include "color.h"

namespace paint_script {

    class Pen {
    public:
        // コンストラクタ
        //
        // color: 色
        explicit Pen(Color color);

    public:
        // 色を返す
        //
        // 戻り値: 色
        inline Color get_color() const
        {
            return m_color;
        }

    private:
        Color           m_color;
    };
}

#endif
// color.h
#ifndef COLOR_H_INCLUDED
#define COLOR_H_INCLUDED

namespace paint_script {

    // 色
    struct Color {
        unsigned char  red;         // 赤成分
        unsigned char  green;       // 緑成分
        unsigned char  blue;        // 青成分
    };


    // 同じ色かどうか
    inline bool is_equal_color(const Color& color1, const Color& color2)
    {
        return color1.red == color2.red
            && color1.green == color2.green
            && color1.blue == color2.blue
            ;
    }
}

#endif
// bmp.cpp
#include "bmp.h"
#include "color.h"
#include <cassert>
#include <cstdint>
#include <fstream>

namespace paint_script {

    bool Bmp::save(const std::string& path, unsigned int width, unsigned int height, const std::vector<std::vector<Color>>& pixels)
    {
        std::ofstream ofs {path, std::ios_base::out | std::ios_base::binary};
        if (!ofs) {
            return false;
        }

        // ----- ファイルヘッダ部 -----
        // Windows API の BITMAPFILEHEADER構造体にあたる。
        // https://learn.microsoft.com/en-us/windows/win32/api/wingdi/ns-wingdi-bitmapfileheader

        // ファイルタイプ
        // 必ず 0x4d42 ("BM" のこと)
        std::uint16_t file_type {0x4d42};
        ofs.write(reinterpret_cast<const char*>(&file_type), sizeof(file_type));

        // ファイルサイズ
        // 縦横のピクセル数 * 1ピクセル当たりのバイト数(PaintScript では 4バイト固定) + ヘッダ部のバイト数。
        // ヘッダ部の大きさは、sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) より。
        std::uint32_t file_size {width * height * 4 + 54};
        ofs.write(reinterpret_cast<const char*>(&file_size), sizeof(file_size));

        // 予約領域
        std::uint32_t reserved {0};
        ofs.write(reinterpret_cast<const char*>(&reserved), sizeof(reserved));

        // ファイル先頭から、ピクセル情報までの距離
        std::uint32_t offset_to_pixels {54};
        ofs.write(reinterpret_cast<const char*>(&offset_to_pixels), sizeof(offset_to_pixels));


        // ----- ビットマップ情報ヘッダ部 -----
        // Windows API の _BITMAPINFOHEADER構造体にあたる。
        // https://learn.microsoft.com/ja-jp/windows/win32/wmdm/-bitmapinfoheader

        // ビットマップ情報ヘッダ部のサイズ
        std::uint32_t bitmap_info_header_size {40};
        ofs.write(reinterpret_cast<const char*>(&bitmap_info_header_size), sizeof(bitmap_info_header_size));

        // 横方向のピクセル数
        std::int32_t w {static_cast<std::int32_t>(width)};
        ofs.write(reinterpret_cast<const char*>(&w), sizeof(w));

        // 縦方向のピクセル数
        std::int32_t h {static_cast<std::int32_t>(height)};
        ofs.write(reinterpret_cast<const char*>(&h), sizeof(h));

        // プレーン数。必ず 1
        std::uint16_t planes {1};
        ofs.write(reinterpret_cast<const char*>(&planes), sizeof(planes));

        // 1ピクセル当たりのビット数。PaintScript では 24 に固定
        std::uint16_t bit_count {24};
        ofs.write(reinterpret_cast<const char*>(&bit_count), sizeof(bit_count));

        // 圧縮形式。無圧縮は 0
        std::uint32_t compression {0};
        ofs.write(reinterpret_cast<const char*>(&compression), sizeof(compression));

        // 画像サイズ。無圧縮であれば 0 で構わない
        std::uint32_t image_size {0};
        ofs.write(reinterpret_cast<const char*>(&image_size), sizeof(image_size));

        // メートル当たりの横方向のピクセル数の指示。不要なら 0 にできる
        std::int32_t x_pixels_per_meter {0};
        ofs.write(reinterpret_cast<const char*>(&x_pixels_per_meter), sizeof(x_pixels_per_meter));

        // メートル当たりの縦方向のピクセル数の指示。不要なら 0 にできる
        std::int32_t y_pixels_per_meter {0};
        ofs.write(reinterpret_cast<const char*>(&y_pixels_per_meter), sizeof(y_pixels_per_meter));

        // カラーテーブル内の色のうち、実際に使用している個数。パレット形式でなければ無関係
        std::uint32_t clr_used {0};
        ofs.write(reinterpret_cast<const char*>(&clr_used), sizeof(clr_used));

        // カラーテーブル内の色のうち、重要色である色の個数。パレット形式でなければ無関係
        std::uint32_t clr_important {0};
        ofs.write(reinterpret_cast<const char*>(&clr_important), sizeof(clr_important));


        // ----- ピクセル情報 -----
        // Windows API の RGBQUAD に当たる。
        // https://learn.microsoft.com/ja-jp/windows/win32/api/wingdi/ns-wingdi-rgbquad
        for (std::int32_t y {h - 1}; y >= 0; --y) {
            for (std::int32_t x {0}; x < w; ++x) {
                const Color pixel {pixels.at(y).at(x)};
                ofs.write(reinterpret_cast<const char*>(&pixel.blue), sizeof(pixel.blue));
                ofs.write(reinterpret_cast<const char*>(&pixel.green), sizeof(pixel.green));
                ofs.write(reinterpret_cast<const char*>(&pixel.red), sizeof(pixel.red));
            }
        }

        return true;
    }

    bool Bmp::load(const std::string& path, unsigned int* width, unsigned int* height, std::vector<std::vector<Color>>* pixels)
    {
        assert(width);
        assert(height);
        assert(pixels);

        std::ifstream ifs {path, std::ios_base::in | std::ios_base::binary};
        if (!ifs) {
            return false;
        }

        // 不要なところを読み飛ばす
        ifs.seekg(18, std::ios_base::beg);

        // 横方向のピクセル数
        std::int32_t w {};
        ifs.read(reinterpret_cast<char*>(&w), sizeof(w));
        if (w < 1) {
            return false;
        }
        *width = static_cast<unsigned int>(w);
        
        // 縦方向のピクセル数
        std::int32_t h {};
        ifs.read(reinterpret_cast<char*>(&h), sizeof(h));
        if (h < 1) {
            return false;
        }
        *height = static_cast<unsigned int>(h);

        // 不要なところを読み飛ばす
        ifs.seekg(28, std::ios_base::cur);

        // ピクセル情報
        // vector は、ビットマップの大きさに合わせて resize する。
        pixels->resize(h);
        for (auto& row : *pixels) {
            row.resize(w);
        }
        for (std::int32_t y {h - 1}; y >= 0; --y) {
            for (std::int32_t x {0}; x < w; ++x) {
                std::uint8_t b {};
                ifs.read(reinterpret_cast<char*>(&b), sizeof(b));
                std::uint8_t g {};
                ifs.read(reinterpret_cast<char*>(&g), sizeof(g));
                std::uint8_t r {};
                ifs.read(reinterpret_cast<char*>(&r), sizeof(r));

                pixels->at(y).at(x) = Color{r, g, b};
            }
        }

        return true;
    }
}
// bmp.h
#ifndef BMP_H_INCLUDED
#define BMP_H_INCLUDED

#include <string>
#include <vector>

namespace paint_script {

    struct Color;

    class Bmp {
    public:
        Bmp() = delete;

        // ファイルに書き出す
        //
        // path: ファイルパス
        // width: 横方向のピクセル数
        // height: 縦方向のピクセル数
        // pixels: ピクセル情報
        // 戻り値: 成否
        static bool save(const std::string& path, unsigned int width, unsigned int height, const std::vector<std::vector<Color>>& pixels);

        // ファイルから読み込む
        //
        // path: ファイルパス
        // width: 横方向のピクセル数を受け取るポインタ。ヌルポインタ不可
        // height: 縦方向のピクセル数を受け取るポインタ。ヌルポインタ不可
        // pixels: ピクセル情報を受け取るポインタ。ヌルポインタ不可
        // 戻り値: 成否
        static bool load(const std::string& path, unsigned int* width, unsigned int* height, std::vector<std::vector<Color>>* pixels);
    };

}

#endif

ラムダ式の再帰呼び出し

ラムダ式も再帰呼び出しできますが、自分自身の名前が必要なので、書き方は限定されます。

[](int times) {
    if (times <= 0) {
        return;
    }

    std::cout << "Hello\n";
    ????(times - 1);  // 自分自身の名前が分からない
}(5);

auto を使って変数に受け取れば名前が付けられますが、ラムダ式本体から、外部にある静的でないローカル変数の名前は使えないので、以下のコードはコンパイルエラーになります(「関数ポインタとラムダ式」のページを参照)。

auto print_hello = [](int times) {
    if (times <= 0) {
        return;
    }

    std::cout << "Hello\n";
    print_hello(times - 1);  // コンパイルエラー
};
print_hello(5);

キャプチャすればいいと思うかもしれませんが、auto で宣言しようとしている変数名を、その初期化式の中で使うことはできないため(型推論の判断に必要な式の中に、まだ型が決まっていないものが登場することになるので)7、これもコンパイルエラーになります。

auto print_hello = [print_hello](int times) {  // コンパイルエラー。ここで print_hello は使えない
    if (times <= 0) {
        return;
    }

    std::cout << "Hello\n";
    print_hello(times - 1);
};
print_hello(5);

そこで、std::function と参照キャプチャを使います。

#include <functional>
#include <iostream>

int main()
{
    std::function<void (int)> print_hello = [&print_hello](int times) {
        if (times <= 0) {
            return;
        }

        std::cout << "Hello\n";
        print_hello(times - 1);
    };
    print_hello(5);
}

実行結果:

Hello
Hello
Hello
Hello
Hello

ただし、std::function は実行速度が遅く、またメモリ使用量も膨らむため再帰呼び出しをあまり深くできない欠点があります8

この欠点への対処として、ジェネリックラムダ (generic lambda) と呼ばれる機能を使う方法があります。ジェネリックラムダは C++14 でラムダ式を拡張した機能で、仮引数の型を auto することによって、任意の型の値を渡せるようにしたものです。型名が不明な print_hello を引数に渡すことが可能になるため、以下のように書けます。

#include <iostream>

int main()
{
    auto print_hello = [](auto self, int times) {
        if (times <= 0) {
            return;
        }

        std::cout << "Hello\n";
        self(self, times - 1);
    };
    print_hello(print_hello, 5);
}

実行結果:

Hello
Hello
Hello
Hello
Hello

再び auto で受け取るかたちに戻りましたが、print_hello をキャプチャしているわけではないので問題は消えました。呼び出しのたびに、呼び出すラムダ式の名前と、第1引数の両方に print_hello と書かなければならないのが冗長ではありますが、std::function を使う方法よりも実行効率は良くなっています。

【C++23】この冗長な記述は、C++23 の新機能である deducing this によって解消します。[](this auto self, int times) のように宣言することで、self の名前でクロージャオブジェクトを参照できるようになります(この self を明示的なオブジェクトパラメータ (explicit object parameter) と呼びます)9。これで print_hello(5) のように呼び出せます。

まとめ


新C++編の【本編】の各ページには、末尾に練習問題があります。ページ内で学んだ知識を確認する簡単な問題から、これまでに学んだ知識を組み合わせなければならない問題、あるいは更なる自力での調査や模索が必要になるような高難易度な問題をいくつか掲載しています。


参考リンク


練習問題

問題の難易度について。

★は、すべての方が取り組める入門レベルの問題です。
★★は、自力でプログラミングができるようなるために、入門者の方であっても取り組んでほしい問題です。
★★★は、本格的にプログラマーを目指す人のための問題です。

問題1 (基本★)

階乗を計算する関数を再帰呼び出しを利用して作成してください。

解答・解説

問題2 (応用★★)

std::stack を使って、文字列に含まれている括弧((){}[])がすべて正しく閉じられているかどうかを調べるプログラムを作成してください。

たとえば、aa(a{aa})aa[aa(a)] は正常であるといえますが、aa(a{aa}aa{[a}a](a) は正しくありません(1つ目の ( が閉じられておらず、[ を閉じる前に { が閉じられている)。

解答・解説

問題3 (調査★★★)

再帰呼び出しを活用して描けるフラクタル図形と呼ばれる図形があります。フラクタル図形について調べ、その中から1つを選んで、ペイントスクリプトに実装してください。

解答・解説


解答・解説ページの先頭



更新履歴




はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る