#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <alloc.h>
#include <limits.h>

#include "queue.h"

typedef struct RunStruct {
	unsigned long   Begin;
	unsigned long   Count;
	}               RUN_ENT;

static struct RunArray {
	unsigned long   Current;
	unsigned long   Count;
	int             Index;
	char          **Buf;
	}              *RA;

static unsigned long BufSize;
static unsigned BufCount;
static char   **OutBuf;
static unsigned O_Index;
static unsigned Low;

void            FillRunBuffer(int x);
void            WriteOutputBuffer(void);

 void
Merge (void) {
	extern FILE    *fint, *fout;
	extern QUE_DEF  Runs;
	extern int      RecLen;
	extern int      comp(const void *a, const void *b);
	extern char   **SortArray;
	extern unsigned S_ArraySize;
	extern char     IntName[65];

	unsigned        i, j;
	QUE_ENTRY      *t;
	RUN_ENT        *p;
	unsigned long   MemLeft;

	for (i = 0; i < S_ArraySize; ++i) free(SortArray[i]);
	free(SortArray);
	MemLeft = (S_ArraySize * sizeof(char far *)) + (S_ArraySize * (RecLen + 2));

	if ((fint = freopen(IntName, "r", fint)) == NULL) {
		fprintf(stderr, "%s\n", IntName);
		fprintf(stderr, "Major error! %d", errno);
		perror("");
		exit(11);
		}

	if ((RA = malloc(Runs.Count * sizeof(struct RunArray))) == NULL) {
		fprintf(stderr, "Major Error. Insufficient memory for run array.\n");
		exit(12);
		}
	MemLeft -= (Runs.Count * sizeof(struct RunArray));

	BufSize = MemLeft / (Runs.Count + 1);
	if (BufSize > UINT_MAX) BufSize = UINT_MAX;
	BufCount = (int) (BufSize / (RecLen + 2 + sizeof(char *)));
	BufSize = BufCount * (RecLen + 2);

	for (i = 0, t = Runs.Head; t != NULL; ++i, t = t->Next) {
		p = t->Body;
		RA[i].Current = p->Begin;
		RA[i].Count = p->Count;
		RA[i].Index = 0;
		if ((RA[i].Buf = malloc(BufCount * sizeof(char *))) == NULL) {
			fprintf(stderr, "Major Error. Insufficient memory for run item\n");
			exit(12);
			}
		MemLeft -= BufCount * sizeof(char *);
		for (j = 0; j < BufCount; ++j) {
			if ((RA[i].Buf[j] = malloc(RecLen + 2)) == NULL) {
				fprintf(stderr, "Major Error. Insufficient memory for run item buffer.\n");
				exit(12);
				}
			MemLeft -= RecLen + 2;
			}
		}

	if ((OutBuf = malloc(BufCount * sizeof(char *))) == NULL) {
		fprintf(stderr, "Insufficient memory: 3\n");
		exit(12);
		}
	MemLeft -= BufCount * sizeof(char *);
	for (j = 0; j < BufCount; ++j) {
		if ((OutBuf[j] = malloc(RecLen + 2)) == NULL) {
			fprintf(stderr, "Insufficient memory: 4\n");
			exit(12);
			}
		MemLeft -= RecLen + 2;
		}
	O_Index = 0;

	for (i = 0; i < Runs.Count; ++i) FillRunBuffer(i);

	Low = 0;

	while (1) {
		for (Low = 0, i = 1; i < Runs.Count; ++i) {
			if (comp(&RA[i].Buf[RA[i].Index], &RA[Low].Buf[RA[Low].Index]) < 0)
				Low = i;
			}
		if (RA[Low].Buf[RA[Low].Index] == NULL) break;
		strcpy(OutBuf[O_Index++], RA[Low].Buf[RA[Low].Index++]);
		if (RA[Low].Index >= BufCount) FillRunBuffer(Low);
		if (O_Index >= BufCount) WriteOutputBuffer();
		}

	if (O_Index > 0) WriteOutputBuffer();
	fclose(fint);
	fclose(fout);
	}



 void
FillRunBuffer (int x) {
	unsigned        i;

	fseek(fint, RA[x].Current, SEEK_SET);
	for (i = 0; (i < BufCount) && (i < RA[x].Count); ++i) {
		fgets(RA[x].Buf[i], RecLen + 1, fint);
		}
	RA[x].Count -= i;
	for (; i < BufCount; ++i) RA[x].Buf[i] = NULL;
	RA[x].Current = ftell(fint);
	RA[x].Index = 0;
	}


 void
WriteOutputBuffer (void) {
	extern int      errno;
	extern long     OutCount;
	unsigned        i;

	for (i = 0; i < O_Index; ++i) {
		fputs(OutBuf[i], fout);
		if (errno) {
			perror("I/O error on output file");
			exit(8);
			}
		OutCount++;
		}
	O_Index = 0;
	}