#pragma once

#pragma pack(push,8)
#pragma warning(push,3)
#include <functional>

#define DEGREE 5

class CTest_BTree;
template<
	class _Key, 
	class _Data, 
	class _Compare = std::less<_Key>, 
	class _Alloc = std::allocator<std::pair<const _Key, _Data> > >
class BTree {
public:
	typedef _Key key_type;
	typedef _Data data_type;
	typedef std::pair<key_type, data_type> value_type;
	typedef value_type* pointer;
	typedef value_type& reference;
	typedef _Compare key_compare;
	typedef unsigned int size_type;
	
	struct NODE;
	struct iterator {
		iterator() : m_pNode(NULL), m_index(-1) {
		}
		NODE* m_pNode;
		int m_index;
		
		pointer operator->() const
		{	// return pointer to class object
			if(NULL == m_pNode) {
				return NULL;
			}
			return &(m_pNode->m_values[m_index]);
		}
		iterator& operator = (const iterator& i) {
			m_index = i.m_index;
			m_pNode = i.m_pNode;

			return (*this);
		}
	};

	struct NODE {
		NODE() {
			Init();
		}
		int 		m_count;
		value_type	m_values[DEGREE];
		NODE* 		m_children[DEGREE+1];
		NODE* 		m_parent;
		/**
			init
		*/
		void Init()	{
			m_count = 0;
			m_parent = NULL;
			memset(m_children, 0, sizeof(NODE*)*(DEGREE+1));
		} 
		/**
			Áߺ¹ Å° Çã¿ëÇÏÁö ¾ÊÀ½.
			Áߺ¹ µÇ´Â Å°°¡ ÀÖ´Ù¸é ÀÌÀü Å°¿¡ ´ëÇÑ µ¥ÀÌÅÍ´Â µ¤¾î ½áÁü
		*/
		void insert(const value_type& x, int index) {
			key_compare compare_functor;
			if(compare_functor(x.first, m_values[index].first) || compare_functor(m_values[index].first, x.first)) {
				for(int i=m_count; i>index; --i) {
					m_values[i] = m_values[i-1];
					m_children[i+1] = m_children[i];
				}
				if(index <= m_count) {
					m_children[index+1] = m_children[index];
				}
				m_count += 1;
			}
			m_values[index] = x;
		}
		
		/**
			Finds an element whose key		
		*/
		std::pair<int, bool> find(const key_type& key) const {
			key_compare compare_functor;
			int index = 0;
			for(index=0; index<m_count; ++index) {
				if(compare_functor(key, m_values[index].first)) {
					return std::make_pair(index, false);
				}
				else if(!compare_functor(m_values[index].first, key)) {
					return std::make_pair(index, true);
				}
			}
			return std::make_pair(m_count, false);
		}

		/**
			Å°ÀÇ »èÁ¦
			Å°ÀÇ »èÁ¦´Â Ç×»ó leaf¿¡¼­¸¸ ÀÏ¾î ³ª¹Ç·Î ÀڽĿ¡ ´ëÇÑ °ÆÁ¤Àº ÇÏÁö ¾Ê¾Æµµ µÊ
		*/																										    
		void erase(int index) {
			m_count -= 1;
			for(int i=index; i<m_count; ++i) {
				m_values[i] = m_values[i+1];
			}
		}
		/**
			Å°ÀÇ successor¸¦ ¸®ÅÏ
			leafÀÏ °æ¿ì¿¡´Â NULL¸®ÅÏ
		*/
		NODE* findSuccessor(int index) {
			NODE* curNode = m_children[index+1];
			NODE* retNode = NULL;
			while(NULL != curNode) {
				retNode = curNode;
				curNode = curNode->m_children[0];
			}

			return retNode;
		}
	};

	NODE* m_root;
	size_type m_size;
public :
	BTree() : m_root(NULL), m_size(0) {
	}
	iterator begin() {
	}
	iterator end() {
	}     
	size_type size() const {
		return m_size;
	}     
	bool empty() const {
		return (0 == m_size) ? true : false;
	}

