filestructure

#include <iostream>
#include <cstdio> // dfdfdaㅣㅏㅣㅏㅣㅏㅣㅏ
#include <algorithm>
using namespace std;


// https://docs.google.com/file/d/0BzNvN1OCjO-fUE52Wm5pdU9iaDg/view
// B-Tree 
// ilI|
//https://bitbucket.org/leejaku
//http://ddmix.blogspot.kr/2014/11/cppalgo.html#more
template <class TYPE> struct Node
{
	TYPE *m_pKeys;
	Node **m_pChildren;
	int m_nKeys;  //Node의 사이즈는 아니고 Node에 Key가 채워진 갯수

	Node(int dim) {
		m_pKeys = new TYPE[dim];
		m_pChildren = new Node*[dim + 1];
		for (int i = 0; i <= dim; i++) m_pChildren[i] = 0;
		m_nKeys = 0;
	}
	~Node() {
		delete[] m_pKeys;
		delete[] m_pChildren;
	}

	typedef Node* PNODE;

	PNODE& Left(int n) { return m_pChildren[n]; }
	PNODE& Right(int n) { return m_pChildren[n + 1]; }
	TYPE& Key(int n) { return m_pKeys[n]; }
	int& Size() { return m_nKeys; }

	void AddValue(const TYPE& value, Node* left, Node* right)
	{
		int i = m_nKeys - 1;
		while(i >= 0 && m_pKeys[i] > value)
		{
			Right(i+1) = Right(i);
			Key(i+1) = Key(i);
			i--;
		}
		i++;
		Key(i) = value;
		//Right(i+1) = Right(i);
		Left(i) = left;
		Right(i) = right;
		m_nKeys++;
	}
	void DelValue(int index)
	{
		for (int i = index; i < Size() - 1; i++)
		{
			Key(i) = Key(i + 1);
			Left(i) = Left(i + 1);
		}
		Right(m_nKeys - 2) = Right(m_nKeys - 1);
		m_nKeys--; 
	}

	int FindKey(const TYPE& key) //찾으면 찾은 위치값을 리턴, 못찾으면 -1을 리턴.
	{
		for (int i = 0; i < m_nKeys; i++)
			if (key == Key(i)) return i;
		return -1;
	}

	void Clear(int dim)
	{
		m_nKeys = 0;
		for (int i = 0; i <= dim; i++) //dim의 Right 노드까지 0으로
			m_pChildren[i] = 0;
	}
};



template <class TYPE> class BTreeMap
{
public:
	enum Exception {
		INVALID_DIMENSION,  // BTree의 차수는 3이상의 홀수여야 한다. 
	};

protected:
	//struct Node<TYPE>;
	//typedef Node<TYPE>* PNODE;

	long m_nCount;
	long m_nDim;

	Node<TYPE>* m_pNodeHead;

	void _RemoveSubtree(Node<TYPE> *pNode);

	Node<TYPE>* _Split(const TYPE& key, Node<TYPE>* pivot);

	bool _BorrowKey(Node<TYPE> *p, int index);
	Node<TYPE>* _BindNode(Node<TYPE> *p, int index);
	TYPE _SwapKey(Node<TYPE> *del, int index);

public:
	BTreeMap(int dim = 5)
	{
		if (dim < 3 || dim % 2 == 0)
			throw INVALID_DIMENSION;

		m_pNodeHead = new Node<TYPE>(dim); // 1개만 생성... 핵노답 [dim] 으로 읽음... ㅋㅋ
		m_nDim = dim;
	}
	~BTreeMap();

	// operations
	bool Find(const TYPE& key, TYPE& value) const;
	bool Insert(const TYPE& value);
	bool Remove(const TYPE& key);
	// BTree도 역시 중복키에 대한 처리가 힘들다. 

	// utilites
	long GetCount() const { return m_nCount; }
	bool IsEmpty() const { return m_nCount == 0; }
	void RemoveAll();
};


template <class TYPE>
void BTreeMap<TYPE>::_RemoveSubtree(Node<TYPE> *pNode)
{
	if (pNode != 0)
	{
		for (int i = 0; i <= pNode->Size(); i++)
			_RemoveSubtree(pNode->Left(i));
		delete pNode;
	}
}

template <class TYPE>
void BTreeMap<TYPE>::RemoveAll()
{
	_RemoveSubtree(m_pNodeHead->Left(0));
	m_pNodeHead->Left(0) = 0;
}

template <class TYPE>
BTreeMap<TYPE>::~BTreeMap()
{
	RemoveAll();
	delete m_pNodeHead;
}

