mydrawbplustree.cpp

B+树的演示程序

// MyDrawBPlusTree.cpp : 实现文件
//

#include "stdafx.h"
#include "BPlusTree.h"
#include "MyDrawBPlusTree.h"


// MyDrawBPlusTree

MyDrawBPlusTree::MyDrawBPlusTree()
{
	m_pDC = NULL;
	m_viewRect = CRect(0,0,0,0);
	m_maxRect = CRect(-200,-100,1224,868);
	m_position = CPoint(0,0);
	MyDrawNode::Initialization();
	m_drawKey0 = -1;
	m_firstDrawKey0 = -1;
	m_drawLevel = 1;
	m_firstDrawLevel = 1;
	m_iType = 0;
	m_bDraw = false;
	m_insertPoint = NULL;
	m_bInsert = false;
	m_inserPosition = CPoint(0,0);
	m_iNumber = -1;
}

MyDrawBPlusTree::~MyDrawBPlusTree()
{
}


// MyDrawBPlusTree 成员函数

void MyDrawBPlusTree::SetDC(CDC* pDC)
{
	m_pDC = pDC;
}
void MyDrawBPlusTree::SetBPlusTree(MyBPlusTree* tree)
{
	m_tree = tree;
}
void MyDrawBPlusTree::Create(CDC* pDC,MyBPlusTree* tree)
{
    SetDC(pDC);
	SetBPlusTree(tree);
	MyDrawNode::SetDC(pDC);
	MyDrawNode::SetN(tree->N);
}

void MyDrawBPlusTree::SetMyRect(RECT viewRect/*view client rect*/)
{
	m_viewRect.left = 0;
	m_viewRect.top = 0;
	m_viewRect.right = viewRect.right - viewRect.left;
	m_viewRect.bottom = viewRect.bottom - viewRect.top;

	m_maxRect.left = m_viewRect.left - m_viewRect.Width();
	m_maxRect.top = m_viewRect.top - m_viewRect.Height();
	m_maxRect.right = m_viewRect.right + m_viewRect.Width();
	m_maxRect.bottom = m_viewRect.bottom;
}

void MyDrawBPlusTree::Coordinate(POINT& position)
{
	int x,y;
	int N = m_tree->N;

	x = (position.x - TREE_LEFT - N * KEY_WIDTH/2) % ((N * KEY_WIDTH + DISTANCE)/2);
	y = (position.y - TREE_TOP) % ((KEY_HEIGHT + POINTER_HEIGHT + LEVEL_DISTANCE)/2);
	if(x != 0)
	{
		int n = (position.x - TREE_LEFT - N * KEY_WIDTH/2) / ((N * KEY_WIDTH + DISTANCE)/2);
		if(x < KEY_WIDTH*N/2)
			position.x = TREE_LEFT + KEY_WIDTH*N/2 + n*(KEY_WIDTH*N + DISTANCE)/2;
		else if(x < KEY_WIDTH*N)
			position.x = TREE_LEFT + KEY_WIDTH*N/2 + (n + 1)*(KEY_WIDTH*N + DISTANCE)/2;
	}
	if(y != 0)
	{
		int n = (position.y - TREE_TOP) / ((KEY_HEIGHT + POINTER_HEIGHT + LEVEL_DISTANCE)/2);
		if(y < KEY_HEIGHT + POINTER_HEIGHT)
			position.y = TREE_TOP + n*(KEY_HEIGHT + POINTER_HEIGHT + LEVEL_DISTANCE)/2;
		else
			position.y = TREE_TOP + (n + 1)*(KEY_HEIGHT + POINTER_HEIGHT + LEVEL_DISTANCE)/2;
	}
}

long MyDrawBPlusTree::GetFirstNodeKey0()
{
	int i=0, n=0;
	if(m_drawKey0 <= -1)
		m_firstDrawKey0 = GetMinKey(m_firstDrawLevel);
	else
		m_firstDrawKey0 = m_drawKey0;
	int k = (m_viewRect.Width())/(m_tree->N * KEY_WIDTH + DISTANCE);
	while(n < k-1)
	{
		i = FindRightNB(m_firstDrawLevel+1);
		if(i == -1)	break;
		m_firstDrawKey0 = GetMaxKey(i-1,m_firstDrawLevel);
		n++;
	}
	return m_firstDrawKey0;
}

int MyDrawBPlusTree::FindRightNB(int level)
{
	if(level > m_tree->m_levels)	return -1;

	int i = m_tree->SearchKey(m_tree->m_root,m_firstDrawKey0,level);
	if(i <= 0)
		i = FindRightNB(level+1);
	return i;
}

