/*  сортировка  массивa - ключa */
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "Alinit.h"

#define LIMIT 31
#define         TEMMEM(a,b)\
		memcpy(a, tosort+b,width)
#define         MEMMEM(a,b)\
		memcpy(tosort+a,tosort+b,width)
#define         MEMTEM(a,b)\
		memcpy(tosort+a,b,width)
#define         TEMMEM2(a,b)\
		memcpy(a, tosort2+b,width2)
#define         MEMMEM2(a,b)\
		memcpy(tosort2+a,tosort2+b,width2)
#define         MEMTEM2(a,b)\
		memcpy(tosort2 + a,b, width2)

int   qsortk(char * tosort, unsigned int num, unsigned int wi,
      int (*compar)(const void *, const void * ))
/* Quick Sort Keys */
/*   Матвеев на основе идей qsort UNIX и   */
/*   algorithm 271 ,communications ACM,vol.8,no 11,p.669    */

/*     11.11.1991 переделана на работу со смещениями */

/*     сделано вместо системного qsort   */
//char * tosort;/*  1 Keys                  */
//unsigned int num   ; /*  число ключей */
//unsigned int wi    ; /* ширина поля 1 ключа   */
//int (*compar)(const void *, const void * );  /*  функция сравнения двух 1 ключей */
{
	int width ; /* ширина поля 1 ключа   */
	int i; /*  результат сравнения двух первых ключей */
	/*  смещения для массива tosort */
	long number;   /*    */
	long origin;   /*  i */
	long lowlim;   /*  k */
	long highlim;  /*  q */
	long partind;  /*  m */
	long pivot;    /*  p */
	char * exch;     /*  x */
	char * temp;     /*   */
	/*  стеки смещений для tosort */
	long parttablow[LIMIT];   /* lt */
	long parttabhigh[LIMIT];   /* ut */
	int rc;
         char * addr;

	width=wi;

        addr=alvec((int)(2*wi),&rc);
        temp=addr;
        exch=addr+wi;

	number=((long)num-1)*width;

	/* sort:begin*/
	origin=0;/*1*/
	partind=0;/*1*/

testsize: /* N */
	if (number-origin>width)
	{
		pivot=(((number+origin)/width)/2)*width;
		TEMMEM(temp,pivot);
		MEMMEM(pivot,origin);
		highlim=number;
		/*  findhigh:*/
		for (lowlim=origin+width;
		    lowlim<=highlim;
		    lowlim+=width)
		{
			i=(*  compar)(tosort+lowlim,temp);
			if ( i>0			    )
			{
				/*   findlow:*/
				for (;highlim>=lowlim;
				    highlim-=width)
				{
					i=    (* compar) (temp,tosort+highlim);
					if
					/*(tosort[highlim]<temp)*/
					(i>0 )
					    {
						TEMMEM(exch,lowlim)     ;
						MEMMEM(lowlim,highlim)    ;
						MEMTEM(highlim,exch)        ;
						highlim-=width;
						goto endhigh;
					}
				}/*findflow*/
				highlim=lowlim-width;
				goto limsmet;
			}
endhigh:/*L*/
			;
		}/* findhigh*/
limsmet:/*M*/
		MEMMEM(origin,highlim)  ;
		MEMTEM(highlim,temp)      ;
		if (2*highlim>origin+number)
		{
			parttablow[partind]=origin;
			parttabhigh[partind]=highlim-width;
			origin=highlim+width;
		}
		else 
		{
			parttablow[partind]=highlim+width;
			parttabhigh[partind]=number;
			number=highlim-width;
		}
		partind++;
		if (partind>LIMIT) {
			return 1;
		}
		goto testsize;
	}/*testsize*/
	if (origin>=number) goto setpart;/*   attention*/
	i=	    (* compar )	    (tosort+origin,	    tosort+number);
	if 
	(i>0)
	{
		TEMMEM(exch,origin)     ;
		MEMMEM(origin,number)     ;
		MEMTEM(number,exch)        ;
	}
setpart:/*P*/
	partind--;
	if (partind>-1)/* attention*/
	{
		origin=parttablow[partind];
		number=parttabhigh[partind];
		goto testsize;
	}
         rc=frevec(&addr);
         return rc;
} /* qsortk*/
/*  сортировка двух массивов - ключей */