template <class TYPE>
bool BTreeMap<TYPE>::Find(const TYPE& key, TYPE& value) const
{
	Node<TYPE> *t;
	int index;
	t = m_pNodeHead->Left(0);
	while (t != 0 && (index = t->FindKey(key)) < 0)   //t노드가 꼬리노드(0)가 아니고, t노드상에서 찾을 수 없을 때(-1)
	{
		int i;
		for (i = 0; i < t->Size() && key > t->Key(i); i++);  //t노드내의 순번은 t노드의 사이즈를 넘지 않고, i번째 Key()값이 key값보다 작다면 i값을 계속 증가.
		t = t->Left(i);
	}
	if (t == 0) return false;

	value = t->Key(index);
	return true;
}

// 삽입하고자 하는 키는 key, 분할 노드의 부모가 pivot
template <class TYPE>
Node<TYPE>* BTreeMap<TYPE>::_Split(const TYPE& key, Node<TYPE>* pivot)
{
	Node<TYPE> *left, *right;
	Node<TYPE> *split;   // 리턴할 노드 
	int i, j;

	right = new Node<TYPE>(m_nDim);

	// 경우 1 : 분할할 노드가 Root 인 경우 
	if (pivot == m_pNodeHead)
	{
		split = pivot->Left(0);  // child == root

								 // left child 생성 
		left = new Node<TYPE>(m_nDim);

		for (i = 0; i < m_nDim / 2; i++)
		{
			left->Key(i) = split->Key(i);
			left->Left(i) = split->Left(i);
		}
		left->Left(i) = split->Left(i); //right에 해당하는 자식 노드는 하나 더 가져옴
		left->Size() = m_nDim / 2;  //left노드의 배열 갯수를 규정

									// right child 생성 
		for (i = m_nDim / 2 + 1, j = 0; i < m_nDim; i++, j++)
		{
			right->Key(j) = split->Key(i);
			right->Left(j) = split->Left(i);
		}
		right->Left(j) = split->Left(i);
		right->Size() = m_nDim / 2;

		// 부모노드 정리 
		TYPE temp = split->Key(m_nDim / 2); //중간 Key값만을 임시 복사
		split->Clear(m_nDim);  //기존 split노드의 Key값과 자식노드들 모두 삭제
		split->AddValue(temp, left, right);
	}

	// 경우 2 : 분할할 노드가 Root가 아닌 경우 
	else
	{
		// 분할할 노드를 찾기 
		for (i = 0; i < pivot->Size() && key > pivot->Key(i); i++);

		// 왼쪽 노드는 이미 있는 노드이므로 갯수만 조정 
		left = pivot->Left(i);
		left->Size() = m_nDim / 2;

		// 오른쪽 노드 생성 
		for (i = m_nDim / 2 + 1, j = 0; i < m_nDim; i++, j++)
		{
			right->Key(j) = left->Key(i);  //갯수만 줄였을 뿐 삭제한 것이 아니므로 자료는 남아있음.
			right->Left(j) = left->Left(i);
		}
		right->Left(j) = left->Left(i);
		right->Size() = m_nDim / 2;

		// 중간키를 부모에 삽입 
		pivot->AddValue(left->Key(m_nDim / 2), left, right);
		split = pivot;
	}
	return split;
}

template <class TYPE>
bool BTreeMap<TYPE>::Insert(const TYPE& value)
{
	Node<TYPE> *t, *p;
	int i;
	p = m_pNodeHead;
	t = m_pNodeHead->Left(0);

	if (t == 0)  // 뿌리노드가 없다면 특별히 생성해주어야 한다. 
	{
		t = new Node<TYPE>(m_nDim);
		m_pNodeHead->Left(0) = t; //처음 t가 정의된 그 위치 그대로,,,
	}
	while (t != 0)
	{
		if (t->FindKey(value) >= 0)  // 중복키 삽입금지 
			return false;
		if (t->Size() == m_nDim) // 꽉찬 노드이면 분할한다. 
			t = _Split(value, p);
		p = t;
		for (i = 0; i < t->Size() && value > t->Key(i); i++);
		t = t->Left(i);
	}
	p->AddValue(value, 0, 0);   // 외부노드로 삽입 
	m_nCount++;
	return true;
}





template <class TYPE>
bool BTreeMap<TYPE>::_BorrowKey(Node<TYPE> *p, int index)
{
	int from, to;
	Node<TYPE> *p1, *p2;
	to = index;

	if (index == p->Size()) // 가장 오른쪽인 경우 왼쪽형제에게 빌림 
		from = index - 1;
	else  // 아니면 오른쪽 형제에게서 빌림 
		from = index + 1;

	p1 = p->Left(from);   // p1 = 빌려주는 노드 
	p2 = p->Left(to);       // p2 = 빌리는 노드 

	if (p1->Size() <= m_nDim / 2)   // 빌려줄 키가 없을 때 실패를 리턴 
		return false;

	if (from > to)   // 오른쪽 형제에게서 빌림 
	{
		p2->AddValue(p->Key(to), p2->Left(p2->Size()), p1->Left(0)); //부모에게서 가져옴.
		p->Key(to) = p1->Key(0);          //형제에게서 부모로.
		p1->DelValue(0);            //형제에게서 빌린값 삭제
	}
	else   // 왼쪽 형제에게서 빌림 
	{
		p2->AddValue(p->Key(from), p1->Left(p1->Size()), p2->Left(0));
		p->Key(from) = p1->Key(p1->Size() - 1);
		p1->DelValue(p1->Size() - 1);
	}
	return true;
}

