/*
 * Copyright (C) 1993-2007 William J. Poser.
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of version 3 of the GNU General Public License as
 * published by  the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 * or go to the web page:  http://www.gnu.org/licenses/gpl.txt.
 */


#include "config.h"
#include "compdefs.h"

#include <stdlib.h>
#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif
#include <stdio.h>
#include <string.h>
#include <wchar.h>
#include <wctype.h>
#include <tre/regex.h>
#ifdef HAVE_UNINUM_UNICODE_H
#include <uninum/unicode.h>
#else
#include "unicode.h"
#endif
#include "comparisons.h"
#include "key.h"
#include "record.h"

#ifdef HAVE_LONG_LONG
typedef long long LongLong; 
#else
typedef long LongLong;
#endif

#ifdef HAVE_LONGDOUBLE
#define DOUBLE (long double)
#else
#define DOUBLE double
#endif

#define INSERTIONSORTTHRESHOLD 7L

#define TRUE 1
#define FALSE 0

/*
 *  This is the recursive routine in K&R with swap in-lined as a macro
 *  and use of a straight insertion sort for small sub-partitions.
 */	 


#define SWAP(a,b,c) temp = a[b];a[b] = a[c];a[c] = temp;

void
QuickSort(struct record **rlist, long left, long right)
{
  long i;
  long last;
  long j;
  long elts;
  struct record *temp;
	
  int Compare(struct record *,struct record *);

  elts = right - left + 1L;
  if(elts < 2L) return;
	
  if(elts < INSERTIONSORTTHRESHOLD){ /* Do a straight insertion sort */
    for(j=1L;j < elts;j++){
      temp = rlist[j+left];
      i = j -1L;
      while( (i >= 0) && (Compare(rlist[i+left],temp) > 0)){
	rlist[i+1L+left] = rlist[i+left];
	--i;
      }
      rlist[i+1L+left] = temp;
    }
    return;
  }
	
  /* If we get here it is worth continuing with quicksort. */
	
  j = (left + right)/2L;
  SWAP(rlist,left,j)
	
    last = left;
  for(i = left+1; i <= right; i++){
    if(Compare(rlist[i],rlist[left]) < 0){
      ++last;
      SWAP(rlist,last,i);
    }
  }
  SWAP(rlist,left,last);
  QuickSort(rlist,left,last-1L);
  QuickSort(rlist,last+1L,right);
}

void
ShellSort(struct record **rlist,long cnt)
{
  long gap;
  long i;
  long j;
   
  struct record *temp;
	
  int Compare(struct record *,struct record *);
   
  for(gap = cnt/2; gap > 0; gap /= 2){
    for(i = gap; i < cnt; i++){
      for(j = i-gap; j>= 0; j -= gap){
	if(Compare(rlist[j],rlist[j+gap]) <= 0) break;
	else{
	  temp = rlist[j];
	  rlist[j] = rlist[j+gap];
	  rlist[j+gap] = temp;
	}
      }
    }
  }
  return;
}

void
Merge(struct record **rlist, long start, long mid, long end) 
{
  long i;
  long j;
  long k;
  struct record **tmp;

  int Compare(struct record *,struct record *);

#ifdef ALLOCAOK
  tmp = (struct record **) alloca(sizeof(struct record *) * (end - start));
#else
  tmp = (struct record **) malloc(sizeof(struct record *) * (end - start));
#endif

  i = start;
  j = mid;
  k = 0;
  while ((i < mid) && (j < end)) {
    if (Compare(rlist[i],rlist[j]) <= 0)
	tmp[k++] = rlist[i++];
      else
	tmp[k++] = rlist[j++];
  }
  while (i < mid) {
    tmp[k++] = rlist[i++];
  }
  while (j < end) {
    tmp[k++] = rlist[j++];
  }
  for (i = 0L; i < (end-start); i++) {
    rlist[start+i] = tmp[i];
  }
#ifndef ALLOCAOK
  free((void *) tmp);
#endif
}

