blockavlnode.h

本人自己的作品

#pragma once
#define CBLOCKAVLNODE_TEMPLATE template<class T,class SB> inline
#define CBLOCKAVLNODE_TEMPLATE_HEAD template<class T,class SB = short>
#define CBLOCKAVLNODE CBlockAVLNode<T,SB>
#ifndef ZEROLINK
#define ZEROLINK -1
#endif
#define CBNSB SB

///块AVL树节点
///说明:这个AVL树应用在B树中，因为B树的块大小是固定的，所以使用的是下标链表的方式
///，可节省空间，所有的原INT的都用short代替，放心，不会溢出的！！！
///注：T在比较大小时，只用了小于作为基础
CBLOCKAVLNODE_TEMPLATE_HEAD class CBlockAVLNode
{
protected:
	///节点数据
	T _data;
	///左子树高度
	SB _left_hei;
	///右子树高度
	SB _right_hei;
	///左子树所在的数组下标
	SB _left;
	///右子树所在的数组下标
	SB _right;
public:
	///构造
	CBlockAVLNode(T data = T());
	///复制构造
	CBlockAVLNode(const CBlockAVLNode& node);
	///析构
	~CBlockAVLNode(void);
	///取得左子树所在的数组下标
	SB Left() const;
	///设置左子树所在的数组下标
	void Left(SB left);
	///取得右子树所在的数组下标
	SB Right() const;
	///设置右子树所在的数组下标
	void Right(SB right);
	///设置左子树高度
	void LeftHei(SB hei);
	///取得左子树高度
	SB& LeftHei();
	///设置右子树高度
	void RightHei(SB hei);
	///取得右子树高度
	SB& RightHei();
	///平衡因子
	long balance() const;
	///树高度
	SB Height() const;
	///取得数据--只读
	const T& Data() const;
	///设置数据
	void Data(const T&  data);
	///得到数据--可更改
	T& GetData();
	///数据复制
	CBLOCKAVLNODE& operator =(const CBlockAVLNode& node);
public:
	///重载!= 与CBlockAVLNode对象比较
	bool operator !=(const CBlockAVLNode& node) const;
	///重载> 与CBlockAVLNode对象比较
	bool operator > (const CBlockAVLNode& node) const;
	///重载>= 与CBlockAVLNode对象比较
	bool operator >=(const CBlockAVLNode& node) const;
	///重载< 与CBlockAVLNode对象比较
	bool operator < (const CBlockAVLNode& node) const;
	///重载<= 与CBlockAVLNode对象比较
	bool operator <=(const CBlockAVLNode& node) const;
	///重载== 与CBlockAVLNode对象比较
	bool operator ==(const CBlockAVLNode& node) const;
	
	///重载!= 与T对象比较
	bool operator !=(const T& data) const;
	///重载> 与T对象比较
	bool operator > (const T& data) const;
	///重载>= 与T对象比较
	bool operator >=(const T& data) const;
	///重载< 与T对象比较
	bool operator < (const T& data) const;
	///重载<= 与T对象比较
	bool operator <=(const T& data) const;
	///重载== 与T对象比较
	bool operator ==(const T& data) const;
};


///构造与析构
CBLOCKAVLNODE_TEMPLATE 
CBLOCKAVLNODE::CBlockAVLNode(T data)
: _data(data)
, _left(-1)
, _right(-1)
, _left_hei(0)
, _right_hei(0)
{
}
CBLOCKAVLNODE_TEMPLATE 
CBLOCKAVLNODE::CBlockAVLNode(const CBLOCKAVLNODE& node)
: _data(node._data)
, _left(node._left)
, _right(node._right)
, _left_hei(node._left_hei)
, _right_hei(node._right_hei)
{
}

CBLOCKAVLNODE_TEMPLATE 
CBLOCKAVLNODE& CBLOCKAVLNODE::operator =(const CBLOCKAVLNODE& node)
{
	_data     = node._data;
	_left     = node._left;
	_right    = node._right;
	_left_hei = node._left_hei;
	_right_hei= node._right_hei;
	return *this;
}
CBLOCKAVLNODE_TEMPLATE 
CBLOCKAVLNODE::~CBlockAVLNode(void)
{
}

///链接
CBLOCKAVLNODE_TEMPLATE 
CBNSB CBLOCKAVLNODE::Left() const
{
	return _left;
}

CBLOCKAVLNODE_TEMPLATE 
void CBLOCKAVLNODE::Left(CBNSB left)
{
	_left = left;
}

CBLOCKAVLNODE_TEMPLATE 
CBNSB CBLOCKAVLNODE::Right() const
{
	return _right;
}

