/****   Copyright (c) 2002-2003  Alexandros V. Gerbessiotis
 ****
 ****   Permission to use, copy, modify, and distribute this software,
 ****   and to incorporate it, in whole or in part, into other software,
 ****   is hereby granted without fee, provided that
 ****     (1) the above copyright notice and this permission notice appear in
 ****         all copies of the source code, and the above copyright notice
 ****         appear in clearly visible form on all supporting documentation
 ****         and distribution media, and
 ****     (2) any redistribution of the software, in original
 ****         or modified form, be without fee and subject to
 ****         these same conditions.
 ****   No guarantee is offered that the code works as
 ****   advertised or is absent of any, even damaging,
 ****   side-effects; use this code on your own personal risk
 ****/
#include        <string.h>
#include        <memory.h>
#include        <limits.h>
#include        "bsp.h"
#include        "mybsp.h"
#define         Div2(x)              ((x) >> 1)
#define         Times2(x)            ((x) << 1)

void sortint_ins(int *keys, int n)
{
        register int i,j;
        int x;

        for(j=1;j<n;j++)
        {
                x=keys[j];
                i=j-1;
                while ( (i>=0) && (keys[i]>x) ) {
                        keys[(i+1)]=keys[i];
                        i--;
                }
                keys[(i+1)]=x;
        }
}

void sort_ins(char *keys, int n, int size, int (*compare) ())
{
        register int i,j;
        char    *x;

        x = (char *) malloc(size*sizeof(char));
        for(j=1;j<n;j++)
        {
                memcpy(x,&keys[j*size],size);
                i=j-1;
                while ( (i>=0) && ( compare(&keys[i*size],x)>0) ) {
                        memcpy(&keys[(i+1)*size],&keys[i*size],size);
                        i--;
                }
                memcpy(&keys[(i+1)*size],x,size);
        }
}

void quick_1_sort(char *keys, int n, int size, int (*compare) (),int l,int r)
{
        register int i,j;
        char    *x,*y;

        i=l;j=r;
        x = (char *) malloc(size*sizeof(char));
        y = (char *) malloc(size*sizeof(char));
        memcpy(x,&keys[((l+r)/2)*size],size);

do
{
        while (compare(&keys[i*size],x) < 0) ++i;
        while (compare(x,&keys[j*size]) < 0) --j;
        if (i <= j )
        {
                memcpy(y,&keys[i*size],size);
                memcpy(&keys[i*size],&keys[j*size],size);
                memcpy(&keys[j*size],y,size);
                ++i;--j;
        }
} while (i <= j);
        if (l < j)
                if ((j-l) <  8)
                        sort_ins  (&keys[l*size],(j-l+1),size,compare);
                else
                        quick_1_sort(keys,n,size,compare,l,j);
        if (i < r)
                if ((r-i) <  8)
                        sort_ins  (&keys[i*size],(r-i+1),size,compare);
                else
                        quick_1_sort(keys,n,size,compare,i,r);

}

void quick2(char *keys, int n, int size, int (*compare) ())
{
                quick_1_sort(keys,n,size,compare,0,n-1);
}

void quicki_1_sort(int *keys, int n, int size, int (*compare) (),int l,int r)
{
         register int i,j;
         register int  x,y;

        i=l;j=r;
        x=keys[(l+r)/2];

do
{
        while (keys[i]<x) i++;
        while (x<keys[j]) j--;
        if (i <= j ) {
                y=keys[i];
                keys[i]=keys[j];
                keys[j]=y;
                i++;j--;
        }
} while (i <= j);

        if (l < j)
                if ((j-l) < 16)
/*
                        sortint_ins(&keys[l],(j-l+1));
*/
                        sortint_ins(&keys[l],(j-l+1));
                else
                        quicki_1_sort(keys,n,size,compare,l,j);
        if (i < r)
                if ((r-i) < 16)
/*
                        sortint_ins(&keys[i],(r-i+1));
*/
                        sortint_ins(&keys[i],(r-i+1));
                else
                        quicki_1_sort(keys,n,size,compare,i,r);
}
void quick2i(int *keys, int n, int sbytes, int (*compare)())
{
                quicki_1_sort(keys,n,sbytes,compare,0,n-1);
}





