arrayavltreeiterator.h

本人自己的作品

#pragma once
#pragma warning(disable: 4311 4312)
#include <stack>
#include <vector>
#include <bitset>
#include <stdexcept>
#include "SmartPtr.h"
#include "BlockAVLNode.h"

#ifndef __blocksize
	#define __blocksize 8192
#endif

#ifndef ZEROLINK
	#define ZEROLINK -1
#endif
#define BLOCKDATASIZE (8000 / (sizeof(T) + sizeof(CBlockAVLNode<char>) - sizeof(char) + sizeof(long)))

template<class T> class CArrayAVLTree;
///虚拟指针式的内存分配器--使用了区域方式:向前申请,向后释放
template<class T>
class MyArrayAlloc
{
	///存放节点使用情况
	short _alloc[BLOCKDATASIZE];
	///队列头
	short _last;
	///队列尾
	short _first;
public:
	///构造--初始化分配器
	MyArrayAlloc()
	{
		clear();
	}
	///初始化分配器
	void clear()
	{
		_last = BLOCKDATASIZE;
		_first= 0;
		for(int i = 0;i < BLOCKDATASIZE;i++)
			_alloc[i] = i;
	}
	///分配一个
	short alloc()
	{
		short sb = _first++;
		if(_first == BLOCKDATASIZE)
			_first = 0;
		if(full())
		{
			std::string str = "Blook is full!";
			throw std::overflow_error(str);
		}
		return _alloc[sb];
	}
	///释放一个
	void free(short sb)
	{
		if(_last == BLOCKDATASIZE)
			_last = 0;
		_alloc[_last] = sb;
		_last++;
	}
	bool full()
	{
		return _last == _first;
	}
};

//遍历器
template<class T>
class ArrayAVLTreeIterator
{
	friend class CArrayAVLTree<T>;
	typedef CArrayAVLTree<T> _Tree;
protected:
	enum IteratorStatus {avl_none=-1,avl_left,avl_now,avl_right};
	struct IterNode
	{
		short link;
		IteratorStatus where;
		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 CBlockAVLNode<T> CNode;
	typedef std::stack<IterNode> CThisStack;
protected:
	CSmartPtr<CThisStack> _nodes;
	const _Tree* _ptree;
	bool _eof;
	bool _bof;
public:
	ArrayAVLTreeIterator()
		: _ptree(NULL)
		, _eof(true)
		, _bof(true)
	{
	}
	ArrayAVLTreeIterator(const ArrayAVLTreeIterator& iter)
		: _ptree(iter._ptree)
		, _eof(iter._eof)
		, _bof(iter._bof)
		, _nodes(iter._nodes)
	{
		ATLASSERT(!_nodes || _nodes->top().where == avl_now);
	}
	ArrayAVLTreeIterator& operator =(const ArrayAVLTreeIterator& 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 ArrayAVLTreeIterator& iter) const
	{
		return !(operator==(iter));
	}
	bool operator ==(const ArrayAVLTreeIterator& 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;
	}
	ArrayAVLTreeIterator& 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->_node[iternode.link].Right() > ZEROLINK)//有最左叶
				{
					_nodes->push(iternode);
					iternode.link  = _ptree->_node[iternode.link].Right();
					iternode.where = avl_left;
					_nodes->push(iternode);
					while(_ptree->_node[iternode.link].Left() > ZEROLINK)
					{
						iternode.where = avl_left;
						iternode.link = _ptree->_node[iternode.link].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;
	}
	ArrayAVLTreeIterator& operator ++(int i)
	{
		return operator ++();
	}
	//反回来
	ArrayAVLTreeIterator& 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->_node[iternode.link].Left() > ZEROLINK)//有最左叶
				{
					_nodes->push(iternode);
					iternode.where = avl_right;
					iternode.link = _ptree->_node[iternode.link].Left();
					_nodes->push(iternode);
					while(_ptree->_node[iternode.link].Right() > ZEROLINK)
					{
						iternode.where = avl_right;
						iternode.link = _ptree->_node[iternode.link].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;
	}
	ArrayAVLTreeIterator& operator --(int i)
	{
		return operator --();
	}
protected:
	short nowsb() const
	{
		return _nodes->top().link;
	}
public:
	T& Data()
	{
		long l = (long)_ptree;
		_Tree* t = (_Tree*)l;
		return t->_node[_nodes->top().link].GetData();
	}
	const T& operator *() const
	{
		return _ptree->_node[_nodes->top().link].Data();
	}
	const T* operator ->() const
	{
		return &_ptree->_node[_nodes->top().link].Data();
	}
	ArrayAVLTreeIterator& clear()
	{
		_ptree = NULL;
		_eof = true;
		_bof = true;
		_nodes.Destory();
		return *this;
	}
};