cblockavltree.h

本人自己的作品

#pragma once
#include <stack>
#include <vector>
#include <bitset>
#include "BlockAVLNode.h"
#include "SmartPtr.h"

#define CBLOCKAVLTREE_TEMPLATE template<class T> inline
#define CBLOCKAVLTREE_TEMPLATE_HEAD template<class T>
#define CBLOCKAVLTREE CBlockAVLTree<T>
#ifndef ZEROLINK
	#define ZEROLINK -1
#endif



CBLOCKAVLTREE_TEMPLATE_HEAD
class CBlockAVLTree
{
protected:
	typedef BlockAVLIterator<T> iterator;
	typedef BlockAVLIterator<T>::CThisStack CThisStack;
	typedef BlockAVLIterator<T>::CNode CNode;
	typedef BlockAVLIterator<T>::IterNode IterNode;
	typedef BlockAVLIterator<T>::avltreelink avltreelink;
	friend class iterator;
protected:
	long	_size;//大小
	long	_head;//头
	long	_firstunused;
	long	_lastunused;
	long	_maxsize;
	struct BDATA
	{
		long	used;
		CNode	node;
	};
	BDATA* _data;
public:
	CBlockAVLTree(void);
	CBlockAVLTree(const CBlockAVLTree& tree);
	~CBlockAVLTree(void);
	//清除
	void clear();
	//仅存盘使用
	void NewData(){_data = new BDATA[_maxsize];}
	LPVOID Data() {return _data;}
protected://存储分配
	long New();
	void Delete(long sb);
public:
	CBlockAVLTree& operator = (const CBlockAVLTree& tree);
public:
	//查找
	iterator find(T& data) const;
	//查找大等于
	iterator find_lower(const T& data) const;
	//查找大于
	iterator find_upper(const T& data) const;
	//查找小等于
	iterator find_front_lower(const T& data) const;
	//查找小于
	iterator find_front_upper(const T& data) const;
protected:
	//查找近似区域
	iterator fina_all(const T& data) const;
public://插入
	bool insert(const T& data);
	long insertrange(T* first,long size);
	//修改已存在数据的非索引的值
	bool modify(const T& data);
	//替换
	bool modify(const T& old,const T& now);
	//删除
	bool erase(T& data);
	long eraserange(T& first,T& last);
	long eraserange(T* first,long size);
protected:
	// 查找替代者
	long GetDt(CThisStack& node_stack,long node);
protected://平衡（使用旋转）
	void BalanceTree(CThisStack& nodes);
	long LLTurn(long& X);
	long LRTurn(long& X);
	long RRTurn(long& X);
	long RLTurn(long& X);
public:
	//总大小
	long maxsize() const;
	//数据数量
	long size() const;
	//数据大小
	long datasize() const;
	//高度
	long height() const;
	//平衡因子
	long balance() const;
	bool isfull() const;
	//新的一块的大小
	static long blocksize();
public:
	iterator begin() const;
	iterator last() const;
	iterator end() const;
	iterator bof() const;
	void Iterator() const;
};
/////////////////////////////构造与析构///////////////////////////
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::CBlockAVLTree(void)
: _head(ZEROLINK)
, _size(0)
, _data(NULL)
, _firstunused(-1)
, _maxsize(0)
, _lastunused(0)
{
}
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::CBlockAVLTree(const CBLOCKAVLTREE& tree)
: _head(ZEROLINK)
, _size(0)
, _data(NULL)
, _firstunused(-1)
, _maxsize(0)
, _lastunused(0)
{
	operator =(tree);
}

CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE& CBLOCKAVLTREE::operator =(const CBLOCKAVLTREE& tree)
{
	clear();
	iterator iter = tree.begin();
	for(;!iter.IsNull();iter++)
		insert(*iter);
	return *this;
}
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::~CBlockAVLTree(void)
{
	clear();
}
//清零
CBLOCKAVLTREE_TEMPLATE
void CBLOCKAVLTREE::clear()
{
	//清除分配器就行了
	_size = 0;
	_maxsize = 0;
	_head = ZEROLINK;
	_firstunused = ZEROLINK;
	_lastunused  = 0;
	if(_data)
		delete[] _data;
	_data = NULL;
}
/////////////////////////////////////////////////////////////////

