//===============Inserção========================================

//encontra o ponto de corte para particionar em dois um nó que é grande demais

int cut(int order){
	//se a ordem for par, retorna o índice do meio
	if(order %2 == 0){
		return order/2;
	}
	else{//se não, retorna o indice do meio mais um
		return order/2 + 1;
	}
}

/*Cria um novo registro*/
record * make_record(char **rec, int size, int key_id){
	record* new_record = (record*)malloc(sizeof(record));
	new_record->size = size;
	new_record->key = strtoull(rec[key_id], NULL, 0);

	int i;
	new_record->fields = malloc(size*(sizeof(char)*30));//aloca espaço para cada campo do vetor
	for (i = 0; i < size; i++){
		new_record->fields[i] = rec[i];
	}
	return new_record;
}

/*Cria um nó vazio que pode ser adaptado para ser uma folha ou um nó interno*/
node * make_node(int order){
	node * new_node;
	new_node = malloc(sizeof(node));
	new_node->keys = malloc(order * sizeof(unsigned long long int));
	new_node->pointers = malloc((order+1)*sizeof(void *)); // esses ponteiros podem ser de registros ou de nós, por isso usei void
	new_node->is_leaf = false;
	new_node->num_keys = 0;
	new_node->parent = NULL;
	new_node->next = NULL;
	new_node->order = order;
	return new_node;
}

/*Adapta um nó para que ele seja uma folha*/
node * make_leaf(int order){
	node* leaf = make_node(order);
	leaf->is_leaf = true;
	return leaf;
}

/*Essa função encontra no vetor de chaves do nó mãe
 o indice do nó a esquerda do nó onde a chave vai ser inserida*/
int get_left_index(node * parent, node * left){
	int left_index = 0;
	//começa na chave 0 do pai e caminha até encontrar o nó da esquerda
	while(left_index <= parent->num_keys && parent->pointers[left_index] != left){
		left_index++;
	}

	return left_index;
}

/*Insere em uma folha uma chave e um ponteiro para seu registro correspondente.
Retorna a folha alterada*/
node * insert_into_leaf(node * leaf, unsigned long long key, record * pointer){
	int i;
	int insertion_point = 0;

	// caminha no vetor de chaves da folha até encontrar o índice onde a chave deve ser inserida
	while(insertion_point < leaf->num_keys && leaf->keys[insertion_point] < key){
		insertion_point ++;
	}

	/*caminha da última chave no vetor até o ponto de inseção
	movendo as chaves e os registros um índice para frente para que haja espaço
	para a nova chave e para o novo registro
	*/
	for(i = leaf->num_keys; i > insertion_point; i--){
		leaf->keys[i] = leaf->keys[i-1];
		leaf->pointers[i] = leaf->pointers[i-1];
	}

	//insere a nova chave e registro no espaço recentemente aberto
	leaf->keys[insertion_point] = key;
	leaf->pointers[insertion_point] = pointer;
	leaf->num_keys ++;

	return leaf;
}

