/**
 * \file sort.c
 * \brief Sorting and comparision functions
 */
#include "copyrite.h"

#include "config.h"
#include <string.h>
#include <math.h>
#include "conf.h"
#include "externs.h"
#include "parse.h"
#include "ansi.h"
#include "command.h"
#include "sort.h"
#include "confmagic.h"


#define EPSILON 0.000000001  /**< limit of precision for float equality */

/** qsort() comparision routine for int */
int
int_comp(const void *s1, const void *s2)
{
  int a, b;

  a = *(const int *) s1;
  b = *(const int *) s2;

  if (a == b)
    return 0;
  else if (a < b)
    return -1;
  else
    return 1;
}


/** qsort() comparision routine for unsigned int */
int
uint_comp(const void *s1, const void *s2)
{
  unsigned int a, b;

  a = *(const unsigned int *) s1;
  b = *(const unsigned int *) s2;

  if (a == b)
    return 0;
  else if (a < b)
    return -1;
  else
    return 1;
}


/** qsort() comparision routine for NVAL/double */
int
nval_comp(const void *a, const void *b)
{
  const NVAL *x = a, *y = b;
  const double epsilon = pow(10.0, -FLOAT_PRECISION);
  int eq = (fabs(*x - *y) <= (epsilon * fabs(*x)));
  return eq ? 0 : (*x > *y ? 1 : -1);
}


/** qsort() comparision routine for strings.
 * Uses strcmp()
 */
int
str_comp(const void *s1, const void *s2)
{
  const char *a, *b;

  a = *(const char **) s1;
  b = *(const char **) s2;

  return strcmp(a, b);
}

/** qsort() comparision routine for strings.
 * Uses strcasecmp().
 * Case-insensitive.
 */
int
stri_comp(const void *s1, const void *s2)
{
  const char *a, *b;

  a = *(const char **) s1;
  b = *(const char **) s2;

  return strcasecmp(a, b);
}

/** qsort() comparision routine for dbrefs. */
int
dbref_comp(const void *s1, const void *s2)
{
  dbref a, b;

  a = *(const dbref *) s1;
  b = *(const dbref *) s2;

  if (a == b)
    return 0;
  else if (a < b)
    return -1;
  else
    return 1;
}


dbref ucomp_executor, ucomp_caller, ucomp_enactor;
char ucomp_buff[BUFFER_LEN];
PE_Info *ucomp_pe_info;

/** qsort() comparision routine used by sortby() */
int
u_comp(const void *s1, const void *s2)
{
  char result[BUFFER_LEN], *rp;
  char const *tbuf;
  int n;

  /* Our two arguments are passed as %0 and %1 to the sortby u-function. */

  /* Note that this function is for use in conjunction with our own
   * sane_qsort routine, NOT with the standard library qsort!
   */
  global_eval_context.wenv[0] = (char *) s1;
  global_eval_context.wenv[1] = (char *) s2;

  /* Run the u-function, which should return a number. */

  tbuf = ucomp_buff;
  rp = result;
  if (process_expression(result, &rp, &tbuf,
                         ucomp_executor, ucomp_caller, ucomp_enactor,
                         PE_DEFAULT, PT_DEFAULT, ucomp_pe_info))
    return 0;
  n = parse_integer(result);

  return n;
}



/** Used with fun_sortby()
 *
 * Based on Andrew Molitor's qsort, which doesn't require transitivity
 * between comparisons (essential for preventing crashes due to
 * boneheads who write comparison functions where a > b doesn't mean b
 * < a).
 *
 * Actually, this sort doesn't require commutivity.
 * Sorting doesn't make sense without transitivity...
 */

void
sane_qsort(void *array[], int left, int right, comp_func compare)
{

  int i, last;
  void *tmp;

loop:
  if (left >= right)
    return;

  /* Pick something at random at swap it into the leftmost slot   */
  /* This is the pivot, we'll put it back in the right spot later */

  i = get_random_long(left, right);
  tmp = array[i];
  array[i] = array[left];
  array[left] = tmp;

  last = left;
  for (i = left + 1; i <= right; i++) {

    /* Walk the array, looking for stuff that's less than our */
    /* pivot. If it is, swap it with the next thing along     */

    if (compare(array[i], array[left]) < 0) {
      last++;
      if (last == i)
        continue;

      tmp = array[last];
      array[last] = array[i];
      array[i] = tmp;
    }
  }

  /* Now we put the pivot back, it's now in the right spot, we never */
  /* need to look at it again, trust me.                             */

  tmp = array[last];
  array[last] = array[left];
  array[left] = tmp;

  /* At this point everything underneath the 'last' index is < the */
  /* entry at 'last' and everything above it is not < it.          */

  if ((last - left) < (right - last)) {
    sane_qsort(array, left, last - 1, compare);
    left = last + 1;
    goto loop;
  } else {
    sane_qsort(array, last + 1, right, compare);
    right = last - 1;
    goto loop;
  }
}




