/****   Copyright (c) 1997-2003  Constantionos J. Siniolakis and
 ****                       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        <stdio.h>
#include        "bsp.h"
#include        "mybsp.h"
#define 	Div2(x)              ((x) >> 1)
#define 	Times2(x)            ((x) << 1)
#define 	CDiv(x, y)           (((x) != 0)?((((x) - 1)/(y))+1):0)
#define 	Mask(x, sbit, nbits) ((x >> sbit) & ~(UINT_MAX << nbits))
#define  Parent(i)   ((i-1)>>1)
#define  Left(i)     ((i<<1)+1)
#define  Right(i)    ((i<<1)+2)
#define MINS 30

/*** FLog2 */
int FLog2 (int x)
{
  register int l;
  if (x <= 1) {
      return(0);
  } else {
      l = 0;
      while (x = Div2(x)) l++;
      return(l);
  }
}

/*** CLog2 */
int CLog2 (int x)
{
  register int l;
  if (x <= 1) {
     return(0);
  } else {
      x--; l = 1;
      while (x = Div2(x)) l++;
      return(l);
  }
}

/*** Exp2 */
int Exp2 (int x)
{
  return (int)((unsigned int)(1) << x);
}

/*** sort_ins */
void sort_ins (char *src,int n,int sbytes,int (*compare)(const void * , const
void *) )
{
  char *tmp;
  register int i,idx;

  if ((n <= 1)||(sbytes <= 0)) return;
  tmp= (char *) malloc(sbytes*sizeof(char));
  check_if_null((void *)tmp,"sort_ins","tmp");
  for(i=1;i<n;i++) {
     memcpy(tmp,&src[i*sbytes],sbytes);
     idx=i;
     while ((idx > 0) && compare(&src[(idx-1)*sbytes], tmp) > 0) {
        memcpy(&src[idx*sbytes], &src[(idx-1)*sbytes], sbytes);
        idx--;
     }
     memcpy(&src[idx*sbytes], tmp, sbytes);
  }
 
  free((void *)tmp);
}


void sortint_ins (int *src,int n)
{
  register int tmp;
  register int i,idx;

  if (n <= 1) return;
  for(i=1;i<n;i++) {
     tmp=src[i];
     idx=i-1; 
     while ((idx>=0) && (src[idx] > tmp)) {
          src[idx+1]=src[idx];
          idx--; 
     }
     src[idx+1]=tmp;
  }
}


void str_insert(int *keys, int n)
{
        register int i,j;
        register 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 quick_1_sort(int *keys, int n, 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));
*/
                        str_insert(&keys[l],(j-l+1));
                else
                        quick_1_sort(keys,n,l,j);
        if (i < r)
                if ((r-i) < 16)
/*
                        sortint_ins(&keys[i],(r-i+1));
*/
                        str_insert(&keys[i],(r-i+1));
                else
                        quick_1_sort(keys,n,i,r);

}
void quicki(int *keys, int n, int sbytes, int (*compare)(const void *,const void *))
{
                quick_1_sort(keys,n,0,n-1);
}



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

  if ((n <= 1)  || (sbytes <= 0)) return;
  temp= (char *) malloc(n*sbytes*sizeof(char));
  check_if_null((void *)temp,"sort_mrg","temp");

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

  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 (compare(&s[i*sbytes], &s[j*sbytes]) < 0) {
                  memcpy(&t[l*sbytes], &s[i*sbytes], sbytes);
                  i++; l++; 
              } else {
                  memcpy(&t[l*sbytes], &s[j*sbytes], sbytes);
                  j++; l++;
              }
          }

           if (i < q) memcpy(&t[l*sbytes], &s[i*sbytes], (q - i) * sbytes);    
           if (j < r) memcpy(&t[l*sbytes], &s[j*sbytes], (r - j) * sbytes);
      }
      tmp=s; s=t; t=tmp;
  }
  if (s != src) memcpy(src, s, n * sbytes); 
  free((void *)temp);
}

void mergei (int  *src,int  n,int sbytes,int (*compare)(const void *, const void*))
{
  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);  
}


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

        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) < 8)
                        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 quick_q_sort(char *keys, int n, int size, int (*compare) (const void *, const void*),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) < 16)
                        sort_ins(&keys[l*size],(j-l+1),size,compare);
                else
                        quick_q_sort(keys,n,size,compare,l,j);
        if (i < r)
                if ((r-i) < 16)
                        sort_ins(&keys[i*size],(r-i+1),size,compare);
                else
                        quick_q_sort(keys,n,size,compare,i,r);
        
}

void sort2_q(char *keys, int n, int size, int (*compare) (const void *, const void*))
{
                quick_q_sort(keys,n,size,compare,0,n-1);
}


/**** HEAP SORTING ***/