	/**
		Inserts x into the map.
	*/
	std::pair<iterator, bool> insert(const value_type& x) {
		if(NULL == m_root) {
			m_root = new NODE;
		}    		
		return insertWithoutOverwrite(m_root, x);
	}
	/**
		Finds an element whose key is k. 
	*/
	iterator find(const key_type& k) {
		std::pair<iterator, bool> ret = find(m_root, k);
		if(true == ret.second) {
			return itr;
		}
		itr.m_pNode = NULL;
		itr.m_index = -1;
		return itr;						 
	}
	void erase(iterator pos) {
		m_size--;
		iterator leafItr;
		leafItr.m_pNode = pos.m_pNode->findSuccessor(pos.m_index);
		if(NULL == leafItr.m_pNode) {	// m_root°¡ leaf´Ù
			pos.m_pNode->erase(pos.m_index);
			leafItr.m_pNode = pos.m_pNode;
		}
		else { // leaf¿Í swap ÈÄ 
			value_type tmpValue = leafItr.m_pNode->m_values[0];
			leafItr.m_pNode->m_values[0] = pos.m_pNode->m_values[pos.m_index];
			pos.m_pNode->m_values[pos.m_index] = tmpValue;
			leafItr.m_pNode->erase(0);
		}

		while(DEGREE/2 > leafItr.m_pNode->m_count && NULL != leafItr.m_pNode->m_parent) {
			iterator parentItr, sibilingItr;

			findSibilingAndParent(leafItr, sibilingItr, parentItr);
			
			leafItr.m_pNode->insert(parentItr.m_pNode->m_values[parentItr.m_index], leafItr.m_index);
		
			if(DEGREE/2 < sibilingItr.m_pNode->m_count) {
				parentItr.m_pNode->m_values[parentItr.m_index] = sibilingItr.m_pNode->m_values[sibilingItr.m_index];				
				correctChildrenLinks(leafItr, sibilingItr);
				sibilingItr.m_pNode->erase(sibilingItr.m_index);
			}
			else {
				NODE* left = parentItr.m_pNode->m_children[parentItr.m_index];
				NODE* right = parentItr.m_pNode->m_children[parentItr.m_index+1];
		
				/**
					À§ÀÇ °úÁ¤¿¡¼­ insertÇϸ鼭 µÚ·Î ¹Ð·Á³µ´ø ÀÚ½Ä ³ëµåµé¿¡ ´ëÇÑ ¸µÅ©¸¦ ´Ù½Ã ÇÑÄ­¾¿ ¾ÕÀ¸·Î..-_-;;
				*/
				if(left == leafItr.m_pNode) {
					for(int i=leafItr.m_index; i<left->m_count; i++) {
						left->m_children[i] = left->m_children[i+1];
						left->m_children[i+1] = NULL;
					}
				}

				leafItr.m_pNode = merge(left, right);

				parentItr.m_pNode->m_children[parentItr.m_index+1] = NULL;
                     				
				parentItr.m_pNode->erase(parentItr.m_index);
				for(int i=parentItr.m_index+1; i<parentItr.m_pNode->m_count+1; ++i) {
					parentItr.m_pNode->m_children[i] = parentItr.m_pNode->m_children[i+1]; 
				}
			}

			if(leafItr.m_pNode->m_parent == m_root && 0 == m_root->m_count) {
				delete leafItr.m_pNode->m_parent;
				leafItr.m_pNode->m_parent = NULL;
				m_root = leafItr.m_pNode;
				break;
			}
          	leafItr.m_pNode = leafItr.m_pNode->m_parent;
		}
	}

