src/sort.c

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