/*Insere em uma folha cheia uma nova chave e um ponteiro para registro,
de forma q ultrapasse o tamanho máximo e q a folha seja dividida em duas*/
node * insert_into_leaf_after_splitting(node * root, node * leaf, unsigned long long int key, record * pointer){
	node * new_leaf;
	void ** temp_pointers;
	unsigned long long int * temp_keys;
	unsigned long long int new_key;
	int insertion_point, split, i, j, ord;

	ord = root->order;

	new_leaf = make_leaf(ord);

	temp_keys = malloc(ord * sizeof(unsigned long long int));
	temp_pointers = malloc(ord * sizeof(void*));

	//caminha no vetor de chaves da folha procurando o ponto de inserção da nova chave
	insertion_point = 0;
	while(insertion_point < (ord - 1) && leaf->keys[insertion_point] < key){
		insertion_point ++;
	}

	/*caminha no índice tanto dos vetores temporarios quanto nos originais até achar o ponto de inserção
		quando o encontra ela aumenta apenas o j de forma q o índice de inserção seja pulado e as chaves e registros seja movidos
		um indice para frente, deixando o espaço para o novo registro
	*/
	for(i = 0, j = 0; i < leaf->num_keys; i++, j ++){
		if(j == insertion_point){
			j++;
		}
		temp_keys[j] = leaf->keys[i];
		temp_pointers[j] = leaf->pointers[i];
	}

	temp_keys[insertion_point] = key;
	temp_pointers[insertion_point] = pointer;

	leaf->num_keys =0;
	//encontra o ponto onde os vetores devem ser divididos
	 split = cut(ord-1);

	 //copia e cola a primeira metade das chaves e registros na folha
	 for(i = 0; i < split; i++){
	 	leaf->pointers[i] = temp_pointers[i];
	 	leaf->keys[i] = temp_keys[i];
	 	leaf->num_keys ++;
	 }

	 //copia e cola a segunda metade das chaves e registros na nova folha
	 for(i = split, j = 0; i < ord; i++, j ++){
	 	new_leaf-> pointers[j] = new_leaf->pointers[i];
	 	new_leaf->keys[j] = temp_keys[i];
	 	new_leaf->num_keys ++;
	 }

	 free(temp_pointers);
	 free(temp_keys);

	 /*o último ponteiro da nova folha vai apontar para a folha cujo ultimo ponteiro da folha antiga costumava apontar
	 	e o ultimo ponteiro da folha antiga agora vai apontar para a nova folha*/
	 new_leaf->pointers[ord - 1] = leaf->pointers[ord - 1];
	 leaf->pointers[ord - 1] = new_leaf;

	 //limpa os índices q não estão sendo usados em ambas as folhas
	 for(i = leaf->num_keys ; i < ord - 1; i++){
	 	leaf->pointers[i] = NULL;
	 }
	 for(i = new_leaf->num_keys; i <ord - 1; i ++){
	 	new_leaf->pointers[i] = NULL;
	 }

	 /*coloca a mãe da folha antiga como mãe da folha nova
	 e coloca a primeira chave da nova folha como a chave do nó-folha */
	 new_leaf->parent = leaf->parent;
	 new_key = new_leaf->keys[0];

	 //e finalmente insere a nova folha no nó mãe
	 return insert_into_parent(root, leaf, key, new_leaf);
}

