src/util/sort.cpp

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