void MergeSort(struct record **rlist, long begin, long end)
{
    long mid;
    if (end - begin <= 1L) return;
    mid = (begin + end) / 2L;
    MergeSort(rlist, begin, mid);
    MergeSort(rlist, mid, end);
    Merge(rlist, begin, mid, end);
}

 void InsertionSort(struct record **rlist, long items) {
   long i;
   long j;
   struct record *value;

  int Compare(struct record *,struct record *);

   for(i = 1L; i < items; i++) {
     value = rlist[i];
     for (j = i - 1L; (j >= 0L) && (Compare(rlist[j],value) > 0);j--) {
       rlist[j + 1] = rlist[j];
     }
     rlist[j + 1] = value;
   }
 }

inline int
sign(DOUBLE x)
{
  if(x > 0.0) return (1);
  else if (x < 0.0) return (-1);
  else return (0);
}

inline int
isign(long x)
{
  if(x > 0L) return (1);
  else if (x < 0L) return (-1);
  else return (0);
}

/* Compare two wide strings using a rank table, without reference to the locale.  */
int
wcscmpli (const wchar_t *rt, const wchar_t *a, const wchar_t *b) {
  while (rt[*a] == rt[*b++]) {
    if (*a++ =='\0') return(0);
  }
  return(rt[*a] - rt[*--b]);
}

/*
 * This is the subroutine that does the actual comparison of two records.
 *
 * It returns:
 *	 0 if a = b
 *	-1 if a < b 
 *	 1 if b > a
 *
 * It iterates over the keys, returning as soon as it finds a key on
 * which the two records compare differently. For each key it first
 * tests to see if the records have values for that key. If they do,
 * it does the actual comparison, the details depending on whether the
 * comparison is numeric (including dates, times, and sizes), or lexicographic.
 * If both records lack the key, it returns 0. If one record lacks the
 * key and the other does not, it returns a value depending on how
 * MissingKeyComparison is set for this key.
 *
 * Whether a key exists for a particular record is determined by
 * testing whether the pointer is null. It is therefore important
 * that key pointers be set to null during key extraction if a key is missing. 
 */


#define LOWBITONLYMASK 0x01
#define HIGHBITOFFMASK 0x7F
#define HIGHBITSHIFT      7
#define MIN(a,b) (a>b?b:a)

