buffer.cpp

有计算机图形学、图像处理、dbms、sniffer、中游俄罗斯外挂、othello、遗传算法、舌苔分析等程序。

// Buffer.cpp: implementation of the CBuffer class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Database.h"
#include "Buffer.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CBuffer::CBuffer()
{
    count=0;
	increase=0;
	length=0;
	data=NULL;
}

CBuffer::~CBuffer()
{
    delete []data;
}

CBuffer::CBuffer(UINT len, UINT incr):length(len),increase(incr)
{
    count=0;
	data=new PDB[len+1];
	memset(data,0,(length+1)*sizeof(PDB));
}

BOOL CBuffer::Append(PDB dbptr)
{
	PDB *newbase=NULL;
    if(count>=length)// 已容纳指针数>= 可容纳指针数(已满)
	{
		if(increase>0)
		{
			newbase=(PDB *)realloc(data,(length+increase+1)*sizeof(PDB));
			if(!newbase)
				return FALSE;//内存不足
			data=newbase;
			length+=increase;
		}
		else
			return FALSE;
	}
	data[++count]=dbptr;
    return TRUE;
}

void CBuffer::HeapAdjust(UINT s, UINT m)
{
    PDB rc=data[s];
	UINT j;
	for( j=2*s ; j<=m ; j*=2)
	{
		if(j<m && data[j]<data[j+1])//j为记录小者的下标
			++j;
        if(rc >= data[j])
			break;
		data[s]=data[j];
		s=j;
	}
	data[s]=rc;
}

void CBuffer::HeapSort()
{
	UINT i;
	PDB temp=0;//用于交换
    for(i=count/2; i>0; --i)
		HeapAdjust(i,count);
	for(i=count; i>1; --i)
	{
		temp=data[1];
		data[1]=data[i];
		data[i]=temp;

		HeapAdjust(1,i-1);
	}
}

CBuffer &CBuffer::operator =(const CBuffer &buffer)
{
    count=buffer.count;
	increase=buffer.increase;
	length=buffer.length;

	delete []data;
	data=new PDB[length+1];
	memcpy(data,buffer.data,(length+1)*sizeof(PDB));

	return *this;
}

PDB CBuffer::operator [](UINT index) const
{
    ASSERT(index>=1 && index<=count);
	return data[index];
}

//交
CBuffer *CBuffer::operator *(const CBuffer &buf)
{
	UINT i1=1,i2=1;
	CBuffer *Retbuf=new CBuffer(200,100);
 
	
	CBuffer buf1;
	CBuffer buf2;
	unsigned int lar=0,sml=0;
	if(count>buf.count)
	{
		lar=count;
		sml=buf.count;
	}
	else
	{
		lar=buf.count;
		sml=count;
	}
	double cost=1+double(lar)/double(sml)-log2( (double)lar );

	if(cost>0)//用折半查找
	{
        buf1=(count > buf.count) ? buf : *this;
		buf2=(count > buf.count) ? *this: buf;
		UINT low=0,high=buf2.count,mid=0;
		UINT i;
		for(i=1;i<=buf1.count;i++)
		{
			low=1;
			high=buf2.count;

			while(low<=high)
			{
				mid=(low+high)/2;
				if(buf1[i]==buf2[mid])
				{
					if(! (Retbuf->Append(buf1[i])) )
					{
						delete Retbuf;
						return NULL;
					}
					else
						break;
				}
				else if(buf1[i]<buf2[mid])
					high=mid-1;
				else
					low=mid+1;
			}
		}
	}
	else//归并
	{
		while(i1<=count&&i2<=buf.count)
		{
			if(data[i1] < buf[i2])
			{
				i1++;
			}
			else if(data[i1] > buf[i2])
			{
				i2++;
			}
			else//==
			{
				if(! (Retbuf->Append(data[i1])) )
				{
					delete Retbuf;
					return NULL;
				}
				i1++;
				i2++;
			}
		}
	}

	return Retbuf;    
}
//并
CBuffer *CBuffer::operator +(const CBuffer &buf)
{
	UINT i1=1,i2=1;
	CBuffer *Retbuf=new CBuffer(200,100);
	
	while(i1<=count&&i2<=buf.count)
	{
		if(data[i1] < buf[i2])
		{
			if( !(Retbuf->Append(data[i1])) )
			{
				delete Retbuf; 
				return NULL;
			}
			i1++;
		}
		else if(data[i1] > buf[i2])
		{
			if(! (Retbuf->Append(buf[i2])) )
			{
				delete Retbuf;
				return NULL;
			}
			i2++;
		}
		else//==
		{
			if(! (Retbuf->Append(data[i1])) )
			{
				delete Retbuf;
				return NULL;
			}
			i1++;
			i2++;
		}
	}
	while(i1<=count)
	{
		if(! (Retbuf->Append(data[i1])) )
		{
			delete Retbuf;
			return NULL;
		}
		i1++;
	}
	while(i2<=buf.count)
	{
		if(! (Retbuf->Append(buf[i2])) )
		{
			delete Retbuf;
			return NULL;
		}
		i2++;
	}

	return Retbuf;
}
//差
CBuffer *CBuffer::operator -(const CBuffer &buf)
{
	UINT i1=1,i2=1;
    CBuffer *Retbuf=new CBuffer(200,100);
	while(i1<=count&&i2<=buf.count)
	{
		if(data[i1]<buf[i2])
        {
			if(! (Retbuf->Append(data[i1])) )
			{
				delete Retbuf;
				return NULL;
			}
			i1++;
		}
		else if(data[i1]>buf[i2])
		{
			i2++;
		}
		else//==
		{
			i1++;
			i2++;
		}
	}
	while(i1<=count)
	{
		if(! (Retbuf->Append(data[i1])) )
		{
			delete Retbuf;
			return NULL;
		}
		i1++;
	}

	return Retbuf;
}

double CBuffer::log2(double x)
{
    return ( (log(x))/(log(2.0)) );
}

BOOL CBuffer::Contain(PDB recptr)
{
    UINT low=1,high=count,mid=0;
	
	while(low<=high)
	{
		mid=(low+high)/2;
		if(data[mid]==recptr)
		{
			return TRUE;
		}
		else if(data[mid]>recptr)
			high=mid-1;
		else
			low=mid+1;
	}
	return FALSE;
}