////////////////存储分配///////////////////////////
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::New()
{
	if(isfull())//
	{
		long newsize = _maxsize + blocksize();
		BDATA* newdata = new BDATA[newsize];
		memcpy(newdata,_data,sizeof(BDATA) * _maxsize);
		delete[] _data;
		_data    = newdata;
		for(long i = _maxsize;i < newsize;i++)
			_data[i].used = i;
		_firstunused = _maxsize;
		_lastunused  = newsize;
		_maxsize = newsize;
	}
	//使用队列方式
	long reid = _data[_firstunused].used;
	_data[_firstunused].used = ZEROLINK;
	_firstunused++;
	if(_firstunused == _maxsize)
		_firstunused = 0;
	return reid;
}
CBLOCKAVLTREE_TEMPLATE
void CBLOCKAVLTREE::Delete(long sb)
{
	if(sb > _maxsize && sb <= ZEROLINK)
	{
		ATLTRACE("不存在的下标！");
		ATLASSERT(0);//不应该出现
		return;
	}
	//使用队列方式
	if(_lastunused == _maxsize)
		_lastunused = 0;
	ATLASSERT(_data[_lastunused].used == ZEROLINK);
	_data[_lastunused].used = sb;
	_lastunused++;
}
/////////////////////////////////////////////////////////////////
//////////////////////属性/////////////////////

