#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

#define MAX_BUFFER 512	//buffer最大容量
#define NO_MEANING 99999999	//當(dāng)某順串已經(jīng)全部處理完時(shí)，給敗方樹外部節(jié)點(diǎn)填充這個(gè)超大值
#define MAX 10	//最大選手?jǐn)?shù)目


/********************* 緩沖區(qū)類，用環(huán)狀數(shù)組實(shí)現(xiàn)的隊(duì)列來實(shí)現(xiàn)之 ********************/
//設(shè)置頭指針front，尾指針rear
//插入在rear處，刪除在front處
template <class Elem> class Buffer{
	
	private:
		Elem * buf;	//存放元素的數(shù)組
		int front, rear;
		int n; //buffer中當(dāng)前元素的數(shù)目
	
	public:
		
		//constructor
		Buffer(){
			buf = new Elem [MAX_BUFFER];
			front = 0;
			rear = 0;
			n = 0;
			
		}

		//destructor
		~Buffer(){
		delete buf;
		}

		//判斷buffer是否為空
		bool isEmpty(){
			return (n==0);
		}

		//判斷buffer是否滿
		bool isFull(){
			return (n==MAX_BUFFER);
		}
		
		//列出buffer中所有的元素
		//假設(shè)元素類型為內(nèi)建類型
		void list(){
			if (isEmpty()){
				cout<<"no data!"<<endl<<endl;
				return;
			}

			int temp = front;
			for(int i = 0; i < n; i++){
				cout<<buf[temp % MAX_BUFFER]<<"  ";
				temp++;
			}
			cout<<endl<<endl;
		}
		
		//往buffer中插入元素x
		bool insert(Elem x){
			if(isFull()==false){//非滿
			buf[rear] = x;
			rear = (rear+1)%MAX_BUFFER;
			n++;
			return true;
			}
			else{
				cout<<"BUFFER FULL!"<<endl;
				return false;
			}
		}

		//從buffer中讀取元素x，并在buffer中刪除它
		bool read(Elem & x){
			if(isEmpty()==false){//非空
				x = buf[front];
				front = (front+1)%MAX_BUFFER;
				n--;
				return true;
			}
			else{
				cout<<"BUFFER EMPTY!"<<endl;
				return false;
			}
		}

		void flush(FILE  * outputFile){
			
			//寫入輸出文件
			int temp = front;
			for(int i = 0; i < n; i++){
				fprintf(outputFile,"%d ", buf[temp % MAX_BUFFER]);
				//cout<<buf[temp % MAX_BUFFER]<<"  ";
				temp++;
			}

			//清零
			n = 0;
			front = 0;
			rear = 0;
		}

};


/******** 全局Winner函數(shù)，確認(rèn)A[b]和A[c]的勝者，返回其下標(biāo)，為b和c之一 ********/
//這里取值小的為勝者
template<class T>
int Winner(T A[], int b, int c){
	//注意：這里我假定T是內(nèi)建類型，這樣才能直接比較大小
	if(A[b] < A[c])
		return b;
	else return c;
}


/********* 全局Loser函數(shù)，確認(rèn)A[b]和A[c]的敗者，返回其下標(biāo)，為b和c之一 **********/
//這里取值大的為敗者
template<class T>
int Loser(T A[], int b, int c){
	//注意：這里我假定T是內(nèi)建類型，這樣才能直接比較大小
	if(A[b] >= A[c])
		return b;
	else return c;
}


/**************** 敗方樹的實(shí)現(xiàn) ***************/
template<class T>
class LoserTree{
	private:
		int MaxSize;	//最大選手?jǐn)?shù)
		int n;	//當(dāng)前選手?jǐn)?shù)
		int LowExt;	//最底層外部節(jié)點(diǎn)數(shù)
		int offset;	//最底層外部節(jié)點(diǎn)之上的節(jié)點(diǎn)總數(shù)
		int * B;	//贏者樹數(shù)組，實(shí)際存放的是下標(biāo)
		T * L;	//元素?cái)?shù)組
		void Play(int p, int lc, int rc, int(* winner)(T A[], int b, int c), int(* loser)(T A[], int b, int c));

	public:
		LoserTree(int Treesize = MAX);
		~LoserTree(){delete [] B;}
		//初始化敗方樹
		void Initialize(T A[], int size,int (*winner)(T A[], int b, int c), int(*loser)(T A[], int b, int c));
		//返回最終勝者索引
		int Winner();
		//位置i的選手改變后重構(gòu)敗方樹
		void RePlay(int i, int(*winner)(T A[], int b, int c), int (*loser)(T A[], int b, int c));
};


