btree.h

本人自己的作品

/***************************************
作者：胡天水
电邮：[e-mail]
时间：2004年11-12月间
功能：B-树的C++模板类(块的查找使用的是AVL树)
版权：如果你是通过本人得到的这个类，你可以任
	意使用，但对类内部的更改必须给本人一个COPY
使用说明：
	一、T应为固定大小的结构或类，变长类(如string)
	是无法处理的，SORRY！当然解决的办法还是有的
	二、如果你要使用键值对的map请做好你的结构。
	如：
	struct A
	{
		long	key;
		B	    value;
	};
	重载 >、 >= 、== 、!= 、<、 <=这六个操作
	符，以便内部对key进行比较(如未提供，无法通过
	编译。
	三、内部可能还有错误(模板是好用,不过很难控制),
	并且做这种数据结构，我的知识明显不够用(学习不
	认真？！——在中专读书，谁的数学会好呢？？？)

文件操作类的规范说明：
	应提供可按Number操作文件和内存块的类.
	一、内存由你分配且应该使用固定内存块(不用delete
	的那种,要不很难应付内存泄漏),建议使用HeapCreate
	建一个堆,使用堆内存),当然你考虑是不是要注释VC的
	#ifdef _DEBUG
	#define new DEBUG_NEW
	#endif
	因为内存分配可能不要VC来处理(内存泄漏也只有自
	己负责了)
	二、应对文件进行事务处理,以便出错时回滚(内部没
	有使用,但建议你提供,否则操作出错,是无法挽回的).
	三、每块定为8092字节
	四、每块的Number应该保存在文件中，以备下次使用
	五、应保存树的首块Number，以备保存文件后还能构造正
	确的B树
	六、内部会调用的函数具体如下:
	1.
	long NewBlock(NewFunc func);
	分配新块调用所提供的new构造器,以构造正确的块
	注:NewFunc的格式为void (*NewFunc)(LPVOID mem)
	2.
	LPVOID GetBlock(long id);
	返回这个Number的数据的内存
	3.
	LPVOID ReadBlock(long id)
	返回这个Number的数据的内存(应该是读取后写入内存的)
	注:这两个函数是不一样的,前者不用读取,后者要读取!
	当然,B树内部可以保存你这个id我已让你分配了内存
	--一般用在新建一个块又未写入文件的情况
	4.
	void DeleteBlock(long id)
	删除文件块
	5.
	void SaveBlock(long id)
	将对这个Number的块的更改写入文件
*****************************************/
#ifndef _HUTIAN_BTREE_CALSS
#define _HUTIAN_BTREE_CALSS
#pragma once
#ifdef WIN32
	#ifndef __ATLBASE_H__
		#include <atlbase.h>
	#endif
#endif
#include "BTreeIterator.h"
struct BTreeBase
{
	BTreeFileBase* m_pFile;
	long m_size;
	long m_head;
	BTreeBase(BTreeFileBase* pFile = NULL,long size = 0,long head = ZEROLINK)
		: m_size(size)
		, m_head(head)
		, m_pFile(pFile){}
#ifdef WIN32
	virtual void Save(IStream* stream)
	{
		ULONG ul;
		stream->Write(&m_size,sizeof(long),&ul);
		stream->Write(&m_head,sizeof(long),&ul);
	}
	virtual void Load(IStream* stream)
	{
		ULONG ul;
		stream->Read(&m_size,sizeof(long),&ul);
		stream->Read(&m_head,sizeof(long),&ul);
	}
#endif
	void Load(BTreeFileBase* pFile,long size,long head)
	{
		m_pFile= pFile;
		m_size = size;
		m_head = head;
	}
	void SetFile(BTreeFileBase* pFile)
	{
		m_pFile= pFile;
	}
};

#define CBTREE_TEMPLATE template<typename T> inline
#define CBTREE_TEMPLATE_HEAD template<typename T>
#define CBTREE CBTree<T>
 