CBLOCKAVLNODE_TEMPLATE 
void CBLOCKAVLNODE::Right(CBNSB right)
{
	_right = right;
}
///高度
CBLOCKAVLNODE_TEMPLATE 
void CBLOCKAVLNODE::LeftHei(CBNSB hei)
{
	_left_hei = hei;
}
CBLOCKAVLNODE_TEMPLATE 
CBNSB& CBLOCKAVLNODE::LeftHei()
{
	return _left_hei;
}
CBLOCKAVLNODE_TEMPLATE 
void CBLOCKAVLNODE::RightHei(CBNSB hei)
{
	_right_hei= hei;
}
CBLOCKAVLNODE_TEMPLATE 
CBNSB& CBLOCKAVLNODE::RightHei()
{
	return _right_hei;
}
///平衡因子
CBLOCKAVLNODE_TEMPLATE 
long CBLOCKAVLNODE::balance() const
{
	return _left_hei - _right_hei;
}
///高度
CBLOCKAVLNODE_TEMPLATE 
CBNSB CBLOCKAVLNODE::Height() const
{
	return _left_hei > _right_hei ?
		_left_hei + 1 : _right_hei + 1;///还有自己的高度
}
///数据
CBLOCKAVLNODE_TEMPLATE 
const T& CBLOCKAVLNODE::Data() const
{
	return _data;
}
///数据
CBLOCKAVLNODE_TEMPLATE 
T& CBLOCKAVLNODE::GetData()
{
	return _data;
}


CBLOCKAVLNODE_TEMPLATE 
void CBLOCKAVLNODE::Data(const T& data)
{
	_data = data;
}

///比较
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator !=(const CBLOCKAVLNODE& node) const
{
	return node._data < _data || _data < node._data;
}
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator >(const CBLOCKAVLNODE& node) const
{
	return node._data < _data;
}
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator >=(const CBLOCKAVLNODE& node) const
{
	return !(_data < node._data);
}
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator <(const CBLOCKAVLNODE& node) const
{
	return _data < node._data;
}

CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator <=(const CBLOCKAVLNODE& node) const
{
	return !(node._data < _data);
}
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator ==(const CBLOCKAVLNODE& node) const
{
	return !(node._data < _data) && !(_data < node._data);
}

///比较
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator !=(const T& data) const
{
	return data < _data || _data < data;
}
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator >(const T& data) const
{
	return data < _data;
}
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator >=(const T& data) const
{
	return !(_data < data);
}
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator <(const T& data) const
{
	return _data < data;
}

CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator <=(const T& data) const
{
	return !(data < _data);
}
CBLOCKAVLNODE_TEMPLATE 
bool CBLOCKAVLNODE::operator ==(const T& data) const
{
	return !(data < _data) && !(_data < data);
}

template<class T> class CBlockAVLTree;

