src/sort.c

   1 #include "angband.h"
   2 #include "sort.h"
   3
   4
   5 /*
   6  * Angband sorting algorithm -- quick sort in place
   7  *
   8  * Note that the details of the data we are sorting is hidden,
   9  * and we rely on the "ang_sort_comp()" and "ang_sort_swap()"
  10  * function hooks to interact with the data, which is given as
  11  * two pointers, and which may have any user-defined form.
  12  */
  13 void ang_sort_aux(vptr u, vptr v, int p, int q)
  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);
  48
  49         /* Recurse right side */
  50         ang_sort_aux(u, v, b + 1, q);
  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 {
  64         /* Sort the array */
  65         ang_sort_aux(u, v, 0, n - 1);
  66 }
  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
 267         u16b holder;
 268
 269         /* Unused */
 270         (void)v;
 271
 272         /* Swap */
 273         holder = who[a];
 274         who[a] = who[b];
 275         who[b] = holder;
 276 }
 277
 278 bool ang_sort_comp_quest_num(vptr u, vptr v, int a, int b)
 279 {
 280         QUEST_IDX *q_num = (QUEST_IDX *)u;
 281         quest_type *qa = &quest[q_num[a]];
 282         quest_type *qb = &quest[q_num[b]];
 283
 284         /* Unused */
 285         (void)v;
 286
 287         return (qa->comptime != qb->comptime) ?
 288                 (qa->comptime < qb->comptime) :
 289                 (qa->level <= qb->level);
 290 }
 291
 292 void ang_sort_swap_quest_num(vptr u, vptr v, int a, int b)
 293 {
 294         QUEST_IDX *q_num = (QUEST_IDX *)u;
 295         QUEST_IDX tmp;
 296
 297         /* Unused */
 298         (void)v;
 299
 300         tmp = q_num[a];
 301         q_num[a] = q_num[b];
 302         q_num[b] = tmp;
 303 }
 304