template <class TYPE>
Node<TYPE>* BTreeMap<TYPE>::_BindNode(Node<TYPE>* p, int index)
{
	Node<TYPE> *left, *right;
	int i;

	if (index == p->Size()) index--; // 가장 오른쪽이면 index 감소

	left = p->Left(index);
	right = p->Right(index);

	left->Key(left->Size()++) = p->Key(index);   // 왼쪽노드에 부모키를 복사 
	for (i = 0; i < right->Size(); i++)  // 왼쪽노드에 오른쪽 노드를 복사 
	{
		left->Key(left->Size()) = right->Key(i);
		left->Left(left->Size()++) = right->Left(i);
	}
	left->Left(left->Size()) = right->Left(i);

	p->DelValue(index);   // 부모노드에서 결합한 키를 삭제 
	p->Left(index) = left;  // 포인터 조절 
	delete right;

	if (p->Size() == 0)   // 뿌리노드일 수 밖에 없음 이경우....
	{
		delete p;
		m_pNodeHead->Left(0) = left;
	}
	return left;  // 결합된 노드를 리턴 
}

template <class TYPE>
TYPE BTreeMap<TYPE>::_SwapKey(Node<TYPE> *del, int index)
{
	Node<TYPE> *cdd, *cddp;    // cdd는 대체노드, cddp는 대체노드의 부모 
	cddp = del;
	cdd = cddp->Right(index);   // 삭제키의 오른쪽 자식

	while (cdd->Left(0) != 0)
	{
		cddp = cdd;
		cdd = cdd->Left(0);
	}
	TYPE temp = del->Key(index);
	del->Key(index) = cdd->Key(0);  // del에 말단 cdd위치에 있는 키를 대체 
	cdd->Key(0) = temp;
	return cdd->Key(0);    // 노드 위치는 바뀌었지만 처음 del로 입력된 Key값을 리턴
}

template <class TYPE>
bool BTreeMap<TYPE>::Remove(const TYPE& key)
{
	Node<TYPE> *t, *p;
	int pi = 0;   // 부모의 index
	int ti = 0;   // 현재노드의 index
	TYPE value = key;

	p = m_pNodeHead;
	t = m_pNodeHead->Left(0);

	while (t != 0)
	{
		if (t->Size() <= m_nDim / 2 && p != m_pNodeHead) // 확장할 필요가 있으면 확장 (root 노드는 m_nDim/2보다 커도 상관없다.)
		{
			if (!_BorrowKey(p, pi))  // 형제에게서 빌려보고 실패하면 형제와 결합 
				t = _BindNode(p, pi);
		}
		if ((ti = t->FindKey(value)) >= 0)  // 삭제키가 이 노드에 있으면 
		{
			if (t->Left(0) == 0) break;  // 외부노드이면 break;
			else value = _SwapKey(t, ti);   // 내부노드이면 바꿈. 이제 새로운 value를 아래로 내려야 한다. 
		}
		p = t;
		for (pi = 0; pi < t->Size() && (value > t->Key(pi) || value == t->Key(pi)); pi++);
		t = t->Left(pi);
	}
	if (t == 0) return false;   // 찾을 수 없음. 
	if (t->Size() <= m_nDim / 2 && p != m_pNodeHead)  // 외부노드인데 키수가 너무 적으면 
		if (!_BorrowKey(p, pi)) t = _BindNode(p, pi);
	t->DelValue(t->FindKey(value));  // 노드의 키를 삭제 
	m_nCount--;
	return true;
}


int main()
{

	Node<int> node(5);

	//Node<int>* t = (Node<int>*)0x1;
	node.AddValue(3, (Node<int>*)0x1, (Node<int>*)0x2);
	node.AddValue(5, (Node<int>*)0x3, (Node<int>*)0x4);
	node.AddValue(2, (Node<int>*)0x5, (Node<int>*)0x6);
	node.AddValue(1, (Node<int>*)0x7, (Node<int>*)0x8);

	for (int i = 0; i<node.m_nKeys; i++)
	{
		printf("%d (%d, %d)\n", node.m_pKeys[i], node.Left(i), node.Right(i));
	}

	node.DelValue(1);
	printf("\n");
	for (int i = 0; i<node.m_nKeys; i++)
	{
		printf("%d (%d, %d)\n", node.m_pKeys[i], node.Left(i), node.Right(i));
	}
	return 0;
}