/*Insere em um nó uma nova chave e um noov ponteiro de nó filho
 sem que isso torne o nó grande demais*/

 node * insert_into_node(node * root, node * n, int left_index, unsigned long long int key, node * right){
 	int i;

 	/*caminha da ultima chave inserida no nó até o indice depois do esquerdo
 	e passa as chaves já inseridas um índice para frente de forma q o índice depois do esquerdo
 	fique livre para uso*/
 	for(i = n->num_keys; i > left_index; i --){
 		n->pointers[i+1] = n->pointers[i];
 		n->keys[i] = n->keys[i -1];
 	}

 	n->pointers[left_index +1] = right; //insere a referencia para o novo nó apos o indice da esquerda do nó antigo
 	n->keys[left_index] = key;
 	n->num_keys ++;

 	return root;
 }

 /*Insere em um nó uma nova chave e ponteiro para nó filho de forma que
 o nó se torne grande demais e seja particionado em 2*/

 node * insert_into_node_after_splitting(node * root, node * old_node, int left_index, unsigned long long int key, node * right){

 	int i, j, split, k_prime;
 	int ord = root->order;
 	node * new_node;
 	node *child;
 	unsigned long long int * temp_keys;
 	node ** temp_pointers;

 	/*Criamos um vetor de chaves e um vetor de ponteiros para armazenar toda a informação na ordem certa
 		e depois criamos um novo nó e copiamos no nó antigo metado das chaves e metade dos ponteiros
 		e no nó novo a outra metade*/

 		temp_pointers = malloc((ord + 1)* sizeof(node *));
 		temp_keys = malloc((ord + 1)* sizeof(unsigned long long int));

 		//percorre o nó antigo gravando cada ponteiro no vetor de nós filhos temporario
 		//quando chega no indice onde do ponteiro novo será inserido ele pula o indice
 		for(i = 0, j = 0; i < old_node->num_keys + 1; i++, j++){
 			if(j == left_index + 1){
 				j ++;
 			}
 			temp_pointers[j] = old_node->pointers[i];
 		}

 		//faz a mesma coisa para o vetor de chaves
 		for(i =0,j=0; i <old_node->num_keys; i++, j++){
 			if(j == left_index){
 				j++;
 			}
 			temp_keys[j] = old_node->keys[i];
 		}

 		/*Cria um novo nó e copia metade das chaves e ponteiros para ele
 		e a outra metade para o nó antigo*/
 		split = cut(ord);
 		new_node = make_node(ord);
 		old_node->num_keys = 0;

 		//copia a primeira metade das chaves e ponteiros para o nó antigo
 		for(i = 0; i <split - 1; i++){
 			old_node->pointers[i] = temp_pointers[i];
 			old_node->keys[i] = temp_keys[i];
 			old_node->num_keys ++;
 		}
 		old_node->pointers[i] = temp_pointers[i];

 		//armazena a chave do final do nó com as menores chaves
 		//isso vai ser usado depois para inserir essa chave no pai dos 2 nós, essa é a chave q sobe
 		k_prime = temp_keys[split - 1];

 		//i começa como o pŕoximo indice depois do ultimo inserido no nó antigo
 		/*copia a segunda metade das chaves e ponteiros e cola no novo nó*/
 		for(++ i, j =0; i <ord; i ++, j ++ ){
 			new_node->pointers[j] = temp_pointers[i];
 			new_node->keys[j] = temp_keys[i];
 			new_node->num_keys ++;
 		}


 		new_node->pointers[j] = temp_pointers[i];
 		free(temp_pointers);
 		free(temp_keys);
 		new_node->parent = old_node->parent;

 		//caminha pelos nós filhos do novo nó e faz com que cada um deles tenha a referencia do nó mãe como parent
 		for(i = 0; i <= new_node->num_keys; i++){
 			child = new_node->pointers[i];
 			child->parent = new_node;
 		}

 		/*e finalmente insere uma nova chave no nó mãe dos dois nós gerados pela partição
			o velho a esquerda e o novo a direita
 		*/
			return insert_into_parent(root, old_node, k_prime, new_node);
 }


 /*Insere um novo nó(ou folha) na árvore
  retorna a raiz da árvore depois da inserção*/

 node * insert_into_parent(node * root, node * left, unsigned long long int key, node * right){

 	int left_index;
 	int ord = root->order;
 	node * parent;

 	parent = left->parent;

 	/*Caso número 1: Uma nova raiz*/
 	if(parent == NULL){
 		return insert_into_new_root(left, key, right);
 	}

 	/*Caso número 2: Uma folha ou um nó*/

 	//procuramos no nó mãe o ponteiro para o nó da esquerda
 	left_index = get_left_index(parent, left);

 	//A nova chave cabe no nó sem estourar ele
 	if(parent->num_keys < (ord-1)){
 		return insert_into_node(root, parent, left_index, key, right);
 	}

 	//A nova chave vai estourar o nó, precisamos dividi-lo em 2
 	return insert_into_node_after_splitting(root, parent, left_index, key, right);
 }

 /*Cria uma nova raiz para 2 sub-árvores
 	e depois insere a chave correta na nova raiz*/

node * insert_into_new_root(node * left, unsigned long long int key, node * right){

	int ord = left->order;
	node * root = make_node(ord);
	root->keys[0] = key;
	root->pointers[0] =left;
	root->pointers[1] = right;
	root->num_keys++;
	root->parent = NULL;
	left->parent = root;
	right->parent = root;
	return root;
}

/*Primeira inserção, começando uma nova árvore!*/
node * start_new_tree(unsigned long long int key, record * pointer, int order){

	node * root = make_leaf(order);
	root->keys[0] = key;
	root->pointers[0] = pointer;
	root->pointers[order -1] = NULL;
	root->parent = NULL;
	root->num_keys ++;
	root->order = order;
	return root;
}

/*Função principal de inserção
 insere na árvore uma chave e seu ponteiro de registro ou nó filho*/
//é o ponto de entrada de todos os tipos de inserção e é chamada pela main
node * insert(node * root, unsigned long long int key, char **rec, int size, int key_id, int order){

	record * pointer;
	node * leaf;

	/*Se a chave já existe*/
	if (find_rec(root, key) != NULL){
		return root;
	}

	/*Cria um novo registro com os valores dados*/
	pointer = make_record(rec, size, key_id);


	/*Se a árvore não existe ainda*/
	if(root == NULL){
		return start_new_tree(key, pointer, order);
	}

	/*Se a árvore existe*/

	//encontramos uma folha
	leaf = find_leaf(root, key);

	/*Se a folha tem espaço para a chave e ponteiro*/
	if(leaf->num_keys < order -1){
		leaf = insert_into_leaf(leaf, key, pointer);
		return root;
	}

	/*A folha precisa ser dividida em 2*/
	return insert_into_leaf_after_splitting(root, leaf, key, pointer);

}