int
Compare(struct record *a,struct record *b)
{
  int i, j, k, r;
  int rval;
  wchar_t *ap;
  wchar_t *bp;
  wchar_t *rt;
  unsigned short APresent;
  unsigned short BPresent;
  wchar_t **ATxt;
  wchar_t **BTxt;
  long *ANum;
  long *BNum;
  short ANumericFirstP;
  short BNumericFirstP;
  int AParts;
  int BParts;
  int lim;

#ifndef NOCOMPARISONCNT 
  extern LongLong ComparisonCnt;
#endif
  extern int KeyCount;
  extern struct keyinfo **KeyInfo;

  rval = 0;
#ifndef NOCOMPARISONCNT 
  ComparisonCnt++;
#endif

  for(i = 0; i < KeyCount; i++){

    if(KeyInfo[i]->CompType & CRANDOM) {
      return((random()%3)-1);
    }

    /* Set flags for presence of key in each record */
    APresent = BPresent = FALSE;
    if(KeyInfo[i]->CompType & CNUMERIC){
      if(a->klistptr[i].n != NULL) APresent=TRUE;
      if(b->klistptr[i].n != NULL) BPresent=TRUE;
    }
    else{
      ap = a->klistptr[i].t;
      if(ap != NULL) APresent=TRUE;
      bp = b->klistptr[i].t;
      if(bp != NULL) BPresent=TRUE;
    }

    if(APresent && BPresent){
      /* Straight numeric */
      if(KeyInfo[i]->CompType & CNUMERIC){
	if(KeyInfo[i]->CompType & CINVERSE){
	  rval = sign(*(b->klistptr[i].n) - *(a->klistptr[i].n));
	}
	else rval = sign(*(a->klistptr[i].n) - *(b->klistptr[i].n));
      }
      /* Numeric string */
      else if(KeyInfo[i]->CompType & CNUMSTR){
	if(a->klistptr[i].N.sign < b->klistptr[i].N.sign) rval = -1;
	else if(a->klistptr[i].N.sign > b->klistptr[i].N.sign) rval = 1;
	/* Signs are same */
	else if(a->klistptr[i].N.cnt < b->klistptr[i].N.cnt) rval = -1 * a->klistptr[i].N.sign;
	else if(b->klistptr[i].N.cnt < a->klistptr[i].N.cnt) rval = a->klistptr[i].N.sign;
	else rval = a->klistptr[i].N.sign * strcmp(a->klistptr[i].N.txt,b->klistptr[i].N.txt);
      }
      /* Non-numeric */
      else {
	rt = KeyInfo[i]->RankTable;
	rval = 1;		/* Use as flag to see if we reached end of string */
	if(KeyInfo[i]->CompType & CHYBRID) {
	    ANumericFirstP = (a->klistptr[i].H->cnt >> HIGHBITSHIFT) & LOWBITONLYMASK;
	    BNumericFirstP = (b->klistptr[i].H->cnt >> HIGHBITSHIFT) & LOWBITONLYMASK;
	    AParts = a->klistptr[i].H->cnt & HIGHBITOFFMASK;
	    BParts = b->klistptr[i].H->cnt & HIGHBITOFFMASK;
	    ATxt = a->klistptr[i].H->tlist;BTxt = b->klistptr[i].H->tlist;
	    ANum = a->klistptr[i].H->ilist;BNum = b->klistptr[i].H->ilist;
	    if(ANumericFirstP && !BNumericFirstP) return -1;
	    else if(BNumericFirstP && !ANumericFirstP) return 1;
	    else {
	      lim = MIN(AParts,BParts);
	      for(j=0; j < lim; j++) {
		k = j/2; r= j%2;
		if(r == ANumericFirstP) {
#ifdef LOCALE_SORT_ORDER
		  if(KeyInfo[i]->LocaleP) rval = wcscmp(ATxt[k],BTxt[k]);
		  else rval = wcscmpli(rt,ATxt[k],BTxt[k]);
#else
		  rval = wcscmpli(rt,ATxt[k],BTxt[k]);
#endif
		}
		else rval = isign(ANum[k]-BNum[k]);
		if(rval != 0) return rval;
	      }
	      if(BParts > AParts) rval = -1;
	      else if(AParts > BParts) rval = 1;
	      if(rval != 0) return(rval);
	      else continue;
	    }
	} /* End of hybrid section */
	else { /* Non-hybrid lexicographic comparison */
#ifdef LOCALE_SORT_ORDER
	  /* Locale-based */
	  if(KeyInfo[i]->LocaleP) {
	    rval = wcscmp(ap,bp);
	    if(rval!=0) return(rval);
	    else continue;
	  }
	  /* Locale-independent */
	  else {
#endif
	    for( ; rt[*ap] == rt[*bp]; ap++, bp++){
	      if(*ap == (wchar_t) '\0'){rval=0;break;} 
	    }
	    if(rval != 0){
	      if(KeyInfo[i]->CompType & CINVERSE) rval = rt[*bp] - rt[*ap];
	      else rval = rt[*ap] - rt[*bp];
	    }
#ifdef LOCALE_SORT_ORDER
	  }
#endif
	} /* End of non-hybrid lexicographic comparison */
      }	/* End of lexicographic comparison */
    } /* End of case where both keys are present */

    /* If we get here at least one record lacks this key */
    else{
      if (APresent && !BPresent) rval = 1 - KeyInfo[i]->MissingKeyComparison;
      else{
	if (!APresent && BPresent) rval = KeyInfo[i]->MissingKeyComparison - 1;
	else{
	  if (!APresent && !BPresent)rval = 0;
	}
      }
    }
    if(rval != 0) return(rval); /* If records are same on this key, go on to next key */
  } /* End of loop over keys */
  return(0);			/* If we get here, records tie on all keys */
}