long MyDrawBPlusTree::GetMaxKey(int i,int level)
{
	MyNode* pnode = (MyNode*)(m_tree->m_current->p[i]);
	while(pnode->m_level > level)
		pnode = (MyNode*)pnode->p[pnode->m_n];
	return pnode->k[0];
}

long MyDrawBPlusTree::GetMinKey(int level)
{
	MyNode* pnode = m_tree->m_root;
	while(pnode->m_level > level)
		pnode = (MyNode*)pnode->p[0];
	return pnode->k[0];
}

int MyDrawBPlusTree::GetNumberOfNode(int level)
{
	int i = m_tree->m_nodes;
	for(int j=0;j<level;j++)
		i /= 2;
	return i;
}

void MyDrawBPlusTree::DrawTree(long key0,int level,int type,void* insertPoint/*=NULL*/,int i/*=-1*/)
{
	if(!m_tree)	return;
	if(!m_tree->m_root)	return;
	
	m_drawKey0 = key0;
	m_drawLevel = level;
	m_iType = type;
	m_bDraw = false;
	m_bInsert = false;
	m_insertPoint = insertPoint;
	m_iNumber = i;
	
	m_firstDrawLevel = (level>4) ? level-4 : 1;
	if(m_tree->m_keys == 0)
		m_firstDrawKey0 = 0;
	else
		m_firstDrawKey0 = GetFirstNodeKey0();
	

	if( (m_firstDrawKey0 == GetMinKey(m_firstDrawLevel)) || (GetNumberOfNode(m_firstDrawLevel)<9) )
		m_position.x = DISTANCE + (KEY_WIDTH * m_tree->N) / 2;
	else
		m_position.x = -2*DISTANCE - (KEY_WIDTH * m_tree->N);
	m_position.y = m_viewRect.bottom - LEVEL_DISTANCE - KEY_HEIGHT - POINTER_HEIGHT - LEAF_KEY_POINT_LONGTH - LEAF_KEY_POINT_RADIUS*2;
	Coordinate(m_position);
	
	DrawSubNode(m_tree->m_root);
}

POINT MyDrawBPlusTree::DrawSubNode(MyNode* pnode)
{
	POINT point;
	// draw lowest level
	if(pnode->m_level <= m_firstDrawLevel)
	{
		point = m_position;
		if( (pnode->k[0] == m_firstDrawKey0) || m_bDraw )
		{
			m_bDraw = true;
			// if(IsPtInMaxRect(m_position))
			if(m_maxRect.PtInRect(m_position))
			{
				if( (pnode->k[0] == m_drawKey0) && (pnode->m_level == m_drawLevel) )
					DrawNode(pnode,m_position,1);
				else
					DrawNode(pnode,m_position,0);
			}
		}
		return point;
	}

	// draw sub node
	int i,min=0;
	MyNode* node;
	POINT* position = new POINT[m_tree->N+1];

	for(i=0;i<pnode->m_n+1;i++)
	{
		node= (MyNode*)((MyNode*)pnode)->p[i];
		BOOL b = m_maxRect.PtInRect(m_position);
		if(m_maxRect.PtInRect(m_position))
		{
			point = DrawSubNode(node);
			if(m_bDraw)
                position[i] = point;
			else
				min++;
		}
		else
		{
			position[pnode->m_n] = m_position;
			break;
		}
		if(m_bDraw)
			if(node->m_level == m_firstDrawLevel)
				m_position.x += DISTANCE + KEY_WIDTH * m_tree->N;
	}
	if(!m_bDraw)
		return m_position;

	// draw pnode
	point.x = position[min].x + (position[pnode->m_n].x - position[min].x) / 2;
	point.y = position[min].y - LEVEL_DISTANCE - POINTER_HEIGHT - KEY_HEIGHT;

	Coordinate(point);
	// if(IsPtInMaxRect(point))
	if(m_maxRect.PtInRect(point))
	{
		if( (pnode->k[0] == m_drawKey0) && (pnode->m_level == m_drawLevel) )
			DrawNode(pnode,point,1);
		else
			DrawNode(pnode,point,0);
	}
	
	// draw arrow
	POINT ptPoint;
	ptPoint = m_drawNode.GetFirstPointFrom();
	int width = m_drawNode.GetPointDistance();
	int distance = pnode->m_level*pnode->m_level*(DISTANCE + (KEY_WIDTH * m_tree->N) / 2);
	for(i=0;i<min;i++)
	{
		m_drawNode.DrawArrow(ptPoint,CPoint(position[min].x - distance*(min-i),position[min].y),2,false);
		ptPoint.x += width;
	}
	for(i=min;i<pnode->m_n+1;i++)
	{
		m_drawNode.DrawArrow(ptPoint,position[i],1,false);
		ptPoint.x += width;
	}
	if(m_bInsert)
	{
		ptPoint.x = point.x;
		ptPoint.y += POINTER_HEIGHT;
        m_drawNode.DrawArrow(m_inserPosition,ptPoint,1,true);
		m_bInsert = false;
	}

	delete[] position;
	return point;
}