template<class T>
LoserTree<T>::LoserTree(int TreeSize){
	MaxSize = TreeSize;
	B = new int[MaxSize];
	n = 0;
}


//成員函數(shù)Winner，返回最終勝者的索引
template<class T>
int LoserTree<T>::Winner(){
	return (n)?B[0]:0;
}


//成員函數(shù)Initilalize負(fù)責(zé)初始化敗者樹
template<class T>
void LoserTree<T>::Initialize(T A[], int size, int(*winner)(T A[], int b, int c), int(*loser)(T A[], int b, int c)) {

	//能否處理size個(gè)選手的數(shù)組a[]
	if(size > MaxSize || size < 2){
		cout<<"Bad Input!"<<endl<<endl;
		return;
	}

	//初始化成員變量
	n = size;
	L = A;

	//計(jì)算s=2^log(n-1)
	int i,s;
	for(s = 1; 2*s <= n-1; s+=s);

	LowExt = 2*(n-s);
	offset = 2*s-1;

	//最底層外部節(jié)點(diǎn)的比賽
	for(i = 2; i <= LowExt; i+=2)
		Play((offset+i)/2, i-1, i, winner, loser);
	//處理其余外部節(jié)點(diǎn)
	if(n%2){//n為奇數(shù)，內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)比賽
		//這里用L[LowExt+1]和它的父節(jié)點(diǎn)比賽
		//因?yàn)榇藭r(shí)它的父節(jié)點(diǎn)中存放的是其兄弟節(jié)點(diǎn)處的比賽勝者索引
		Play(n/2, B[(n-1)/2], LowExt+1, winner, loser);
		i = LowExt+3;
	}
	else i = LowExt+2;

	//剩余外部節(jié)點(diǎn)的比賽
	for(; i<=n; i+=2)
		Play((i-LowExt+n-1)/2, i-1, i, winner, loser);

	/*
	///////////////映射成敗者樹/////////////////
	//如果采用贏者樹的Play成員函數(shù)，則初始化敗方樹時(shí)需要以下的部分
	  
	int * temp;
	temp = new int [MaxSize];

	temp[0] = B[1];  //全局勝者
	
	int j;
	//和最底層外部節(jié)點(diǎn)相關(guān)的內(nèi)部節(jié)點(diǎn)
	for(j = 2; j <= LowExt; j+=2)
		temp[(offset+j)/2] = loser(L, j-1, j);
	//其余的第一個(gè)外部節(jié)點(diǎn)
	if(n%2){
		temp[n/2] = loser(L, B[n-1], LowExt+1);
		j = LowExt+3;
	}
	else j = LowExt+2;
	//剩余外部節(jié)點(diǎn)
	for(; j<=n; j+=2)
		temp[(j-LowExt+n-1)/2] = loser(L, j-1, j);

	//孩子都是內(nèi)部節(jié)點(diǎn)的內(nèi)部節(jié)點(diǎn)
	if(n%2){
		for(int k=n-1-(n+1)/2; k >= 1; k--)
			temp[k] = loser(L, B[2*k], B[2*k+1]);
	}
	else{
		for(int kk = n-1-n/2; kk >= 1; kk--)
			temp[kk] = loser(L, B[2*kk], B[2*kk+1]);
	}

	//把temp賦值給B
	delete [] B;
	B = temp;
	*/
}



//成員函數(shù)Play負(fù)責(zé)在內(nèi)部節(jié)點(diǎn)B[p]處開始比賽
template<class T>
void LoserTree<T>::Play(int p, int lc, int rc, int(* winner)(T A[], int b, int c), int(* loser)(T A[], int b, int c)){
	
		B[p] = loser(L, lc, rc);//敗者索引放在B[p]中
			
		int temp1, temp2;
		temp1 = winner(L, lc, rc);//p處的勝者索引

		while(p>1 && p%2){//右孩子，需要沿路徑繼續(xù)向上比賽
							  //和B[p]的父結(jié)點(diǎn)所標(biāo)識(shí)的外部結(jié)點(diǎn)相比較
			temp2 = winner(L, temp1, B[p/2]);//p的勝者和p的父結(jié)點(diǎn)比較，贏者暫存在temp2中
			B[p/2] = loser(L, temp1, B[p/2]);//敗者索引放入B[p/2]
			temp1 = temp2;
			p/=2;
		}//while

		//結(jié)束循環(huán)(B[p]是左孩子，或者B[1])之后，在B[p]的父結(jié)點(diǎn)寫入勝者索引
		B[p/2] = temp1; 


	/*
	//如果用贏者樹映射成敗方樹的方法，這段和贏者樹完全一樣
	//這部分和贏者樹的Play成員函數(shù)完全一樣
	//在B[p]處開始比賽
	//lc和rc分別是B[p]的左右孩子
	B[p] = winner(L, lc, rc);

	//如果B[p]位于右孩子處且沒有到樹根，則需要繼續(xù)向上比賽
	while(p > 1 && p % 2){//右孩子
		B[p/2] = winner(L, B[p-1], B[p]);
		p/=2;
	}
	*/
}