void sift(char *keys,int n,int size,int (*compare)(const void *, const void*),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 heap2(char *keys, int n, int size, int (*compare) (const void *, const void*))
{
        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)(const void *,const void*),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 heap2i(int *keys, int n, int size, int (*compare) (const void* , const void*))
{
        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)(const void *,const void*);              /* 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 str_select(char *keys, int n, int size, int (*compare) (const void *,const void*))
{
	register int i,j,k;
	char	*x;

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

void Ins_Sort (char *src, int nelems, int sbytes, int (*compare)(const void *,const void*))
{
  char *tmp ;
  int    i, idx ;

 tmp = (char *)malloc(sbytes) ;

  for (i = 1 ; i < nelems ; i++)
    {
      memcpy(tmp, &src[i*sbytes], sbytes) ;
      idx = i ;
      while ((idx > 0) && compare(&src[(idx-1)*sbytes], tmp) > 0)
        {
          memcpy(&src[idx*sbytes], &src[(idx-1)*sbytes], sbytes) ;
          --idx ;
        }
      memcpy(&src[idx*sbytes], tmp, sbytes) ;
    }
  
  free(tmp) ;
}


void Q_Sort (char *src, int nelems, char * mid, char *tmp, int sbytes, int (*compare)(const void *, const void*))
{
  register int     l, r ;

  l = 0 ; r = nelems-1 ;
  memcpy(mid, &src[((l+r)/2)*sbytes], sbytes) ;

  while (l <= r)
    {
      while (compare(&src[l*sbytes], mid) < 0) ++l ;
      while (compare(&src[r*sbytes], mid) > 0) --r ;
      if (l <= r)
        {
          memcpy(tmp, &src[l*sbytes], sbytes) ;
          memcpy(&src[l*sbytes], &src[r*sbytes], sbytes) ;
          memcpy(&src[r*sbytes], tmp, sbytes) ;
          ++l ; --r ;
        }
    }
  
  if (r > 0) 
    {
      if ((r+1) < MINS) Ins_Sort(src, r+1, sbytes, compare) ;
      else              Q_Sort(src, r+1, mid, tmp, sbytes, compare) ;
    }
  if (l < nelems) 
    {
      if ((nelems-l) < MINS) Ins_Sort(&src[l*sbytes], nelems-l, sbytes, compare) ;
      else         Q_Sort(&src[l*sbytes], nelems-l, mid, tmp, sbytes, compare) ;
    }
}

void qsort2 (char *src, int nelems, int sbytes, int (*compare)(const void *,const void*))
{
  char   *mid, *tmp ;
 
  if ((mid = (char *)malloc(sbytes)) == NULL)
    {
    }
  if ((tmp = (char *)malloc(sbytes)) == NULL)
    {
    }
 
  Q_Sort(src, nelems, mid, tmp, sbytes, compare) ;

  free(tmp) ; free(mid) ;
}



void Heapify (char *heap, int nelems, int i, char *tmp, int schars, int (*compare)(const
void * , const void *))
{
  register int     l, r, t ;
  
  l = Left(i) ;
  r = Right(i) ;

  if ((l < nelems) && (compare(&heap[l*schars], &heap[i*schars]) > 0))
       t = l ;
  else t = i ;
  if ((r < nelems) && (compare(&heap[r*schars], &heap[t*schars]) > 0))
       t = r ;
   
  if (t != i)
    {
      memcpy(tmp, &heap[i*schars], schars) ;
      memcpy(&heap[i*schars], &heap[t*schars], schars) ;
      memcpy(&heap[t*schars], tmp, schars) ;
      Heapify(heap, nelems, t, tmp, schars, compare) ;
    }
}
void Build_Heap (char *heap, int nelems, int schars, int (*compare)(const void *,const
void*))
{
  char *tmp ;
  register int    i ;

  if ((tmp = (char *)malloc(schars)) == NULL)
    {
      printf("heap_sort: out of memory.\n") ;
    }

  for (i = nelems - 1 ; i >= 0 ; --i)
    {
      Heapify(heap, nelems, i, tmp, schars, compare) ;
    }

  free(tmp) ;
}

void heap (char *src, int nelems, int schars, int (*compare)(const void *,const void*))
{
  char *tmp ;
  register int    i ;

  if ((tmp = (char *)malloc(schars)) == NULL)
    {
      printf   ("heap_sort: out of memory.\n") ;
    }

  Build_Heap(src, nelems, schars, compare) ;

  for (i = nelems - 1 ; i >= 1 ; --i)
    {
      memcpy(tmp, src, schars) ;
      memcpy(src, &src[i*schars], schars) ;
      memcpy(&src[i*schars], tmp, schars) ;
      Heapify(src, i, 0, tmp, schars, compare) ;
    }

  free(tmp) ;
}

void Heapifyi (int *heap,int nelems,int i,int tmp,int schars,int (*compare)(const void *,const void*))
{
  register int     l, r, t ;
  
  l = Left(i) ;
  r = Right(i) ;

  if ((l < nelems) && (heap[l] >heap[i]))
       t = l ;
  else t = i ;
  if ((r < nelems) && (heap[r] >heap[t]))
       t = r ;
   
  if (t != i)
    {
      tmp=heap[i];
      heap[i]=heap[t];
      heap[t]=tmp;
      Heapifyi(heap, nelems, t, tmp, schars, compare) ;
    }
}
void Build_Heapi (int *heap, int nelems, int schars, int (*compare)(const void *,const void*))
{
  int tmp ;
  register int    i ;

  for (i = nelems - 1 ; i >= 0 ; --i)
    {
      Heapifyi(heap, nelems, i, tmp, schars, compare) ;
    }
}

void heapi (int* src, int nelems, int schars, int (*compare)(const void *,const void*))
{
  int tmp ;
  register int    i ;

  Build_Heapi(src, nelems, schars, compare) ;

  for (i = nelems - 1 ; i >= 1 ; --i)
    {
      tmp=src[0];
      src[0]=src[i] ;
      src[i]=tmp;
      Heapifyi(src, i, 0, tmp, schars, compare) ;
    }

}