void quick(char *keys, int n, int size, int (*compare) ())
{
        register int i,j,l,r,s;
        char    *x,*y;
        int     lstack[1000];
        int     rstack[1000];

        x = (char *) malloc(size*sizeof(char));
        y = (char *) malloc(size*sizeof(char));
        s=0;
        lstack[0]=0;rstack[0]=n-1;
do {
        l=lstack[s]; r=rstack[s]; s--;
        do {
                i=l;
                j=r;
                memcpy(x,&keys[((l+r)/2)*size],size);

                do {
                        while (compare(&keys[i*size],x) < 0) i++;
                        while (compare(x,&keys[j*size]) < 0) j--;
                        if (i <= j )
                        {
                                memcpy(y,&keys[i*size],size);
                                memcpy(&keys[i*size],&keys[j*size],size);
                                memcpy(&keys[j*size],y,size);
                                i++;
                                j--;
                        }
                } while (i <= j); 

                if (i < r)
                if ((r-i) < 16)
                        sort_ins(&keys[i*size],(r-i+1),size,compare);
                else
                {
                        s++; lstack[s]=i; rstack[s]=r;
                }
                r=j;


        } while ( l < r);
} while (s>= 0);

}

void quicki(int *keys, int n, int size, int (*compare) ())
{
        register int i,j,l,r,s;
        int x,y;
        int     lstack[1000];
        int     rstack[1000];

        s=0;
        lstack[0]=0;rstack[0]=n-1;
do {
        l=lstack[s]; r=rstack[s]; s--;
        do {
                i=l;
                j=r;
                x=keys[((l+r)/2)];

                do {
                        while (keys[i]<x) i++;
                        while (x<keys[j]) j--;
                        if (i <= j )
                        {
                                y=keys[i];
                                keys[i]=keys[j];
                                keys[j]=y;
                                i++;
                                j--;
                        }
                } while (i <= j); 

                if (i < r)
                if ((r-i) < 8)
                        sortint_ins(&keys[i],(r-i+1));
                else
                {
                        s++; lstack[s]=i; rstack[s]=r;
                }
                r=j;


        } while ( l < r);
} while (s>= 0);

}



/**** HEAP SORTING ***/

void sift(char *keys,int n,int size,int (*compare)(),int l,int r)
{
        register int i,j;
        char    *x;

        x = (char *) malloc(size*sizeof(char));
        i=l;j=2*i;

        memcpy(x,&keys[(i-1)*size],size);

        while ( j <= r)
        {
                if (j < r)
                {
                        if (compare(&keys[(j-1)*size],&keys[(j)*size]) <= 0)
                        {
                                j++;
                        }
                }
                if (compare(x,&keys[(j-1)*size]) > 0)
                        break;

        memcpy(&keys[(i-1)*size],&keys[(j-1)*size],size);
        i=j;j=2*i;
        }
        memcpy(&keys[(i-1)*size],x,size);
}


void heap(char *keys, int n, int size, int (*compare) ())
{
        register int l,r;
        char    *x;

        l = n/2+1; r=n;
        x = (char *) malloc(size*sizeof(char));

        while (l > 1)
        {
                l--;
                sift(keys,n,size,compare,l,r);
        }
        while (r > 1)
        {
                memcpy(x,&keys[0],size);
                memcpy(&keys[0],&keys[(r-1)*size],size);
                memcpy(&keys[(r-1)*size],x,size);
                r--;
                sift(keys,n,size,compare,l,r);
        }

}

void siftint(int *keys,int n,int size,int (*compare)(),int l,int r)
{
        register int i,j;
        int     x;

        i=l;j=2*i;

        x=keys[(i-1)];

        while ( j <= r)
        {
                if (j < r)
                {
                        if (keys[j-1]<= keys[j])
                        {
                                j++;
                        }
                }
                if (x>keys[j-1])
                        break;

        keys[i-1]=keys[j-1];
        i=j;j=2*i;
        }
        keys[i-1]=x;
}


void heapi(int *keys, int n, int size, int (*compare) ())
{
        register int l,r;
        int x;

        l = n/2+1; r=n;

        while (l > 1)
        {
                l--;
                siftint(keys,n,size,compare,l,r);
        }
        while (r > 1)
        {
                x=keys[0];
                keys[0]=keys[r-1];
                keys[r-1]=x;
                r--;
                siftint(keys,n,size,compare,l,r);
        }

}

/* GNU>C */
/*
 * qsort.c:
 * Our own version of the system qsort routine which is faster by an average
 * of 25%, with lows and highs of 10% and 50%.
 * The THRESHold below is the insertion sort threshold, and has been adjusted
 * for records of size 48 bytes.
 * The MTHREShold is where we stop finding a better median.
 */

