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

#define W 6
#define MAXKEY INT_MAX

typedef int KeyType;
typedef int LoserTree[W];
typedef struct{
	KeyType key;
}RcdType;
typedef struct{
	RcdType rec;
	KeyType key;
	int rnum;
}RcdNode, WorkArea[W];

void Select_MiniMax(LoserTree ls, WorkArea wa, int q)
{
	int t, p;
	int tmp;
	for(t=(W+q)/2,p=ls[t]; t>0; t=t/2,p=ls[t])
	{
		if(wa[p].rnum<wa[q].rnum || wa[p].rnum==wa[q].rnum && wa[p].key<wa[q].key)
		{
			tmp = ls[t];
			ls[t] = q;
			q = tmp;
		}
	}
	ls[0] = q;
}

void Construct_Loser(LoserTree ls, WorkArea wa, FILE *fi)
{
	int i;

	for(i=0; i<W; i++)
		wa[i].rnum = wa[i].key = ls[i] = 0;

	fseek(fi, 0, SEEK_SET);
	for(i=W-1; i>=0; i--)
	{
		fread(&wa[i].rec, sizeof(RcdType), 1, fi);
		wa[i].key = wa[i].rec.key;
		wa[i].rnum = 1;
		Select_MiniMax(ls, wa, i);
	}
}

void get_run(LoserTree ls, WorkArea wa, FILE *fi, FILE *fo, int rc, int *rmax)
{
	int q, minimax;

	while(wa[ls[0]].rnum == rc)
	{
		q = ls[0];
		minimax = wa[q].key;
		fwrite(&wa[q].rec, sizeof(RcdType), 1, fo);

		fread(&wa[q].rec, sizeof(RcdType), 1, fi);
		if(feof(fi))
		{
			wa[q].rnum = *rmax+1;
			wa[q].key = MAXKEY;
		}
		else
		{
			wa[q].key = wa[q].rec.key;
			if(wa[q].key < minimax)
			{
				*rmax = rc+1;
				wa[q].rnum = *rmax;
			}
			else
				wa[q].rnum = rc;
		}
		Select_MiniMax(ls, wa, q);
	}
}

void Replace_Selection(LoserTree ls, WorkArea wa, FILE *fi, FILE *fo)
{
	int rc, rmax;
	RcdType RUNEND_SYMBOL;

	Construct_Loser(ls, wa, fi);

	RUNEND_SYMBOL.key = MAXKEY;
	rc = rmax = 1;
	while(rc <= rmax)
	{
		get_run(ls, wa, fi, fo, rc, &rmax);
		fwrite(&RUNEND_SYMBOL, sizeof(RcdType), 1, fo);
		rc = wa[ls[0]].rnum;
	}
}

void main()
{
	FILE *fi, *fo;
	RcdType rcd;
	LoserTree ls;
	WorkArea wa;
	int i;

	if((fi=fopen("fi", "wb+"))==NULL || (fo=fopen("fo", "wb+"))==NULL)
	{
		printf("Can not open i/o file.\n");
		exit(0);
	}

	printf("Please input data: \n");
	scanf("%d", &rcd.key);
	while(rcd.key>0)
	{
		fwrite(&rcd, sizeof(RcdType), 1, fi);
		scanf("%d", &rcd.key);
	}

	Replace_Selection(ls, wa, fi, fo);

	printf("After Sort:\n");
	fseek(fo, 0, SEEK_SET);
	fread(&rcd, sizeof(RcdType), 1, fo);
	while(!feof(fo))
	{
		if(rcd.key == MAXKEY)
			printf("\n");
		else
			printf("%d ", rcd.key);
		fread(&rcd, sizeof(RcdType), 1, fo);
	}

	fclose(fi);
	fclose(fo);
}