#include <stdio.h>
#include "defs.h"
#include "types.h"
#include "exports.h"


#define	BIT8		0xff
#define	BIT12		0xfff
#define	BIT24		0xffffff

#define	CNTSIZE		( 4096 + 4096 + 256 )
#define	COUNT1		&countBuff[ 0 ]
#define	COUNT2		&countBuff[ 4096 ]
#define	COUNT3		&countBuff[ 4096 + 4096 ]
#define	ENDCNT		&countBuff[ CNTSIZE ]


private	int	*countBuff;
private EdgeP	data;
private	EdgeP	*dataBuff;
private	EdgeP	*dataBuff1;


/*
 * Sort the edge array pointed to by 'edgeBuff'.  Return a pointer to a
 * sorted array of pointers into the original data.
 */
public EdgeP *SortEdges( nEdges, edgeBuff, maxX, maxY )
  int    nEdges;
  EdgeP  edgeBuff;
  int    maxX;
  int    maxY;
  {
    EdgeP  *tmp;

    data = edgeBuff;
    dataBuff = tmp = (EdgeP *) Malloc( sizeof( EdgeP ) * nEdges );
    SaveMem();
    countBuff = (int *) Malloc( sizeof( int ) * CNTSIZE );
    dataBuff1 = (EdgeP *) Malloc( sizeof( EdgeP ) * nEdges );
    BucketSort( nEdges, maxY, maxX );
    if( dataBuff != tmp )			/* swapped by sort */
      {
	register EdgeP	*src, *dst, *end;
	
	dataBuff1 = dataBuff;
	dataBuff = tmp;
	src = dataBuff1;
	dst = dataBuff;
	end = &dataBuff1[ nEdges ];
	do { *dst++ = *src++; } while( src < end );
      }
    RestoreMem();
    return( dataBuff );
  }


/*
 * Do an adaptive distribution (bucket or radix) sort on the edges.  The data
 * is sorted by lower left vertex, sorting first in 'y' then in 'x'.   For
 * details on the sort see: Knuth, section 5.2.5.
 * The sort is very fast, basically O(N), albeit a large constant.
 * The sort is adaptive in that it tries to sort the first 12 bits, then if
 * necessary the next 12 bits and then if necessary the last 8 bits.  It is
 * somewhat machine dependent in that it assumes that integers are 23 bits.
 * This scheme eases the amount of memory required to sort arbitrary 32 bit
 * numbers to just 8K + 256 words (instead of 4 Gwords).
 */
