From dd0d8a15b6f4c68f33f8818d78b60f54ae5e4233 Mon Sep 17 00:00:00 2001 From: Habu Date: Fri, 17 Sep 2021 13:00:22 +0900 Subject: [PATCH] =?utf8?q?[Refactor]=20=E3=83=A2=E3=83=B3=E3=82=B9?= =?utf8?q?=E3=82=BF=E3=83=BC=E9=80=B2=E5=8C=96=E3=81=AE=E3=82=B9=E3=83=9D?= =?utf8?q?=E3=82=A4=E3=83=A9=E3=83=BC=E7=94=9F=E6=88=90=E3=83=AB=E3=83=BC?= =?utf8?q?=E3=83=81=E3=83=B3?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Cでなんとかしようとした結果涙ぐましいコードが書かれているが、 わかりづらすぎるうえに計算量が O(N^2) なのでスケールしない。 モンスターが10万種とかになったら破綻する。 STLを使用してきれいに書き直す。 計算量は O(N logN) になる。 --- src/util/sort.cpp | 70 ----------------------- src/util/sort.h | 3 - src/wizard/wizard-spoiler.cpp | 126 ++++++++++++------------------------------ 3 files changed, 35 insertions(+), 164 deletions(-) diff --git a/src/util/sort.cpp b/src/util/sort.cpp index dffc6c71e..d8c7147f3 100644 --- a/src/util/sort.cpp +++ b/src/util/sort.cpp @@ -620,73 +620,3 @@ void ang_sort_swap_cave_temp(player_type *player_ptr, vptr u, vptr v, int a, int who[a] = who[b]; who[b] = holder; } - -/*! - * @brief 進化ツリーをソートするためモンスター種族の判定関数 / - * Sorting hook -- Comp function - * @param u 進化木構造データ - * @param v 未使用 - * @param a 比較したいモンスター種族ID1 - * @param b 比較したいモンスター種族ID2 - * @return 2が大きければTRUEを返す - */ -bool ang_sort_comp_evol_tree(player_type *player_ptr, vptr u, vptr v, int a, int b) -{ - /* Unused */ - (void)player_ptr; - (void)v; - - int **evol_tree = (int **)u; - - int w1 = evol_tree[a][0]; - int w2 = evol_tree[b][0]; - monster_race *r1_ptr = &r_info[w1]; - monster_race *r2_ptr = &r_info[w2]; - - /* Used tree first */ - if (w1 && !w2) - return true; - - if (!w1 && w2) - return false; - - /* Sort by monster level */ - if (r1_ptr->level < r2_ptr->level) - return true; - - if (r1_ptr->level > r2_ptr->level) - return false; - - /* Sort by monster experience */ - if (r1_ptr->mexp < r2_ptr->mexp) - return true; - - if (r1_ptr->mexp > r2_ptr->mexp) - return false; - - /* Compare indexes */ - return w1 <= w2; -} - -/*! - * @brief 進化ツリーをソートするため木構造のスワップ関数 / - * Sorting hook -- Swap function - * @param u 進化木構造データ - * @param v 未使用 - * @param a スワップしたい木構造1 - * @param b スワップしたい木構造2 - * @return 2が大きければTRUEを返す - */ -void ang_sort_swap_evol_tree(player_type *player_ptr, vptr u, vptr v, int a, int b) -{ - /* Unused */ - (void)player_ptr; - (void)v; - - int **evol_tree = (int **)u; - int *holder; - - holder = evol_tree[a]; - evol_tree[a] = evol_tree[b]; - evol_tree[b] = holder; -} diff --git a/src/util/sort.h b/src/util/sort.h index 79ef04f89..3a5acc14f 100644 --- a/src/util/sort.h +++ b/src/util/sort.h @@ -26,6 +26,3 @@ bool ang_sort_comp_pet_dismiss(player_type *player_ptr, vptr u, vptr v, int a, i bool ang_sort_comp_cave_temp(player_type *player_ptr, vptr u, vptr v, int a, int b); void ang_sort_swap_cave_temp(player_type *player_ptr, vptr u, vptr v, int a, int b); - -bool ang_sort_comp_evol_tree(player_type *player_ptr, vptr u, vptr v, int a, int b); -void ang_sort_swap_evol_tree(player_type *player_ptr, vptr u, vptr v, int a, int b); diff --git a/src/wizard/wizard-spoiler.cpp b/src/wizard/wizard-spoiler.cpp index 0b5c122b5..f26f58369 100644 --- a/src/wizard/wizard-spoiler.cpp +++ b/src/wizard/wizard-spoiler.cpp @@ -40,53 +40,43 @@ #include "wizard/monster-info-spoiler.h" #include "wizard/spoiler-util.h" #include +#include #include -/*! - * @brief int配列でstrncmp()と似た比較処理を行う / - * Compare two int-type array like strncmp() and return TRUE if equals - * @param a 比較するint配列1 - * @param b 比較するint配列2 - * @param length - * @return 両者の値が等しければTRUEを返す - */ -static bool int_n_cmp(int *a, int *b, int length) -{ - if (!length) - return true; - - do { - if (*a != *(b++)) - return false; - if (!(*(a++))) - break; - } while (--length); - - return true; -} - -/*! - * @brief ある木が指定された木の部分木かどうかを返す / - * Returns TRUE if an evolution tree is "partial tree" - * @param tree 元となる木構造リスト - * @param partial_tree 部分木かどうか判定したい木構造リスト - * @return 部分木ならばTRUEを返す +/** + * @brief 進化ツリーの一番根元となるモンスターのIDのリストを取得する + * + * @return 進化ツリーの一番根元となるモンスターのIDのリスト(std::setで、evol_root_sortによりソートされている) */ -static bool is_partial_tree(int *tree, int *partial_tree) +static auto get_mon_evol_roots(void) { - int pt_head = *(partial_tree++); - int pt_len = 0; - while (partial_tree[pt_len]) - pt_len++; - - while (*tree) { - if (*(tree++) == pt_head) { - if (int_n_cmp(tree, partial_tree, pt_len)) - return true; + std::set evol_parents; + std::set evol_children; + for (auto r_idx = 1; r_idx < max_r_idx; ++r_idx) { + const auto &r_ref = r_info[r_idx]; + if (r_ref.next_r_idx > 0) { + evol_parents.emplace(r_idx); + evol_children.emplace(r_ref.next_r_idx); } } - return false; + auto evol_root_sort = [](MONRACE_IDX i1, MONRACE_IDX i2) { + auto &r1 = r_info[i1]; + auto &r2 = r_info[i2]; + if (r1.level != r2.level) { + return r1.level < r2.level; + } + if (r1.mexp != r2.mexp) { + return r1.mexp < r2.mexp; + } + return i1 <= i2; + }; + + std::set evol_roots(evol_root_sort); + std::set_difference(evol_parents.begin(), evol_parents.end(), evol_children.begin(), evol_children.end(), + std::inserter(evol_roots, evol_roots.end())); + + return evol_roots; } /*! @@ -97,10 +87,6 @@ static bool is_partial_tree(int *tree, int *partial_tree) static spoiler_output_status spoil_mon_evol(concptr fname) { char buf[1024]; - monster_race *r_ptr; - player_type dummy; - int **evol_tree, i, j, n, r_idx; - int *evol_tree_zero; /* For C_KILL() */ path_build(buf, sizeof buf, ANGBAND_DIR_USER, fname); spoiler_file = angband_fopen(buf, "w"); if (!spoiler_file) { @@ -113,53 +99,13 @@ static spoiler_output_status spoil_mon_evol(concptr fname) spoil_out(buf); spoil_out("------------------------------------------\n\n"); - C_MAKE(evol_tree, max_r_idx, int *); - C_MAKE(*evol_tree, max_r_idx * (max_evolution_depth + 1), int); - for (i = 1; i < max_r_idx; i++) - evol_tree[i] = *evol_tree + i * (max_evolution_depth + 1); - - evol_tree_zero = *evol_tree; - for (i = 1; i < max_r_idx; i++) { - r_ptr = &r_info[i]; - if (!r_ptr->next_exp) - continue; - n = 0; - evol_tree[i][n++] = i; - do { - evol_tree[i][n++] = r_ptr->next_r_idx; - r_ptr = &r_info[r_ptr->next_r_idx]; - } while (r_ptr->next_exp && (n < max_evolution_depth)); - } - - for (i = 1; i < max_r_idx; i++) { - if (!evol_tree[i][0]) - continue; - - for (j = 1; j < max_r_idx; j++) { - if (i == j) - continue; - - if (!evol_tree[j][0]) - continue; - - if (is_partial_tree(evol_tree[j], evol_tree[i])) { - evol_tree[i][0] = 0; - break; - } - } - } - - ang_sort(&dummy, evol_tree, nullptr, max_r_idx, ang_sort_comp_evol_tree, ang_sort_swap_evol_tree); - for (i = 0; i < max_r_idx; i++) { - r_idx = evol_tree[i][0]; - if (!r_idx) - continue; - - r_ptr = &r_info[r_idx]; + for (auto r_idx : get_mon_evol_roots()) { + auto r_ptr = &r_info[r_idx]; fprintf(spoiler_file, _("[%d]: %s (レベル%d, '%c')\n", "[%d]: %s (Level %d, '%c')\n"), r_idx, r_ptr->name.c_str(), (int)r_ptr->level, r_ptr->d_char); - for (n = 1; r_ptr->next_exp; n++) { - fprintf(spoiler_file, "%*s-(%ld)-> ", n * 2, "", (long int)r_ptr->next_exp); + + for (auto n = 1; r_ptr->next_r_idx > 0; n++) { + fprintf(spoiler_file, "%*s-(%d)-> ", n * 2, "", r_ptr->next_exp); fprintf(spoiler_file, "[%d]: ", r_ptr->next_r_idx); r_ptr = &r_info[r_ptr->next_r_idx]; @@ -169,8 +115,6 @@ static spoiler_output_status spoil_mon_evol(concptr fname) fputc('\n', spoiler_file); } - C_KILL(evol_tree_zero, max_r_idx * (max_evolution_depth + 1), int); - C_KILL(evol_tree, max_r_idx, int *); return ferror(spoiler_file) || angband_fclose(spoiler_file) ? spoiler_output_status::SPOILER_OUTPUT_FAIL_FCLOSE : spoiler_output_status::SPOILER_OUTPUT_SUCCESS; } -- 2.11.0