<ClCompile Include="..\..\src\util\angband-files.cpp" />\r
<ClCompile Include="..\..\src\util\object-sort.cpp" />\r
<ClCompile Include="..\..\src\util\string-processor.cpp" />\r
- <ClCompile Include="..\..\src\util\tag-sorter.cpp" />\r
<ClCompile Include="..\..\src\view\display-birth.cpp" />\r
<ClCompile Include="..\..\src\view\display-characteristic.cpp" />\r
<ClCompile Include="..\..\src\view\display-fruit.cpp" />\r
<ClInclude Include="..\..\src\util\object-sort.h" />\r
<ClInclude Include="..\..\src\util\rng-xoshiro.h" />\r
<ClInclude Include="..\..\src\util\string-processor.h" />\r
- <ClInclude Include="..\..\src\util\tag-sorter.h" />\r
<ClInclude Include="..\..\src\view\display-birth.h" />\r
<ClInclude Include="..\..\src\view\display-inventory.h" />\r
<ClInclude Include="..\..\src\view\display-lore-attacks.h" />\r
<ClCompile Include="..\..\src\game-option\keymap-directory-getter.cpp">\r
<Filter>game-option</Filter>\r
</ClCompile>\r
- <ClCompile Include="..\..\src\util\tag-sorter.cpp">\r
- <Filter>util</Filter>\r
- </ClCompile>\r
<ClCompile Include="..\..\src\util\buffer-shaper.cpp">\r
<Filter>util</Filter>\r
</ClCompile>\r
<ClInclude Include="..\..\src\io\command-repeater.h">\r
<Filter>io</Filter>\r
</ClInclude>\r
- <ClInclude Include="..\..\src\util\tag-sorter.h">\r
- <Filter>util</Filter>\r
- </ClInclude>\r
<ClInclude Include="..\..\src\game-option\cheat-types.h">\r
<Filter>game-option</Filter>\r
</ClInclude>\r
util/rng-xoshiro.cpp util/rng-xoshiro.h \
util/sort.cpp util/sort.h \
util/string-processor.cpp util/string-processor.h \
- util/tag-sorter.cpp util/tag-sorter.h \
\
view/display-birth.cpp view/display-birth.h \
view/display-characteristic.cpp view/display-characteristic.h \
#include "util/angband-files.h"
#include "util/bit-flags-calculator.h"
#include "util/quarks.h"
-#include "util/tag-sorter.h"
#include "view/display-messages.h"
#include "world/world.h"
+#include <algorithm>
/*!
* @brief マクロ登録の最大数 / Maximum number of macros (see "io.c")
*/
void init_alloc(void)
{
- std::vector<tag_type> elements(monraces_info.size());
+ std::vector<const MonsterRaceInfo *> elements;
for (const auto &[r_idx, r_ref] : monraces_info) {
if (MonsterRace(r_ref.idx).is_valid()) {
- elements[enum2i(r_ref.idx)].tag = r_ref.level;
- elements[enum2i(r_ref.idx)].index = enum2i(r_ref.idx);
+ elements.push_back(&r_ref);
}
}
- tag_sort(elements.data(), elements.size());
- alloc_race_table.assign(monraces_info.size(), {});
- for (auto i = 1U; i < monraces_info.size(); i++) {
- auto *r_ptr = &monraces_info[i2enum<MonsterRaceId>(elements[i].index)];
+ std::sort(elements.begin(), elements.end(),
+ [](const MonsterRaceInfo *r1_ptr, const MonsterRaceInfo *r2_ptr) {
+ return r1_ptr->level < r2_ptr->level;
+ });
+
+ alloc_race_table.clear();
+ for (const auto r_ptr : elements) {
if (r_ptr->rarity == 0) {
continue;
}
- auto x = r_ptr->level;
- PROB p = (100 / r_ptr->rarity);
- alloc_race_table[i].index = static_cast<short>(elements[i].index);
- alloc_race_table[i].level = x;
- alloc_race_table[i].prob1 = p;
- alloc_race_table[i].prob2 = p;
+ const auto index = static_cast<short>(r_ptr->idx);
+ const auto level = r_ptr->level;
+ const auto prob = static_cast<PROB>(100 / r_ptr->rarity);
+ alloc_race_table.push_back({ index, level, prob, prob });
}
init_object_alloc();
DEPTH level; /* Base dungeon level */
PROB prob1; /* Probability, pass 1 */
PROB prob2; /* Probability, pass 2 */
-
- uint16_t total; /* Unused for now */
};
extern std::vector<alloc_entry> alloc_race_table;
+++ /dev/null
-#include "util/tag-sorter.h"
-
-/*
- * Exchange two sort-entries
- * (should probably be coded inline
- * for speed increase)
- */
-static void swap(tag_type *a, tag_type *b)
-{
- tag_type temp;
-
- temp = *a;
- *a = *b;
- *b = temp;
-}
-
-/*
- * Insertion-Sort algorithm
- * (used by the Quicksort algorithm)
- */
-static void insertion_sort(tag_type elements[], int number)
-{
- tag_type tmp;
- for (int i = 1; i < number; i++) {
- tmp = elements[i];
- int j;
- for (j = i; (j > 0) && (elements[j - 1].tag > tmp.tag); j--) {
- elements[j] = elements[j - 1];
- }
- elements[j] = tmp;
- }
-}
-
-/*
- * Helper function for Quicksort
- */
-static tag_type median3(tag_type elements[], int left, int right)
-{
- int center = (left + right) / 2;
-
- if (elements[left].tag > elements[center].tag) {
- swap(&elements[left], &elements[center]);
- }
- if (elements[left].tag > elements[right].tag) {
- swap(&elements[left], &elements[right]);
- }
- if (elements[center].tag > elements[right].tag) {
- swap(&elements[center], &elements[right]);
- }
-
- swap(&elements[center], &elements[right - 1]);
- return elements[right - 1];
-}
-
-/*
- * Quicksort algorithm
- *
- * The "median of three" pivot selection eliminates
- * the bad case of already sorted input.
- *
- * We use insertion_sort for smaller sub-arrays,
- * because it is faster in this case.
- *
- * For details see: "Data Structures and Algorithm
- * Analysis in C" by Mark Allen Weiss.
- */
-static void quicksort(tag_type elements[], int left, int right)
-{
- tag_type pivot;
- const int array_size_cutoff = 4;
- if (left + array_size_cutoff <= right) {
- pivot = median3(elements, left, right);
-
- int i = left;
- int j = right - 1;
-
- while (true) {
- while (elements[++i].tag < pivot.tag) {
- ;
- }
- while (elements[--j].tag > pivot.tag) {
- ;
- }
-
- if (i < j) {
- swap(&elements[i], &elements[j]);
- } else {
- break;
- }
- }
-
- swap(&elements[i], &elements[right - 1]);
-
- quicksort(elements, left, i - 1);
- quicksort(elements, i + 1, right);
- } else {
- insertion_sort(elements + left, right - left + 1);
- }
-}
-
-/*
- * Frontend for the sorting algorithm
- *
- * Sorts an array of tagged pointers
- * with <number> elements.
- */
-void tag_sort(tag_type elements[], int number)
-{
- quicksort(elements, 0, number - 1);
-}
+++ /dev/null
-#pragma once
-
-#include "system/angband.h"
-
-/*
- * Sort-array element
- */
-struct tag_type {
- int tag;
- int index;
-};
-
-void tag_sort(tag_type elements[], int number);