#include?“BPlusTree.h“
#include?
#include?
#include?

int??M_WAY?=?3;
int??NODE_CAPACITY?=?M_WAY+1;

////////////////////////////////////////////////////

LeaveNode::LeaveNode（）
{
????m_next?=?NULL;
????m_prev?=?NULL;

????m_value??=?new?double[NODE_CAPACITY];
}
LeaveNode::~LeaveNode（）
{
}

void?LeaveNode::Insert（int?key?double?value）
{
????assert（m_currentSize?
????for?（int?i?=?0;?i?????{
????????if?（key?<=?m_key[i]）?//找到插入點
????????{
????????????//后續所有節點后移一個下標對應指針同步操作
????????????for?（int?j?=?m_currentSize?-?1;?j?>=?i;?--j）
????????????{
????????????????m_key[j?+?1]?=?m_key[j];
????????????????m_value[j?+?1]?=?m_value[j];
????????????}

????????????m_key[i]?=?key;
????????????m_value[i]?=?value;

????????????m_currentSize++;

????????????return;
????????}
????}

????m_key[m_currentSize]?=?key;
????m_value[m_currentSize]?=?value;

????m_currentSize++;
}

void?LeaveNode::Split（Node*?&_left?Node*?&_right）
{
????assert（m_currentSize?==?NODE_CAPACITY）;
????
????LeaveNode*?pNew?=?new?LeaveNode;

????int?leftCount?=?（int）ceil（（M_WAY+1）/2.0）;
????int?rightCount?=?m_currentSize?-?leftCount;
????
????int?index?=?0;
????while（index?????{
????????pNew->Insert（m_key[index]?m_value[index]）;

????????index++;
????}

????//原節點剔除分裂到新節點的數據后，繼續保留，充當分裂的第二節點
????while（index?????{
????????m_key[index-leftCount]?=?m_key[index];
????????m_value[index-leftCount]?=?m_value[index];

		++index;
????}
????//更新m_currentSize值
????m_currentSize?=?rightCount;

????//更新雙向鏈表指針
	if（this->GetPrev（）?!=?NULL）
	{
		this->GetPrev（）->SetNext（this）;
	}	

	pNew->SetPrev（this->GetPrev（））;
????pNew->SetNext（this）;

????this->SetPrev（pNew）;

????_right?=?this;
????_left?=?pNew;
}

Node*?LeaveNode::GetMinLeaveNode（）
{
	return?this;
}

bool?LeaveNode::Search（int?key?double?&value?Node?*&_valueNode）
{
????for?（int?i?=?0;?i?????{
????????if?（key?==?m_key[i]）?
????????{
????????????value?=?m_value[i];
????????????_valueNode?=?this;

????????????return?true;
????????}
????????else?if?（key?????????{?//進入此邏輯，說明查無此KEY
????????????break;
????????}
????}

????return?false;
}

bool?LeaveNode::Search（int?key1?int?key2?double*?result?int&?size）
{
????bool?bFind?=?false;
????for?（int?i?=?0;?i?????{
????????if?（m_key[i]?>=?key1?&&?m_key[i]?<=?key2）
????????{
????????????result[size]?=?m_value[i];
????????????size++;

????????????if（!bFind）
????????????{
????????????????bFind??=?true;
????????????}
????????}
????}

????return?bFind;
}

bool?LeaveNode::Delete（int?key）
{
????for?（int?i?=?0;?i?????{
????????if?（key?==?m_key[i]）//找到待刪除元素
????????{
????????????//后續所有節點前移一個下標對應指針同步操作
????????????for?（int?j?=?i;?j????????????{
????????????????m_key[j]?=?m_key[j+1];
????????????????m_value[j]?=?m_value[j+1];
????????????}

????????????m_currentSize--;

????????????return?true;
????????}
????????else?if?（key?