btree.h

本人自己的作品

	return re != 0;
}
//找插入点并插入
CBTREE_TEMPLATE
long CBTREE::Insert(BTBNODE& btbnode,long id)
{
	LPBTBLOCK block = GetBlock(id);
	long re = 0;
	BTREENODE node;
	node.data = btbnode.data;
	AIterator iter = block->find_lower(node);
	if(block->reserve() > ZEROLINK)
	{
		long child;
		if(iter.IsNull())
			child = block->reserve();
		else if(*iter == btbnode)
		{
			//iter->data = btbnode.data;
			return 0;//中间就找到
		}
		else
		{
			child = iter->link;
		}
		re = Insert(btbnode,child);//向下找插入点
		if(re < 0)//下级已分裂
		{
			re = InsertBlock(btbnode,id);
		}
	}
	else//找到插入点
	{
		if(!iter.IsNull() && *iter == btbnode)
		{
			//iter->data = btbnode.data;
			re = 0;//中间就找到
		}
		else
		{
			re = InsertBlock(btbnode,id);
		}
		
	}
	return re;
}
//插入块中
CBTREE_TEMPLATE
long CBTREE::InsertBlock(BTBNODE& btbnode,long id)
{
	LPBTBLOCK block = GetBlock(id);
	if(block->size() < block->maxsize())
	{
		InsertNode(btbnode,id);
		return 1;
	}
	else
	{
		long fenid = NewBlock();
		LPBTBLOCK block2 = GetBlock(fenid);
		BTREENODE dou = block->split(*block2);
		if(btbnode.data < dou.data)
		{
			InsertNode(btbnode,fenid);
			SaveBlock(id);
		}
		else
		{
			InsertNode(btbnode,id);
			SaveBlock(fenid);
		}
		btbnode.data  = dou.data;
		btbnode.left  = fenid;
		btbnode.right = id;
		return -1;
	}
}
//正常插入
//写入,说明:原插入点的链接其实就是NODE的link[0],所以没有移动之
CBTREE_TEMPLATE
void CBTREE::InsertNode(BTBNODE& btbnode,long id)
{
	LPBTBLOCK block = GetBlock(id);
	BTREENODE node;
	node.data = btbnode.data;
	node.link = btbnode.left;
	block->insert(node);
	SaveBlock(id);
}
//修改已存在数据的非索引的值
CBTREE_TEMPLATE
bool CBTREE::modify(const DATA& data)
{
	long id = m_head;
	LPBTBLOCK block;
	BTREENODE node;
	node.data = data;
	AIterator iter;
	while(id > ZEROLINK)
	{
		block = GetBlock(id);
		iter = block->find_lower(node);
		if(iter.IsNull())
			id = block->reserve();
		else if(*iter == data)
		{
			node.link = iter->link;
			node.data = data;
			block->modify(node);
			SaveBlock(id);
			return true;
		}
		else
		{
			id = iter->link;
		}
	}
	return false;
}
///////////////////////删除////////////////////////

CBTREE_TEMPLATE
long CBTREE::eraserange(const CBTREE::DATA& first,const CBTREE::DATA& last)
{
	std::vector<DATA> era;
	iterator f = find_lower(first);
	iterator l = find_lower(last);
	for(;f != l;f++)
		era.push_back(*f);
	long sz = era.size();
	for(long i = 0;i < sz;i++)
		erase(era[i]);
	return sz;
}
CBTREE_TEMPLATE
long CBTREE::eraserange(CBTREE::DATA* first,long size)
{
	if(!first || !size)
		return 0;
	long sz = 0;
	for(long i = 0;i < size;i++)
		if(erase(first[i]))
			sz++;
	return sz;
}
CBTREE_TEMPLATE
bool CBTREE::modify(const CBTREE::DATA& old,const CBTREE::DATA& now)
{
	DATA old2 = old;
	if(erase(old2))
	{
		if(!insert(now))
			ATLASSERT(0);
		return true;
	}
	return false;
}

CBTREE_TEMPLATE
bool CBTREE::erase(CBTREE::DATA& data)
{
	if(m_size == 0 || m_head == ZEROLINK)
	{
		return false;
	}
	long re = Erase(data,m_head);
	if(re)
	{
		m_size--;
		LPBTBLOCK tmp = GetBlock(m_head);
		if(re < 0 && tmp->size() == 0)
		{
			long key = m_head;
			m_head  = tmp->reserve();
			DeleteBlock(key);
		}
	}
	return re != 0;
}