int   qsortkk(char * tosort, char * tosort2, unsigned int num, unsigned int wi,
      int (*compar)(const void *, const void * ), unsigned int wi2,
      int (*compar2)(const void *, const void * ))
/* Quick Sort Consistent (2 Keys: first & second)*/
/*   Матвеев на основе идей qsort UNIX и   */
/*   algorithm 271 ,communications ACM,vol.8,no 11,p.669    */
/*     11.11.1991 переделана на работу со смещениями */
//char * tosort;/*  1 Keys                  */
//char * tosort2;/*  2 Keys                  */
//unsigned int num   ; /*  число ключей */
//unsigned int wi    ; /* ширина поля 1 ключа   */
//unsigned int wi2; /* ширина поля  2 ключа  */
//int (*compar)(const void *, const void * );  /*  функция сравнения двух 1 ключей */
//int (*compar2)(const void *, const void * );  /*  функция сравнения двух 2 ключей */

{
	int width ; /* ширина поля 1 ключа   */
	int width2 ; /* ширина поля  2 ключа  */
	int i; /*  результат сравнения двух первых ключей */
	/*  смещения для массива tosort */
	long number;   /*    */
	long origin;   /*  i */
	long lowlim;   /*  k */
	long highlim;  /*  q */
	long partind;  /*  m */
	long pivot;    /*  p */
	/*  смещения для массива tosort2 */
	long number2;   /*    */
	long origin2;   /*  i */
	long lowlim2;   /*  k */
	long highlim2;  /*  q */
	long pivot2;    /*  p */
	char * temp;     /*  t */
	char * temp2;     /*  t2 */
	char * exch;     /*  x */
	char * exch2;     /*  x2 */
	/*  стеки смещений для tosort */
	long parttablow[LIMIT];   /* lt */
	long parttabhigh[LIMIT];   /* ut */
	/*  стеки смещений для tosort2 */
	long parttablow2[LIMIT];   /* lt */
	long parttabhigh2[LIMIT];   /* ut */
	int rc;
        char * addr;

	width=wi;
	width2=wi2;

        addr=alvec((int)(2*wi+2*wi2),&rc);
        temp=addr;
        temp2=addr+wi;
        exch=temp2+wi2;
        exch2=exch+wi;
	number=((long)num-1)*width;
	number2=((long)num-1)*width2;

	/* sort:begin*/
	origin=0;/*1*/
	partind=0;/*1*/
	origin2=0;

testsize: /* N */
	if (number-origin>width)
	{
		pivot=(((number+origin)/width)/2)*width;
		pivot2=(((number2+origin2)/width2)/2)*width2;
		TEMMEM(temp,pivot);
		TEMMEM2(temp2,pivot2);
		MEMMEM(pivot,origin);
		MEMMEM2(pivot2,origin2);
		highlim=number;
		highlim2=number2;
		/*  findhigh:*/
		for (lowlim=origin+width,lowlim2=origin2+width2;
		    lowlim<=highlim;
		    lowlim+=width,lowlim2+=width2)
		{
			i=(*  compar)(tosort+lowlim,temp);
			if ( i>0  ||
			    ( i==0 && (*  compar2) (tosort2+lowlim2,temp2)>0)
			    )
			{
				/*   findlow:*/
				for (;highlim>=lowlim;
				    highlim-=width,
				    highlim2-=width2)
				{
					i=    (* compar) (temp,tosort+highlim);
					if
					/*(tosort[highlim]<temp)*/
					(i>0  || (i==0 &&
					    (* compar2)    (temp2,tosort2+highlim2)>0))
					    {
						TEMMEM(exch,lowlim)     ;
						TEMMEM2(exch2,lowlim2)   ;
						MEMMEM(lowlim,highlim)    ;
						MEMMEM2(lowlim2,highlim2)  ;
						MEMTEM(highlim,exch)        ;
						MEMTEM2(highlim2,exch2)       ;
						highlim-=width;
						highlim2-=width2;
						goto endhigh;
					}
				}/*findflow*/
				highlim=lowlim-width;
				highlim2=lowlim2-width2;
				goto limsmet;
			}
endhigh:/*L*/
			;
		}/* findhigh*/
limsmet:/*M*/
		MEMMEM(origin,highlim)  ;
		MEMMEM2(origin2,highlim2);
		MEMTEM(highlim,temp)      ;
		MEMTEM2(highlim2,temp2)     ;
		if (2*highlim>origin+number)
		{
			parttablow[partind]=origin;
			parttabhigh[partind]=highlim-width;
			parttablow2[partind]=origin2;
			parttabhigh2[partind]=highlim2-width2;
			origin=highlim+width;
			origin2=highlim2+width2;
		}
		else 
		{
			parttablow[partind]=highlim+width;
			parttabhigh[partind]=number;
			parttablow2[partind]=highlim2+width2;
			parttabhigh2[partind]=number2;
			number=highlim-width;
			number2=highlim2-width2;
		}
		partind++;
		if (partind>LIMIT) {
			return 1;
		}
		goto testsize;
	}/*testsize*/
	if (origin>=number) goto setpart;/*   attention*/
	i=	    (* compar )	    (tosort+origin,	    tosort+number);
	if 
	(i>0  || (i==0 &&
	    (* compar2)	    (tosort2+origin2,	    tosort2+number2)>0 ) )
	{
		TEMMEM(exch,origin)     ;
		TEMMEM2(exch2,origin2)    ;
		MEMMEM(origin,number)     ;
		MEMMEM2(origin2,number2)     ;
		MEMTEM(number,exch)        ;
		MEMTEM2(number2,exch2)       ;
	}
setpart:/*P*/
	partind--;
	if (partind>-1)/* attention*/
	{
		origin=parttablow[partind];
		number=parttabhigh[partind];
		origin2=parttablow2[partind];
		number2=parttabhigh2[partind];
		goto testsize;
	}
        rc=frevec(&addr);
        return rc;

} /* qsortkk*/
/*  сортировка двух массивов - 1 массив - ключ, 2 массив - запись  */
int   qsortkr(char * tosort, char * tosort2, unsigned int num,
      unsigned int wi,
      int (*compar)(const void *, const void * ), unsigned int wi2)