	/**
		1. leaf³ëµåÀÌ¸é ±×³É »èÁ¦
		2. internal ³ëµåÀ̸é successor¸¦ ã¾Æ¼­ swap ÈÄ »èÁ¦
		
		»èÁ¦ ÈÄ Å°ÀÇ °¹¼ö°¡ ¸ðÀÚ¸¦ ¶§
		1. ºÎ¸ð¿¡°Ô¼­ ¾ò¾î ¿Â´Ù.
		2. ºÎ¸ð¿¡°Ô¼­ ¾ò¾î ¿Ô´Âµ¥ ºÎ¸ð°¡ ¸ðÀÚ¶ó¸é ÇüÁ¦ÀÇ °ÍÀ» ºÎ¸ð·Î ¿Ã¸°´Ù.
		3. ÇüÁ¦°¡ ºÎ¸ð·Î ¿Ã¸± ÇüÆíÀÌ ¾ÈµÇ´Â °æ¿ì¿¡´Â ºÎ¸ðÀÇ ÀûÀýÇÑ Å°¿Í µÎ ÇüÁ¦¸¦ ÇÕº´ÇÑ´Ù.
	*/
	size_type erase(const key_type& k) {
		if(NULL == m_root) {
			return 0;
		}
		std::pair<iterator, bool> ret = find(m_root, k);
		if(true == ret.second) { // Áö¿ï Å°°¡ ÀÖ´Ù
			erase(ret.first);	
			return 1;
		}
		return false; // fail to remove the key
	}

	void erase(iterator first, iterator last) {
	}						

	void print() {
		retrival(m_root);
	}
	void retrival(NODE* node) {
		if(NULL == node) {
			return;
		}
		std::cout << "[";
		for(int i=0; i<node->m_count; i++) {
			std::cout << node->m_values[i].first << " ";
		}
		std::cout << "]";
		for(int i=0; i<=node->m_count; i++) {
			if(NULL != node->m_children[i]) {
				retrival(node->m_children[i]);
			}
		}
	}
	void correctChildrenLinks(iterator& cur, iterator& sibiling) {
		if(0 == sibiling.m_index) { 
			cur.m_pNode->m_children[cur.m_pNode->m_count] = sibiling.m_pNode->m_children[sibiling.m_index];

			if(NULL != cur.m_pNode->m_children[cur.m_pNode->m_count]) {
				cur.m_pNode->m_children[cur.m_pNode->m_count]->m_parent = cur.m_pNode;
			}	
			for(int i=sibiling.m_index; i<sibiling.m_pNode->m_count; i++) {
				sibiling.m_pNode->m_children[i] = sibiling.m_pNode->m_children[i+1];
			}
		}
		else {
			cur.m_pNode->m_children[cur.m_index] = sibiling.m_pNode->m_children[sibiling.m_index+1];

			if(NULL != cur.m_pNode->m_children[cur.m_index]) {
				cur.m_pNode->m_children[cur.m_index]->m_parent = cur.m_pNode;
			}	
		}
	}
	void findSibilingAndParent(iterator& cur, iterator& sibiling, iterator& parent) {
		parent.m_pNode = cur.m_pNode->m_parent;
		for(int i=0; i<=parent.m_pNode->m_count; ++i) {
			if(parent.m_pNode->m_children[i] == cur.m_pNode) {
				if(i == parent.m_pNode->m_count) {
					parent.m_index = i-1;
					sibiling.m_pNode = parent.m_pNode->m_children[i-1];
					sibiling.m_index = sibiling.m_pNode->m_count-1;
					cur.m_index = 0;
				}
				else {
					parent.m_index = i;
					sibiling.m_pNode = parent.m_pNode->m_children[i+1];
					sibiling.m_index = 0;
					cur.m_index = cur.m_pNode->m_count;
				}
				break;
			}
		}
	}
	/** 
		¿øÇÏ´Â Å°¸¦ ãÀ¸¸é true¿Í À妽º, Å°°¡ À§Ä¡ÇÑ ³ëµå¸¦ ¸®ÅÏ
		Å°¸¦ ãÁö ¸øÇϸé false¿Í Àμ­Æ® µÇ¾î¾ß ÇÒ ³ëµå, Àμ­Æ® µÇ¾î¾ß ÇÏ´Â À妽º ¸®ÅÏ
	*/
	std::pair<iterator, bool> find(const NODE* pNode, const key_type& key) {
		NODE* pTempNode = const_cast<NODE*>(pNode);
		iterator itr;
		while(NULL != pTempNode) {
			std::pair<int, bool> ret = pTempNode->find(key);
			itr.m_pNode = pTempNode;
			itr.m_index = ret.first;
			if(false == ret.second) {
				pTempNode = pTempNode->m_children[ret.first];
			}
			else {
				return std::make_pair(itr, true);
			}
		}
		return std::make_pair(itr, false);
	}