CBTREE_TEMPLATE
long CBTREE::Erase(CBTREE::DATA& data,long id)
{
	LPBTBLOCK block = GetBlock(id);
	BTREENODE node;
	node.data = data;
	AIterator iter = block->find_lower(node);
	if(block->reserve() > ZEROLINK)
	{
		long re;
		if(iter.IsNull())
			re = Erase(data,block->reserve());
		else if(iter->data == data)
		{ 
			//ATLTRACE("swap\n");
			//寻找替代者--子树的最大者
			data = iter->data;
			long link = iter->link;
			long id2 = link;
			LPBTBLOCK block2;
			while(id2 > ZEROLINK)
			{
				block2 = GetBlock(id2);
				id2 = block2->reserve();
			}
			DATA datanew = block2->last().Data().data;
			block->erase(node);
			node.data = datanew;
			node.link = link;
			block->insert(node);
			SaveBlock(id);
			re = Erase(datanew,link);
		}
		else
		{
			re = Erase(data,iter->link);
		}

		if(re < 0)
		{
			LPBTBLOCK left,right;
			iter = block->find_lower(node);
			long  rightid,leftid;
			if(iter.IsNull())
			{
				rightid = block->reserve();
				right = GetBlock(rightid);
				iter = block->last();
				node = *iter;
				leftid = iter->link;
				left = GetBlock(leftid);
			}
			else
			{
				node = *iter;
				leftid = iter->link;
				left = GetBlock(iter->link);
				iter++;
				if(iter.IsNull())
				{
					rightid = block->reserve();
					right = GetBlock(rightid);
				}
				else
				{
					rightid = iter->link;
					right = GetBlock(rightid);
				}
			}
			if((left->size() + right->size()+1) < right->maxsize())
			{//合并
				right->marge(*left,node);
				if(!block->erase(node))
					ATLASSERT(0);
				SaveBlock(id);
				SaveBlock(rightid);
				DeleteBlock(leftid);
			}
			else
			{
				BTREENODE node2;
				node2 = left->balance(*right,node);//平衡
				node2.link = node.link;
				
				block->erase(node);
				block->insert(node2);
				SaveBlock(id);
				SaveBlock(leftid);
				SaveBlock(rightid);
				return 1;
			}
		}
		else
			return re;
	}
	else
	{
		if(!iter.IsNull() && iter->data == data)
		{
			data = iter->data;
			block->erase(node);
			SaveBlock(id);
		}
		else
		{
			return 0;
		}
	}
	long mid = block->maxsize() / 2 - 2;
	if(block->size() > mid)
		return 1 ;
	else
		return -1;
}
/////////////////////////迭代/////////////////////////////
CBTREE_TEMPLATE
void CBTREE::iter() const
{
	if(m_head == ZEROLINK)
		return;
	iterator it = begin();
	long sz = 0;
	T* t = NULL;
	while(it)
	{
		if(t)
		{
			ATLASSERT(*t < *it);
		}
		else
		{
			t = new T;
		}
		*t = *it;
		it++;
		sz++;
	}
	ATLASSERT(sz == m_size);
	sz = 0;
	while(it)
	{
		it--;
		sz--;
	}
	if(t)
		delete t;
	ATLASSERT(sz == 0);
}
CBTREE_TEMPLATE
long CBTREE::Iter(long id) const
{
	static long sz;
	static DATA data;
	if(id == m_head)
	{
		data = -1;
		sz = 0;
	}
	ATLASSERT(id != ZEROLINK);
	LPBTBLOCK block = GetBlock(id);
	ATLASSERT(block);
	AIterator iter = block->begin();
	AIterator iterend;
	DATA data2;
	long link;
	for(;iter != iterend;iter++)
	{
		link = iter->link;
		if(link > ZEROLINK)
		{
			iterator(link);
		}
		data2 = iter->data;
		ATLASSERT(data < data2);
		data = iter->data;
		sz++;
	}
	link = block->reserve();
	if(link > ZEROLINK)
		iterator(link);
	return sz;
}//迭代
CBTREE_TEMPLATE
CBTREE::iterator CBTREE::begin() const
{
	iterator iter;
	iter._bof = iter._eof = false;
	iter._nodes.New();
	iter._ptree = this;
	IterNode in;
	LPCBTBLOCK block;
	in.id = m_head;
	while(in.id > ZEROLINK)
	{
		block = ReadBlock(in.id);
		in.reserve = block->reserve();
		in.iter = block->begin();
		if(in.reserve > ZEROLINK)
			in.where = iterator::iw_unuse;
		else
			in.where = iterator::iw_yei;
		iter._nodes->push(in);
		in.id = in.iter->link;
	}
	return iter;
}
CBTREE_TEMPLATE
CBTREE::iterator CBTREE::last() const
{
	iterator iter;
	iter._bof = iter._eof = false;
	iter._nodes.New();
	iter._ptree = this;
	IterNode in;
	LPCBTBLOCK block;
	in.id = m_head;
	while(in.id > ZEROLINK)
	{
		block = ReadBlock(in.id);
		in.reserve = block->reserve();
		if(in.reserve > ZEROLINK)
		{
			in.where = iterator::iw_use;
			in.iter.clear();
		}
		else
		{
			in.where = iterator::iw_yei;
			in.iter = block->last();
		}
		iter._nodes->push(in);
		in.id = in.reserve;
	}
	return iter;
}
CBTREE_TEMPLATE
CBTREE::iterator CBTREE::end() const
{
	return iterator();
}
///////////////////////////////属性//////////////////////////
CBTREE_TEMPLATE
long CBTREE::height() const
{
	long hei = 0;
	long id = m_head;
	LPCBTBLOCK block;
	while(id > ZEROLINK)
	{
		block = ReadBlock(id);
		id = block->reserve();
		hei++;
	}
	return hei;
}
CBTREE_TEMPLATE
long CBTREE::size() const
{
	return m_size;
}
CBTREE_TEMPLATE
long CBTREE::head() const
{
	return m_head;
}
#endif