btreeiterator.h

本人自己的作品

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


//新建的构造与析构
typedef void (*NewFunc)(LPVOID mem);

struct BTreeFileBase
{
	//只读读取
	virtual LPVOID ReadBlock(DWORD id) = 0;
	//保存的块
	virtual void SaveBlock(DWORD id) = 0;
	//读取用于事务
	virtual LPVOID GetBlock(DWORD id) = 0;
	//空间分配
	virtual DWORD NewBlock(NewFunc func = NULL) = 0;
	//空间释放
	virtual void DeleteBlock(DWORD id) = 0;
};

template<typename T>
struct BTreeNode
{
	T data;
	long link;

	bool operator < (const BTreeNode<T>& node) const
	{
		return data < node.data;
	}
	bool operator <= (const BTreeNode<T>& node) const
	{
		return !(node.data < data);
	}
	bool operator > (const BTreeNode<T>& node) const
	{
		return node.data < data;
	}
	bool operator >= (const BTreeNode<T>& node) const
	{
		return !(data < node.data);
	}
	bool operator != (const BTreeNode<T>& node) const
	{
		return data < node.data || node.data < data;
	}
	bool operator == (const BTreeNode<T>& node) const
	{
		return !(data < node.data) && !(node.data < data);
	}

	bool operator < (const T& t) const
	{
		return data < t;
	}
	bool operator <= (const T& t) const
	{
		return !(t < data);
	}
	bool operator > (const T& t) const
	{
		return t < data;
	}
	bool operator >= (const T& t) const
	{
		return !(data < t);
	}
	bool operator != (const T& t) const
	{
		return data < t || t < data;
	}
	bool operator == (const T& t) const
	{
		return !(data < t) && !(t < data);
	}
	BTreeNode()
		: link(-1)
	{
	}
};
template<typename T>
struct BTBNode
{
	long left;
	T data;
	long right;
	operator BTreeNode<T>()
	{
		BTreeNode<T> a;
		a.data = data;
		a.link = left;
		return a;
	}
};

template<typename T> class CBTree;

template<typename T>
class BTreeIterator
{
	typedef CBTree<T> _Tree;
	friend class _Tree;
public:
#ifdef CAVLTREE_TEST
	typedef T BTREENODE;
	typedef CArrayAVLTree BTBLOCK;
	typedef CArrayAVLTree::BTreeIterator iterator;
	typedef CArrayAVLTree* LPBTBLOCK;
	typedef long DATA;
#else
	typedef BTreeNode<T> BTREENODE;
	typedef BTBNode<T>   BTBNODE;
	typedef CArrayAVLTree<BTREENODE> BTBLOCK;
	typedef CArrayAVLTree<BTREENODE>::iterator iterator;
	typedef CArrayAVLTree<BTREENODE>* LPBTBLOCK;
	typedef const CArrayAVLTree<BTREENODE>* LPCBTBLOCK;
	typedef T DATA;
#endif
	enum IterWhere {iw_yei ,iw_unuse,iw_use,iw_last};
protected:
	struct IterNode
	{
		iterator iter;
		long reserve;
		long id;
		IterWhere where;//-1叶，0未使用根，1已使用根，2最后
		bool operator == (const IterNode& node)const 
		{
			return id == node.id && where == node.where && iter == node.iter;
		}
		IterNode()
			: id(ZEROLINK),reserve(ZEROLINK) , where(iw_yei)
		{}
		IterNode(const IterNode& node)
			: id(node.id),reserve(node.reserve)
			, where(node.where) , iter(node.iter)
		{}
	};
	typedef std::stack<IterNode> ThisStack;
protected:
	CSmartPtr<ThisStack> _nodes;
	const _Tree*   _ptree;
	bool _eof;
	bool _bof;
public:
	void IKnowCallData(){_can_call_data = true;}
private:
	//能不能调用Data这个函数==以防止出错
	bool _can_call_data;
public:
	BTreeIterator()
		: _ptree(NULL)
		, _eof(true)
		, _bof(true)
		, _can_call_data(false)
	{
	}
	BTreeIterator(const BTreeIterator& iter)
		: _ptree(iter._ptree)
		, _eof(iter._eof)
		, _bof(iter._bof)
		, _nodes(iter._nodes)
		, _can_call_data(false)
	{
	}

