#include <stdio.h>
#include <math.h>
#include <memory.h>
#include "bsp1.h"
#define BYTE_ZERO      (byte)0
#define D              29
struct nd {
            byte      *data ;
            struct nd *next ;
          } ;
typedef struct nd node ;
void error_msg (char *msg)
{
  fprintf(stderr, "%s", msg) ;
  fflush(stderr);
  fflush(stdout);
  exit(1) ;
}
void Ins_Sort (byte *src, t_type nelems, t_type sbytes, 
               int  (*compare)(const byte *,const 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);
}

/****************************************************************************/
/*  This routine assumes that <nelems> = <range>^{<nmsb>}, where range    ***/
/*  is size of the alphabet, i.e. <range> = 26 if the alphabet consists   ***/
/*  of the capital letters.  <offset> corresponds to the ASCII code of    ***/
/*  of the first character of the alphabet, i.e. <offset> = 65.           ***/
/****************************************************************************/

void Hybrid_Sort (byte *src, t_type nelems, t_type sbytes, t_type nmsb, 
                  t_type range, t_type offset, void (*seq_sort)(), 
               int  (*compare)(const byte *,const byte*),
               int  (*compare_tn)(const byte *,const byte*,t_type))
{
  node   *t_h, *tmp_h, *temp_h ;
  byte   *tmp, *temp, *aux ;
  t_type  i, j, idx, pos, sz ;
  double  b, e, r, p, v ;


  if ((tmp_h = (node *)malloc(nelems * sizeof(node))) == NULL)
    {
      error_msg("Out of memory.") ;
      
    }

  for (i = 0 ; i < nelems ; ++i)
    {
      tmp_h[i].next = NULL ;
    }

  b = range * 1.0 ;
  e = nmsb * 1.0 ;
  r = pow(b, e) ;
  for (i = 0 ; i < nelems ; ++i)
    {
      for (j = nmsb-1, v = 0.0, p = 1.0 ; j >= 0 ; --j, p *= b)
        {
          v += p * (src[i*sbytes+j] - offset) ;
        }
      idx = (t_type)((v / r) * nelems) ;
      if ((temp_h = (node *)malloc(sizeof(node))) == NULL)
        {
          error_msg("Out of memory.") ;
	}
      temp_h->data = &src[i*sbytes] ;
      temp_h->next = tmp_h[idx].next ;
      tmp_h[idx].next = temp_h ;
    }

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

  for (i = 0, j = 0 ; i < nelems ; ++i)
    {
      temp_h = tmp_h[i].next ;
      while (temp_h != NULL)
        {
          memcpy(&aux[j++ * sbytes], temp_h->data, sbytes) ;
          t_h = temp_h ;
          temp_h = temp_h->next ;
          free(t_h) ;
	}
    }

  sz = sbytes + 2 * sizeof(t_type) ;
  if ((tmp = (byte *)malloc(sz)) == NULL)
    {
      error_msg("Out of memory.") ;
    }

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

  for (i = 0, idx = 0 ; i < nelems-1 ; ++i)
    {
      if (compare_tn(&aux[i*sbytes], &aux[(i+1)*sbytes], nmsb) == 0)
        {
          j = i++ ;
          while ((i < nelems-1) && (D >= i-j+1) &&
                 (compare_tn(&aux[i*sbytes], &aux[(i+1)*sbytes], nmsb) == 0)) ++i ;
          if (D > i-j)
            Ins_Sort(&aux[j*sbytes], i-j+1, sbytes, compare) ;
          else
            {
              while (i >= j)
                {
                  memcpy(tmp, &aux[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(&aux[i*sbytes], &aux[(i+1)*sbytes], nmsb) == 0))
                {
                  ++i ;
                  memcpy(tmp, &aux[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(&aux[pos*sbytes], &temp[i*sz], sbytes) ;
    }

  for (i = 0 ; i < nelems ; ++i)
    {
      memcpy(&src[i*sbytes], &aux[i*sbytes], sbytes) ;
    }

/*
  free(temp) ; free(tmp) ; free(temp_h);free(tmp_h);
*/
  free(temp) ; free(tmp) ; 
}