#define         MTHRESH         6               /* threshold for median */
/*
#define		INTEGER		1
*/

static  int             qsz;                    /* size of each record */
static  int             (*qcmp)();              /* the comparison routine */

static  int             thresh;                 /* THRESHold in chars */
static  int             mthresh;                /* MTHRESHold in chars */


/*
 * qsort:
 * First, set up some global parameters for qst to share.  Then, quicksort
 * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
 * It's not...
 */


#if !INTEGER
#define THRESH 8
#define COMPARE(i1,i2) (*qcmp)(i1,i2)
#define SWAPP(i1,i2) \
  {ii = qsz;do {c = *(i1);*(i1)++ = *(i2);*(i2)++ = c;} while(--ii);}
#else
#define THRESH 24
#define COMPARE(i1,i2) (*(int *)(i1) - *(int *)(i2))
#define SWAPP(i1,i2) \
  {register int itmp;itmp=*(int *)(i1);*(int *)(i1)=*(int *)(i2);*(int *)(i2)=itmp;}
#endif



void merge(char *keys, int n, int size, int (*compare) ())
{
        register int i;
        int j,k,l,t;
        int h,m,q,p,r,up;
        int *x;
        char *y;

        up=1;p=1;
        y = (char*) malloc(2*n*size);
        for(i=0;i<n;i++)
                memcpy(&y[i*size],&keys[i*size],size);


do {
        h=1; m=n;
        if (up==1) {
                i=0;j=n-1;k=n;l=2*n-1;
        }

        else {
                k=0;l=n-1;i=n;j=2*n-1;
        }

do {
        if (m >= p)
                q=p;
        else
                q=m;
        m=m-q;

        if (m >= p)
                r=p;
        else
                r=m;
        m=m-r;


        while ((q != 0) && ( r != 0)) {
                if (compare(&y[i*size],&y[j*size]) < 0) {
                        memcpy(&y[k*size],&y[i*size],size);
                        k +=h; i++; q--;
                }
                else {
                        memcpy(&y[k*size],&y[j*size],size);
                        k +=h; j--; r--;
                }
        }


        while ( r != 0) {
                memcpy(&y[k*size],&y[j*size],size);
                k +=h; j--; r--;
        }

        while ( q != 0) {
                memcpy(&y[k*size],&y[i*size],size);
                k +=h; i++; q--;
        }
        h=-h; t=k; k=l; l=t;
} while (m>0);
        up=1-up; p=2*p;
} while (p < n);
/*
        if (up==0)
                for(i=0;i<n;i++)
                        memcpy(&y[i*size],&y[(i+n)*size],size);
        for(i=0;i<n;i++)
                memcpy(&keys[i*size],&y[i*size],size);
*/
/*
        if (up==0)
                for(i=0;i<n;i++)
                        memcpy(&keys[i*size],&y[(i+n)*size],size);
        else
                for(i=0;i<n;i++)
                        memcpy(&keys[i*size],&y[i*size],size);
*/
        if (up==0)
                        memcpy(&keys[0*size],&y[(n)*size],n*size);
        else
                        memcpy(&keys[0*size],&y[0*size],n*size);
}

void mergei (int  *src,int  n,int sbytes,int (*compare)())
{
  int  *temp;
  int  *tmp, *s, *t;
  int   phase;
  register int idx;
  register int  i, j, l;
  int  q, r;

  if (n <= 1) return;

  temp= (int *) malloc(n*sizeof(int));
  check_if_null((void *)temp,"sortint_mrg","temp");

  for (idx = 0;idx<n;idx+=16) {
      sortint_ins(&src[idx], MIN(16,(n - idx)));
  }

  s = src; t = temp;
  for (phase = 16; phase < n; phase = Times2(phase)) {
      for (idx = 0; idx < n; idx += Times2(phase)) {
          q = MIN(idx + Times2(phase), n); r = MIN(idx + phase, n);
          i = r; j = idx; l = idx;
          while ((i < q) && (j < r)) {
              if (s[i] < s[j]) {
                  t[l] = s[i];
                  i++; l++;
              } else {
                  t[l] = s[j];
                  j++; l++;
              }
          }
           if (i < q) memcpy(&t[l], &s[i], (q - i) * sizeof(int));
           if (j < r) memcpy(&t[l], &s[j], (r - j) * sizeof(int));
      }

      tmp=s;s=t;t=tmp;
  }
  if (s != src) memcpy(src, s, n * sizeof(int));
  free((void *)temp);
}


