mynode.cpp

B+树的演示程序

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

#include "stdafx.h"
#include "MyBPlusTree.h"
#include "MyNode.h"


// MyNode
int MyNode::N = MINIMUS_NUMBER_OF_NODE;
int MyNode::M = (MyNode::N + 1)/2;

int MyNode::SetMaxNumber(int n)
{
	if( (n<MINIMUS_NUMBER_OF_NODE) || (n>MAXIMUM_NUMBER_OF_NODE) )
		return -1;
	N = n;
	M = (N+1)/2;
	return 0;
}

MyNode::MyNode()
{	
	m_n = 0;
	m_level = 2;
	// k = NULL;
	// p = NULL;
	for(int i=0;i<N;i++)
	{
		k[i] = 0;
		p[i] = NULL;
	}
	p[N] = NULL;
}

MyNode::~MyNode()
{
}
bool MyNode::Create()
{
	/*
	k = new long[N];
	if(!k)	return false;
	p = new void*[N+1];
	if(!p)	return false;
	for(int i=0;i<N;i++)
	{
		k[i] = 0;
		p[i] = NULL;
	}
	p[N] = NULL;
	*/
	return true;
}
bool MyNode::Release()
{
	/*
	for(int i=0;i<N;i++)
	{
		k[i] = 0;
		p[i] = NULL;
	}
	p[N] = NULL;
	if(k)
	{	delete k;	k = NULL;	}
	if(p)
	{	delete p;	p = NULL;	}
	*/
	return true;
}

// MyNode 成员函数
bool MyNode::CreateRoot(long key,MyNode* node1,MyNode* node2)
{
	if(!Create())
		return false;
    m_n = 1;
	m_level = node1->m_level+1;

	k[0] = key;
	p[0] = (void*)node1;
	p[1] = (void*)node2;
	return true;
}

// Search fuction, Node / Leaf 's search.
// return the position of the key(0 - N)
int MyNode::Search(long key)
{
	return -1;
}

// Insert fuction,
int MyNode::Insert(long key,void* pkey,int i)
{
	return -1;
}
int MyNode::SplitNode(MyNode* newNode,int m/*type*/)	// only use when level = 1
{
	return -1;
}

// Delete fuction
int MyNode::Delete(int i)
{
	return -1;
}
long MyNode::GetMinKey(int i/*=0*/)
{
	if( (i < 0)	|| (i > m_n) )	return -1;

	if(m_level == 1)
		return k[0];

	MyNode* temp;
	temp = (MyNode*)p[i];
	while(temp->m_level > 1)
		temp = (MyNode*)temp->p[0];
	return temp->k[0];
}
long MyNode::GetKeyFromLeft(MyNode* left)
{
	return -1;
}
long MyNode::GetKeyFromRight(MyNode* right)
{
	return -1;
}
long MyNode::UniteRight(MyNode* right)
{
	return -1;
}


// MyBranch

MyBranch::MyBranch()
{
	m_level = 2;
}

MyBranch::MyBranch(int level)
{
	m_level = level;
}

MyBranch::~MyBranch()
{
}

// MyBranch 成员函数

// Search fuction, Node / Leaf 's search.
// return the position of the key(0 - N)
int MyBranch::Search(long key)
{
	if(m_level <= 1)
		return -1;

	int i;
	for(i=0;i<m_n;i++)
		if(key < k[i])
			break;
	return i;
}

// Insert fuction,
int MyBranch::Insert(long key,void* pkey,int i)
{
	if(m_level <= 1)
		return -1;

	if( (i < 0)	|| (i > m_n+1) )	return -1;
	if(m_n >= N)	return -1;

	int m = 1;
	// notice here, / insert 0 or \ insert 0
	if( (i == 0) && (key < ((MyNode*)p[0])->k[0]) )
	{
		// insert a node at first position of branch / insert
		p[m_n+1] = p[m_n];
		m = 0;
	}
	else
		i++;

	for(int j=m_n;j>=i;j--)
	{
		k[j-m+1] = k[j-m];
		p[j+1] = p[j];
	}
	k[i-m] = key;
	p[i] = pkey;
	m_n++;
	return i;
}
int MyBranch::SplitNode(MyNode* newNode,int m/*type*/)	// only use when level = 1
{
	if(m_n < N) return -1;
	if(m_level <= 1)	return -1;

	k[M-1] = 0;
	m_n--;
	for(int j=0;j<N-M;j++)
	{
		newNode->k[j] = k[j+M];
		k[j+M] = 0;
		newNode->p[j] = p[j+M];
		p[j+M] = NULL;
		newNode->m_n++;
		m_n--;
	}
	newNode->p[N-M] = p[N];
	p[N] = NULL;

	return j;
}