/****************************** gensort ************/

typedef struct sort_record s_rec;

/** Sorting strings by different values. We store both the string and
 * its 'key' to sort by. Sort of a hardcode munge.
 */
struct sort_record {
  char *ptr;     /**< NULL except for sortkey */
  char *val;     /**< The string this is */
  dbref db;      /**< dbref (default 0, bad is -1) */
  char *str;     /**< string comparisons */
  int num;       /**< integer comparisons */
  NVAL numval;   /**< float comparisons */
  int freestr;   /**< free str on completion */
};


#define GENRECORD(x) void x(s_rec *rec,dbref player,char *sortflags); \
  void x(s_rec *rec, \
    dbref player __attribute__ ((__unused__)), \
    char *sortflags __attribute__ ((__unused__)))



GENRECORD(gen_alphanum)
{
  size_t len;
  if (strchr(rec->val, ESC_CHAR) || strchr(rec->val, TAG_START)) {
    rec->str = mush_strdup(remove_markup(rec->val, &len), "genrecord");
    rec->freestr = 1;
  } else {
    rec->str = rec->val;
  }
}

GENRECORD(gen_dbref)
{
  rec->num = qparse_dbref(rec->val);
}

GENRECORD(gen_num)
{
  rec->num = parse_integer(rec->val);
}

GENRECORD(gen_float)
{
  rec->numval = parse_number(rec->val);
}

#define RealGoodObject(x) (GoodObject(x) && !IsGarbage(x))

GENRECORD(gen_db_name)
{
  rec->str = (char *) "";
  if (RealGoodObject(rec->db))
    rec->str = (char *) Name(rec->db);
}

GENRECORD(gen_db_idle)
{
  rec->num = -1;
  if (RealGoodObject(rec->db)) {
    if (Priv_Who(player))
      rec->num = least_idle_time_priv(rec->db);
    else
      rec->num = least_idle_time(rec->db);
  }
}

GENRECORD(gen_db_conn)
{
  rec->num = -1;
  if (RealGoodObject(rec->db)) {
    if (Priv_Who(player))
      rec->num = most_conn_time_priv(rec->db);
    else
      rec->num = most_conn_time(rec->db);
  }
}

GENRECORD(gen_db_ctime)
{
  if (RealGoodObject(rec->db))
    rec->num = CreTime(rec->db);
}

GENRECORD(gen_db_owner)
{
  if (RealGoodObject(rec->db))
    rec->num = Owner(rec->db);
}

GENRECORD(gen_db_loc)
{
  rec->num = -1;
  if (RealGoodObject(rec->db) && Can_Locate(player, rec->db)) {
    rec->num = Location(rec->db);
  }
}

GENRECORD(gen_db_attr)
{
  /* Eek, I hate dealing with memory issues. */

  static char *defstr = (char *) "";
  const char *ptr;

  rec->str = defstr;
  if (RealGoodObject(rec->db) && sortflags && *sortflags &&
      (ptr = do_get_attrib(player, rec->db, sortflags)) != NULL) {
    rec->str = mush_strdup(ptr, "genrecord");
    rec->freestr = 1;
  }
}


typedef int (*qsort_func) (const void *, const void *);
typedef void (*makerecord) (s_rec *, dbref player, char *sortflags);


/* Compare(r,x,y) {
 *   if (x->db < 0 && y->db < 0)
 *     return 0;  // Garbage is identical.
 *   if (x->db < 0)
 *     return 2;  // Garbage goes last.
 *   if (y->db < 0)
 *     return -2; // Garbage goes last.
 *   if (r < 0)
 *     return -2; // different
 *   if (r > 0)
 *     return 2;  // different
 *   if (x->db < y->db)
 *     return -1; // similar
 *   if (y->db < x-db)
 *     return 1;  // similar
 *   return 0;    // identical
 * }
 */

/* If I could, I'd let sort() toss out non-existant dbrefs
 * Instead, sort stuffs them into a jumble at the end. */

#define Compare(r,x,y) \
        ((x->db < 0 || y->db < 0) ? \
           ((x->db < 0 && y->db < 0) ? 0 : (x->db < 0 ? 2 : -2)) \
           : ((fabs((double)r) > 0.000000001) ? (r < 0 ? -2 : 2) \
             : (x->db == y->db ? 0 : (x->db < y->db ? -1 : 1)) \
           ) \
         )

static int
s_comp(const void *s1, const void *s2)
{
  const s_rec *sr1 = (const s_rec *) s1;
  const s_rec *sr2 = (const s_rec *) s2;
  int res = 0;
  res = strcoll(sr1->str, sr2->str);
  return Compare(res, sr1, sr2);
}

