#include <stdio.h>
#include <memory.h>
#include "bsp1.h"
#define BYTE_ZERO      (byte)0
#define D               5
#define Memcpy(x,y,z) {for(sr=(x),de=(y),k=(z);0<k;++sr,++de,--k) *sr=*de;}

void error_msg (char *msg)
{
  fprintf(stderr, "%s", msg) ;
  exit(1) ;
}

void Ins_Sort (byte *src, t_type nelems, t_type sbytes,
               int  (*compare)(byte *, byte*))
{
  byte *tmp ;
  register t_type i, idx ;
  if ((tmp = (byte *)malloc(sbytes)) == NULL)
    {
      error_msg("Out of memory.") ;
    }

  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 rsort_msb (byte *src, t_type nelems, t_type sbytes, t_type msb)
{
  byte *trg;
  t_type tmp[MX_BYTE+1];
  register int i;
  register t_type  idx;
  t_type j;
  register t_type k;

  if ((trg = (byte *)malloc(nelems * sbytes)) == NULL)
    {
      error_msg("Out of memory.") ;
    }

  for (k = Min(sbytes, msb) - 1 ; k >= 0 ; --k)
    {
      for (i = 0 ; i <= MX_BYTE ; ++i) tmp[i] = BYTE_ZERO ;
      for (j = 0 ; j < nelems ; ++j) tmp[src[j*sbytes+k]] += 1 ;
      for (i = 1 ; i <= MX_BYTE ; ++i) tmp[i] = tmp[i] + tmp[i-1] ;
      for (j = nelems ; j > 0 ; )
        {
          idx = --tmp[src[(--j)*sbytes+k]] ;
          memcpy(&trg[idx*sbytes], &src[j*sbytes], sbytes) ;
        }
      memcpy(src, trg, nelems * sbytes) ;
    }

  free(trg) ;
}

/*** START HERE***/
/*** END HERE***/
void RS_Sort (byte *src, t_type nelems, t_type sbytes, t_type nmsb, 
              void (*seq_sort)(), 
               int  (*compare)(byte *, byte*),
               int  (*compare_tn)(byte *,byte*,t_type))
{
  byte *tmp, *temp ;
  int j ;
  register t_type pos,sz,k;
  t_type i, idx ;
  byte *sr,*de;

  sz = sbytes + 2 * sizeof(t_type) ;
  tmp  = (byte *)malloc(sz);
  temp = (byte *)malloc(nelems * sz);

  rsort_msb(src, nelems, sbytes, nmsb) ;

  for (i = 0, idx = 0 ; i < nelems-1 ; ++i)
    {
      if (compare_tn(&src[i*sbytes], &src[(i+1)*sbytes], nmsb) == 0)
        {
          j = i++ ;
          while ((i < nelems-1) && ((D) >= i-j-2) &&
                 (compare_tn(&src[i*sbytes], &src[(i+1)*sbytes], nmsb) == 0)) ++i ;
          if ((D) > i-j-3)
            Ins_Sort(&src[j*sbytes], i-j+1, sbytes, compare) ;
          else
            {
              while (i >= j)
                {
                  memcpy(tmp, &src[j*sbytes], sbytes) ;
                  memcpy(&tmp[sbytes], &j, sizeof(t_type)) ;
                  memcpy(&tmp[sbytes+sizeof(t_type)], &idx, sizeof(t_type)) ;
                  memcpy(&temp[idx++*sz], tmp, sz) ;
                  ++j ;
                }
              while ((i < nelems-1) &&
                     (compare_tn(&src[i*sbytes], &src[(i+1)*sbytes], nmsb) == 0))
                {
                  ++i ;
                  memcpy(tmp, &src[i*sbytes], sbytes) ;
                  memcpy(&tmp[sbytes], &i, sizeof(t_type)) ;
                  memcpy(&tmp[sbytes+sizeof(t_type)], &idx, sizeof(t_type)) ;
                  memcpy(&temp[idx++*sz], tmp, sz) ;
                }
            }
        }
    }

  seq_sort(temp, idx, sz, compare) ;

  for (i = 0 ; i < idx ; ++i)
    {
      pos = (t_type)temp[i*sz+sbytes] + i - (t_type)temp[i*sz+sbytes+sizeof(t_type)] ;
      memcpy(&src[pos*sbytes], &temp[i*sz], sbytes) ;
/*  
      for(sr=&src[pos*sbytes],de=&temp[i*sz],j=sbytes;0<j;++sr,++de,--j)
          *sr=*de;
*/  
    }

  free(temp) ; free(tmp) ;
}
