src/libs/ck-libs/metis/GKlib/sort.c

   1 /*!
   2 \file  sort.c
   3 \brief This file contains GKlib's various sorting routines
   4
   5 These routines are implemented using the GKSORT macro that is defined
   6 in gk_qsort.h and is based on GNU's GLIBC qsort() implementation.
   7
   8 Additional sorting routines can be created using the same way that
   9 these routines where defined.
  10
  11 \date   Started 4/4/07
  12 \author George
  13 \version\verbatim $Id: sort.c 10796 2011-09-23 21:33:09Z karypis $ \endverbatim
  14 */
  15
  16 #include <GKlib.h>
  17
  18
  19
  20 /*************************************************************************/
  21 /*! Sorts an array of chars in increasing order */
  22 /*************************************************************************/
  23 void gk_csorti(size_t n, char *base)
  24 {
  25 #define char_lt(a, b) ((*a) < (*b))
  26   GK_MKQSORT(char, base, n, char_lt);
  27 #undef char_lt
  28 }
  29
  30
  31 /*************************************************************************/
  32 /*! Sorts an array of chars in decreasing order */
  33 /*************************************************************************/
  34 void gk_csortd(size_t n, char *base)
  35 {
  36 #define char_gt(a, b) ((*a) > (*b))
  37   GK_MKQSORT(char, base, n, char_gt);
  38 #undef char_gt
  39 }
  40
  41
  42 /*************************************************************************/
  43 /*! Sorts an array of integers in increasing order */
  44 /*************************************************************************/
  45 void gk_isorti(size_t n, int *base)
  46 {
  47 #define int_lt(a, b) ((*a) < (*b))
  48   GK_MKQSORT(int, base, n, int_lt);
  49 #undef int_lt
  50 }
  51
  52
  53 /*************************************************************************/
  54 /*! Sorts an array of integers in decreasing order */
  55 /*************************************************************************/
  56 void gk_isortd(size_t n, int *base)
  57 {
  58 #define int_gt(a, b) ((*a) > (*b))
  59   GK_MKQSORT(int, base, n, int_gt);
  60 #undef int_gt
  61 }
  62
  63
  64 /*************************************************************************/
  65 /*! Sorts an array of floats in increasing order */
  66 /*************************************************************************/
  67 void gk_fsorti(size_t n, float *base)
  68 {
  69 #define float_lt(a, b) ((*a) < (*b))
  70   GK_MKQSORT(float, base, n, float_lt);
  71 #undef float_lt
  72 }
  73
  74
  75 /*************************************************************************/
  76 /*! Sorts an array of floats in decreasing order */
  77 /*************************************************************************/
  78 void gk_fsortd(size_t n, float *base)
  79 {
  80 #define float_gt(a, b) ((*a) > (*b))
  81   GK_MKQSORT(float, base, n, float_gt);
  82 #undef float_gt
  83 }
  84
  85
  86 /*************************************************************************/
  87 /*! Sorts an array of doubles in increasing order */
  88 /*************************************************************************/
  89 void gk_dsorti(size_t n, double *base)
  90 {
  91 #define double_lt(a, b) ((*a) < (*b))
  92   GK_MKQSORT(double, base, n, double_lt);
  93 #undef double_lt
  94 }
  95
  96
  97 /*************************************************************************/
  98 /*! Sorts an array of doubles in decreasing order */
  99 /*************************************************************************/
 100 void gk_dsortd(size_t n, double *base)
 101 {
 102 #define double_gt(a, b) ((*a) > (*b))
 103   GK_MKQSORT(double, base, n, double_gt);
 104 #undef double_gt
 105 }
 106
 107
 108 /*************************************************************************/
 109 /*! Sorts an array of gk_idx_t in increasing order */
 110 /*************************************************************************/
 111 void gk_idxsorti(size_t n, gk_idx_t *base)
 112 {
 113 #define idx_lt(a, b) ((*a) < (*b))
 114   GK_MKQSORT(gk_idx_t, base, n, idx_lt);
 115 #undef idx_lt
 116 }
 117
 118
 119 /*************************************************************************/
 120 /*! Sorts an array of gk_idx_t in decreasing order */
 121 /*************************************************************************/
 122 void gk_idxsortd(size_t n, gk_idx_t *base)
 123 {
 124 #define idx_gt(a, b) ((*a) > (*b))
 125   GK_MKQSORT(gk_idx_t, base, n, idx_gt);
 126 #undef idx_gt
 127 }
 128
 129
 130
 131
 132 /*************************************************************************/
 133 /*! Sorts an array of gk_ckv_t in increasing order */
 134 /*************************************************************************/
 135 void gk_ckvsorti(size_t n, gk_ckv_t *base)
 136 {
 137 #define ckey_lt(a, b) ((a)->key < (b)->key)
 138   GK_MKQSORT(gk_ckv_t, base, n, ckey_lt);
 139 #undef ckey_lt
 140 }
 141
 142
 143 /*************************************************************************/
 144 /*! Sorts an array of gk_ckv_t in decreasing order */
 145 /*************************************************************************/
 146 void gk_ckvsortd(size_t n, gk_ckv_t *base)
 147 {
 148 #define ckey_gt(a, b) ((a)->key > (b)->key)
 149   GK_MKQSORT(gk_ckv_t, base, n, ckey_gt);
 150 #undef ckey_gt
 151 }
 152
 153
 154 /*************************************************************************/
 155 /*! Sorts an array of gk_ikv_t in increasing order */
 156 /*************************************************************************/
 157 void gk_ikvsorti(size_t n, gk_ikv_t *base)
 158 {
 159 #define ikey_lt(a, b) ((a)->key < (b)->key)
 160   GK_MKQSORT(gk_ikv_t, base, n, ikey_lt);
 161 #undef ikey_lt
 162 }
 163
 164
 165 /*************************************************************************/
 166 /*! Sorts an array of gk_ikv_t in decreasing order */
 167 /*************************************************************************/
 168 void gk_ikvsortd(size_t n, gk_ikv_t *base)
 169 {
 170 #define ikey_gt(a, b) ((a)->key > (b)->key)
 171   GK_MKQSORT(gk_ikv_t, base, n, ikey_gt);
 172 #undef ikey_gt
 173 }
 174
 175
 176 /*************************************************************************/
 177 /*! Sorts an array of gk_i32kv_t in increasing order */
 178 /*************************************************************************/
 179 void gk_i32kvsorti(size_t n, gk_i32kv_t *base)
 180 {
 181 #define ikey_lt(a, b) ((a)->key < (b)->key)
 182   GK_MKQSORT(gk_i32kv_t, base, n, ikey_lt);
 183 #undef ikey_lt
 184 }
 185
 186
 187 /*************************************************************************/
 188 /*! Sorts an array of gk_i32kv_t in decreasing order */
 189 /*************************************************************************/
 190 void gk_i32kvsortd(size_t n, gk_i32kv_t *base)
 191 {
 192 #define ikey_gt(a, b) ((a)->key > (b)->key)
 193   GK_MKQSORT(gk_i32kv_t, base, n, ikey_gt);
 194 #undef ikey_gt
 195 }
 196
 197
 198 /*************************************************************************/
 199 /*! Sorts an array of gk_i64kv_t in increasing order */
 200 /*************************************************************************/
 201 void gk_i64kvsorti(size_t n, gk_i64kv_t *base)
 202 {
 203 #define ikey_lt(a, b) ((a)->key < (b)->key)
 204   GK_MKQSORT(gk_i64kv_t, base, n, ikey_lt);
 205 #undef ikey_lt
 206 }
 207
 208
 209 /*************************************************************************/
 210 /*! Sorts an array of gk_i64kv_t in decreasing order */
 211 /*************************************************************************/
 212 void gk_i64kvsortd(size_t n, gk_i64kv_t *base)
 213 {
 214 #define ikey_gt(a, b) ((a)->key > (b)->key)
 215   GK_MKQSORT(gk_i64kv_t, base, n, ikey_gt);
 216 #undef ikey_gt
 217 }
 218
 219
 220 /*************************************************************************/
 221 /*! Sorts an array of gk_zkv_t in increasing order */
 222 /*************************************************************************/
 223 void gk_zkvsorti(size_t n, gk_zkv_t *base)
 224 {
 225 #define zkey_lt(a, b) ((a)->key < (b)->key)
 226   GK_MKQSORT(gk_zkv_t, base, n, zkey_lt);
 227 #undef zkey_lt
 228 }
 229
 230
 231 /*************************************************************************/
 232 /*! Sorts an array of gk_zkv_t in decreasing order */
 233 /*************************************************************************/
 234 void gk_zkvsortd(size_t n, gk_zkv_t *base)
 235 {
 236 #define zkey_gt(a, b) ((a)->key > (b)->key)
 237   GK_MKQSORT(gk_zkv_t, base, n, zkey_gt);
 238 #undef zkey_gt
 239 }
 240
 241
 242 /*************************************************************************/
 243 /*! Sorts an array of gk_fkv_t in increasing order */
 244 /*************************************************************************/
 245 void gk_fkvsorti(size_t n, gk_fkv_t *base)
 246 {
 247 #define fkey_lt(a, b) ((a)->key < (b)->key)
 248   GK_MKQSORT(gk_fkv_t, base, n, fkey_lt);
 249 #undef fkey_lt
 250 }
 251
 252
 253 /*************************************************************************/
 254 /*! Sorts an array of gk_fkv_t in decreasing order */
 255 /*************************************************************************/
 256 void gk_fkvsortd(size_t n, gk_fkv_t *base)
 257 {
 258 #define fkey_gt(a, b) ((a)->key > (b)->key)
 259   GK_MKQSORT(gk_fkv_t, base, n, fkey_gt);
 260 #undef fkey_gt
 261 }
 262
 263
 264 /*************************************************************************/
 265 /*! Sorts an array of gk_dkv_t in increasing order */
 266 /*************************************************************************/
 267 void gk_dkvsorti(size_t n, gk_dkv_t *base)
 268 {
 269 #define dkey_lt(a, b) ((a)->key < (b)->key)
 270   GK_MKQSORT(gk_dkv_t, base, n, dkey_lt);
 271 #undef dkey_lt
 272 }
 273
 274
 275 /*************************************************************************/
 276 /*! Sorts an array of gk_fkv_t in decreasing order */
 277 /*************************************************************************/
 278 void gk_dkvsortd(size_t n, gk_dkv_t *base)
 279 {
 280 #define dkey_gt(a, b) ((a)->key > (b)->key)
 281   GK_MKQSORT(gk_dkv_t, base, n, dkey_gt);
 282 #undef dkey_gt
 283 }
 284
 285
 286 /*************************************************************************/
 287 /*! Sorts an array of gk_skv_t in increasing order */
 288 /*************************************************************************/
 289 void gk_skvsorti(size_t n, gk_skv_t *base)
 290 {
 291 #define skey_lt(a, b) (strcmp((a)->key, (b)->key) < 0)
 292   GK_MKQSORT(gk_skv_t, base, n, skey_lt);
 293 #undef skey_lt
 294 }
 295
 296
 297 /*************************************************************************/
 298 /*! Sorts an array of gk_skv_t in decreasing order */
 299 /*************************************************************************/
 300 void gk_skvsortd(size_t n, gk_skv_t *base)
 301 {
 302 #define skey_gt(a, b) (strcmp((a)->key, (b)->key) > 0)
 303   GK_MKQSORT(gk_skv_t, base, n, skey_gt);
 304 #undef skey_gt
 305 }
 306
 307
 308 /*************************************************************************/
 309 /*! Sorts an array of gk_idxkv_t in increasing order */
 310 /*************************************************************************/
 311 void gk_idxkvsorti(size_t n, gk_idxkv_t *base)
 312 {
 313 #define idxkey_lt(a, b) ((a)->key < (b)->key)
 314   GK_MKQSORT(gk_idxkv_t, base, n, idxkey_lt);
 315 #undef idxkey_lt
 316 }
 317
 318
 319 /*************************************************************************/
 320 /*! Sorts an array of gk_idxkv_t in decreasing order */
 321 /*************************************************************************/
 322 void gk_idxkvsortd(size_t n, gk_idxkv_t *base)
 323 {
 324 #define idxkey_gt(a, b) ((a)->key > (b)->key)
 325   GK_MKQSORT(gk_idxkv_t, base, n, idxkey_gt);
 326 #undef idxkey_gt
 327 }