CBTREE_TEMPLATE_HEAD
class CBTree : public BTreeBase
{
public:
	typedef BTreeIterator<T> iterator;
	typedef BTreeIterator<T>::BTREENODE BTREENODE;
	typedef BTreeIterator<T>::BTBNODE BTBNODE;
	typedef BTreeIterator<T>::BTBLOCK BTBLOCK;
	typedef BTreeIterator<T>::iterator AIterator;
	typedef BTreeIterator<T>::LPBTBLOCK LPBTBLOCK;
	typedef BTreeIterator<T>::LPCBTBLOCK LPCBTBLOCK;
	typedef BTreeIterator<T>::IterNode IterNode;
	typedef BTreeIterator<T>::ThisStack ThisStack;
	typedef BTreeIterator<T>::DATA DATA;
	friend class iterator;
public:
	//一般构造与恢复构造
	CBTree(BTreeFileBase* pFile = NULL,long size = 0,long head = ZEROLINK);
	~CBTree(void);
public://清除
	void clear();
protected://新块
	long NewBlock();
	void DeleteBlock(long id);
	void SaveBlock(long id);
	LPBTBLOCK GetBlock(long id);
	//只读读取
	LPCBTBLOCK ReadBlock(long id) const;
public://插入
	bool insert(const DATA& data);
	//修改已存在数据的非索引的值
	bool modify(const DATA& data);
	long insertrange(DATA* first,long size);
protected:
	long Insert(BTBNODE& node,long id);
	void InsertNode(BTBNODE& node,long id);
	long InsertBlock(BTBNODE& node,long id);
public://删除
	bool erase(DATA& data);
	long eraserange(const DATA& first,const DATA& last);
	long eraserange(DATA* first,long size);
protected:
	long  Erase(DATA& data,long id);
public://修改
	bool modify(const DATA& old,const DATA& now);
public://属性
	long size() const;
	long height() const;
	long head() const;
public://迭代
	iterator begin() const;
	iterator last() const;
	iterator end() const;
	void iter() const;
protected:
	long Iter(long block) const;
public://查找
	iterator find(DATA& data) const;
	//查找大等于
	iterator find_lower(const DATA& data) const;
	//查找大于
	iterator find_upper(const DATA& data) const;
	//查找小等于
	iterator find_front_lower(const DATA& data) const;
	//查找小于
	iterator find_front_upper(const DATA& data) const;
protected:
	//查找近似区域
	iterator fina_all(const DATA& data) const;
};



///////////////构造与析构//////////////////
CBTREE_TEMPLATE
CBTREE::CBTree(BTreeFileBase* pFile,long size,long head)
: BTreeBase(pFile,size,head)
{
}


CBTREE_TEMPLATE
CBTREE::~CBTree(void)
{
	m_size = 0;
	m_head = ZEROLINK;
}
///////////////////////清理///////////////////////////
CBTREE_TEMPLATE
void CBTREE::clear()
{

}

//////////////////////块与文件的操作//////////////////