//新的一块的大小
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::blocksize()
{
	return 8192 / sizeof(BDATA);
}
//是否满
CBLOCKAVLTREE_TEMPLATE
bool CBLOCKAVLTREE::isfull() const
{
	return _size == _maxsize;
}
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::datasize() const
{
	return _maxsize * sizeof(BDATA);
}
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::size() const
{
	return _size;
}
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::maxsize() const
{
	return _maxsize;
}
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::height() const
{
	if(_head > ZEROLINK)
		return _data[_head].node.Height();
	else 
		return 0;
}
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::balance() const
{
	if(_head > ZEROLINK)
		return _data[_head].node.balance();
	else 
		return 0;
}
/////////////////////////////////////////////////////////////////
//////////////////查找///////////////////
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::find(T& data) const
{
	iterator iter;
	if(_head == ZEROLINK)
		return iter;
	if(!iter._nodes.New())
		return iter;
	IterNode iternode;
	iter._ptree = this;
	long sb = _head;
	while(sb > ZEROLINK)
	{
		iternode.link = sb;
		if(_data[sb].node == data)
		{
			iternode.where = iterator::avl_now;
			iter._bof = iter._eof = false;
			iter._nodes->push(iternode);
			data = _data[sb].node.Data();
			return iter;
		}
		if(_data[sb].node < data)
		{
			sb = _data[sb].node.Right();
			iternode.where = iterator::avl_right;
		}
		else
		{
			sb = _data[sb].node.Left();
			iternode.where = iterator::avl_left;
		}
		iter._nodes->push(iternode);
	}
	iter.clear();
	return iter;
}
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::fina_all(const T& data) const
{
	iterator iter;
	if(_head == ZEROLINK)
		return iter;
	if(!iter._nodes.New())
		return iter;
	IterNode iternode;
	iter._ptree = this;
	long sb = _head;
	while(sb > ZEROLINK)
	{
		iternode.link = sb;
		if(_data[sb].node == data)
		{
			iternode.where = iterator::avl_now;
			iter._nodes->push(iternode);
			break;
		}
		if(_data[sb].node < data)
		{
			sb = _data[sb].node.Right();
			iternode.where = iterator::avl_right;
		}
		else
		{
			sb = _data[sb].node.Left();
			iternode.where = iterator::avl_left;
		}
		iter._nodes->push(iternode);
	}
	iternode = iter._nodes->top();
	iter._nodes->pop();
	iternode.where = iterator::avl_now;
	iter._nodes->push(iternode);
	iter._bof = iter._eof = false;
	return iter;
}
//查找大于
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::find_upper(const T& data) const
{
	iterator iter = fina_all(data);
	while(!iter.IsNull() && !(data < *iter))
		iter++;
	return iter;
}
//查找大等于
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::find_lower(const T& data) const
{
	iterator iter = fina_all(data);
	while(!iter.IsNull() && *iter < data)
		iter++;
	return iter;
}
//查找小于
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::find_front_upper(const T& data) const
{
	iterator iter = fina_all(data);
	while(!iter.IsNull() && !(*iter < data))
		iter--;
	return iter;
}
//查找小等于
CBLOCKAVLTREE_TEMPLATE
CBLOCKAVLTREE::iterator CBLOCKAVLTREE::find_front_lower(const T& data) const
{
	iterator iter = fina_all(data);
	while(!iter.IsNull() && data < *iter)
		iter--;
	return iter;
}
////////////////////////////////////////////////////////////////
/////////////////////////////插入与删除////////////////
//旋转
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::LLTurn(long& X)
{
	ATLASSERT(_data[X].node.balance() == 2);
	long B = _data[X].node.Left();

	_data[X].node.Left(_data[B].node.Right());
	if(_data[B].node.Right() == ZEROLINK)
		_data[X].node.LeftHei(0);
	else
		_data[X].node.LeftHei(_data[_data[B].node.Right()].node.Height());

	_data[B].node.Right(X);
	_data[B].node.RightHei(_data[X].node.Height());
	X = B;//实际指向我
	ATLASSERT(_data[X].node.balance() < 2);
	return B;
}
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::LRTurn(long& X)
{
	ATLASSERT(_data[X].node.balance() == 2);
	long B = _data[X].node.Left();
	long C = _data[B].node.Right();

	_data[X].node.Left(_data[C].node.Right());
	if(_data[C].node.Right() == ZEROLINK)
		_data[X].node.LeftHei(0);
	else
		_data[X].node.LeftHei(_data[_data[C].node.Right()].node.Height());

	_data[C].node.Right(X);
	_data[C].node.RightHei(_data[X].node.Height());

	_data[B].node.Right(_data[C].node.Left());
	if(_data[C].node.Left() == ZEROLINK)
		_data[B].node.RightHei(0);
	else
		_data[B].node.RightHei(_data[_data[C].node.Left()].node.Height());

	_data[C].node.Left(B);
	_data[C].node.LeftHei(_data[B].node.Height());
	X = C;//实际指向我
	ATLASSERT(_data[X].node.balance() < 2);
	return C;
}
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::RRTurn(long& X)
{
	ATLASSERT(_data[X].node.balance() == -2);
	long B = _data[X].node.Right();

	_data[X].node.Right(_data[B].node.Left());
	_data[X].node.RightHei(_data[B].node.Left() > ZEROLINK ?
		_data[_data[B].node.Left()].node.Height() : 0);

	_data[B].node.Left(X);
	_data[B].node.LeftHei(_data[X].node.Height());
	X = B;//实际指向我
	ATLASSERT(_data[X].node.balance() > -2);
	return B;
}
CBLOCKAVLTREE_TEMPLATE
long CBLOCKAVLTREE::RLTurn(long& X)
{
	long sb;//其实不怕，不会变了
	ATLASSERT(_data[X].node.balance() == -2);
	long B = _data[X].node.Right();
	long C = _data[B].node.Left();

	sb = _data[C].node.Left();
	_data[X].node.Right(sb);
	_data[X].node.RightHei(_data[C].node.Left() > ZEROLINK ? _data[sb].node.Height() : 0);