//成員函數(shù)RePlay負(fù)責(zé)選手i的值改變后重新開始比賽
template<class T>
void LoserTree<T>::RePlay(int i, int (*winner)(T A[], int b, int c), int (*loser)(T A[], int b, int c)){
	if(i <= 0 || i > n){
		cout<<"Out of Bounds!"<<endl<<endl;
		return;
	}

	int p;
	//確定父節(jié)點(diǎn)的位置
	if(i <= LowExt)
		p = (i+offset)/2;
	else
		p = (i-LowExt+n-1)/2;

	//這里有修改
	//B[0]中始終保存勝者的索引
	B[0] = winner(L, i, B[p]);
	//B[p]中保存敗者的索引
	B[p] = loser(L, i, B[p]);

	//這里有修改
	//沿路徑向上比賽
	for(; (p/2)>=1; p/=2){
		int temp;//臨時(shí)存放贏者的索引
		temp = winner(L,B[p/2], B[0]);
		B[p/2] = loser(L,B[p/2], B[0]);	
		B[0] = temp;
	}
}


/*************** 從文件讀入一批數(shù)據(jù)進(jìn)入緩沖區(qū) *****************/
//輸入?yún)?shù)分別是：
//f - 輸入文件句柄, b - 輸入緩沖區(qū)

template <class T>
void fillBuffer(FILE * f, Buffer<T> & b){
	int m = 0;
	T read;  //讀出的數(shù)據(jù)置放在里面
	while((!feof(f))&&(m < MAX_BUFFER)){
		fscanf(f, "%d ", &read);
		b.insert(read);
		m++;
	}//while
}


/******************** 多路歸并算法 ********************/
//輸入?yún)?shù)分別是：
//lt－敗方樹，racer－最初的競(jìng)賽者，bufferPool－緩沖池，f－輸入/輸出文件句柄數(shù)組
//這里輸出文件句柄是f[0]，輸入文件句柄是f[1]到f[MAX]，MAX為輸入文件的數(shù)目
//NO_MEANING宏代表一個(gè)極大值

template <class T>
void multiMerge(LoserTree<T> & lt, T * racer, Buffer<T> * bufferPool, FILE * * f){
	
	int winner;	//最終勝者索引

	//初始化敗方樹
	lt.Initialize(racer, MAX, Winner, Loser);

	////以下處理f[1]到f[MAX]所代表的MAX個(gè)輸入順串，并把結(jié)果輸出到f[0]所代表的輸出順串中
	
	//取得最終勝者索引
	winner = lt.Winner();
	
	while(racer[winner] != NO_MEANING){//循環(huán)退出時(shí)勝者為NO_MEANING，所有的輸入順串都已經(jīng)處理完畢
		

		//把勝者插入到輸出緩沖區(qū)中
		if(bufferPool[0].isFull())//輸出緩沖區(qū)滿，flush到磁盤文件去
			bufferPool[0].flush(f[0]);
		bufferPool[0].insert(racer[winner]);
	
		//從輸入緩沖區(qū)讀入一個(gè)新的競(jìng)賽者
		if(bufferPool[winner].isEmpty()==false)//輸入緩沖區(qū)不為空
			bufferPool[winner].read(racer[winner]);//從緩沖區(qū)讀入值放進(jìn)racer[winner]
		else{//輸入緩沖區(qū)為空
				
				if(!feof(f[winner])){//如果對(duì)應(yīng)的輸入文件還有數(shù)據(jù)
					
					//從輸入文件讀入一批數(shù)據(jù)到輸入緩沖區(qū)
					fillBuffer(f[winner], bufferPool[winner]);

					//從緩沖區(qū)讀數(shù)據(jù)放進(jìn)racer[winner]
					bufferPool[winner].read(racer[winner]);
				}
				else{//對(duì)應(yīng)的輸入文件沒有數(shù)據(jù)
					//在racer[winner]位置放NO_MEANING
					racer[winner] = NO_MEANING;
				}//else		
		}//else

		//重新進(jìn)行比賽，取得勝者索引
		lt.RePlay(winner, Winner<int>, Loser<int>);
		winner = lt.Winner();

	}//while
	 
	//把輸出緩沖區(qū)中剩余的數(shù)據(jù)寫進(jìn)磁盤文件
	bufferPool[0].flush(f[0]);

}