5 * Angband sorting algorithm -- quick sort in place
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.
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))
31 while (!(*ang_sort_comp)(u, v, b, z)) b--;
34 while (!(*ang_sort_comp)(u, v, z, a)) a++;
40 (*ang_sort_swap)(u, v, a, b);
46 /* Recurse left side */
47 ang_sort_aux(u, v, p, b, ang_sort_comp, ang_sort_swap);
49 /* Recurse right side */
50 ang_sort_aux(u, v, b + 1, q, ang_sort_comp, ang_sort_swap);
55 * Angband sorting algorithm -- quick sort in place
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.
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))
66 ang_sort_aux(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(vptr u, vptr v, int a, int b)
78 POSITION *x = (POSITION*)(u);
79 POSITION *y = (POSITION*)(v);
81 POSITION da, db, kx, ky;
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);
87 /* Approximate Double Distance to the first point */
88 da = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
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);
94 /* Approximate Double Distance to the first point */
95 db = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
97 /* Compare the distances */
103 * Sorting hook -- comp function -- by importance level of grids
105 * We use "u" and "v" to point to arrays of "x" and "y" positions,
106 * and sort the arrays by level of monster
108 bool ang_sort_comp_importance(vptr u, vptr v, int a, int b)
110 POSITION *x = (POSITION*)(u);
111 POSITION *y = (POSITION*)(v);
112 grid_type *ca_ptr = ¤t_floor_ptr->grid_array[y[a]][x[a]];
113 grid_type *cb_ptr = ¤t_floor_ptr->grid_array[y[b]][x[b]];
114 monster_type *ma_ptr = ¤t_floor_ptr->m_list[ca_ptr->m_idx];
115 monster_type *mb_ptr = ¤t_floor_ptr->m_list[cb_ptr->m_idx];
116 monster_race *ap_ra_ptr, *ap_rb_ptr;
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;
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;
128 if (ap_ra_ptr && !ap_rb_ptr) return TRUE;
129 if (!ap_ra_ptr && ap_rb_ptr) return FALSE;
131 /* Compare two monsters */
132 if (ap_ra_ptr && ap_rb_ptr)
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;
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;
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;
146 /* Higher level monsters first (if known) */
147 if (ap_ra_ptr->r_tkills && ap_rb_ptr->r_tkills)
149 if (ap_ra_ptr->level > ap_rb_ptr->level) return TRUE;
150 if (ap_ra_ptr->level < ap_rb_ptr->level) return FALSE;
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;
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;
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;
166 /* If all conditions are same, compare distance */
167 return ang_sort_comp_distance(u, v, a, b);
172 * Sorting hook -- swap function -- by "distance to player"
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.
177 void ang_sort_swap_distance(vptr u, vptr v, int a, int b)
179 POSITION *x = (POSITION*)(u);
180 POSITION *y = (POSITION*)(v);
198 * Sorting hook -- Comp function -- see below
200 * We use "u" to point to array of monster indexes,
201 * and "v" to select the type of sorting to perform on "u".
203 bool ang_sort_art_comp(vptr u, vptr v, int a, int b)
205 u16b *who = (u16b*)(u);
206 u16b *why = (u16b*)(v);
213 /* Sort by total kills */
216 /* Extract total kills */
217 z1 = a_info[w1].tval;
218 z2 = a_info[w2].tval;
220 /* Compare total kills */
221 if (z1 < z2) return (TRUE);
222 if (z1 > z2) return (FALSE);
226 /* Sort by monster level */
230 z1 = a_info[w1].sval;
231 z2 = a_info[w2].sval;
234 if (z1 < z2) return (TRUE);
235 if (z1 > z2) return (FALSE);
239 /* Sort by monster experience */
242 /* Extract experience */
243 z1 = a_info[w1].level;
244 z2 = a_info[w2].level;
246 /* Compare experience */
247 if (z1 < z2) return (TRUE);
248 if (z1 > z2) return (FALSE);
252 /* Compare indexes */
258 * Sorting hook -- Swap function -- see below
260 * We use "u" to point to array of monster indexes,
261 * and "v" to select the type of sorting to perform.
263 void ang_sort_art_swap(vptr u, vptr v, int a, int b)
265 u16b *who = (u16b*)(u);
277 bool ang_sort_comp_quest_num(vptr u, vptr v, int a, int b)
279 QUEST_IDX *q_num = (QUEST_IDX *)u;
280 quest_type *qa = &quest[q_num[a]];
281 quest_type *qb = &quest[q_num[b]];
286 return (qa->comptime != qb->comptime) ?
287 (qa->comptime < qb->comptime) :
288 (qa->level <= qb->level);
291 void ang_sort_swap_quest_num(vptr u, vptr v, int a, int b)
293 QUEST_IDX *q_num = (QUEST_IDX *)u;
306 * @brief ペット入りモンスターボールをソートするための比較関数
307 * @param u 所持品配列の参照ポインタ
311 * @return 1の方が大であればTRUE
313 bool ang_sort_comp_pet(vptr u, vptr v, int a, int b)
315 u16b *who = (u16b*)(u);
320 monster_type *m_ptr1 = ¤t_floor_ptr->m_list[w1];
321 monster_type *m_ptr2 = ¤t_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];
328 if (m_ptr1->nickname && !m_ptr2->nickname) return TRUE;
329 if (m_ptr2->nickname && !m_ptr1->nickname) return FALSE;
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;
334 if (r_ptr1->level > r_ptr2->level) return TRUE;
335 if (r_ptr2->level > r_ptr1->level) return FALSE;
337 if (m_ptr1->hp > m_ptr2->hp) return TRUE;
338 if (m_ptr2->hp > m_ptr1->hp) return FALSE;
346 * @brief モンスター種族情報を特定の基準によりソートするための比較処理
347 * Sorting hook -- Comp function -- see below
348 * @param u モンスター種族情報の入れるポインタ
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".
356 bool ang_sort_comp_hook(vptr u, vptr v, int a, int b)
358 u16b *who = (u16b*)(u);
359 u16b *why = (u16b*)(v);
366 /* Sort by player kills */
369 /* Extract player kills */
370 z1 = r_info[w1].r_pkills;
371 z2 = r_info[w2].r_pkills;
373 /* Compare player kills */
374 if (z1 < z2) return (TRUE);
375 if (z1 > z2) return (FALSE);
379 /* Sort by total kills */
382 /* Extract total kills */
383 z1 = r_info[w1].r_tkills;
384 z2 = r_info[w2].r_tkills;
386 /* Compare total kills */
387 if (z1 < z2) return (TRUE);
388 if (z1 > z2) return (FALSE);
392 /* Sort by monster level */
396 z1 = r_info[w1].level;
397 z2 = r_info[w2].level;
400 if (z1 < z2) return (TRUE);
401 if (z1 > z2) return (FALSE);
405 /* Sort by monster experience */
408 /* Extract experience */
409 z1 = r_info[w1].mexp;
410 z2 = r_info[w2].mexp;
412 /* Compare experience */
413 if (z1 < z2) return (TRUE);
414 if (z1 > z2) return (FALSE);
418 /* Compare indexes */
424 * @brief モンスター種族情報を特定の基準によりソートするためのスワップ処理
425 * Sorting hook -- Swap function -- see below
426 * @param u モンスター種族情報の入れるポインタ
428 * @param a スワップするモンスター種族のID1
429 * @param b スワップするモンスター種族のID2
432 * We use "u" to point to array of monster indexes,
433 * and "v" to select the type of sorting to perform.
435 void ang_sort_swap_hook(vptr u, vptr v, int a, int b)
437 u16b *who = (u16b*)(u);
450 * hook function to sort monsters by level
452 bool ang_sort_comp_monster_level(vptr u, vptr v, int a, int b)
454 u16b *who = (u16b*)(u);
459 monster_race *r_ptr1 = &r_info[w1];
460 monster_race *r_ptr2 = &r_info[w2];
465 if (r_ptr2->level > r_ptr1->level) return TRUE;
466 if (r_ptr1->level > r_ptr2->level) return FALSE;
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;
475 * @brief ペットになっているモンスターをソートするための比較処理
476 * @param u モンスターの構造体配列
478 * @param a 比較対象のモンスターID1
479 * @param b 比較対象のモンスターID2
480 * @return 2番目が大ならばTRUEを返す
482 bool ang_sort_comp_pet_dismiss(vptr u, vptr v, int a, int b)
484 u16b *who = (u16b*)(u);
489 monster_type *m_ptr1 = ¤t_floor_ptr->m_list[w1];
490 monster_type *m_ptr2 = ¤t_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];
497 if (w1 == p_ptr->riding) return TRUE;
498 if (w2 == p_ptr->riding) return FALSE;
500 if (m_ptr1->nickname && !m_ptr2->nickname) return TRUE;
501 if (m_ptr2->nickname && !m_ptr1->nickname) return FALSE;
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;
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;
509 if (r_ptr1->level > r_ptr2->level) return TRUE;
510 if (r_ptr2->level > r_ptr1->level) return FALSE;
512 if (m_ptr1->hp > m_ptr2->hp) return TRUE;
513 if (m_ptr2->hp > m_ptr1->hp) return FALSE;
520 * @brief フロア保存時のcurrent_floor_ptr->grid_array情報テンプレートをソートするための比較処理
521 * @param u current_floor_ptr->grid_arrayテンプレートの参照ポインタ
523 * @param a スワップするモンスター種族のID1
524 * @param b スワップするモンスター種族のID2
525 * @return aの方が大きければtrue
527 bool ang_sort_comp_cave_temp(vptr u, vptr v, int a, int b)
529 cave_template_type *who = (cave_template_type *)(u);
531 u16b o1 = who[a].occurrence;
532 u16b o2 = who[b].occurrence;
542 * @brief フロア保存時のcurrent_floor_ptr->grid_array情報テンプレートをソートするためのスワップ処理 / Sorting hook -- Swap function
543 * @param u current_floor_ptr->grid_arrayテンプレートの参照ポインタ
545 * @param a スワップするモンスター種族のID1
546 * @param b スワップするモンスター種族のID2
549 void ang_sort_swap_cave_temp(vptr u, vptr v, int a, int b)
551 cave_template_type *who = (cave_template_type *)(u);
553 cave_template_type holder;
566 * @brief 進化ツリーをソートするためモンスター種族の判定関数 /
567 * Sorting hook -- Comp function
570 * @param a 比較したいモンスター種族ID1
571 * @param b 比較したいモンスター種族ID2
572 * @return 2が大きければTRUEを返す
574 bool ang_sort_comp_evol_tree(vptr u, vptr v, int a, int b)
576 int **evol_tree = (int **)u;
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];
586 /* Used tree first */
587 if (w1 && !w2) return TRUE;
588 if (!w1 && w2) return FALSE;
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;
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;
598 /* Compare indexes */
603 * @brief 進化ツリーをソートするため木構造のスワップ関数 /
604 * Sorting hook -- Swap function
607 * @param a スワップしたい木構造1
608 * @param b スワップしたい木構造2
609 * @return 2が大きければTRUEを返す
611 void ang_sort_swap_evol_tree(vptr u, vptr v, int a, int b)
613 int **evol_tree = (int **)u;
620 holder = evol_tree[a];
621 evol_tree[a] = evol_tree[b];
622 evol_tree[b] = holder;