1 #include "util/sort.h"
2 #include "dungeon/quest.h"
3 #include "grid/feature.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"
12 * @brief クイックソートの実行 / Quick sort in place
13 * @param u アイテムやモンスター等への配列
14 * @param v 条件基準IDへの参照ポインタ
17 * @param ang_sort_comp 比較用の関数ポインタ
18 * @param ang_sort_swap スワップ用の関数ポインタ
21 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),
22 void (*ang_sort_swap)(player_type *, vptr, vptr, int, int))
32 while (!(*ang_sort_comp)(player_ptr, u, v, b, z))
36 while (!(*ang_sort_comp)(player_ptr, u, v, z, a))
42 (*ang_sort_swap)(player_ptr, u, v, a, b);
47 /* Recurse left side */
48 exe_ang_sort(player_ptr, u, v, p, b, ang_sort_comp, ang_sort_swap);
50 /* Recurse right side */
51 exe_ang_sort(player_ptr, u, v, b + 1, q, ang_sort_comp, ang_sort_swap);
55 * @brief クイックソートの受け付け / Accepting auick sort in place
56 * @param u アイテムやモンスター等への配列
57 * @param v 条件基準IDへの参照ポインタ
60 * @param ang_sort_comp 比較用の関数ポインタ
61 * @param ang_sort_swap スワップ用の関数ポインタ
64 void ang_sort(player_type *player_ptr, vptr u, vptr v, int n, bool (*ang_sort_comp)(player_type *, vptr, vptr, int, int),
65 void (*ang_sort_swap)(player_type *, vptr, vptr, int, int))
67 exe_ang_sort(player_ptr, u, v, 0, n - 1, ang_sort_comp, ang_sort_swap);
71 * Sorting hook -- comp function -- by "distance to player"
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.
76 bool ang_sort_comp_distance(player_type *player_ptr, vptr u, vptr v, int a, int b)
78 POSITION *x = (POSITION *)(u);
79 POSITION *y = (POSITION *)(v);
81 /* Absolute distance components */
89 /* Approximate Double Distance to the first point */
90 POSITION da = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
92 /* Absolute distance components */
100 /* Approximate Double Distance to the first point */
101 POSITION db = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
103 /* Compare the distances */
108 * Sorting hook -- comp function -- by importance level of grids
110 * We use "u" and "v" to point to arrays of "x" and "y" positions,
111 * and sort the arrays by level of monster
113 bool ang_sort_comp_importance(player_type *player_ptr, vptr u, vptr v, int a, int b)
115 POSITION *x = (POSITION *)(u);
116 POSITION *y = (POSITION *)(v);
117 grid_type *ca_ptr = &player_ptr->current_floor_ptr->grid_array[y[a]][x[a]];
118 grid_type *cb_ptr = &player_ptr->current_floor_ptr->grid_array[y[b]][x[b]];
119 monster_type *ma_ptr = &player_ptr->current_floor_ptr->m_list[ca_ptr->m_idx];
120 monster_type *mb_ptr = &player_ptr->current_floor_ptr->m_list[cb_ptr->m_idx];
121 monster_race *ap_ra_ptr, *ap_rb_ptr;
123 /* The player grid */
124 if (y[a] == player_ptr->y && x[a] == player_ptr->x)
127 if (y[b] == player_ptr->y && x[b] == player_ptr->x)
130 /* Extract monster race */
131 if (ca_ptr->m_idx && ma_ptr->ml)
132 ap_ra_ptr = &r_info[ma_ptr->ap_r_idx];
136 if (cb_ptr->m_idx && mb_ptr->ml)
137 ap_rb_ptr = &r_info[mb_ptr->ap_r_idx];
141 if (ap_ra_ptr && !ap_rb_ptr)
144 if (!ap_ra_ptr && ap_rb_ptr)
147 /* Compare two monsters */
148 if (ap_ra_ptr && ap_rb_ptr) {
149 /* Unique monsters first */
150 if ((ap_ra_ptr->flags1 & RF1_UNIQUE) && !(ap_rb_ptr->flags1 & RF1_UNIQUE))
152 if (!(ap_ra_ptr->flags1 & RF1_UNIQUE) && (ap_rb_ptr->flags1 & RF1_UNIQUE))
155 /* Shadowers first (あやしい影) */
156 if ((ma_ptr->mflag2 & MFLAG2_KAGE) && !(mb_ptr->mflag2 & MFLAG2_KAGE))
158 if (!(ma_ptr->mflag2 & MFLAG2_KAGE) && (mb_ptr->mflag2 & MFLAG2_KAGE))
161 /* Unknown monsters first */
162 if (!ap_ra_ptr->r_tkills && ap_rb_ptr->r_tkills)
164 if (ap_ra_ptr->r_tkills && !ap_rb_ptr->r_tkills)
167 /* Higher level monsters first (if known) */
168 if (ap_ra_ptr->r_tkills && ap_rb_ptr->r_tkills) {
169 if (ap_ra_ptr->level > ap_rb_ptr->level)
171 if (ap_ra_ptr->level < ap_rb_ptr->level)
175 /* Sort by index if all conditions are same */
176 if (ma_ptr->ap_r_idx > mb_ptr->ap_r_idx)
178 if (ma_ptr->ap_r_idx < mb_ptr->ap_r_idx)
182 /* An object get higher priority */
183 if (player_ptr->current_floor_ptr->grid_array[y[a]][x[a]].o_idx && !player_ptr->current_floor_ptr->grid_array[y[b]][x[b]].o_idx)
186 if (!player_ptr->current_floor_ptr->grid_array[y[a]][x[a]].o_idx && player_ptr->current_floor_ptr->grid_array[y[b]][x[b]].o_idx)
189 /* Priority from the terrain */
190 if (f_info[ca_ptr->feat].priority > f_info[cb_ptr->feat].priority)
193 if (f_info[ca_ptr->feat].priority < f_info[cb_ptr->feat].priority)
196 /* If all conditions are same, compare distance */
197 return ang_sort_comp_distance(player_ptr, u, v, a, b);
201 * Sorting hook -- swap function -- by "distance to player"
203 * We use "u" and "v" to point to arrays of "x" and "y" positions,
204 * and sort the arrays by distance to the player.
206 void ang_sort_swap_distance(player_type *player_ptr, vptr u, vptr v, int a, int b)
211 POSITION *x = (POSITION *)(u);
212 POSITION *y = (POSITION *)(v);
214 POSITION temp = x[a];
224 * Sorting hook -- Comp function -- see below
226 * We use "u" to point to array of monster indexes,
227 * and "v" to select the type of sorting to perform on "u".
229 bool ang_sort_art_comp(player_type *player_ptr, vptr u, vptr v, int a, int b)
234 u16b *who = (u16b *)(u);
235 u16b *why = (u16b *)(v);
242 /* Sort by total kills */
244 /* Extract total kills */
245 z1 = a_info[w1].tval;
246 z2 = a_info[w2].tval;
248 /* Compare total kills */
256 /* Sort by monster level */
259 z1 = a_info[w1].sval;
260 z2 = a_info[w2].sval;
270 /* Sort by monster experience */
272 /* Extract experience */
273 z1 = a_info[w1].level;
274 z2 = a_info[w2].level;
276 /* Compare experience */
284 /* Compare indexes */
289 * Sorting hook -- Swap function -- see below
291 * We use "u" to point to array of monster indexes,
292 * and "v" to select the type of sorting to perform.
294 void ang_sort_art_swap(player_type *player_ptr, vptr u, vptr v, int a, int b)
300 u16b *who = (u16b *)(u);
301 u16b holder = who[a];
306 bool ang_sort_comp_quest_num(player_type *player_ptr, vptr u, vptr v, int a, int b)
312 QUEST_IDX *q_num = (QUEST_IDX *)u;
313 quest_type *qa = &quest[q_num[a]];
314 quest_type *qb = &quest[q_num[b]];
315 return (qa->comptime != qb->comptime) ? (qa->comptime < qb->comptime) : (qa->level <= qb->level);
318 void ang_sort_swap_quest_num(player_type *player_ptr, vptr u, vptr v, int a, int b)
324 QUEST_IDX *q_num = (QUEST_IDX *)u;
325 QUEST_IDX tmp = q_num[a];
331 * @brief ペット入りモンスターボールをソートするための比較関数
332 * @param u 所持品配列の参照ポインタ
336 * @return 1の方が大であればTRUE
338 bool ang_sort_comp_pet(player_type *player_ptr, vptr u, vptr v, int a, int b)
343 u16b *who = (u16b *)(u);
348 monster_type *m_ptr1 = &player_ptr->current_floor_ptr->m_list[w1];
349 monster_type *m_ptr2 = &player_ptr->current_floor_ptr->m_list[w2];
350 monster_race *r_ptr1 = &r_info[m_ptr1->r_idx];
351 monster_race *r_ptr2 = &r_info[m_ptr2->r_idx];
353 if (m_ptr1->nickname && !m_ptr2->nickname)
356 if (m_ptr2->nickname && !m_ptr1->nickname)
359 if ((r_ptr1->flags1 & RF1_UNIQUE) && !(r_ptr2->flags1 & RF1_UNIQUE))
362 if ((r_ptr2->flags1 & RF1_UNIQUE) && !(r_ptr1->flags1 & RF1_UNIQUE))
365 if (r_ptr1->level > r_ptr2->level)
368 if (r_ptr2->level > r_ptr1->level)
371 if (m_ptr1->hp > m_ptr2->hp)
374 if (m_ptr2->hp > m_ptr1->hp)
381 * @brief モンスター種族情報を特定の基準によりソートするための比較処理
382 * Sorting hook -- Comp function -- see below
383 * @param u モンスター種族情報の入れるポインタ
385 * @param a 比較するモンスター種族のID1
386 * @param b 比較するモンスター種族のID2
387 * @return 2の方が大きければTRUEを返す
388 * We use "u" to point to array of monster indexes,
389 * and "v" to select the type of sorting to perform on "u".
391 bool ang_sort_comp_hook(player_type *player_ptr, vptr u, vptr v, int a, int b)
396 u16b *who = (u16b *)(u);
397 u16b *why = (u16b *)(v);
404 /* Sort by player kills */
406 /* Extract player kills */
407 z1 = r_info[w1].r_pkills;
408 z2 = r_info[w2].r_pkills;
410 /* Compare player kills */
417 /* Sort by total kills */
419 /* Extract total kills */
420 z1 = r_info[w1].r_tkills;
421 z2 = r_info[w2].r_tkills;
423 /* Compare total kills */
430 /* Sort by monster level */
433 z1 = r_info[w1].level;
434 z2 = r_info[w2].level;
443 /* Sort by monster experience */
445 /* Extract experience */
446 z1 = r_info[w1].mexp;
447 z2 = r_info[w2].mexp;
449 /* Compare experience */
456 /* Compare indexes */
461 * @brief モンスター種族情報を特定の基準によりソートするためのスワップ処理
462 * Sorting hook -- Swap function -- see below
463 * @param u モンスター種族情報の入れるポインタ
465 * @param a スワップするモンスター種族のID1
466 * @param b スワップするモンスター種族のID2
469 * We use "u" to point to array of monster indexes,
470 * and "v" to select the type of sorting to perform.
472 void ang_sort_swap_hook(player_type *player_ptr, vptr u, vptr v, int a, int b)
478 u16b *who = (u16b *)(u);
487 * hook function to sort monsters by level
489 bool ang_sort_comp_monster_level(player_type *player_ptr, vptr u, vptr v, int a, int b)
495 u16b *who = (u16b *)(u);
500 monster_race *r_ptr1 = &r_info[w1];
501 monster_race *r_ptr2 = &r_info[w2];
503 if (r_ptr2->level > r_ptr1->level)
506 if (r_ptr1->level > r_ptr2->level)
509 if ((r_ptr2->flags1 & RF1_UNIQUE) && !(r_ptr1->flags1 & RF1_UNIQUE))
512 if ((r_ptr1->flags1 & RF1_UNIQUE) && !(r_ptr2->flags1 & RF1_UNIQUE))
519 * @brief ペットになっているモンスターをソートするための比較処理
520 * @param u モンスターの構造体配列
522 * @param a 比較対象のモンスターID1
523 * @param b 比較対象のモンスターID2
524 * @return 2番目が大ならばTRUEを返す
526 bool ang_sort_comp_pet_dismiss(player_type *player_ptr, vptr u, vptr v, int a, int b)
531 u16b *who = (u16b *)(u);
536 monster_type *m_ptr1 = &player_ptr->current_floor_ptr->m_list[w1];
537 monster_type *m_ptr2 = &player_ptr->current_floor_ptr->m_list[w2];
538 monster_race *r_ptr1 = &r_info[m_ptr1->r_idx];
539 monster_race *r_ptr2 = &r_info[m_ptr2->r_idx];
541 if (w1 == player_ptr->riding)
544 if (w2 == player_ptr->riding)
547 if (m_ptr1->nickname && !m_ptr2->nickname)
550 if (m_ptr2->nickname && !m_ptr1->nickname)
553 if (!m_ptr1->parent_m_idx && m_ptr2->parent_m_idx)
556 if (!m_ptr2->parent_m_idx && m_ptr1->parent_m_idx)
559 if ((r_ptr1->flags1 & RF1_UNIQUE) && !(r_ptr2->flags1 & RF1_UNIQUE))
562 if ((r_ptr2->flags1 & RF1_UNIQUE) && !(r_ptr1->flags1 & RF1_UNIQUE))
565 if (r_ptr1->level > r_ptr2->level)
568 if (r_ptr2->level > r_ptr1->level)
571 if (m_ptr1->hp > m_ptr2->hp)
574 if (m_ptr2->hp > m_ptr1->hp)
581 * @brief フロア保存時のgrid情報テンプレートをソートするための比較処理
582 * @param u gridテンプレートの参照ポインタ
584 * @param a スワップするモンスター種族のID1
585 * @param b スワップするモンスター種族のID2
586 * @return aの方が大きければtrue
588 bool ang_sort_comp_cave_temp(player_type *player_ptr, vptr u, vptr v, int a, int b)
594 grid_template_type *who = (grid_template_type *)(u);
596 u16b o1 = who[a].occurrence;
597 u16b o2 = who[b].occurrence;
603 * @brief フロア保存時のgrid情報テンプレートをソートするためのスワップ処理 / Sorting hook -- Swap function
604 * @param u gridテンプレートの参照ポインタ
606 * @param a スワップするモンスター種族のID1
607 * @param b スワップするモンスター種族のID2
610 void ang_sort_swap_cave_temp(player_type *player_ptr, vptr u, vptr v, int a, int b)
616 grid_template_type *who = (grid_template_type *)(u);
617 grid_template_type holder;
625 * @brief 進化ツリーをソートするためモンスター種族の判定関数 /
626 * Sorting hook -- Comp function
629 * @param a 比較したいモンスター種族ID1
630 * @param b 比較したいモンスター種族ID2
631 * @return 2が大きければTRUEを返す
633 bool ang_sort_comp_evol_tree(player_type *player_ptr, vptr u, vptr v, int a, int b)
639 int **evol_tree = (int **)u;
641 int w1 = evol_tree[a][0];
642 int w2 = evol_tree[b][0];
643 monster_race *r1_ptr = &r_info[w1];
644 monster_race *r2_ptr = &r_info[w2];
646 /* Used tree first */
653 /* Sort by monster level */
654 if (r1_ptr->level < r2_ptr->level)
657 if (r1_ptr->level > r2_ptr->level)
660 /* Sort by monster experience */
661 if (r1_ptr->mexp < r2_ptr->mexp)
664 if (r1_ptr->mexp > r2_ptr->mexp)
667 /* Compare indexes */
672 * @brief 進化ツリーをソートするため木構造のスワップ関数 /
673 * Sorting hook -- Swap function
676 * @param a スワップしたい木構造1
677 * @param b スワップしたい木構造2
678 * @return 2が大きければTRUEを返す
680 void ang_sort_swap_evol_tree(player_type *player_ptr, vptr u, vptr v, int a, int b)
686 int **evol_tree = (int **)u;
689 holder = evol_tree[a];
690 evol_tree[a] = evol_tree[b];
691 evol_tree[b] = holder;