From cf25be32e6d3f376ebea40774a84b474b0cdfdd8 Mon Sep 17 00:00:00 2001 From: Hourier <66951241+Hourier@users.noreply.github.com> Date: Sat, 25 May 2024 22:42:14 +0900 Subject: [PATCH] =?utf8?q?[Refactor]=20#4155=20sort.cpp=20=E3=81=AE?= =?utf8?q?=E4=B8=AD=E3=82=92=E5=BF=85=E8=A6=81=E3=81=AA=E3=83=95=E3=82=A3?= =?utf8?q?=E3=83=BC=E3=83=AB=E3=83=89=E3=81=A0=E3=81=91=E5=BC=95=E6=95=B0?= =?utf8?q?=E3=81=AB=E3=81=99=E3=82=8B=E3=82=88=E3=81=86=E5=A4=89=E6=9B=B4?= =?utf8?q?=E3=81=97=E3=81=9F?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- src/util/sort.cpp | 187 +++++++++++++++++++++++++++--------------------------- src/util/sort.h | 2 - 2 files changed, 94 insertions(+), 95 deletions(-) diff --git a/src/util/sort.cpp b/src/util/sort.cpp index 2ccd1f193..61c5ac0f0 100644 --- a/src/util/sort.cpp +++ b/src/util/sort.cpp @@ -13,103 +13,16 @@ #include "system/terrain-type-definition.h" #include "util/point-2d.h" -/* - * @brief クイックソートの実行 / Quick sort in place - * @param u アイテムやモンスター等への配列 - * @param v 条件基準IDへの参照ポインタ - * @param a 比較対象のID1 - * @param b 比較対象のID2 - * @param ang_sort_comp 比較用の関数ポインタ - * @param ang_sort_swap スワップ用の関数ポインタ - */ -static void exe_ang_sort(PlayerType *player_ptr, std::vector &ys, std::vector &xs, int p, int q, SortKind kind) -{ - if (p >= q) { - return; - } - - int z = p; - int a = p; - int b = q; - while (true) { - /* Slide i2 */ - auto is_less_i2 = false; - do { - switch (kind) { - case SortKind::DISTANCE: - is_less_i2 = ang_sort_comp_distance(player_ptr, ys, xs, b, z); - break; - case SortKind::IMPORTANCE: - is_less_i2 = ang_sort_comp_importance(player_ptr, ys, xs, b, z); - break; - default: - THROW_EXCEPTION(std::logic_error, "Invalid Sort Kind was specified!"); - } - - if (!is_less_i2) { - b--; - } - } while (!is_less_i2); - - /* Slide i1 */ - auto is_less_i1 = false; - do { - switch (kind) { - case SortKind::DISTANCE: - is_less_i1 = ang_sort_comp_distance(player_ptr, ys, xs, z, a); - break; - case SortKind::IMPORTANCE: - is_less_i1 = ang_sort_comp_importance(player_ptr, ys, xs, z, a); - break; - default: - THROW_EXCEPTION(std::logic_error, "Invalid Sort Kind was specified!"); - } - - if (!is_less_i1) { - a++; - } - } while (!is_less_i1); - - if (a >= b) { - break; - } - - std::swap(xs[a], xs[b]); - std::swap(ys[a], ys[b]); - a++, b--; - } - - /* Recurse left side */ - exe_ang_sort(player_ptr, ys, xs, p, b, kind); - - /* Recurse right side */ - exe_ang_sort(player_ptr, ys, xs, b + 1, q, kind); -} - -/* - * @brief クイックソートの受け付け / Accepting auick sort in place - * @param u アイテムやモンスター等への配列 - * @param v 条件基準IDへの参照ポインタ - * @param a 比較対象のID1 - * @param b 比較対象のID2 - * @param ang_sort_comp 比較用の関数ポインタ - * @param ang_sort_swap スワップ用の関数ポインタ - */ -void ang_sort(PlayerType *player_ptr, std::vector &ys, std::vector &xs, SortKind kind) -{ - exe_ang_sort(player_ptr, ys, xs, 0, std::ssize(ys) - 1, kind); -} - +namespace { /* * Sorting hook -- comp function -- by "distance to player" * * We use "u" and "v" to point to arrays of "x" and "y" positions, * and sort the arrays by double-distance to the player. */ -bool ang_sort_comp_distance(PlayerType *player_ptr, std::vector &ys, std::vector &xs, int a, int b) +bool ang_sort_comp_distance(const Pos2D &p_pos, std::vector &ys, std::vector &xs, int a, int b) { /* Absolute distance components */ - const auto p_pos = player_ptr->get_position(); auto xa = xs[a]; xa -= p_pos.x; xa = std::abs(xa); @@ -139,14 +52,12 @@ bool ang_sort_comp_distance(PlayerType *player_ptr, std::vector &ys, std::v * We use "u" and "v" to point to arrays of "x" and "y" positions, * and sort the arrays by level of monster */ -bool ang_sort_comp_importance(PlayerType *player_ptr, std::vector &ys, std::vector &xs, int a, int b) +bool ang_sort_comp_importance(const FloorType &floor, const Pos2D &p_pos, std::vector &ys, std::vector &xs, int a, int b) { - const auto &floor = *player_ptr->current_floor_ptr; const auto &grid1 = floor.get_grid({ ys[a], xs[a] }); const auto &grid2 = floor.get_grid({ ys[b], xs[b] }); const auto &monster_a = floor.m_list[grid1.m_idx]; const auto &monster_b = floor.m_list[grid2.m_idx]; - const auto p_pos = player_ptr->get_position(); if (p_pos == Pos2D(ys[a], xs[a])) { return true; } @@ -229,5 +140,95 @@ bool ang_sort_comp_importance(PlayerType *player_ptr, std::vector &ys, std: return false; } - return ang_sort_comp_distance(player_ptr, ys, xs, a, b); + return ang_sort_comp_distance(p_pos, ys, xs, a, b); +} + +/* + * @brief クイックソートの実行 / Quick sort in place + * @param u アイテムやモンスター等への配列 + * @param v 条件基準IDへの参照ポインタ + * @param a 比較対象のID1 + * @param b 比較対象のID2 + * @param ang_sort_comp 比較用の関数ポインタ + * @param ang_sort_swap スワップ用の関数ポインタ + */ +void exe_ang_sort(PlayerType *player_ptr, std::vector &ys, std::vector &xs, int p, int q, SortKind kind) +{ + if (p >= q) { + return; + } + + const auto &floor = *player_ptr->current_floor_ptr; + const auto p_pos = player_ptr->get_position(); + int z = p; + int a = p; + int b = q; + while (true) { + /* Slide i2 */ + auto is_less_i2 = false; + do { + switch (kind) { + case SortKind::DISTANCE: + is_less_i2 = ang_sort_comp_distance(p_pos, ys, xs, b, z); + break; + case SortKind::IMPORTANCE: + is_less_i2 = ang_sort_comp_importance(floor, p_pos, ys, xs, b, z); + break; + default: + THROW_EXCEPTION(std::logic_error, "Invalid Sort Kind was specified!"); + } + + if (!is_less_i2) { + b--; + } + } while (!is_less_i2); + + /* Slide i1 */ + auto is_less_i1 = false; + do { + switch (kind) { + case SortKind::DISTANCE: + is_less_i1 = ang_sort_comp_distance(p_pos, ys, xs, z, a); + break; + case SortKind::IMPORTANCE: + is_less_i1 = ang_sort_comp_importance(floor, p_pos, ys, xs, z, a); + break; + default: + THROW_EXCEPTION(std::logic_error, "Invalid Sort Kind was specified!"); + } + + if (!is_less_i1) { + a++; + } + } while (!is_less_i1); + + if (a >= b) { + break; + } + + std::swap(xs[a], xs[b]); + std::swap(ys[a], ys[b]); + a++, b--; + } + + /* Recurse left side */ + exe_ang_sort(player_ptr, ys, xs, p, b, kind); + + /* Recurse right side */ + exe_ang_sort(player_ptr, ys, xs, b + 1, q, kind); +} +} + +/* + * @brief クイックソートの受け付け / Accepting auick sort in place + * @param u アイテムやモンスター等への配列 + * @param v 条件基準IDへの参照ポインタ + * @param a 比較対象のID1 + * @param b 比較対象のID2 + * @param ang_sort_comp 比較用の関数ポインタ + * @param ang_sort_swap スワップ用の関数ポインタ + */ +void ang_sort(PlayerType *player_ptr, std::vector &ys, std::vector &xs, SortKind kind) +{ + exe_ang_sort(player_ptr, ys, xs, 0, std::ssize(ys) - 1, kind); } diff --git a/src/util/sort.h b/src/util/sort.h index bfdeafe51..dc5c31e60 100644 --- a/src/util/sort.h +++ b/src/util/sort.h @@ -9,5 +9,3 @@ enum class SortKind { class PlayerType; void ang_sort(PlayerType *player_ptr, std::vector &ys, std::vector &xs, SortKind kind); -bool ang_sort_comp_distance(PlayerType *player_ptr, std::vector &ys, std::vector &xs, int a, int b); -bool ang_sort_comp_importance(PlayerType *player_ptr, std::vector &ys, std::vector &xs, int a, int b); -- 2.11.0