	/**
		Å°¸¦ »ðÀÔ. ¸¸ÀÏ Å°ÀÇ Áߺ¹ÀÌ ÀÖ´Ù¸é µ¤¾î ¾²Áö ¾Ê°í false¸¦ ¸®ÅÏÇÑ´Ù.
	*/
	std::pair<iterator, bool> insertWithoutOverwrite(NODE* pNode, const value_type& x) {
		std::pair<iterator, bool> ret = find(pNode, x.first);
		if(false == ret.second) {
			ret.first.m_pNode->insert(x, ret.first.m_index);
			m_size++;
		}
		else {
			return std::make_pair(ret.first, false);
		}

		if(DEGREE == ret.first.m_pNode->m_count) {
			split(ret.first.m_pNode);
		}
		return std::make_pair(ret.first, true);
	}
	void split(NODE* pNode) {
		NODE* curNode = pNode;

		while(DEGREE == curNode->m_count) {
			NODE* parentNode = NULL;
			if(NULL != curNode->m_parent) {
				parentNode = curNode->m_parent;
			}
			else {
				parentNode = new NODE;
				m_root = parentNode;
				curNode->m_parent = parentNode;
			}

			NODE* sibilingNode = new NODE;
			sibilingNode->m_parent = parentNode;

			std::pair<int, bool> ret = parentNode->find(curNode->m_values[DEGREE/2].first);
			parentNode->insert(curNode->m_values[DEGREE/2], ret.first);

			for(int i=(curNode->m_count/2+1), j=0; i<curNode->m_count; i++, j++) {
				sibilingNode->m_values[j] = curNode->m_values[i];
				sibilingNode->m_children[j] = curNode->m_children[i];
				if(NULL != sibilingNode->m_children[j]) {
					sibilingNode->m_children[j]->m_parent = sibilingNode;
				}
				curNode->m_children[i] = NULL;
			}
			sibilingNode->m_count = curNode->m_count/2;
			sibilingNode->m_children[sibilingNode->m_count] = curNode->m_children[curNode->m_count];
			if(NULL != sibilingNode->m_children[sibilingNode->m_count]) {
				sibilingNode->m_children[sibilingNode->m_count]->m_parent = sibilingNode; 
			}
			curNode->m_children[curNode->m_count] = NULL;

			curNode->m_count = sibilingNode->m_count;

			parentNode->m_children[ret.first] = curNode;
			parentNode->m_children[ret.first+1] = sibilingNode;

			curNode = parentNode;
		}
	}  
	NODE* merge(NODE* left, NODE* right) {
		for(int i=0; i<right->m_count; ++i) {
			left->m_values[left->m_count+i] = right->m_values[i];
		}
		
		for(int i= ((NULL != left->m_children[left->m_count]) ? 1 :0); i<=right->m_count; ++i) {
			left->m_children[left->m_count+i] = right->m_children[i];
			if(NULL != right->m_children[i]) {
				right->m_children[i]->m_parent = left;
			}
		}
		left->m_count += right->m_count;
		delete right;
		return left;
	}

	void clear() {
	}

	data_type& operator[](const key_type& k) {
		NODE* outNode;
		int index;
		if(false == findKeyInNode(m_root, k, &outNode, index)) {
			value_type value;
			value.first = k;
			insert(value);
		}
		
		return outNode->m_values[index];
	}
};