//建造新块的new函数--用于分配时的回调
CBTREE_TEMPLATE
void NewBlock(LPVOID mem)
{
	new(mem) CBTREE::BTBLOCK;
}
//分配新块
CBTREE_TEMPLATE
long CBTREE::NewBlock()
{
	return m_pFile->NewBlock(::NewBlock<T>);
}
//返回这个Number的数据的内存
CBTREE_TEMPLATE
CBTREE::LPBTBLOCK CBTREE::GetBlock(long id)
{
	return (LPBTBLOCK)m_pFile->GetBlock(id);
}
//取读并返回块内存
CBTREE_TEMPLATE
CBTREE::LPCBTBLOCK CBTREE::ReadBlock(long id) const
{
	return (LPBTBLOCK)m_pFile->ReadBlock(id);
}
//删除一个块(从文件中)
CBTREE_TEMPLATE
void CBTREE::DeleteBlock(long id)
{
	return m_pFile->DeleteBlock(id);
}
//保存块
CBTREE_TEMPLATE
void CBTREE::SaveBlock(long id)
{
	return m_pFile->SaveBlock(id);
}
////////////////////查找//////////////////////
CBTREE_TEMPLATE
CBTREE::iterator CBTREE::find(CBTREE::DATA& data) const
{
	iterator iter;
	if(m_size == 0 || m_head == ZEROLINK)
		return iter;
	iter._nodes.New();
	iter._ptree = this;

	IterNode iternode;
	LPCBTBLOCK block;
	BTREENODE avlnode;

	iternode.id = m_head;
	while(iternode.id > ZEROLINK)
	{
		block = ReadBlock(iternode.id);
		avlnode.data = data;
		iternode.iter = block->find_lower(avlnode);
		iternode.reserve = block->reserve();
		if(iternode.iter.IsNull())
		{
			iternode.id = iternode.reserve;
			iternode.where = iterator::iw_use;
			iternode.iter.clear();
			iter._nodes->push(iternode);
		}
		else if(iternode.iter->data == data)
		{
			if(iternode.reserve > ZEROLINK)
				iternode.where = iterator::iw_unuse;
			else
				iternode.where = iterator::iw_yei;
			iter._nodes->push(iternode);
			data = iternode.iter->data;
			iter._bof = iter._eof = false;
			return iter;
		}
		else
		{
			iternode.id = iternode.iter->link;
			iternode.where = iterator::iw_unuse;
			iter._nodes->push(iternode);
		}
	}
	iter.clear();
	return iter;
}
CBTREE_TEMPLATE
CBTREE::iterator CBTREE::fina_all(const CBTREE::DATA& data) const
{
	iterator iter;
	if(m_size == 0 || m_head == ZEROLINK)
		return iter;
	iter._nodes.New();
	iter._ptree = this;

	IterNode iternode;
	LPCBTBLOCK block;
	BTREENODE avlnode;

	iternode.id = m_head;
	while(iternode.id > ZEROLINK)
	{
		block = ReadBlock(iternode.id);
		avlnode.data = data;
		iternode.iter = block->find_lower(avlnode);
		iternode.reserve = block->reserve();
		if(iternode.iter.IsNull())
		{
			iter._bof = false;
			iternode.id = iternode.reserve;
			iternode.where = iterator::iw_use;
			iternode.iter.clear();
			iter._nodes->push(iternode);
		}
		else if(iternode.iter->data == data)
		{
			iter._bof = iter._eof = false;
			if(iternode.reserve > ZEROLINK)
				iternode.where = iterator::iw_unuse;
			else
				iternode.where = iterator::iw_yei;
			iter._nodes->push(iternode);
			break;
		}
		else
		{
			iter._eof = false;
			iternode.id = iternode.iter->link;
			if(iternode.reserve > ZEROLINK)
				iternode.where = iterator::iw_unuse;
			else
				iternode.where = iterator::iw_yei;
			iter._nodes->push(iternode);
		}
	}
	iternode = iter._nodes->top();
	if(iternode.reserve > ZEROLINK && iternode.where)
	{
		iter._nodes->pop();
		iternode.where = iterator::iw_unuse;
		iter._nodes->push(iternode);
	}
	return iter;
}
//查找大于
CBTREE_TEMPLATE
CBTREE::iterator CBTREE::find_upper(const CBTREE::DATA& data) const
{
	iterator iter = fina_all(data);
	while(!iter.eof() && !iter.IsNull() && !(data < *iter))
		iter++;
	if(iter.eof())
		iter.clear();
	return iter;
}
//查找大等于
CBTREE_TEMPLATE
CBTREE::iterator CBTREE::find_lower(const CBTREE::DATA& data) const
{
	iterator iter = fina_all(data);
	while(!iter.eof() && !iter.IsNull() && *iter < data)
		iter++;
	if(iter.eof())
		iter.clear();
	return iter;
}
//查找小于
CBTREE_TEMPLATE
CBTREE::iterator CBTREE::find_front_upper(const CBTREE::DATA& data) const
{
	iterator iter = fina_all(data);
	while(!iter.bof() && !iter.IsNull() && !(*iter < data))
		iter--;
	if(iter.bof())
		iter.clear();
	return iter;
}
//查找小等于
CBTREE_TEMPLATE
CBTREE::iterator CBTREE::find_front_lower(const CBTREE::DATA& data) const
{
	iterator iter = fina_all(data);
	while(!iter.eof() && !iter.IsNull() && *iter < data)
		iter++;
	if(iter.eof())
		iter.clear();
	return iter;
}
///////////////////插入//////////////////////////
CBTREE_TEMPLATE
long CBTREE::insertrange(CBTREE::DATA* first,long size)
{
	if(!first || !size)
		return 0;
	long sz = 0;
	for(long i = 0;i < size;i++)
		if(insert(first[i]))
			sz++;
	return sz;
}
/***************************************************
说明：向块中插入,可能有的情况:
      1.找到相同节点,不工作,
	  2.找到位置后正常插入(不用变化块)
	  3.找到的块已经放不下了,那么就分为两块后插入
	    此时应向父块报告应增加一个结点(分开时的中间值),放入中间值;
		如又放不下,分开后向上报告,如到回到根,应增加一个根(加了一层)
****************************************************/
CBTREE_TEMPLATE
bool CBTREE::insert(const CBTREE::DATA& data)
{
	if(m_size == 0 || m_head == ZEROLINK)
	{
		m_head = NewBlock();
		LPBTBLOCK block = GetBlock(m_head);
		BTREENODE node;
		block->reserve(ZEROLINK);
		node.data = data;
		node.link = ZEROLINK;
		block->insert(node);
		SaveBlock(m_head);
		m_size = 1;
		return true;
	}
	BTBNODE btbnode;
	btbnode.data = data;
	btbnode.left = btbnode.right = ZEROLINK;
	long re = Insert(btbnode,m_head);
	if(re)
	{
		m_size++;//有插入，要计数
		if(re < 0)//还有溢出节点，说明有新的根了
		{
			m_head = NewBlock();
			LPBTBLOCK block = GetBlock(m_head);
			BTREENODE node;
			block->reserve(btbnode.right);
			node.data = btbnode.data;
			node.link = btbnode.left;
			block->insert(node);
			SaveBlock(m_head);
		}
	}