//遍历器
template<class T>
class BlockAVLIterator
{
	friend class CBlockAVLTree<T>;
public:
	//遍历
	enum avltreelink {avl_none=-1,avl_left,avl_now,avl_right};
	struct IterNode
	{
		long link;
		avltreelink where;//0左子树，1当前，2左子树
		bool operator ==(const IterNode& node) const
		{
			return link == node.link && where == node.where;
		}
		IterNode(): link(ZEROLINK) , where(avl_none){}
		IterNode(const IterNode& node)
			: link(node.link) , where(node.where){}
	};
	typedef std::stack<IterNode> CThisStack;
	typedef CBlockAVLTree<T> _Tree;
public:
	typedef CBlockAVLNode<T,long> CNode;
protected:
	const _Tree* _ptree;
	bool _eof;
	bool _bof;
	CSmartPtr<CThisStack> _nodes;
public:
	BlockAVLIterator()
		: _ptree(NULL)
		, _eof(true)
		, _bof(true)
	{
	}
	BlockAVLIterator(const BlockAVLIterator& iter)
		: _ptree(iter._ptree)
		, _eof(iter._eof)
		, _bof(iter._bof)
		, _nodes(iter._nodes)
	{
		ATLASSERT(!_nodes || _nodes->top().where == avl_now);
	}
	BlockAVLIterator& operator =(const BlockAVLIterator& iter)
	{
		_nodes = iter._nodes;
		_ptree = iter._ptree;
		_eof = iter._eof;
		_bof = iter._bof;
		ATLASSERT(!_nodes || _nodes->top().where == avl_now);
		return *this;
	}
	bool IsNull() const
	{
		return !_ptree || !_nodes || _nodes->empty();
	}
	operator bool() const
	{
		return !IsNull();
	}
	bool bof()  const
	{
		return _bof;
	}
	bool eof() const
	{
		return _eof;
	}
	bool operator !=(const BlockAVLIterator& iter) const
	{
		return !(operator==(iter));
	}
	bool operator ==(const BlockAVLIterator& iter)const
	{
		if(IsNull() && iter.IsNull())
			return true;
		if(IsNull() || iter.IsNull())
			return false;
		if(_nodes->empty() && iter._nodes->empty())
			return true;
		if(_nodes->empty() || iter._nodes->empty())
			return false;
		if(_ptree != iter._ptree)
			return false;
		if(_ptree == iter._ptree && _bof == iter._bof && _eof == iter._eof)
			return true;
		ATLASSERT(!_nodes || _nodes->top().where == avl_now);
		ATLASSERT(!iter._nodes || iter._nodes->top().where == avl_now);
		if(_nodes->top() == iter._nodes->top())
			return true;
		return false;
	}
	BlockAVLIterator& operator ++()
	{
		//栈为空？
		if(IsNull())
		{
			if(_ptree && _bof && !_eof)
			{
				operator=(_ptree->begin());
			}
			else
			{
				//ATLTRACE("已迭代到最后，无法前进！\n");
				ATLASSERT(0);
			}
			return *this;
		}
		IterNode iternode;
		while(!_nodes->empty())
		{
			iternode = _nodes->top();
			if(iternode.where == avl_left)//还没到过，正好使用
			{
				break;
			}
			_nodes->pop();
			if(iternode.where == avl_now)//用过，应到右子树的最左叶
			{
				iternode.where = avl_right;
				if(_ptree->_data[iternode.link].node.Right() > ZEROLINK)//有最左叶
				{
					_nodes->push(iternode);
					iternode.link  = _ptree->_data[iternode.link].node.Right();
					iternode.where = avl_left;
					_nodes->push(iternode);
					while(_ptree->_data[iternode.link].node.Left() > ZEROLINK)
					{
						iternode.where = avl_left;
						iternode.link = _ptree->_data[iternode.link].node.Left();
						_nodes->push(iternode);
					}
					break;
				}
			}//没有，等于看过右子树
		}
		if(!_nodes->empty())
		{//还有东西
			iternode = _nodes->top();
			_nodes->pop();
			iternode.where = avl_now;
			_nodes->push(iternode);
		}
		else
		{
			_nodes.Destory();
			_eof = true;
			_bof = false;
		}
		return *this;
	}
	BlockAVLIterator& operator ++(int i)
	{
		return operator ++();
	}
	//反回来
	BlockAVLIterator& operator --()
	{
		if(IsNull())
		{
			if(_ptree && !_bof && _eof)
			{
				operator=(_ptree->last());
			}
			else
			{
				ATLASSERT(0);
				//ATLTRACE("已迭代到最前，无法后退！\n");
			}
			return *this;
		}
		IterNode iternode;
		while(!_nodes->empty())
		{
			iternode = _nodes->top();
			if(iternode.where == avl_right)//还没到过，正好使用
			{
				break;
			}
			_nodes->pop();
			if(iternode.where == avl_now)//用过，应到左子树的最右叶
			{
				iternode.where = avl_left;
				if(_ptree->_data[iternode.link].node.Left() > ZEROLINK)//有最左叶
				{
					_nodes->push(iternode);
					iternode.where = avl_right;
					iternode.link = _ptree->_data[iternode.link].node.Left();
					_nodes->push(iternode);
					while(_ptree->_data[iternode.link].node.Right() > ZEROLINK)
					{
						iternode.where = avl_right;
						iternode.link = _ptree->_data[iternode.link].node.Right();
						_nodes->push(iternode);
					}
					break;
				}
			}//没有，等于看过右子树
		}
		if(!_nodes->empty())
		{//还有东西
			iternode = _nodes->top();
			_nodes->pop();
			iternode.where = avl_now;
			_nodes->push(iternode);
		}
		else
		{
			_nodes.Destory();
			_eof = false;
			_bof = true;
		}
		return *this;
	}
	BlockAVLIterator& operator --(int i)
	{
		return operator --();
	}
protected:
	long nowsb() const
	{
		return _nodes->top().link;
	}
public:
	const T& operator *() const
	{
		long sb = _nodes->top().link;
		CNode node = _ptree->_data[sb].node;
		T t = node.Data();
		return _ptree->_data[_nodes->top().link].node.Data();
	}
	const T* operator ->() const
	{
		return &_ptree->_data[_nodes->top().link].node.Data();
	}
	BlockAVLIterator& clear()
	{
		_ptree = NULL;
		_eof = true;
		_bof = true;
		_nodes.Destory();
		return *this;
	}
};