node.cpp

B+树的演示程序

// Node.cpp

#include "Node.h"
#include <iostream>

using namespace std;


int Node::N;
int Node::M;

Node::Node(int level/*=2*/)
{
    my_num = 0;
	my_level = level;
	k = new long[N]();
	for(int i=0;i<N;i++)
		k[i] = 0;
	p = new Node*[N+1];
	for(int i=0;i<N+1;i++)
		p[i] = NULL;
}

// a new root that with k[0] = key,p[0] = node1,p[1] = node2 , and now level should be node->my_level+1
Node::Node(int key,Node* node1,Node* node2,int level/*=2*/)
{
    my_num = 1;
	my_level = level;
	Node::k = new long[N]();
	for(int i=0;i<N;i++)
		k[i] = 0;
	Node::p = new Node*[N+1];
	for(int i=0;i<N+1;i++)
		p[i] = NULL;

	k[0] = key;
	p[0] = node1;
	p[1] = node2;
}

Node::~Node()
{
	delete [] Node::k;
	delete [] Node::p;
}

void Node::SetMaxNum(int n/*=3*/)
{
	N = n;
	M = (N+1)/2;
	return;
}

// return the position of the key should be .
int Node::Search(long key)
{
	if(my_level == 1)
		return ((Leaf*)this)->Search(key);

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

int Node::Insert(long key,Node* pkey,int i)
{
	if(my_level == 1)
		return ((Leaf*)this)->Insert(key,(long*)pkey,i);

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

	int m = 1;
	// notice here, / insert 0 or \ insert 0
	// that \ insert at 0 can not be judge at here, unless you transport a state via.
	if( (i == 0) && (key < GetMinKey() ) )
	{
		// insert a node at first position of branch / insert
		p[my_num+1] = p[my_num];
		m = 0;
	}
	else
		i++;

	for(int j=my_num;j>=i;j--)
	{
		k[j-m+1] = k[j-m];
		p[j+1] = p[j];
	}
	k[i-m] = key;
	p[i] = pkey;
	my_num++;
	return i;
}

int Node::Delete(int i)
{
	if(my_level == 1)
		return ((Leaf*)this)->Delete(i);	
	
	if( (i < 0)	|| (i > my_num) )	return -1;

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

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

void Node::SplitNode(Node* newNode,int m/*type*/)
{
	if(my_num < N) return ;

	if(my_level == 1)
	{
		((Leaf*)this)->SplitLeaf((Leaf*)newNode,m);
		return;
	}

	k[M-1] = 0;
	my_num--;
	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->my_num++;
		my_num--;
	}
	newNode->p[N-M] = p[N];
	p[N] = NULL;

	return ;
}

long Node::GetMinKey(int i/*=0*/)
{
	if( (i < 0)	|| (i > my_num) )	return -1;

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

	Node* temp;    
	temp = p[i];
	while(temp->my_level > 1)
		temp = temp->p[0];
	return temp->k[0];
}

long Node::GetKeyFromLeft(Node* leftNode)
{
	if(my_level == 1)
		return ((Leaf*)this)->GetKeyFromLeft((Leaf*)leftNode);

	long key;
	key = GetMinKey();

	p[my_num+1] = p[my_num];

	for(int j=my_num;j>0;j--)
	{
		k[j] = k[j-1];
		p[j] = p[j-1];
	}
	k[0] = key;
	p[0] = leftNode->p[leftNode->my_num];
	my_num++;

	// here is / insert	
	//Insert(key,leftNode->p[leftNode->my_num],0);
	leftNode->Delete(leftNode->my_num);

	return key;
}

long Node::GetKeyFromRight(Node* rightNode)
{
	if(my_level == 1)
		return ((Leaf*)this)->GetKeyFromRight((Leaf*)rightNode);

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

	k[my_num] = key;
	p[my_num+1] = rightNode->p[0];
	my_num++;

	rightNode->Delete(0);

	return key;
}

long Node::UniteRight(Node* rightNode)
{
	if(my_level == 1)
		return ((Leaf*)this)->UniteRight((Leaf*)rightNode);

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

// the fuctions of class Leaf

Leaf::Leaf()
{
	my_num = 0;
	my_level = 1;
	// Leaf::p = new long*[N];
	//for(int i=0;i<N;i++)
	//	p[i] = NULL;
	my_next = NULL;
}

Leaf::~Leaf()
{
	//delete [] Leaf::p;
}

int Leaf::Search(long key)
{
	int i;
	for(i=0;i<my_num;i++)
		if(key <= k[i])	break;
	return i;
}

int Leaf::Find(long key)
{
	int i;
	i = Search(key);
	if(key = *((long*)p[i]))
		return i;
	else
		return -1;
}

int Leaf::Insert(long key,long* pkey,int i)
{
	if(my_num >= N)	return -2;
	if( (i < 0)	|| (i > my_num) )	return -1;

	for(int j=my_num;j>i;j--)
	{
		k[j] = k[j-1];
		p[j] = p[j-1];
	}
	k[i] = key;
	p[i] = (Node*)pkey;
	my_num++;
	return i;
}

int Leaf::Delete(int i)
{
	if( (i < 0)	|| (i >= my_num) )	return -1;

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

Leaf* Leaf::Next()
{
	return my_next;
}

void Leaf::SplitLeaf(Leaf* newLeaf,int m/*type*/)
{
	if( (m != 0) && (m != 1) )	return ;

	for(int j=0;j<N-M+m;j++)
	{
		newLeaf->k[j] = k[j+M-m];
		k[j+M-m] = 0;
		newLeaf->p[j] = p[j+M-m];
		p[j+M-m] = NULL;
		newLeaf->my_num++;
		my_num--;
	}
	newLeaf->my_next = my_next;
	my_next = newLeaf;
	return ;
}

long Leaf::GetKeyFromLeft(Leaf* leftLeaf)
{
	long key;
	key = leftLeaf->k[leftLeaf->my_num-1];

	Insert(key,(long*)leftLeaf->p[leftLeaf->my_num-1],0);
	leftLeaf->Delete(leftLeaf->my_num-1);

	return key;
}

long Leaf::GetKeyFromRight(Leaf* rightLeaf)
{
	long key;
	key = rightLeaf->k[0];

	Insert(key,(long*)rightLeaf->p[0],my_num);
	rightLeaf->Delete(0);

	return key;
}

long Leaf::UniteRight(Leaf* rightLeaf)
{	
	for(int j=0;j<rightLeaf->my_num;j++)
		Insert(rightLeaf->k[j],(long*)rightLeaf->p[j],my_num);
	my_next = rightLeaf->my_next;
	return rightLeaf->k[0];
}