src/sort.c

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