Polyphase Merge(2)

Đây là bài cài đặt của bạn Vũ Âu, mà cũng thật có duyên, mình vô tình vô nhầm 3 cái blog khác nhau của bạn ấy. Bài này dựa sát theo bài cài đặt của thầy Long, mời các bạn xem qua.

//200090513_polymerge.cpp
//ES
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <iomanip.h>
#include <string.h>
#include <stdlib.h>

#define n 100
typedef int elem;
typedef struct 
{
	FILE *f;
	elem buffer;
}tape;

int size=sizeof(elem);

int ss(int x, int y)
{
	return x-y;
}

//mo tape
void opentape(tape &X, char *filename)
{
	X.f=fopen(filename, "rb");
	fread(&X.buffer,size, 1,X.f);
}

//doc tape
void readtape(tape &X, elem &x)
{
	memcpy(&x,&X.buffer,size);
	fread(&X.buffer,size,1,X.f);
}

//Chep 1 phan tu
void copyitemp(tape &X, tape &Y, int &EOR, elem &x, int (*comp)(elem, elem))
{
	readtape(X,x);
	fwrite(&x,size,1,Y.f);
	EOR=feof(X.f)||comp(x,X.buffer)>0;
}

//Chep 1 run
void copyrun(tape &X, tape &Y, elem &x, int (*comp)(elem, elem))
{
	int EOR;
	do
	{
		copyitemp(X,Y,EOR,x,comp);
	}while(!EOR);
}

//Chon file dich
void filedich(int a[], int d[], int &level, int &j)
{
	int z,i;
	if(d[j]<d[j+1])
		j++;
	else
	{
		if(d[j]==0)
		{
			z=a[n-2];//??
			for(i=0; i<n-2; i++)
			{
				d[i]=a[i+1]+z-a[i];
				a[i]=a[i+1]+z;
			}
			d[n-2]=z-a[n-2];
			a[n-2]=z;
			level++;
		}
		j=0;
	}
	d[j]--;
}

void polyphase(char *filename, int (*comp)(elem, elem))
{
	int a[n], d[n], t[n], ta[n], mx, k, i, j,level,tt,dt,z,EOR;
	elem last[n], x;
	char s[n][20],s1[20];
	tape f[n],F;

	for(i=0; i<n; i++)
	{
		strcpy(s[i],"TMP.");
		itoa(i,s1,10);
		strcat(s[i],s1);
	}
	//------Phan phoi ban dau--------------
	opentape(F,filename);
	for(i=0; i<n-1; i++)
	{
		f[i].f=fopen(s[i],"wb");
		a[i]=d[i]=1;
	}
	d[n-1]=0;
	level=1;
	j=0;
	do
	{
		filedich(a,d,level,j);
		copyrun(F,f[j],last[j],comp);
	}while(!feof(F.f) && (j<n-2));
	while(!feof(F.f))
	{
		filedich(a,d,level,j);
		if(comp(last[j],F.buffer)>0)
			copyrun(F,f[j],last[j],comp);
		else
		{
			copyrun(F,f[j],last[j],comp);
			if(!feof(F.f))
				copyrun(F,f[j],last[j],comp);
			else
				d[j]++;
		}
	}
	fclose(F.f);
	for(i=0; i<n-1; i++)
		fclose(f[i].f);
	//----------------Tron-------
	for(i=0; i<n; i++) //mo file f1,f2...f(n-1) de doc
		t[i]=i;//luu y: t[i] chu k phai f[i]
	for(i=0; i<n-1; i++) //mo du 1 ten cung k sao
		opentape(f[i],s[i]);
	//lap //cho den khi level =0
	do
	{
		//mo f(tn) de ghi//sai, mo f[ti]
		f[t[i]].f=fopen(s[t[i]],"wb");//???
		//z=a[n-1]
		z=a[n-2];
		//lap //cho den khi z=0;
		do
		{
			//k=0;//ghi nhan so run that
			k=0;
			//voi i=1..n-1 Thuc hien:
			for(i=0; i<n-1; i++)
			{
				//-neu d[i]>0: d[i]=d[i]-1
				//nguoc lai: {k=k+1;ta[k]=ti//ta la mang co run dang tron
				if(d[i]>0)
					d[i]--;
				else
					ta[k++]=t[i];//ta[k++]=t[i]//??
			}
			//neu k=0 thi: d[n]=d[n]+1;
			if(k==0)
				d[n-1]++;
			/*nguoc lai: 
				-lap cho den khi k=0;*/
			else
			{
				do
				{
					//min(fta1^,fta2^..ftak^):ftamx^
					mx=0;
					for(i=1; i<k; i++)
						if(comp(f[ta[mx]].buffer,f[ta[i]].buffer)>0)
							mx=i;
					//Chep 1 phan tu tu ta[mx] vao t[n](EOR)
					copyitemp(f[ta[mx]],f[t[n-1]],EOR,x,comp);
					/*Neu EOR thi: tamx=tak
									k=k-1*/
					if(EOR)
						ta[mx]=ta[--k];//????
				}while(k>0);
				//--------=> Tron xong 1 bo run---------
				z--;
			}
		}while(z>0);
		//dong ftn-1,ftn
		fclose(f[t[n-2]].f);
		fclose(f[t[n-1]].f);
		//-----------------Chuyen muc--------------
		z=a[n-2];
		tt=t[n-1];
		dt=d[n-1];
		//voi i=n-1...1 thuc hien
		for(i=n-2;i>=0;i--)
		{
			a[i+1]=a[i]-z;
			t[i+1]=t[i];
			d[i+1]=d[i];
		}
		a[0]=z;
		t[0]=tt;
		d[0]=dt;
		level--;
		//mo ft1 de doc
		opentape(f[t[0]],s[t[0]]);
	}while(level>0);
	//mo F de ghi
	F.f=fopen(filename,"wb");
	opentape(f[t[0]],s[t[0]]);//hoi nay la file dich, gio doi lai la file dau
	//Chep 1 run tu ft1 vao F
	copyrun(f[t[0]],F,x,comp);
	//dong ft1-ftn-1
	fclose(F.f);
	for(i=0; i<n-1; i++)
		fclose(f[t[i]].f);
	//don dep
	for(i=0; i<n; i++)
		remove(s[i]);
}

//tao file ngau nhien
void taofile(char *filename, int h)
{
	srand((unsigned)time(NULL));
	FILE *f=fopen(filename, "wb");
	int i,x;
	for(i=0; i<h; i++)
	{
		x=rand()%1000;
		fwrite(&x, size,1,f);
	}
	fclose(f);
}

//in file
void infile(char *filename)
{
	FILE *f= fopen(filename, "rb");
	int x;
	fread(&x,size,1,f);
	while(!feof(f))
	{
		cout<<x<<"   ";
		fread(&x,size,1,f);
	}
	fclose(f);
}

void main()
{
	int m;
	cout<<"polyphase program"
        <<"\nCompleted by Nguyen Thu Huong 20090514"
        <<"\n---------------******----------------\n";
	cout<<"Nhap so phan tu can tron: ";
	cin >>m;
	taofile("poly.txt",m);
	infile("poly.txt");
	cout<<"\n------------------------\n";
	cout<<endl;
	polyphase("poly.txt",ss);
	infile("poly.txt");
	cout<<endl;
}