/* Quick Sort nonConsistent (1 Keys & 1 Records)*/
/*   Матвеев на основе идей qsort UNIX и   */
/*   algorithm 271 ,communications ACM,vol.8,no 11,p.669    */
/*     11.11.1991  работа со смещениями */
//char * tosort;/*  Keys                  */
//char * tosort2;/*  Records                */
//unsigned int num   ; /*  число ключей */
//unsigned int wi    ; /* ширина поля  ключа   */
//unsigned int wi2    ; /* ширина поля  записи */
//int (*compar)(const void *, const void * );  /*  функция сравнения двух  ключей */

{
	/*  смещения для массива tosort */
	long number;   /*    */
	long origin;   /*  i */
	long lowlim;   /*  k */
	long highlim;  /*  q */
	long partind;  /*  m */
	long pivot;    /*  p */
	/*  смещения для массива tosort2 */
	long number2;   /*    */
	long origin2;   /*  i */
	long lowlim2;   /*  k */
	long highlim2;  /*  q */
	long pivot2;    /*  p */
	char * temp;     /*  t */
	char * temp2;     /*  t2 */
	char * exch;     /*  x */
	char * exch2;     /*  x2 */
	/*  стеки смещений для tosort */
	long parttablow[LIMIT];   /* lt */
	long parttabhigh[LIMIT];   /* ut */
	/*  стеки смещений для tosort2 */
	long parttablow2[LIMIT];   /* lt */
	long parttabhigh2[LIMIT];   /* ut */
	int width ; /* ширина поля  ключа   */
	int width2 ; /* ширина поля  записи */
	int rc;
        char * addr;

	width=wi;
	width2=wi2;

        addr=alvec((int)(2*wi+2*wi2),&rc);
        temp=addr;
        temp2=addr+wi;
        exch=temp2+wi2;
        exch2=exch+wi;
	number=((long)num-1)*width;
	number2=((long)num-1)*width2;

	/* sort:begin*/
	origin=0;/*1*/
	partind=0;/*1*/
	origin2=0;

testsize: /* N */
	if (number-origin>width)
	{
		pivot=(((number+origin)/width)/2)*width;
		pivot2=(((number2+origin2)/width2)/2)*width2;
		TEMMEM(temp,pivot);
		TEMMEM2(temp2,pivot2);
		MEMMEM(pivot,origin);
		MEMMEM2(pivot2,origin2);
		highlim=number;
		highlim2=number2;
		/*  findhigh:*/
		for (lowlim=origin+width,lowlim2=origin2+width2;
		    lowlim<=highlim;
		    lowlim+=width,lowlim2+=width2)
		{
			if (
			    (*  compar)
			    (tosort+lowlim,temp)>0
			    )
			{
				/*   findlow:*/
				for (;highlim>=lowlim;
				    highlim-=width,
				    highlim2-=width2)
				{
					if 
                                   /*(tosort[highlim]<temp)*/
					( (* compar )
					    (temp,tosort+highlim)>0)
					{
						TEMMEM(exch,lowlim)     ;
						TEMMEM2(exch2,lowlim2)   ;
						MEMMEM(lowlim,highlim)    ;
						MEMMEM2(lowlim2,highlim2)  ;
						MEMTEM(highlim,exch)        ;
						MEMTEM2(highlim2,exch2)       ;
						highlim-=width;
						highlim2-=width2;
						goto endhigh;
					}
				}/*findflow*/
				highlim=lowlim-width;
				highlim2=lowlim2-width2;
				goto limsmet;
			}
endhigh:/*L*/
			;
		}/* findhigh*/

limsmet:/*M*/
		MEMMEM(origin,highlim)  ;
		MEMMEM2(origin2,highlim2);
		MEMTEM(highlim,temp)      ;
		MEMTEM2(highlim2,temp2)     ;
		if (2*highlim>origin+number)
		{
			parttablow[partind]=origin;
			parttabhigh[partind]=highlim-width;
			parttablow2[partind]=origin2;
			parttabhigh2[partind]=highlim2-width2;
			origin=highlim+width;
			origin2=highlim2+width2;
		}
		else 
		{
			parttablow[partind]=highlim+width;
			parttabhigh[partind]=number;
			parttablow2[partind]=highlim2+width2;
			parttabhigh2[partind]=number2;
			number=highlim-width;
			number2=highlim2-width2;
		}
		partind++;
		if (partind>LIMIT) {

			return 1;
		}
		goto testsize;
	}/*testsize*/
	if (origin>=number) goto setpart;/*   attention*/
	if 
     /*       (tosort[origin]>tosort[number]) */
	((* compar )	    (tosort+origin,	    tosort+number)>0 )
	{
		TEMMEM(exch,origin)     ;
		TEMMEM2(exch2,origin2)    ;
		MEMMEM(origin,number)     ;
		MEMMEM2(origin2,number2)     ;
		MEMTEM(number,exch)        ;
		MEMTEM2(number2,exch2)       ;
	}
setpart:/*P*/
	partind--;
	if (partind>-1)/* attention*/
	{
		origin=parttablow[partind];
		number=parttabhigh[partind];
		origin2=parttablow2[partind];
		number2=parttabhigh2[partind];
		goto testsize;
	}
        rc=frevec(&addr);
        return rc;
} /* qsortkr*/
