losertree.h

队放置于硬盘上的文件进行外排序

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


//比较两个数的大小，值小者为胜，返回其下标
template<class T>
int Winner(T A[], int b, int c)
{
	if(A[b] < A[c])
		return b;
	else return c;
}


//比较两个数的大小，值大者败，返回其下标
template<class T>
int Loser(T A[], int b, int c)
{
	if(A[b] < A[c])
		return c;
	else return b;
}


//****************************************败者树*******************************************
/*
以下是败者树类：
基本数据：
	MaxSize：纪录最多可以容纳的选手数目
	n:当前选手数目
	LowExt：纪录最底层外部结点数
	offset：最底层外部结点之上的结点总数
	* B：存储赢者下标的数组
	* L：存储元素的数组
成员函数：
	Play()：从指定下标处进行比赛
	RePlay()：函数用于将位置i的选手改变后重构败者树
	LoserTree(int Treesize = MAX)：构造函数
	~LoserTree()：析构函数
	void Initialize：初始化函数
	int Winner()：不同于之前定义的比较两个人胜者的大小的winner函数，此处的函数是返回最终胜者的索引
*/
template<class T>
class LoserTree
{
	private:
		int MEMORY1Size;
		int n;
		int LowExt;
		int offset;	
		int * B;
		T * L;
		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 = MEMORY1);
		~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();
		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)
{
	MEMORY1Size = TreeSize;
	B = new int[MEMORY1Size];
	n = 0;
}


//成员函数Winner，返回最终胜者的索引
template<class T>
int LoserTree<T>::Winner()
{
	return (n)?B[0]:0;
}


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--;
	
	//判断size是否符合要求
	if(size > MEMORY1Size || size < 2)
		return;

	//初始化成员变量
	n = size;
	L = A;

	//计算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;

	//最底层外部节点的比赛
	for(i = 2; i <= LowExt; i+=2)
		Play((offset+i)/2, i-1, i, winner, loser);

	//处理其余外部节点
	if(n%2)
	{//n为奇数，内部节点和它的父节点比赛
		Play(n/2, B[(n-1)/2], LowExt+1, winner, loser);
		i = LowExt+3;
	}
	else i = LowExt+2;

	//剩余外部节点的比赛
	for(; i<=n; i+=2)
		Play((i-LowExt+n-1)/2, i-1, i, winner, loser);
}


//成员函数Play负责在内部节点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)
		{//右孩子，需要沿路径继续向上比赛
							  //和B[p]的父结点所标识的外部结点相比较
			temp2 = winner(L, temp1, B[p/2]);//p的胜者和p的父结点比较，赢者暂存在temp2中
			B[p/2] = loser(L, temp1, B[p/2]);//败者索引放入B[p/2]
			temp1 = temp2;
			p/=2;
		}

		//结束循环(B[p]是左孩子，或者B[1])之后，在B[p]的父结点写入胜者索引
		B[p/2] = temp1; 
}


//选手i的值改变后修改相应结点的值
/*
在判断输入的参数i符合要求后，RePlay首先确定i父结点的值，
然后将i和它父结点进行比赛，胜者放入B[0]中，败者放入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)
		return;

	int p;
	//确定i的父节点
	if(i <= LowExt)
		p = (i+offset)/2;
	else
		p = (i-LowExt+n-1)/2;

	//B[0]，B[p]中始终保存胜者,负者的索引
	B[0] = winner(L, i, B[p]);
	B[p] = loser(L, i, B[p]);

	for(; (p/2)>=1; p/=2)
	{
		int temp;
		temp = winner(L,B[p/2], B[0]);
		B[p/2] = loser(L,B[p/2], B[0]);	
		B[0] = temp;
	}
}


/*
下面函数fillBuffer()执行的是让缓冲区从文件中读入数据
参数：
	f ：输入文件句柄
	b ： 输入缓冲区
实现：从文件中逐个取出MAX_BUFFER个纪录存入放入数组read当中，
	  当文件中剩余的纪录不足以填满一个缓冲区时，将buffer中的当前元素数目减一
*/
template <class T>
void fillBuffer(FILE * f, Buffer<T> & b)
{
	int m = 0;
	char read[52]; 
	while((!feof(f))&&(m < MEMORY2))
	{
		fgets(read,52, f);
		T t(read);
		b.insert(t);
		m++;
	}
	if(feof(f)&&m>0)
		b.n--;
}


/******************** 多路归并算法 ********************/
//输入参数分别是：
//lt－败方树，racer－最初的竞赛者，bufferPool－缓冲池，f－输入/输出文件句柄数组
//这里输出文件句柄是f[0]，输入文件句柄是f[1]到f[MEMORY1]，MEMORY1为输入文件的数目
//NO_MEANING宏代表一个极大值

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

	//初始化败方树
	lt.Initialize(racer, branches, Winner, Loser);

	//以下处理f[1]到f[MEMORY1]所代表的MEMORY1个输入顺串，并把结果输出到f[0]所代表的输出顺串中
	
	//取得最终胜者索引
	winner = lt.Winner();

	int k = branches;

	while(racer[winner] != NO_MEANING){//循环退出时胜者为NO_MEANING，所有的输入顺串都已经处理完毕
		
		//把胜者插入到输出缓冲区中
		if(bufferPool[0].isFull())//输出缓冲区满，flush到磁盘文件去
			bufferPool[0].flush(f[0]);

        k--;

        if(k == 0)
		{
		   bufferPool[0].insert(racer[winner]);
		   k=1;
		}
	
		//从输入缓冲区读入一个新的竞赛者
		if(bufferPool[winner].isEmpty()==false)//输入缓冲区不为空
			bufferPool[winner].read(racer[winner]);//从缓冲区读入值放进racer[winner]
		else
		{//输入缓冲区为空
				
				if(!feof(f[winner]))
				{//如果对应的输入文件还有数据
					
					//从输入文件读入一批数据到输入缓冲区
					fillBuffer(f[winner], bufferPool[winner]);

					//从缓冲区读数据放进racer[winner]
					bufferPool[winner].read(racer[winner]);
				}
				//对应的输入文件没有数据,在racer[winner]位置放NO_MEANING
				else
					racer[winner] = NO_MEANING;	
		}

		//重新进行比赛，取得胜者索引
		lt.RePlay(winner, Winner<T>, Loser<T>);
		winner = lt.Winner(); 
		if(!(racer[winner]!=NO_MEANING))
			break;

	}
	 
	//把输出缓冲区中剩余的数据写进磁盘文件
	bufferPool[0].flush(f[0]);

}