#include "angband.h"
#include "sort.h"
-
/*
* Angband sorting algorithm -- quick sort in place
*
* function hooks to interact with the data, which is given as
* two pointers, and which may have any user-defined form.
*/
-void ang_sort_aux(vptr u, vptr v, int p, int q)
+void ang_sort_aux(vptr u, vptr v, int p, int q,
+ bool(*ang_sort_comp)(vptr u, vptr v, int a, int b), void(*ang_sort_swap)(vptr u, vptr v, int a, int b))
{
int z, a, b;
}
/* Recurse left side */
- ang_sort_aux(u, v, p, b);
+ ang_sort_aux(u, v, p, b, ang_sort_comp, ang_sort_swap);
/* Recurse right side */
- ang_sort_aux(u, v, b + 1, q);
+ ang_sort_aux(u, v, b + 1, q, ang_sort_comp, ang_sort_swap);
}
* function hooks to interact with the data, which is given as
* two pointers, and which may have any user-defined form.
*/
-void ang_sort(vptr u, vptr v, int n)
+void ang_sort(vptr u, vptr v, int n,
+ bool(*ang_sort_comp)(vptr u, vptr v, int a, int b) , void(*ang_sort_swap)(vptr u, vptr v, int a, int b))
{
/* Sort the array */
- ang_sort_aux(u, v, 0, n - 1);
+ ang_sort_aux(u, v, 0, n - 1, ang_sort_comp, ang_sort_swap);
+}
+
+
+/*
+ * Sorting hook -- comp function -- by "distance to player"
+ *
+ * We use "u" and "v" to point to arrays of "x" and "y" positions,
+ * and sort the arrays by double-distance to the player.
+ */
+bool ang_sort_comp_distance(vptr u, vptr v, int a, int b)
+{
+ POSITION *x = (POSITION*)(u);
+ POSITION *y = (POSITION*)(v);
+
+ POSITION da, db, kx, ky;
+
+ /* Absolute distance components */
+ kx = x[a]; kx -= p_ptr->x; kx = ABS(kx);
+ ky = y[a]; ky -= p_ptr->y; ky = ABS(ky);
+
+ /* Approximate Double Distance to the first point */
+ da = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
+
+ /* Absolute distance components */
+ kx = x[b]; kx -= p_ptr->x; kx = ABS(kx);
+ ky = y[b]; ky -= p_ptr->y; ky = ABS(ky);
+
+ /* Approximate Double Distance to the first point */
+ db = ((kx > ky) ? (kx + kx + ky) : (ky + ky + kx));
+
+ /* Compare the distances */
+ return (da <= db);
+}
+
+
+/*
+ * Sorting hook -- comp function -- by importance level of grids
+ *
+ * We use "u" and "v" to point to arrays of "x" and "y" positions,
+ * and sort the arrays by level of monster
+ */
+bool ang_sort_comp_importance(vptr u, vptr v, int a, int b)
+{
+ POSITION *x = (POSITION*)(u);
+ POSITION *y = (POSITION*)(v);
+ grid_type *ca_ptr = ¤t_floor_ptr->grid_array[y[a]][x[a]];
+ grid_type *cb_ptr = ¤t_floor_ptr->grid_array[y[b]][x[b]];
+ monster_type *ma_ptr = ¤t_floor_ptr->m_list[ca_ptr->m_idx];
+ monster_type *mb_ptr = ¤t_floor_ptr->m_list[cb_ptr->m_idx];
+ monster_race *ap_ra_ptr, *ap_rb_ptr;
+
+ /* The player grid */
+ if (y[a] == p_ptr->y && x[a] == p_ptr->x) return TRUE;
+ if (y[b] == p_ptr->y && x[b] == p_ptr->x) return FALSE;
+
+ /* Extract monster race */
+ if (ca_ptr->m_idx && ma_ptr->ml) ap_ra_ptr = &r_info[ma_ptr->ap_r_idx];
+ else ap_ra_ptr = NULL;
+ if (cb_ptr->m_idx && mb_ptr->ml) ap_rb_ptr = &r_info[mb_ptr->ap_r_idx];
+ else ap_rb_ptr = NULL;
+
+ if (ap_ra_ptr && !ap_rb_ptr) return TRUE;
+ if (!ap_ra_ptr && ap_rb_ptr) return FALSE;
+
+ /* Compare two monsters */
+ if (ap_ra_ptr && ap_rb_ptr)
+ {
+ /* Unique monsters first */
+ if ((ap_ra_ptr->flags1 & RF1_UNIQUE) && !(ap_rb_ptr->flags1 & RF1_UNIQUE)) return TRUE;
+ if (!(ap_ra_ptr->flags1 & RF1_UNIQUE) && (ap_rb_ptr->flags1 & RF1_UNIQUE)) return FALSE;
+
+ /* Shadowers first (あやしい影) */
+ if ((ma_ptr->mflag2 & MFLAG2_KAGE) && !(mb_ptr->mflag2 & MFLAG2_KAGE)) return TRUE;
+ if (!(ma_ptr->mflag2 & MFLAG2_KAGE) && (mb_ptr->mflag2 & MFLAG2_KAGE)) return FALSE;
+
+ /* Unknown monsters first */
+ if (!ap_ra_ptr->r_tkills && ap_rb_ptr->r_tkills) return TRUE;
+ if (ap_ra_ptr->r_tkills && !ap_rb_ptr->r_tkills) return FALSE;
+
+ /* Higher level monsters first (if known) */
+ if (ap_ra_ptr->r_tkills && ap_rb_ptr->r_tkills)
+ {
+ if (ap_ra_ptr->level > ap_rb_ptr->level) return TRUE;
+ if (ap_ra_ptr->level < ap_rb_ptr->level) return FALSE;
+ }
+
+ /* Sort by index if all conditions are same */
+ if (ma_ptr->ap_r_idx > mb_ptr->ap_r_idx) return TRUE;
+ if (ma_ptr->ap_r_idx < mb_ptr->ap_r_idx) return FALSE;
+ }
+
+ /* An object get higher priority */
+ 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;
+ 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;
+
+ /* Priority from the terrain */
+ if (f_info[ca_ptr->feat].priority > f_info[cb_ptr->feat].priority) return TRUE;
+ if (f_info[ca_ptr->feat].priority < f_info[cb_ptr->feat].priority) return FALSE;
+
+ /* If all conditions are same, compare distance */
+ return ang_sort_comp_distance(u, v, a, b);
+}
+
+
+/*
+ * Sorting hook -- swap function -- by "distance to player"
+ *
+ * We use "u" and "v" to point to arrays of "x" and "y" positions,
+ * and sort the arrays by distance to the player.
+ */
+void ang_sort_swap_distance(vptr u, vptr v, int a, int b)
+{
+ POSITION *x = (POSITION*)(u);
+ POSITION *y = (POSITION*)(v);
+
+ POSITION temp;
+
+ /* Swap "x" */
+ temp = x[a];
+ x[a] = x[b];
+ x[b] = temp;
+
+ /* Swap "y" */
+ temp = y[a];
+ y[a] = y[b];
+ y[b] = temp;
+}
+
+
+
+/*
+ * Sorting hook -- Comp function -- see below
+ *
+ * We use "u" to point to array of monster indexes,
+ * and "v" to select the type of sorting to perform on "u".
+ */
+bool ang_sort_art_comp(vptr u, vptr v, int a, int b)
+{
+ u16b *who = (u16b*)(u);
+ u16b *why = (u16b*)(v);
+
+ int w1 = who[a];
+ int w2 = who[b];
+
+ int z1, z2;
+
+ /* Sort by total kills */
+ if (*why >= 3)
+ {
+ /* Extract total kills */
+ z1 = a_info[w1].tval;
+ z2 = a_info[w2].tval;
+
+ /* Compare total kills */
+ if (z1 < z2) return (TRUE);
+ if (z1 > z2) return (FALSE);
+ }
+
+
+ /* Sort by monster level */
+ if (*why >= 2)
+ {
+ /* Extract levels */
+ z1 = a_info[w1].sval;
+ z2 = a_info[w2].sval;
+
+ /* Compare levels */
+ if (z1 < z2) return (TRUE);
+ if (z1 > z2) return (FALSE);
+ }
+
+
+ /* Sort by monster experience */
+ if (*why >= 1)
+ {
+ /* Extract experience */
+ z1 = a_info[w1].level;
+ z2 = a_info[w2].level;
+
+ /* Compare experience */
+ if (z1 < z2) return (TRUE);
+ if (z1 > z2) return (FALSE);
+ }
+
+
+ /* Compare indexes */
+ return (w1 <= w2);
+}
+
+
+/*
+ * Sorting hook -- Swap function -- see below
+ *
+ * We use "u" to point to array of monster indexes,
+ * and "v" to select the type of sorting to perform.
+ */
+void ang_sort_art_swap(vptr u, vptr v, int a, int b)
+{
+ u16b *who = (u16b*)(u);
+ u16b holder;
+
+ /* Unused */
+ (void)v;
+
+ /* Swap */
+ holder = who[a];
+ who[a] = who[b];
+ who[b] = holder;
+}
+
+bool ang_sort_comp_quest_num(vptr u, vptr v, int a, int b)
+{
+ QUEST_IDX *q_num = (QUEST_IDX *)u;
+ quest_type *qa = &quest[q_num[a]];
+ quest_type *qb = &quest[q_num[b]];
+
+ /* Unused */
+ (void)v;
+
+ return (qa->comptime != qb->comptime) ?
+ (qa->comptime < qb->comptime) :
+ (qa->level <= qb->level);
}
+void ang_sort_swap_quest_num(vptr u, vptr v, int a, int b)
+{
+ QUEST_IDX *q_num = (QUEST_IDX *)u;
+ QUEST_IDX tmp;
+
+ /* Unused */
+ (void)v;
+
+ tmp = q_num[a];
+ q_num[a] = q_num[b];
+ q_num[b] = tmp;
+}
+
+
+/*!
+* @brief ペット入りモンスターボールをソートするための比較関数
+* @param u 所持品配列の参照ポインタ
+* @param v 未使用
+* @param a 所持品ID1
+* @param b 所持品ID2
+* @return 1の方が大であればTRUE
+*/
+bool ang_sort_comp_pet(vptr u, vptr v, int a, int b)
+{
+ u16b *who = (u16b*)(u);
+
+ int w1 = who[a];
+ int w2 = who[b];
+
+ monster_type *m_ptr1 = ¤t_floor_ptr->m_list[w1];
+ monster_type *m_ptr2 = ¤t_floor_ptr->m_list[w2];
+ monster_race *r_ptr1 = &r_info[m_ptr1->r_idx];
+ monster_race *r_ptr2 = &r_info[m_ptr2->r_idx];
+
+ /* Unused */
+ (void)v;
+
+ if (m_ptr1->nickname && !m_ptr2->nickname) return TRUE;
+ if (m_ptr2->nickname && !m_ptr1->nickname) return FALSE;
+
+ if ((r_ptr1->flags1 & RF1_UNIQUE) && !(r_ptr2->flags1 & RF1_UNIQUE)) return TRUE;
+ if ((r_ptr2->flags1 & RF1_UNIQUE) && !(r_ptr1->flags1 & RF1_UNIQUE)) return FALSE;
+ if (r_ptr1->level > r_ptr2->level) return TRUE;
+ if (r_ptr2->level > r_ptr1->level) return FALSE;
+ if (m_ptr1->hp > m_ptr2->hp) return TRUE;
+ if (m_ptr2->hp > m_ptr1->hp) return FALSE;
+
+ return w1 <= w2;
+}
+
+
+
+/*!
+ * @brief モンスター種族情報を特定の基準によりソートするための比較処理
+ * Sorting hook -- Comp function -- see below
+ * @param u モンスター種族情報の入れるポインタ
+ * @param v 条件基準ID
+ * @param a 比較するモンスター種族のID1
+ * @param b 比較するモンスター種族のID2
+ * @return 2の方が大きければTRUEを返す
+ * We use "u" to point to array of monster indexes,
+ * and "v" to select the type of sorting to perform on "u".
+ */
+bool ang_sort_comp_hook(vptr u, vptr v, int a, int b)
+{
+ u16b *who = (u16b*)(u);
+ u16b *why = (u16b*)(v);
+
+ int w1 = who[a];
+ int w2 = who[b];
+
+ int z1, z2;
+
+ /* Sort by player kills */
+ if (*why >= 4)
+ {
+ /* Extract player kills */
+ z1 = r_info[w1].r_pkills;
+ z2 = r_info[w2].r_pkills;
+
+ /* Compare player kills */
+ if (z1 < z2) return (TRUE);
+ if (z1 > z2) return (FALSE);
+ }
+
+
+ /* Sort by total kills */
+ if (*why >= 3)
+ {
+ /* Extract total kills */
+ z1 = r_info[w1].r_tkills;
+ z2 = r_info[w2].r_tkills;
+
+ /* Compare total kills */
+ if (z1 < z2) return (TRUE);
+ if (z1 > z2) return (FALSE);
+ }
+
+
+ /* Sort by monster level */
+ if (*why >= 2)
+ {
+ /* Extract levels */
+ z1 = r_info[w1].level;
+ z2 = r_info[w2].level;
+
+ /* Compare levels */
+ if (z1 < z2) return (TRUE);
+ if (z1 > z2) return (FALSE);
+ }
+
+
+ /* Sort by monster experience */
+ if (*why >= 1)
+ {
+ /* Extract experience */
+ z1 = r_info[w1].mexp;
+ z2 = r_info[w2].mexp;
+
+ /* Compare experience */
+ if (z1 < z2) return (TRUE);
+ if (z1 > z2) return (FALSE);
+ }
+
+
+ /* Compare indexes */
+ return (w1 <= w2);
+}
+
+
+/*!
+ * @brief モンスター種族情報を特定の基準によりソートするためのスワップ処理
+ * Sorting hook -- Swap function -- see below
+ * @param u モンスター種族情報の入れるポインタ
+ * @param v 未使用
+ * @param a スワップするモンスター種族のID1
+ * @param b スワップするモンスター種族のID2
+ * @return なし
+ * @details
+ * We use "u" to point to array of monster indexes,
+ * and "v" to select the type of sorting to perform.
+ */
+void ang_sort_swap_hook(vptr u, vptr v, int a, int b)
+{
+ u16b *who = (u16b*)(u);
+ u16b holder;
+
+ /* Unused */
+ (void)v;
+
+ /* Swap */
+ holder = who[a];
+ who[a] = who[b];
+ who[b] = holder;
+}
+
+/*
+ * hook function to sort monsters by level
+ */
+bool ang_sort_comp_monster_level(vptr u, vptr v, int a, int b)
+{
+ u16b *who = (u16b*)(u);
+
+ int w1 = who[a];
+ int w2 = who[b];
+
+ monster_race *r_ptr1 = &r_info[w1];
+ monster_race *r_ptr2 = &r_info[w2];
+
+ /* Unused */
+ (void)v;
+
+ if (r_ptr2->level > r_ptr1->level) return TRUE;
+ if (r_ptr1->level > r_ptr2->level) return FALSE;
+
+ if ((r_ptr2->flags1 & RF1_UNIQUE) && !(r_ptr1->flags1 & RF1_UNIQUE)) return TRUE;
+ if ((r_ptr1->flags1 & RF1_UNIQUE) && !(r_ptr2->flags1 & RF1_UNIQUE)) return FALSE;
+ return w1 <= w2;
+}
+
+
+/*!
+* @brief ペットになっているモンスターをソートするための比較処理
+* @param u モンスターの構造体配列
+* @param v 未使用
+* @param a 比較対象のモンスターID1
+* @param b 比較対象のモンスターID2
+* @return 2番目が大ならばTRUEを返す
+*/
+bool ang_sort_comp_pet_dismiss(vptr u, vptr v, int a, int b)
+{
+ u16b *who = (u16b*)(u);
+
+ int w1 = who[a];
+ int w2 = who[b];
+
+ monster_type *m_ptr1 = ¤t_floor_ptr->m_list[w1];
+ monster_type *m_ptr2 = ¤t_floor_ptr->m_list[w2];
+ monster_race *r_ptr1 = &r_info[m_ptr1->r_idx];
+ monster_race *r_ptr2 = &r_info[m_ptr2->r_idx];
+
+ /* Unused */
+ (void)v;
+
+ if (w1 == p_ptr->riding) return TRUE;
+ if (w2 == p_ptr->riding) return FALSE;
+
+ if (m_ptr1->nickname && !m_ptr2->nickname) return TRUE;
+ if (m_ptr2->nickname && !m_ptr1->nickname) return FALSE;
+
+ if (!m_ptr1->parent_m_idx && m_ptr2->parent_m_idx) return TRUE;
+ if (!m_ptr2->parent_m_idx && m_ptr1->parent_m_idx) return FALSE;
+
+ if ((r_ptr1->flags1 & RF1_UNIQUE) && !(r_ptr2->flags1 & RF1_UNIQUE)) return TRUE;
+ if ((r_ptr2->flags1 & RF1_UNIQUE) && !(r_ptr1->flags1 & RF1_UNIQUE)) return FALSE;
+
+ if (r_ptr1->level > r_ptr2->level) return TRUE;
+ if (r_ptr2->level > r_ptr1->level) return FALSE;
+
+ if (m_ptr1->hp > m_ptr2->hp) return TRUE;
+ if (m_ptr2->hp > m_ptr1->hp) return FALSE;
+
+ return w1 <= w2;
+}
+
+
+/*!
+ * @brief フロア保存時のcurrent_floor_ptr->grid_array情報テンプレートをソートするための比較処理
+ * @param u current_floor_ptr->grid_arrayテンプレートの参照ポインタ
+ * @param v 未使用
+ * @param a スワップするモンスター種族のID1
+ * @param b スワップするモンスター種族のID2
+ * @return aの方が大きければtrue
+ */
+bool ang_sort_comp_cave_temp(vptr u, vptr v, int a, int b)
+{
+ cave_template_type *who = (cave_template_type *)(u);
+
+ u16b o1 = who[a].occurrence;
+ u16b o2 = who[b].occurrence;
+
+ /* Unused */
+ (void)v;
+
+ return o2 <= o1;
+}
+
+
+/*!
+ * @brief フロア保存時のcurrent_floor_ptr->grid_array情報テンプレートをソートするためのスワップ処理 / Sorting hook -- Swap function
+ * @param u current_floor_ptr->grid_arrayテンプレートの参照ポインタ
+ * @param v 未使用
+ * @param a スワップするモンスター種族のID1
+ * @param b スワップするモンスター種族のID2
+ * @return なし
+ */
+void ang_sort_swap_cave_temp(vptr u, vptr v, int a, int b)
+{
+ cave_template_type *who = (cave_template_type *)(u);
+
+ cave_template_type holder;
+
+ /* Unused */
+ (void)v;
+
+ /* Swap */
+ holder = who[a];
+ who[a] = who[b];
+ who[b] = holder;
+}
+
+
+/*!
+ * @brief 進化ツリーをソートするためモンスター種族の判定関数 /
+ * Sorting hook -- Comp function
+ * @param u 進化木構造データ
+ * @param v 未使用
+ * @param a 比較したいモンスター種族ID1
+ * @param b 比較したいモンスター種族ID2
+ * @return 2が大きければTRUEを返す
+ */
+bool ang_sort_comp_evol_tree(vptr u, vptr v, int a, int b)
+{
+ int **evol_tree = (int **)u;
+
+ int w1 = evol_tree[a][0];
+ int w2 = evol_tree[b][0];
+ monster_race *r1_ptr = &r_info[w1];
+ monster_race *r2_ptr = &r_info[w2];
+
+ /* Unused */
+ (void)v;
+
+ /* Used tree first */
+ if (w1 && !w2) return TRUE;
+ if (!w1 && w2) return FALSE;
+
+ /* Sort by monster level */
+ if (r1_ptr->level < r2_ptr->level) return TRUE;
+ if (r1_ptr->level > r2_ptr->level) return FALSE;
+
+ /* Sort by monster experience */
+ if (r1_ptr->mexp < r2_ptr->mexp) return TRUE;
+ if (r1_ptr->mexp > r2_ptr->mexp) return FALSE;
+
+ /* Compare indexes */
+ return w1 <= w2;
+}
+
+/*!
+ * @brief 進化ツリーをソートするため木構造のスワップ関数 /
+ * Sorting hook -- Swap function
+ * @param u 進化木構造データ
+ * @param v 未使用
+ * @param a スワップしたい木構造1
+ * @param b スワップしたい木構造2
+ * @return 2が大きければTRUEを返す
+ */
+void ang_sort_swap_evol_tree(vptr u, vptr v, int a, int b)
+{
+ int **evol_tree = (int **)u;
+ int *holder;
+
+ /* Unused */
+ (void)v;
+
+ /* Swap */
+ holder = evol_tree[a];
+ evol_tree[a] = evol_tree[b];
+ evol_tree[b] = holder;
+}