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

再帰呼び出し 🔗

では、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); // １つ上のピクセルを塗る
        paint_dot(x, y + 1, pen); // １つ下のピクセルを塗る
        paint_dot(x - 1, y, pen); // １つ左のピクセルを塗る
        paint_dot(x + 1, y, pen); // １つ右のピクセルを塗る
    }
}

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

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
            ;
    }
}

この時点で塗りつぶしの対象になっているのは、起点のピクセルと、その上下左右のピクセルの計５ピクセルだけです。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 でも動作します。

【Ｃ言語プログラマ】Ｃ言語では 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

スタックオーバーフロー 🔗

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

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::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});

        // ４方向に座標を移動させるための配列
        constexpr int dx[] {0, 0, -1, 1};
        constexpr int dy[] {-1, 1, 0, 0};

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

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

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

            // 上下左右のピクセルが target_color と一致するなら、その座標情報をスタックに入れる。
            // キャンバスの端を越えないようにチェック。
            for (int i {0}; i < 4; ++i) {
                int nx {x + dx[i]};
                int ny {y + dy[i]};

                if (is_inside(nx, ny) && is_equal_color(target_color, get_pixel(nx, ny))) {
                    pixel_stack.push({nx, ny});
                }               
            }
        }
    }
}

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

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

これで正常に動作はしますがかなりの無駄があります。たとえば、起点から１つ上のピクセルに処理を進めたあと、そのピクセルからさらに上下左右を確認していくので、さきほど調べたはずのピクセルに戻ってきます。また、起点から上–>右と進むことと、起点から右–>上と進むことは、結局同じピクセルを確認することになります。このように、同じピクセルを何度も調べる無駄によって処理回数が増加しています。

この無駄をなくすには、すでに処理済みのピクセルを除外する仕組みが必要です。二次元配列を用意して、その座標がすでに処理済みかどうかを管理すれば、すでに処理済みのピクセルを無視できるようになり、処理回数を減らせます。

#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 {};

        // すでに確認済みのピクセルかどうかを管理する二次元配列
        std::vector<std::vector<bool>> visited(m_width, std::vector<bool>(m_height, false));

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

        // ４方向に座標を移動させるための配列
        constexpr int dx[] {0, 0, -1, 1};
        constexpr int dy[] {-1, 1, 0, 0};

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

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

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

            // 上下左右のピクセルが target_color と一致するなら、その座標情報をスタックに入れる。
            // キャンバスの端を越えないようにチェック。
            for (int i {0}; i < 4; ++i) {
                int nx {x + dx[i]};
                int ny {y + dy[i]};

                if (is_inside(nx, ny) && is_equal_color(target_color, get_pixel(nx, ny)) && !visited[nx][ny]) {
                    pixel_stack.push({nx, ny});
                    visited[nx][ny] = true;
                }               
            }
        }
    }
}

塗りつぶす範囲が広い場合、このような実装で大幅に速くなります。

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

//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 {};

        // すでに確認済みのピクセルかどうかを管理する二次元配列
        std::vector<std::vector<bool>> visited(m_width, std::vector<bool>(m_height, false));

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

        // ４方向に座標を移動させるための配列
        constexpr int dx[] {0, 0, -1, 1};
        constexpr int dy[] {-1, 1, 0, 0};

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

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

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

            // 上下左右のピクセルが target_color と一致するなら、その座標情報をスタックに入れる。
            // キャンバスの端を越えないようにチェック。
            for (int i {0}; i < 4; ++i) {
                int nx {x + dx[i]};
                int ny {y + dy[i]};

                if (is_inside(nx, ny) && is_equal_color(target_color, get_pixel(nx, ny)) && !visited[nx][ny]) {
                    pixel_stack.push({nx, ny});
                    visited[nx][ny] = true;
                }               
            }
        }
    }

    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 コマンドには２つのパラメータが必要です。\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 コマンドには３つのパラメータが必要です。\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 << "( コマンドには２つのパラメータが必要です。\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 コマンドには３つのパラメータが必要です。\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 コマンドには２つのパラメータが必要です。\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 コマンドには４つのパラメータが必要です。\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 コマンドには４つのパラメータが必要です。\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 コマンドには４つのパラメータが必要です。\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 コマンドには３つのパラメータが必要です。\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 コマンドには３つのパラメータが必要です。\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 コマンドには１つのパラメータが必要です。\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 コマンドには１つのパラメータが必要です。\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 コマンドには１つのパラメータが必要です。\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;

        // 履歴情報を辿りながら、１つずつ実行していく
        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 コマンドには１つのパラメータが必要です。\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"
                  << "キャンバスを１色で塗りつぶします。\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"
                  << "現在のペンを使って、指定した２つの座標を結ぶ直線を描画します。\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();

        // １行ずつ読み込みながら、履歴に追加
        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));

        // ファイルサイズ
        // 縦横のピクセル数 * １ピクセル当たりのバイト数(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));

        // １ピクセル当たりのビット数。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

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー

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

このページの概要 🔗

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