// Delete fuction
int MyBranch::Delete(int i)
{
	if(m_level == 1)
		return -1;	
	
	if( (i < 0)	|| (i > m_n) )	return -1;

	int m;
	m = (i == 0) ? 0 : 1;

	for(int j=i;j<m_n;j++)
	{
		k[j-m] = k[j-m+1];
		p[j] = p[j+1];
	}
	if(i == 0)
		p[m_n-1] = p[m_n];
	p[j] = NULL;
	k[j-m] = 0;
	m_n--;
	return i;
}

long MyBranch::GetKeyFromLeft(MyNode* left)
{
	if(m_level == 1)
		return -1;

	long key;
	key = GetMinKey();
	
	p[m_n+1] = p[m_n];
	for(int j=m_n;j>0;j--)
	{
		k[j] = k[j-1];
		p[j] = p[j-1];
	}
	k[0] = key;
	p[0] = left->p[left->m_n];
	m_n++;

	// Insert(key,leftNode->p[leftNode->my_num],0);
	left->Delete(left->m_n);

	return key;
}
long MyBranch::GetKeyFromRight(MyNode* right)
{
	if(m_level == 1)
		return -1;

	long key;
	key = right->GetMinKey();

	// Insert(key,rightNode->p[0],my_num);
	k[m_n] = key;
	p[m_n+1] = right->p[0];
	m_n++;
	right->Delete(0);

	return key;
}

long MyBranch::UniteRight(MyNode* right)
{
	if(m_level == 1)
		return -1;

	int num = m_n;
	long key = right->GetMinKey();
	
	k[num] = key;
	p[num+1] = right->p[0];
	m_n++;
	
	for(int j=0;j<right->m_n;j++)
	{
		k[num+1+j] = right->k[j];
		p[num+2+j] = right->p[j+1];
		m_n++;
	}	
	return key;
}

// MyLeaf

MyLeaf::MyLeaf()
{
	m_level = 1;
	m_next = NULL;
}

MyLeaf::~MyLeaf()
{
}


// MyLeaf 成员函数

// Search fuction, Node / Leaf 's search.
int MyLeaf::Search(long key)	// return the position of the key(0 - N), -1 is error or no key
{
	if(m_level > 1)	return -1;

	int i;
	for(i=0;i<m_n;i++)
		if(key <= k[i])	break;
	return i;
}

// Insert fuction,
int MyLeaf::Insert(long key,void* pkey,int i)	// return position of noed (0 - N), -1 is error.
{
	if(m_level > 1)	return -1;
	if(m_n >= N)	return -1;
	if( (i < 0)	|| (i > m_n) )	return -1;

	for(int j=m_n;j>i;j--)
	{
		k[j] = k[j-1];
		p[j] = p[j-1];
	}
	k[i] = key;
	p[i] = pkey;
	m_n++;
	return i;
}
// you should new the Leaf or Node in the BPlusTree class.
int MyLeaf::SplitNode(MyNode* newNode,int m/*type*/)	// only use when level = 1
{
	if(m_level > 1)	return -1;
	if( (m != 0) && (m != 1) )	return -1;

	for(int j=0;j<N-M+m;j++)
	{
		newNode->k[j] = k[j+M-m];
		k[j+M-m] = 0;
		newNode->p[j] = p[j+M-m];
		p[j+M-m] = NULL;
		newNode->m_n++;
		m_n--;
	}
	((MyLeaf*)newNode)->m_next = m_next;
	m_next = (MyLeaf*)newNode;
	return j;
}

// Delete fuction
int MyLeaf::Delete(int i)
{
	if(m_level > 1)	return -1;
	if( (i < 0)	|| (i >= m_n) )	return -1;

	for(int j=i;j<m_n;j++)
	{
		k[j] = k[j+1];
		p[j] = p[j+1];
	}
	k[j] = 0;
	p[j] = NULL;

	m_n--;
	return i;
}
long MyLeaf::GetKeyFromLeft(MyNode* left)
{
	if(m_level > 1)	return -1;

	long key;
	key = left->k[left->m_n-1];

	Insert(key,left->p[left->m_n-1],0);
	left->Delete(left->m_n-1);

	return key;
}
long MyLeaf::GetKeyFromRight(MyNode* right)
{
	if(m_level > 1)	return -1;

	long key;
	key = right->k[0];

	Insert(key,right->p[0],m_n);	
	right->Delete(0);

	return key;
}
long MyLeaf::UniteRight(MyNode* right)
{
	if(m_level > 1)	return -1;

	for(int j=0;j<right->m_n;j++)
		Insert(right->k[j],right->p[j],m_n);
	m_next = ((MyLeaf*)right)->m_next;
	return right->k[0];
}