src/sort.c

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