void MyDrawBPlusTree::DrawNode(MyNode* pnode,POINT position,int type)
{
	if(type == 0)
	{
		m_drawNode.DrawNode(pnode,position,false);
		return;
	}

	MyNode* tnode = (MyNode*)m_insertPoint;
	POINT pt,pt2,pt3;
	CRect rect;

	switch(m_iType)
	{
	case 1:		// search
		m_drawNode.DrawNode(pnode,position,true);
		break;
	case 10:	// insert long in leaf
		m_drawNode.DrawNode(pnode,position,false);
		m_drawNode.DrawInsertKey(*((long*)m_insertPoint));
		break;
	case 11:	// insert in node
		m_drawNode.DrawNode(pnode,position,false);
		m_bInsert = true;
		m_drawKey0 = tnode->k[0];
		m_iType = 1;
		if(pnode->m_level == m_firstDrawLevel)
			m_position.x += DISTANCE + KEY_WIDTH * m_tree->N;
		m_inserPosition = DrawSubNode(tnode);
		break;
	case 12:	// insert root
		m_drawNode.DrawNode(pnode,position,true);
		m_drawKey0 = m_tree->m_root->k[0];
		m_drawLevel = m_tree->m_root->m_level;
		m_iType = 1;
		break;
	case 13:	// insert splide
		m_drawNode.DrawNode(pnode,position,true);
		// m_bInsert = true;
		m_drawKey0 = tnode->k[0];
		m_iType = 1;
		if(pnode->m_level == m_firstDrawLevel)
			m_position.x += DISTANCE + KEY_WIDTH * m_tree->N;
		m_inserPosition = DrawSubNode(tnode);
		break;
	case 15:	// insert complete
		m_drawNode.DrawNode(pnode,position,false);
		
		// draw point key
		pt.x = m_drawNode.m_rect.left + KEY_WIDTH/2 + KEY_WIDTH*m_iNumber;
		pt.y = m_drawNode.m_rect.bottom;
		pt2.x = pt.x;
		pt2.y = pt.y + LEAF_KEY_POINT_LONGTH;
		rect.top = pt2.y;
		rect.bottom = rect.top + 2*LEAF_KEY_POINT_RADIUS;
		rect.left = pt.x - LEAF_KEY_POINT_RADIUS;
		rect.right = pt.x + LEAF_KEY_POINT_RADIUS;
		pt3.x = pt.x;
		pt3.y = pt2.y + LEAF_KEY_POINT_RADIUS;
		m_drawNode.DrawArrow(pt,pt2,0,true);		
		m_pDC->SelectObject(&MyDrawNode::m_penThinLight);
		m_pDC->Ellipse(&rect);
		m_drawNode.DrawFont(pt3,*(long*)pnode->p[m_iNumber],true);
		m_iType = 0;
		break;
	case 20:		// delete key
		m_drawNode.DrawNode(pnode,position,false);
		if( (m_drawLevel > 1) && (m_iNumber>0) )
				m_iNumber--;
		// delete i at pnode in leaf		
		pt.x = m_drawNode.m_rect.left + KEY_WIDTH*m_iNumber;
		pt.y = m_drawNode.m_rect.top;
		pt2.x = pt.x + KEY_WIDTH;
		pt2.y = pt.y + KEY_WIDTH;
		m_pDC->SelectObject(&MyDrawNode::m_penThickLight);
		m_pDC->MoveTo(pt);
		m_pDC->LineTo(pt2);
		m_iType = 0;
		break;
	case 21:	// delete root
		m_drawNode.DrawNode(pnode,position,false);

		rect = m_drawNode.m_rect;
		m_pDC->SelectObject(&MyDrawNode::m_penThickLight);
		m_pDC->MoveTo(rect.TopLeft());
		m_pDC->LineTo(rect.BottomRight());
		m_iType = 0;
		break;
	default:
		m_drawNode.DrawNode(pnode,position,false);
		break;
	}
}