	BTreeIterator& operator =(const BTreeIterator& iter)
	{
		_nodes = iter._nodes;
		_ptree = iter._ptree;
		_eof = iter._eof;
		_bof = iter._bof;
		return *this;
	}
	bool operator ==(const BTreeIterator& 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;
		ATLASSERT(_nodes->top().where == iw_use || _nodes->top().where == iw_yei);
		ATLASSERT(iter._nodes->top().where == iw_use || iter._nodes->top().where == iw_yei);
		if(_nodes->top() == iter._nodes->top())
			return true;
		return false;
	}
	bool bof() const
	{
		return _bof;
	}
	bool eof() const
	{
		return _eof;
	}
	bool operator !=(const BTreeIterator& iter) const
	{
		return !(operator==(iter));
	}
	bool IsNull() const
	{
		return !_nodes || !_ptree || _nodes->empty();
	}
	operator bool() const
	{
		return !IsNull();
	}
	BTreeIterator& operator ++()
	{
		//栈为空？
		if(IsNull())
		{
			if(_ptree && _bof && !_eof)
			{
				operator=(_ptree->begin());
			}
			else
			{
				ATLASSERT(0);
				ATLASSERT("已迭代到最后，无法前进！\n");
			}
			return *this;
		}
		IterNode stk;
		stk = _nodes->top();
		//为叶
		if(stk.where == iw_yei)
		{
			_nodes->pop();
			stk.iter++;
			if(!stk.iter.IsNull())
			{
				_nodes->push(stk);
				return *this;//不空,退出
			}
			//叶看完,变为根
		}
		LPCBTBLOCK block;
		long link;
		//为根
		while(_nodes->size())
		{
			stk = _nodes->top();
			_nodes->pop();
			if(stk.where == iw_unuse)//还未使用
			{
				ATLASSERT(!stk.iter.IsNull());
				stk.where = iw_use;
				_nodes->push(stk);
				break;//使用
			}
			else if(stk.where == iw_use)
			{
				stk.iter++;
				if(stk.iter.IsNull())
				{
					stk.where = iw_last;//最后
					stk.iter.clear();
					link = stk.reserve;
				}
				else
				{
					stk.where = iw_unuse;//又一个
					link = stk.iter->link;
				}
				_nodes->push(stk);
				stk.id = link;
				while(stk.reserve > ZEROLINK)
				{
					block = (LPBTBLOCK)_ptree->ReadBlock(stk.id);
					stk.iter = block->begin();
					stk.reserve = block->reserve();
					if(stk.reserve > ZEROLINK)
						stk.where = iw_unuse;
					else
						stk.where = iw_yei;
					_nodes->push(stk);
					stk.id = stk.iter->link;
				}
				break;
			}//全部用过
		}
		if(_nodes->empty())
		{
			_nodes.Destory();
			_eof  = true;
			_bof = false;
		}
		return *this;
	}
	BTreeIterator& operator ++(int i)
	{
		return operator ++();
	}
	//反回来
	BTreeIterator& operator --()
	{
		//栈为空？
		if(IsNull())
		{
			if(_ptree && !_bof && _eof)
			{
				operator=(_ptree->last());
				_eof  = false;
				_bof = false;
			}
			else
			{
				ATLASSERT(0);
				ATLASSERT("已迭代到最前，无法后退！\n");
			}
			return *this;
		}
		IterNode stk;
		stk = _nodes->top();
		//为叶
		if(stk.where == iw_yei)
		{
			_nodes->pop();
			stk.iter--;
			if(!stk.iter.IsNull())
			{
				_nodes->push(stk);
				return *this;//不空,退出
			}
			//叶看完,变为根
		}
		LPCBTBLOCK block;
		//为根
		while(_nodes->size())
		{
			stk = _nodes->top();
			_nodes->pop();
			if(stk.where > 1)//尾
			{
				ATLASSERT(stk.iter.IsNull());
				block = (LPBTBLOCK)_ptree->ReadBlock(stk.id);
				stk.iter = block->last();
				stk.where = iw_use;
				_nodes->push(stk);
				break;//使用
			}
			else if(stk.where == iw_use)//使用过
			{
				stk.where = iw_unuse;
				_nodes->push(stk);
				stk.id = stk.iter->link;
				while(stk.id > ZEROLINK)
				{
					block = (LPBTBLOCK)_ptree->ReadBlock(stk.id);

					stk.reserve = block->reserve();
					if(stk.reserve > ZEROLINK)
					{
						stk.where = iw_use;
						stk.iter.clear();
					}
					else
					{
						stk.where = iw_yei;
						stk.iter = block->last();
					}
					_nodes->push(stk);
					stk.id = stk.reserve;
				}
				break;
			}
			else//全部用过
			{
				stk.iter--;
				if(!stk.iter.IsNull())//还未使用
				{
					stk.where = iw_use;
					_nodes->push(stk);
					break;//使用
				}
			}
		}
		if(_nodes->empty())
		{
			_nodes.Destory();
			_eof = false;
			_bof = true;
		}
		return *this;
	}
	BTreeIterator& operator --(int i)
	{
		return operator --();
	}
	const DATA& operator *() const
	{
		return _nodes->top().iter->data;
	}
	T& Data(DWORD& saveid)//给修改非键数据一个快速方式,数据保存由外部控制
	{
		if(!_can_call_data)
			throw exception("这样调用必须明白你在做什么");
		saveid = _nodes->top().id;
		return _nodes->top().iter.Data().data;
	}
	const DATA* operator ->() const
	{
		return &_nodes->top().iter.Data().data;
	}
	BTreeIterator& clear()
	{
		_ptree = NULL;
		_eof = true;
		_bof = true;
		_nodes.Destory();
		return *this;
	}
};