src/util/sort.cpp

   1 #include "util/sort.h"
   2 #include "artifact/fixed-art-types.h"
   3 #include "dungeon/quest.h"
   4 #include "grid/grid.h"
   5 #include "monster-race/monster-race.h"
   6 #include "monster-race/race-flags1.h"
   7 #include "monster/monster-flag-types.h"
   8 #include "system/artifact-type-definition.h"
   9 #include "system/floor-type-definition.h"
  10 #include "system/grid-type-definition.h"
  11 #include "system/monster-entity.h"
  12 #include "system/monster-race-info.h"
  13 #include "system/player-type-definition.h"
  14 #include "system/terrain-type-definition.h"
  15
  16 /*
  17  * @brief クイックソートの実行 / Quick sort in place
  18  * @param u アイテムやモンスター等への配列
  19  * @param v 条件基準IDへの参照ポインタ
  20  * @param a 比較対象のID1
  21  * @param b 比較対象のID2
  22  * @param ang_sort_comp 比較用の関数ポインタ
  23  * @param ang_sort_swap スワップ用の関数ポインタ
  24  */
  25 static void exe_ang_sort(PlayerType *player_ptr, vptr u, vptr v, int p, int q, bool (*ang_sort_comp)(PlayerType *, vptr, vptr, int, int),
  26     void (*ang_sort_swap)(PlayerType *, vptr, vptr, int, int))
  27 {
  28     if (p >= q) {
  29         return;
  30     }
  31
  32     int z = p;
  33     int a = p;
  34     int b = q;
  35     while (true) {
  36         /* Slide i2 */
  37         while (!(*ang_sort_comp)(player_ptr, u, v, b, z)) {
  38             b--;
  39         }
  40
  41         /* Slide i1 */
  42         while (!(*ang_sort_comp)(player_ptr, u, v, z, a)) {
  43             a++;
  44         }
  45
  46         if (a >= b) {
  47             break;
  48         }
  49
  50         (*ang_sort_swap)(player_ptr, u, v, a, b);
  51
  52         a++, b--;
  53     }
  54
  55     /* Recurse left side */
  56     exe_ang_sort(player_ptr, u, v, p, b, ang_sort_comp, ang_sort_swap);
  57
  58     /* Recurse right side */
  59     exe_ang_sort(player_ptr, u, v, b + 1, q, ang_sort_comp, ang_sort_swap);
  60 }
  61
  62 /*
  63  * @brief クイックソートの受け付け / Accepting auick sort in place
  64  * @param u アイテムやモンスター等への配列
  65  * @param v 条件基準IDへの参照ポインタ
  66  * @param a 比較対象のID1
  67  * @param b 比較対象のID2
  68  * @param ang_sort_comp 比較用の関数ポインタ
  69  * @param ang_sort_swap スワップ用の関数ポインタ
  70  */
  71 void ang_sort(PlayerType *player_ptr, vptr u, vptr v, int n, bool (*ang_sort_comp)(PlayerType *, vptr, vptr, int, int),
  72     void (*ang_sort_swap)(PlayerType *, vptr, vptr, int, int))
  73 {
  74     exe_ang_sort(player_ptr, u, v, 0, n - 1, ang_sort_comp, ang_sort_swap);
  75 }
  76
  77 /*
  78  * Sorting hook -- comp function -- by "distance to player"
  79  *
  80  * We use "u" and "v" to point to arrays of "x" and "y" positions,
  81  * and sort the arrays by double-distance to the player.
  82  */
  83 bool ang_sort_comp_distance(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
  84 {
  85     POSITION *x = (POSITION *)(u);
  86     POSITION *y = (POSITION *)(v);
  87
  88     /* Absolute distance components */
  89     POSITION kx = x[a];
  90     kx -= player_ptr->x;
  91     kx = std::abs(kx);
  92     POSITION ky = y[a];
  93     ky -= player_ptr->y;
  94     ky = std::abs(ky);
  95
  96     /* Approximate Double Distance to the first point */
  97     POSITION da = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
  98
  99     /* Absolute distance components */
 100     kx = x[b];
 101     kx -= player_ptr->x;
 102     kx = std::abs(kx);
 103     ky = y[b];
 104     ky -= player_ptr->y;
 105     ky = std::abs(ky);
 106
 107     /* Approximate Double Distance to the first point */
 108     POSITION db = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
 109
 110     /* Compare the distances */
 111     return da <= db;
 112 }
 113
 114 /*
 115  * Sorting hook -- comp function -- by importance level of grids
 116  *
 117  * We use "u" and "v" to point to arrays of "x" and "y" positions,
 118  * and sort the arrays by level of monster
 119  */
 120 bool ang_sort_comp_importance(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 121 {
 122     POSITION *x = (POSITION *)(u);
 123     POSITION *y = (POSITION *)(v);
 124     Grid *ca_ptr = &player_ptr->current_floor_ptr->grid_array[y[a]][x[a]];
 125     Grid *cb_ptr = &player_ptr->current_floor_ptr->grid_array[y[b]][x[b]];
 126     MonsterEntity *ma_ptr = &player_ptr->current_floor_ptr->m_list[ca_ptr->m_idx];
 127     MonsterEntity *mb_ptr = &player_ptr->current_floor_ptr->m_list[cb_ptr->m_idx];
 128     MonsterRaceInfo *ap_ra_ptr, *ap_rb_ptr;
 129
 130     /* The player grid */
 131     if (y[a] == player_ptr->y && x[a] == player_ptr->x) {
 132         return true;
 133     }
 134
 135     if (y[b] == player_ptr->y && x[b] == player_ptr->x) {
 136         return false;
 137     }
 138
 139     /* Extract monster race */
 140     if (ca_ptr->m_idx && ma_ptr->ml) {
 141         ap_ra_ptr = &monraces_info[ma_ptr->ap_r_idx];
 142     } else {
 143         ap_ra_ptr = nullptr;
 144     }
 145
 146     if (cb_ptr->m_idx && mb_ptr->ml) {
 147         ap_rb_ptr = &monraces_info[mb_ptr->ap_r_idx];
 148     } else {
 149         ap_rb_ptr = nullptr;
 150     }
 151
 152     if (ap_ra_ptr && !ap_rb_ptr) {
 153         return true;
 154     }
 155
 156     if (!ap_ra_ptr && ap_rb_ptr) {
 157         return false;
 158     }
 159
 160     /* Compare two monsters */
 161     if (ap_ra_ptr && ap_rb_ptr) {
 162         /* Unique monsters first */
 163         if (ap_ra_ptr->kind_flags.has(MonsterKindType::UNIQUE) && ap_rb_ptr->kind_flags.has_not(MonsterKindType::UNIQUE)) {
 164             return true;
 165         }
 166         if (ap_ra_ptr->kind_flags.has_not(MonsterKindType::UNIQUE) && ap_rb_ptr->kind_flags.has(MonsterKindType::UNIQUE)) {
 167             return false;
 168         }
 169
 170         /* Shadowers first (あやしい影) */
 171         if (ma_ptr->mflag2.has(MonsterConstantFlagType::KAGE) && mb_ptr->mflag2.has_not(MonsterConstantFlagType::KAGE)) {
 172             return true;
 173         }
 174         if (ma_ptr->mflag2.has_not(MonsterConstantFlagType::KAGE) && mb_ptr->mflag2.has(MonsterConstantFlagType::KAGE)) {
 175             return false;
 176         }
 177
 178         /* Unknown monsters first */
 179         if (!ap_ra_ptr->r_tkills && ap_rb_ptr->r_tkills) {
 180             return true;
 181         }
 182         if (ap_ra_ptr->r_tkills && !ap_rb_ptr->r_tkills) {
 183             return false;
 184         }
 185
 186         /* Higher level monsters first (if known) */
 187         if (ap_ra_ptr->r_tkills && ap_rb_ptr->r_tkills) {
 188             if (ap_ra_ptr->level > ap_rb_ptr->level) {
 189                 return true;
 190             }
 191             if (ap_ra_ptr->level < ap_rb_ptr->level) {
 192                 return false;
 193             }
 194         }
 195
 196         /* Sort by index if all conditions are same */
 197         if (ma_ptr->ap_r_idx > mb_ptr->ap_r_idx) {
 198             return true;
 199         }
 200         if (ma_ptr->ap_r_idx < mb_ptr->ap_r_idx) {
 201             return false;
 202         }
 203     }
 204
 205     /* An object get higher priority */
 206     if (!player_ptr->current_floor_ptr->grid_array[y[a]][x[a]].o_idx_list.empty() && player_ptr->current_floor_ptr->grid_array[y[b]][x[b]].o_idx_list.empty()) {
 207         return true;
 208     }
 209
 210     if (player_ptr->current_floor_ptr->grid_array[y[a]][x[a]].o_idx_list.empty() && !player_ptr->current_floor_ptr->grid_array[y[b]][x[b]].o_idx_list.empty()) {
 211         return false;
 212     }
 213
 214     /* Priority from the terrain */
 215     if (terrains_info[ca_ptr->feat].priority > terrains_info[cb_ptr->feat].priority) {
 216         return true;
 217     }
 218
 219     if (terrains_info[ca_ptr->feat].priority < terrains_info[cb_ptr->feat].priority) {
 220         return false;
 221     }
 222
 223     /* If all conditions are same, compare distance */
 224     return ang_sort_comp_distance(player_ptr, u, v, a, b);
 225 }
 226
 227 /*
 228  * Sorting hook -- swap function -- by "distance to player"
 229  *
 230  * We use "u" and "v" to point to arrays of "x" and "y" positions,
 231  * and sort the arrays by distance to the player.
 232  */
 233 void ang_sort_swap_position(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 234 {
 235     /* Unused */
 236     (void)player_ptr;
 237
 238     POSITION *x = (POSITION *)(u);
 239     POSITION *y = (POSITION *)(v);
 240
 241     POSITION temp = x[a];
 242     x[a] = x[b];
 243     x[b] = temp;
 244
 245     temp = y[a];
 246     y[a] = y[b];
 247     y[b] = temp;
 248 }
 249
 250 /*
 251  * Sorting hook -- Comp function -- see below
 252  *
 253  * We use "u" to point to array of monster indexes,
 254  * and "v" to select the type of sorting to perform on "u".
 255  */
 256 bool ang_sort_art_comp(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 257 {
 258     /* Unused */
 259     (void)player_ptr;
 260
 261     uint16_t *who = (uint16_t *)(u);
 262     uint16_t *why = (uint16_t *)(v);
 263
 264     const auto w1 = i2enum<FixedArtifactId>(who[a]);
 265     const auto w2 = i2enum<FixedArtifactId>(who[b]);
 266
 267     int z1;
 268     int z2;
 269
 270     /* Sort by total kills */
 271     const auto &artifact_w1 = ArtifactsInfo::get_instance().get_artifact(w1);
 272     const auto &artifact_w2 = ArtifactsInfo::get_instance().get_artifact(w2);
 273     if (*why >= 3) {
 274         /* Extract total kills */
 275         z1 = enum2i(artifact_w1.bi_key.tval());
 276         z2 = enum2i(artifact_w2.bi_key.tval());
 277
 278         /* Compare total kills */
 279         if (z1 < z2) {
 280             return true;
 281         }
 282
 283         if (z1 > z2) {
 284             return false;
 285         }
 286     }
 287
 288     /* Sort by monster level */
 289     if (*why >= 2) {
 290         /* Extract levels */
 291         z1 = artifact_w1.bi_key.sval().value();
 292         z2 = artifact_w2.bi_key.sval().value();
 293
 294         /* Compare levels */
 295         if (z1 < z2) {
 296             return true;
 297         }
 298
 299         if (z1 > z2) {
 300             return false;
 301         }
 302     }
 303
 304     /* Sort by monster experience */
 305     if (*why >= 1) {
 306         /* Extract experience */
 307         z1 = artifact_w1.level;
 308         z2 = artifact_w2.level;
 309
 310         /* Compare experience */
 311         if (z1 < z2) {
 312             return true;
 313         }
 314
 315         if (z1 > z2) {
 316             return false;
 317         }
 318     }
 319
 320     /* Compare indexes */
 321     return w1 <= w2;
 322 }
 323
 324 /*
 325  * Sorting hook -- Swap function -- see below
 326  *
 327  * We use "u" to point to array of monster indexes,
 328  * and "v" to select the type of sorting to perform.
 329  */
 330 void ang_sort_art_swap(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 331 {
 332     /* Unused */
 333     (void)player_ptr;
 334     (void)v;
 335
 336     uint16_t *who = (uint16_t *)(u);
 337     uint16_t holder = who[a];
 338     who[a] = who[b];
 339     who[b] = holder;
 340 }
 341
 342 bool ang_sort_comp_quest_num(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 343 {
 344     /* Unused */
 345     (void)player_ptr;
 346     (void)v;
 347
 348     const auto &quest_list = QuestList::get_instance();
 349     QuestId *q_num = (QuestId *)u;
 350     const auto *qa = &quest_list[q_num[a]];
 351     const auto *qb = &quest_list[q_num[b]];
 352     return (qa->comptime != qb->comptime) ? (qa->comptime < qb->comptime) : (qa->level <= qb->level);
 353 }
 354
 355 void ang_sort_swap_quest_num(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 356 {
 357     /* Unused */
 358     (void)player_ptr;
 359     (void)v;
 360
 361     QuestId *q_num = (QuestId *)u;
 362     QuestId tmp = q_num[a];
 363     q_num[a] = q_num[b];
 364     q_num[b] = tmp;
 365 }
 366
 367 /*!
 368  * @brief ペット入りモンスターボールをソートするための比較関数
 369  * @param u 所持品配列の参照ポインタ
 370  * @param v 未使用
 371  * @param a 所持品ID1
 372  * @param b 所持品ID2
 373  * @return 1の方が大であればTRUE
 374  */
 375 bool ang_sort_comp_pet(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 376 {
 377     /* Unused */
 378     (void)v;
 379
 380     uint16_t *who = (uint16_t *)(u);
 381
 382     int w1 = who[a];
 383     int w2 = who[b];
 384
 385     const auto &monster1 = player_ptr->current_floor_ptr->m_list[w1];
 386     const auto &monster2 = player_ptr->current_floor_ptr->m_list[w2];
 387     const auto &monrace1 = monraces_info[monster1.r_idx];
 388     const auto &monrace2 = monraces_info[monster2.r_idx];
 389
 390     if (monster1.is_named() && !monster2.is_named()) {
 391         return true;
 392     }
 393
 394     if (monster2.is_named() && !monster1.is_named()) {
 395         return false;
 396     }
 397
 398     if (monrace1.kind_flags.has(MonsterKindType::UNIQUE) && monrace2.kind_flags.has_not(MonsterKindType::UNIQUE)) {
 399         return true;
 400     }
 401
 402     if (monrace2.kind_flags.has(MonsterKindType::UNIQUE) && monrace1.kind_flags.has_not(MonsterKindType::UNIQUE)) {
 403         return false;
 404     }
 405
 406     if (monrace1.level > monrace2.level) {
 407         return true;
 408     }
 409
 410     if (monrace2.level > monrace1.level) {
 411         return false;
 412     }
 413
 414     if (monster1.hp > monster2.hp) {
 415         return true;
 416     }
 417
 418     if (monster2.hp > monster1.hp) {
 419         return false;
 420     }
 421
 422     return w1 <= w2;
 423 }
 424
 425 /*!
 426  * @brief モンスター種族情報を特定の基準によりソートするための比較処理
 427  * Sorting hook -- Comp function -- see below
 428  * @param u モンスター種族情報の入れるポインタ
 429  * @param v 条件基準ID
 430  * @param a 比較するモンスター種族のID1
 431  * @param b 比較するモンスター種族のID2
 432  * @return 2の方が大きければTRUEを返す
 433  * We use "u" to point to array of monster indexes,
 434  * and "v" to select the type of sorting to perform on "u".
 435  */
 436 bool ang_sort_comp_hook(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 437 {
 438     /* Unused */
 439     (void)player_ptr;
 440
 441     MonsterRaceId *who = (MonsterRaceId *)(u);
 442     uint16_t *why = (uint16_t *)(v);
 443
 444     auto w1 = who[a];
 445     auto w2 = who[b];
 446
 447     int z1, z2;
 448
 449     /* Sort by player kills */
 450     if (*why >= 4) {
 451         /* Extract player kills */
 452         z1 = monraces_info[w1].r_pkills;
 453         z2 = monraces_info[w2].r_pkills;
 454
 455         /* Compare player kills */
 456         if (z1 < z2) {
 457             return true;
 458         }
 459         if (z1 > z2) {
 460             return false;
 461         }
 462     }
 463
 464     /* Sort by total kills */
 465     if (*why >= 3) {
 466         /* Extract total kills */
 467         z1 = monraces_info[w1].r_tkills;
 468         z2 = monraces_info[w2].r_tkills;
 469
 470         /* Compare total kills */
 471         if (z1 < z2) {
 472             return true;
 473         }
 474         if (z1 > z2) {
 475             return false;
 476         }
 477     }
 478
 479     /* Sort by monster level */
 480     if (*why >= 2) {
 481         /* Extract levels */
 482         z1 = monraces_info[w1].level;
 483         z2 = monraces_info[w2].level;
 484
 485         /* Compare levels */
 486         if (z1 < z2) {
 487             return true;
 488         }
 489         if (z1 > z2) {
 490             return false;
 491         }
 492     }
 493
 494     /* Sort by monster experience */
 495     if (*why >= 1) {
 496         /* Extract experience */
 497         z1 = monraces_info[w1].mexp;
 498         z2 = monraces_info[w2].mexp;
 499
 500         /* Compare experience */
 501         if (z1 < z2) {
 502             return true;
 503         }
 504         if (z1 > z2) {
 505             return false;
 506         }
 507     }
 508
 509     /* Compare indexes */
 510     return w1 <= w2;
 511 }
 512
 513 /*!
 514  * @brief モンスター種族情報を特定の基準によりソートするためのスワップ処理
 515  * Sorting hook -- Swap function -- see below
 516  * @param u モンスター種族情報の入れるポインタ
 517  * @param v 未使用
 518  * @param a スワップするモンスター種族のID1
 519  * @param b スワップするモンスター種族のID2
 520  * @details
 521  * We use "u" to point to array of monster indexes,
 522  * and "v" to select the type of sorting to perform.
 523  */
 524 void ang_sort_swap_hook(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 525 {
 526     /* Unused */
 527     (void)player_ptr;
 528     (void)v;
 529
 530     uint16_t *who = (uint16_t *)(u);
 531     uint16_t holder;
 532
 533     holder = who[a];
 534     who[a] = who[b];
 535     who[b] = holder;
 536 }
 537
 538 /*
 539  * hook function to sort monsters by level
 540  */
 541 bool ang_sort_comp_monster_level(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 542 {
 543     /* Unused */
 544     (void)player_ptr;
 545     (void)v;
 546
 547     MonsterRaceId *who = (MonsterRaceId *)(u);
 548
 549     auto w1 = who[a];
 550     auto w2 = who[b];
 551
 552     MonsterRaceInfo *r_ptr1 = &monraces_info[w1];
 553     MonsterRaceInfo *r_ptr2 = &monraces_info[w2];
 554
 555     if (r_ptr2->level > r_ptr1->level) {
 556         return true;
 557     }
 558
 559     if (r_ptr1->level > r_ptr2->level) {
 560         return false;
 561     }
 562
 563     if (r_ptr2->kind_flags.has(MonsterKindType::UNIQUE) && r_ptr1->kind_flags.has_not(MonsterKindType::UNIQUE)) {
 564         return true;
 565     }
 566
 567     if (r_ptr1->kind_flags.has(MonsterKindType::UNIQUE) && r_ptr2->kind_flags.has_not(MonsterKindType::UNIQUE)) {
 568         return false;
 569     }
 570
 571     return w1 <= w2;
 572 }
 573
 574 /*!
 575  * @brief ペットになっているモンスターをソートするための比較処理
 576  * @param u モンスターの構造体配列
 577  * @param v 未使用
 578  * @param a 比較対象のモンスターID1
 579  * @param b 比較対象のモンスターID2
 580  * @return 2番目が大ならばTRUEを返す
 581  */
 582 bool ang_sort_comp_pet_dismiss(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 583 {
 584     /* Unused */
 585     (void)v;
 586
 587     uint16_t *who = (uint16_t *)(u);
 588
 589     int w1 = who[a];
 590     int w2 = who[b];
 591
 592     const auto &monster1 = player_ptr->current_floor_ptr->m_list[w1];
 593     const auto &monster2 = player_ptr->current_floor_ptr->m_list[w2];
 594     const auto &monrace1 = monraces_info[monster1.r_idx];
 595     const auto &monrace2 = monraces_info[monster2.r_idx];
 596
 597     if (w1 == player_ptr->riding) {
 598         return true;
 599     }
 600
 601     if (w2 == player_ptr->riding) {
 602         return false;
 603     }
 604
 605     if (monster1.is_named() && !monster2.is_named()) {
 606         return true;
 607     }
 608
 609     if (monster2.is_named() && !monster1.is_named()) {
 610         return false;
 611     }
 612
 613     if (!monster1.parent_m_idx && monster2.parent_m_idx) {
 614         return true;
 615     }
 616
 617     if (!monster2.parent_m_idx && monster1.parent_m_idx) {
 618         return false;
 619     }
 620
 621     if (monrace1.kind_flags.has(MonsterKindType::UNIQUE) && monrace2.kind_flags.has_not(MonsterKindType::UNIQUE)) {
 622         return true;
 623     }
 624
 625     if (monrace2.kind_flags.has(MonsterKindType::UNIQUE) && monrace1.kind_flags.has_not(MonsterKindType::UNIQUE)) {
 626         return false;
 627     }
 628
 629     if (monrace1.level > monrace2.level) {
 630         return true;
 631     }
 632
 633     if (monrace2.level > monrace1.level) {
 634         return false;
 635     }
 636
 637     if (monster1.hp > monster2.hp) {
 638         return true;
 639     }
 640
 641     if (monster2.hp > monster1.hp) {
 642         return false;
 643     }
 644
 645     return w1 <= w2;
 646 }
 647
 648 /*!
 649  * @brief フロア保存時のgrid情報テンプレートをソートするための比較処理
 650  * @param u gridテンプレートの参照ポインタ
 651  * @param v 未使用
 652  * @param a スワップするモンスター種族のID1
 653  * @param b スワップするモンスター種族のID2
 654  * @return aの方が大きければtrue
 655  */
 656 bool ang_sort_comp_cave_temp(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 657 {
 658     /* Unused */
 659     (void)player_ptr;
 660     (void)v;
 661
 662     grid_template_type *who = (grid_template_type *)(u);
 663
 664     uint16_t o1 = who[a].occurrence;
 665     uint16_t o2 = who[b].occurrence;
 666
 667     return o2 <= o1;
 668 }
 669
 670 /*!
 671  * @brief フロア保存時のgrid情報テンプレートをソートするためのスワップ処理 / Sorting hook -- Swap function
 672  * @param u gridテンプレートの参照ポインタ
 673  * @param v 未使用
 674  * @param a スワップするモンスター種族のID1
 675  * @param b スワップするモンスター種族のID2
 676  */
 677 void ang_sort_swap_cave_temp(PlayerType *player_ptr, vptr u, vptr v, int a, int b)
 678 {
 679     /* Unused */
 680     (void)player_ptr;
 681     (void)v;
 682
 683     grid_template_type *who = (grid_template_type *)(u);
 684     grid_template_type holder;
 685
 686     holder = who[a];
 687     who[a] = who[b];
 688     who[b] = holder;
 689 }