private BucketSort( nEdges, maxY, maxX )
  int  nEdges;
  int  maxX;
  int  maxY;
  {
		/* sort by y coordinate */
   {
    register int	*cp, *end;

    cp = COUNT1;
    end = ENDCNT;
    do { *cp++ = 0; } while( cp < end );
   }

   {
    register EdgeP	dat, end;
    register int	*count1, *count2, *count3;

    count1 = COUNT1;
    count2 = COUNT2;
    count3 = COUNT3;
    dat = data;
    end = &data[ nEdges ];

    if( maxY <= BIT12 )
      {
	do
	  {
	    count1[ dat->y & BIT12 ]++;
	    dat++;
	  }
	while( dat < end );
      }
    else if( maxY <= BIT24 )
      {
	do
	  {
	    count1[ dat->y & BIT12 ]++;
	    count2[ ( dat->y >> 12 ) & BIT12 ]++;
	    dat++;
	  }
	while( dat < end );
      }
    else
      {
	do
	  {
	    count1[ dat->y & BIT12 ]++;
	    count2[ ( dat->y >> 12 ) & BIT12 ]++;
	    count3[ ( dat->y >> 24 ) & BIT8 ]++;
	    dat++;
	  }
	while( dat < end );
      }

   }

   {
    register int	*cp, *cp_1;
    register int	*cp2, *cp2_1;
    register int	*end;
    cp = COUNT1;
    cp_1 = &cp[1];
    cp2 = COUNT2;
    cp2_1 = &cp2[1];
    end = COUNT2;
    do
      {
	*cp_1++ += *cp++;
	*cp2_1++ += *cp2++;
      }
    while( cp_1 < end );
    
    cp = COUNT3;
    cp_1 = &cp[1];
    end = ENDCNT;
    do { *cp_1++ += *cp++; } while( cp_1 < end );
   }

   {
    register int	tmp;
    register int	*count;
    register EdgeP	dat;
    register EdgeP	*datPtr, *end;
    
    dat = &data[ nEdges-1 ];
    count = COUNT1;
    datPtr = dataBuff;
    do
      {
	tmp = --count[ dat->y & BIT12 ];
	datPtr[ tmp ] = dat;
	dat--;
      }
    while( dat >= data );
    
    if( maxY <= BIT12 )
	goto doneY;

    datPtr = &dataBuff[ nEdges-1 ];
    end = dataBuff;
    count = COUNT2;
    do
      {
	tmp = -- count[ ((*datPtr)->y >> 12) & BIT12 ];
	dataBuff1[ tmp ] = *datPtr;
	datPtr--;
      }
    while( datPtr >= end );

    if( maxY <= BIT24 )
      {
	datPtr = dataBuff1;
	dataBuff1 = dataBuff;
	dataBuff = datPtr;
	goto doneY;
      }

    datPtr = &dataBuff1[ nEdges-1 ];
    end = dataBuff1;
    count = COUNT3;
    do
      {
	tmp = -- count[ ((*datPtr)->y >> 24) & BIT8 ];
	dataBuff[ tmp ] = *datPtr;
	datPtr--;
      }
    while( datPtr >= end );

   }

  doneY :
		/* now sort according to left x coordinate */
   {
    register int	*cp, *end;

    cp = COUNT1;
    end = ENDCNT;
    do { *cp++ = 0; } while( cp < end );
   }

   {
    register EdgeP	dat, end;
    register int	*count1, *count2, *count3;

    count1 = COUNT1;
    count2 = COUNT2;
    count3 = COUNT3;
    dat = data;
    end = &data[ nEdges ];

    if( maxX <= BIT12 )
      {
	do
	  {
	    count1[ dat->left & BIT12 ]++;
	    dat++;
	  }
	while( dat < end );
      }
    else if( maxX <= BIT24 )
      {
	do
	  {
	    count1[ dat->left & BIT12 ]++;
	    count2[ ( dat->left >> 12 ) & BIT12 ]++;
	    dat++;
	  }
	while( dat < end );
      }
    else
      {
	do
	  {
	    count1[ dat->left & BIT12 ]++;
	    count2[ ( dat->left >> 12 ) & BIT12 ]++;
	    count3[ ( dat->left >> 24 ) & BIT8 ]++;
	    dat++;
	  }
	while( dat < end );
      }

   }

   {
    register int	*cp, *cp_1;
    register int	*cp2, *cp2_1;
    register int	*end;
    cp = COUNT1;
    cp_1 = &cp[1];
    cp2 = COUNT2;
    cp2_1 = &cp2[1];
    end = COUNT2;
    do
      {
	*cp_1++ += *cp++;
	*cp2_1++ += *cp2++;
      }
    while( cp_1 < end );
    
    cp = COUNT3;
    cp_1 = &cp[1];
    end = ENDCNT;
    do { *cp_1++ += *cp++; } while( cp_1 < end );
   }

   {
    register int	tmp;
    register int	*count;
    register EdgeP	*datPtr, *end;
    
    datPtr = &dataBuff[ nEdges-1 ];
    count = COUNT1;
    end = dataBuff;
    do
      {
	tmp = --count[ (*datPtr)->left & BIT12 ];
	dataBuff1[ tmp ] = *datPtr;
	datPtr--;
      }
    while( datPtr >= end );
    
    if( maxX <= BIT12 )
      {
	datPtr = dataBuff1;
	dataBuff1 = dataBuff;
	dataBuff = datPtr;
	return;
      }

    datPtr = &dataBuff1[ nEdges-1 ];
    end = dataBuff1;
    count = COUNT2;
    do
      {
	tmp = -- count[ ((*datPtr)->left >> 12) & BIT12 ];
	dataBuff[ tmp ] = *datPtr;
	datPtr--;
      }
    while( datPtr >= end );

    if( maxX <= BIT24 )
	return;

    datPtr = &dataBuff[ nEdges-1 ];
    end = dataBuff;
    count = COUNT3;
    do
      {
	tmp = -- count[ ((*datPtr)->left >> 24) & BIT8 ];
	dataBuff1[ tmp ] = *datPtr;
	datPtr--;
      }
    while( datPtr >= end );
    datPtr = dataBuff;
    dataBuff = dataBuff1;
    dataBuff1 = datPtr;
   }
  }


#include "tmpfile.h"


typedef struct
  {
    FILE  *fp;
    int   eof;
    Edge  edge;
  } InputFile;


/*
 * Do an external merge-sort on the 'nfiles' temporary files, and write the
 * resulting sorted file to 'fout'.
 */
public void MergeFiles( nFiles, fout )
  int	nFiles;
  FILE	*fout;
  {
    TMPFile		*f;
    char		*tmp;
    IPoint		minp;
    InputFile		mf[ MAXMERGEFILES ];
    register InputFile	*cf, *minF, *lastFile;
    register int	compare;
    
    f = &tmpFiles[ SPLITFILES ];
    cf = mf;
    while( f < &tmpFiles[ SPLITFILES + nFiles ] )
      {
	if( (cf->fp = fopen( f->name, "r" )) == NULL )
	    Crash( "can't reopen tmp file '%s'\n", 2, f->name );
	setbuffer( cf->fp, Malloc( FILEBUFSIZE ), FILEBUFSIZE );
	cf->eof = not ( fread( &(cf->edge), sizeof( Edge ), 1, cf->fp ) );
	f++;
	cf++;
      }
    
    do
      {
	minF = NULL;
	for( cf = mf, lastFile = &mf[ nFiles ]; cf < lastFile; cf++ )
	  {
	    if( not cf->eof )
	      {
		if( minF == NULL )
		  {
		    minF = cf;
		    minp.x = cf->edge.left;
		    minp.y = cf->edge.y;
		  }
		else
		  {
		    if( (compare = cf->edge.left - minp.x) < 0 )
		      {
			minF = cf;
			minp.x = cf->edge.left;
			minp.y = cf->edge.y;
		      }
		    else if( compare == 0 and cf->edge.y < minp.y )
		      {
			minF = cf;
			minp.x = cf->edge.left;
			minp.y = cf->edge.y;
		      }
		  }
	      }
	  }
	if( minF != NULL )
	  {
	    fwrite( &(minF->edge), sizeof( Edge ), 1, fout );
	    minF->eof = not fread( &(minF->edge), sizeof(Edge), 1, minF->fp );
	  }
      }
    while( minF != NULL );

    f = &tmpFiles[ SPLITFILES ];
    cf = mf;
    while( f < &tmpFiles[ SPLITFILES + nFiles ] )
      {
	fclose( cf->fp );
	unlink( f->name );
	f++;
	cf++;
      }
    fclose( fout );
  }