static int
si_comp(const void *s1, const void *s2)
{
  const s_rec *sr1 = (const s_rec *) s1;
  const s_rec *sr2 = (const s_rec *) s2;
  int res = 0;
  res = strcasecoll(sr1->str, sr2->str);
  return Compare(res, sr1, sr2);
}

static int
i_comp(const void *s1, const void *s2)
{
  const s_rec *sr1 = (const s_rec *) s1;
  const s_rec *sr2 = (const s_rec *) s2;
  int res = 0;
  res = sr1->num - sr2->num;
  return Compare(res, sr1, sr2);
}

static int
f_comp(const void *s1, const void *s2)
{
  const s_rec *sr1 = (const s_rec *) s1;
  const s_rec *sr2 = (const s_rec *) s2;
  NVAL res = 0;
  res = sr1->numval - sr2->numval;
  return Compare(res, sr1, sr2);
}

typedef struct _list_type_list_ {
  char *name;
  makerecord make_record;
  qsort_func sorter;
  int isdbs;
} list_type_list;

char ALPHANUM_LIST[] = "A";
char INSENS_ALPHANUM_LIST[] = "I";
char DBREF_LIST[] = "D";
char NUMERIC_LIST[] = "N";
char FLOAT_LIST[] = "F";
char DBREF_NAME_LIST[] = "NAME";
char DBREF_NAMEI_LIST[] = "NAMEI";
char DBREF_IDLE_LIST[] = "IDLE";
char DBREF_CONN_LIST[] = "CONN";
char DBREF_CTIME_LIST[] = "CTIME";
char DBREF_OWNER_LIST[] = "OWNER";
char DBREF_LOCATION_LIST[] = "LOC";
char DBREF_ATTR_LIST[] = "ATTR";
char DBREF_ATTRI_LIST[] = "ATTRI";
char *UNKNOWN_LIST = NULL;

list_type_list ltypelist[] = {
  /* List type name,            recordmaker,    comparer, dbrefs? */
  {ALPHANUM_LIST, gen_alphanum, s_comp, 0},
  {INSENS_ALPHANUM_LIST, gen_alphanum, si_comp, 0},
  {DBREF_LIST, gen_dbref, i_comp, 0},
  {NUMERIC_LIST, gen_num, i_comp, 0},
  {FLOAT_LIST, gen_float, f_comp, 0},
  {DBREF_NAME_LIST, gen_db_name, s_comp, 1},
  {DBREF_NAMEI_LIST, gen_db_name, si_comp, 1},
  {DBREF_IDLE_LIST, gen_db_idle, i_comp, 1},
  {DBREF_CONN_LIST, gen_db_conn, i_comp, 1},
  {DBREF_CTIME_LIST, gen_db_ctime, i_comp, 1},
  {DBREF_OWNER_LIST, gen_db_owner, i_comp, 1},
  {DBREF_LOCATION_LIST, gen_db_loc, i_comp, 1},
  {DBREF_ATTR_LIST, gen_db_attr, s_comp, 1},
  {DBREF_ATTRI_LIST, gen_db_attr, si_comp, 1},
  /* This stops the loop, so is default */
  {NULL, gen_alphanum, s_comp, 0}
};

char *
get_list_type(char *args[], int nargs, int type_pos, char *ptrs[], int nptrs)
{
  static char stype[BUFFER_LEN];
  int i;
  char *str;
  if (nargs >= type_pos) {
    str = args[type_pos - 1];
    if (*str) {
      strcpy(stype, str);
      str = strchr(stype, ':');
      if (str)
        *(str++) = '\0';
      for (i = 0; ltypelist[i].name && strcasecmp(ltypelist[i].name, stype);
           i++) ;
      /* return ltypelist[i].name; */
      if (ltypelist[i].name) {
        return args[type_pos - 1];
      }
    }
  }
  return autodetect_list(ptrs, nptrs);
}

char *
get_list_type_noauto(char *args[], int nargs, int type_pos)
{
  static char stype[BUFFER_LEN];
  int i;
  char *str;
  if (nargs >= type_pos) {
    str = args[type_pos - 1];
    if (*str) {
      strcpy(stype, str);
      str = strchr(stype, ':');
      if (str)
        *(str++) = '\0';
      for (i = 0; ltypelist[i].name && strcasecmp(ltypelist[i].name, stype);
           i++) ;
      /* return ltypelist[i].name; */
      return args[type_pos - 1];
    }
  }
  return UNKNOWN_LIST;
}


/** A generic comparer routine to compare two values of any sort type.
 * \param
 */
