src/sort.c

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