int
gencomp(dbref player, char *a, char *b, char *sort_type)
{
  char *ptr;
  int i, len;
  int result;
  s_rec s1, s2;
  ptr = NULL;
  if (!sort_type) {
    /* Advance i to the default */
    for (i = 0; ltypelist[i].name; i++) ;
  } else if ((ptr = strchr(sort_type, ':'))) {
    len = ptr - sort_type;
    ptr += 1;
    if (!*ptr)
      ptr = NULL;
    for (i = 0;
         ltypelist[i].name && strncasecmp(ltypelist[i].name, sort_type, len);
         i++) ;
  } else {
    for (i = 0; ltypelist[i].name && strcasecmp(ltypelist[i].name, sort_type);
         i++) ;
  }
  s1.freestr = s2.freestr = 0;
  if (ltypelist[i].isdbs) {
    s1.db = parse_objid(a);
    s2.db = parse_objid(b);
    if (!RealGoodObject(s1.db))
      s1.db = NOTHING;
    if (!RealGoodObject(s2.db))
      s2.db = NOTHING;
  } else {
    s1.db = s2.db = 0;
  }

  s1.val = a;
  s2.val = b;
  ltypelist[i].make_record(&s1, player, ptr);
  ltypelist[i].make_record(&s2, player, ptr);
  result = ltypelist[i].sorter((const void *) &s1, (const void *) &s2);
  if (s1.freestr)
    mush_free(s1.str, "genrecord");
  if (s2.freestr)
    mush_free(s2.str, "genrecord");
  return result;
}

/** A generic sort routine to sort several different
 * types of arrays, in place.
 * \param player the player executing the sort.
 * \param s the array to sort.
 * \param n number of elements in array s
 * \param sort_type the string that describes the sort type.
 */

void
do_gensort(dbref player, char *keys[], char *strs[], int n, char *sort_type)
{
  char *ptr;
  static char stype[BUFFER_LEN];
  int i, sorti;
  s_rec *sp;
  ptr = NULL;
  if (!sort_type || !*sort_type) {
    /* Advance sorti to the default */
    for (sorti = 0; ltypelist[sorti].name; sorti++) ;
  } else if (strchr(sort_type, ':') != NULL) {
    strcpy(stype, sort_type);
    ptr = strchr(stype, ':');
    *(ptr++) = '\0';
    if (!*ptr)
      ptr = NULL;
    for (sorti = 0;
         ltypelist[sorti].name && strcasecmp(ltypelist[sorti].name, stype);
         sorti++) ;
  } else {
    for (sorti = 0;
         ltypelist[sorti].name && strcasecmp(ltypelist[sorti].name, sort_type);
         sorti++) ;
  }
  sp = mush_calloc(n, sizeof(s_rec), "do_gensort");
  for (i = 0; i < n; i++) {
    /* Elements are 0 by default thanks to calloc. Only need to touch
       those that need other values. */
    sp[i].val = keys[i];
    if (strs)
      sp[i].ptr = strs[i];
    if (ltypelist[sorti].isdbs) {
      sp[i].db = parse_objid(keys[i]);
      if (!RealGoodObject(sp[i].db))
        sp[i].db = NOTHING;
    }
    ltypelist[sorti].make_record(&(sp[i]), player, ptr);
  }
  qsort((void *) sp, n, sizeof(s_rec), ltypelist[sorti].sorter);

  for (i = 0; i < n; i++) {
    keys[i] = sp[i].val;
    if (strs) {
      strs[i] = sp[i].ptr;
    }
    if (sp[i].freestr)
      mush_free(sp[i].str, "genrecord");
  }
  mush_free((Malloc_t) sp, "do_gensort");
}

typedef enum {
  L_NUMERIC,
  L_FLOAT,
  L_ALPHANUM,
  L_DBREF
} ltype;

char *
autodetect_list(char *ptrs[], int nptrs)
{
  char *sort_type;
  ltype lt;
  int i;

  lt = L_NUMERIC;
  sort_type = NUMERIC_LIST;

  for (i = 0; i < nptrs; i++) {
    switch (lt) {
    case L_NUMERIC:
      if (!is_strict_integer(ptrs[i])) {
        /* If it's not an integer, see if it's a floating-point number */
        if (is_strict_number(ptrs[i])) {
          lt = L_FLOAT;
          sort_type = FLOAT_LIST;
        } else if (i == 0) {

          /* If we get something non-numeric, switch to an
           * alphanumeric guess, unless this is the first
           * element and we have a dbref.
           */
          if (is_objid(ptrs[i])) {
            lt = L_DBREF;
            sort_type = DBREF_LIST;
          } else
            return ALPHANUM_LIST;
        }
      }
      break;
    case L_FLOAT:
      if (!is_strict_number(ptrs[i]))
        return ALPHANUM_LIST;
      break;
    case L_DBREF:
      if (!is_objid(ptrs[i]))
        return ALPHANUM_LIST;
      break;
    default:
      return ALPHANUM_LIST;
    }
  }
  return sort_type;
}