#include "arvoreb.h"

/* Cria uma arvore B com a ordem passada pelo parametro. Devolve NULL
   Caso a ordem seja maior do que o tamanho maximo especificado, ou 
   se deu algum pau de memoria
*/
ArvB *ArvBCria(int ordem) {
  ArvB *arv=NULL;

  if ((ordem < 1) || (ordem > TAMMAX)) 
    return NULL;

  if ( (arv=(ArvB*)calloc(1,sizeof(ArvB))) == NULL )
    return NULL;

  arv->ordem = ordem;
  arv->elems = 0;

  return arv;
}



/* Destroi a Arvore B. O apontador arvore deve retornar Nulo.
   int retorna 1 se tudo deu certo, ou 0 se deu algum tipo de pau.
*/
int ArvBDestroi(ArvB **arvore) { 
  int i;

  if (arvore == NULL)
    return 0;

  if (*arvore == NULL) 
    return 1;
 
  for (i=0; i < (*arvore)->elems; i++)
    if ( ArvBDestroi(&((*arvore)->filhos[i])) == 0 ) 
      return 0;
  ArvBDestroi(&((*arvore)->filhos[i]));
  free(*arvore);
  *arvore = NULL;

  return 1;
} 




#define NenhumValor INT_MIN

ArvB *ArvBNovoNoh(ArvB *arv1, ArvB *arv2, int ordem, int valor) {
  ArvB *tmp;

  tmp = ArvBCria(ordem);
  tmp->filhos[0] = arv1;
  tmp->filhos[1] = arv2;
  tmp->info[0] = valor;
  tmp->elems = 1;

  return tmp;
}


void ArvBInsereNoNoh(ArvB *arvore, ArvB *filho, int valor) {
  int j;

  for (j=arvore->elems; (j>0) && (valor < arvore->info[j-1]); j-- ) {
    arvore->info[j] = arvore->info[j-1];
    arvore->filhos[j+1] = arvore->filhos[j];
  }
  arvore->elems++;
  arvore->info[j] = valor;
  arvore->filhos[j+1] = filho;
}

/* arvore....: a B-Tree na qual voce quer inserir o valor
   novaarvore: a B-Tree na qual contém a segunda metade resultante da
               operação de quebra.
   valor.....: valor a inserir
*************************************************************************
*** Funcionamento:
    Esta funcao vai até o local de inserção do 'valor' e o insere. Caso 
 este valor ultrapasse a ordem da árvore, o nó em qual o 'valor' foi 
 inserido é quebrado. 
    Para que isso aconteca, copiamos para uma árvore  'novaarvore' 
 (passada por referência) os elementos apartir da posição (metade+1) até 
 o fim. Deixamos na 'arvore' os elementos da posicao 0 até a metade. 
 E retornamos o valor da posicao do meio, fazendo com que este "suba".
    Como a função é recursiva, se possuirmos um retorno diferente de 
 'NenhumValor' (este é um #define de INT_MIX, só para indicar que o valor
 retornado não é um número válido, isto é, não é um valor a ser "subido"),
 devemos inserir este valor retornado no nó atual e colocar como filho 
 direito dele (->filhos[i+1]) a 'novaarvore' (isto é feito com a função
 ArvBInsereNoNoh(*arvore,*novaarvore,ins)).
    O valor 'NenhumValor' será retornado só quando não tiver mais filhos
 para inserir, isto é, quando a inserção for feita em um nó com ordem-1
 elementos.
   
*/

int ArvBInsereInterno(ArvB **arvore, ArvB **novaarvore, int valor) {
  int i, j, k;
  int ins;

  if ( *arvore == NULL ) { /* Este é o fim da arvore */
    *novaarvore = NULL;
    return valor;
  } else {
    /* Ache a posicao da inserção */
    for (i=0; (i < (*arvore)->elems) && (valor  > (*arvore)->info[i]); i++);
    /* Insere no filho. RECURSAO*/
    ins = ArvBInsereInterno(&((*arvore)->filhos[i]), novaarvore, valor);

    if ( ins != NenhumValor ) { /* temos que inserir um valor */
      /* Insere no nó, mesmo que ultrapasse a ordem.
       * Coloque como filho direito a subarvore 'novaarvore'
       */
      ArvBInsereNoNoh(*arvore,*novaarvore,ins); 

      if ((*arvore)->elems > (*arvore)->ordem) {
	/* quebre o noh atual */
	*novaarvore = ArvBCria((*arvore)->ordem);
	/* copia da metade+1 para o novo vetor */
	k = (*arvore)->elems;
	(*novaarvore)->filhos[0] = (*arvore)->filhos[(*arvore)->elems/2+1];
	(*novaarvore)->filhos[0] = (*arvore)->filhos[k/2+1];
	for (j=(k/2+1); j < k; j++) {
	  ArvBInsereNoNoh(*novaarvore,(*arvore)->filhos[j+1],(*arvore)->info[j]);
	  (*arvore)->elems--;
	  (*arvore)->info[j]=0; /* para ficar bonitinho */
	}
	(*arvore)->elems--; /* desconsidera o que vai subir */
	k = (*arvore)->info[(*arvore)->elems]; /*guarda o elemento para retornar */
	(*arvore)->info[(*arvore)->elems]=0; /* para ficar bonitinho */

	return k; /* retorna k, que é a mediana, o valor que vai subir */
      }
    }
    return NenhumValor; /* nao precisa inserir nenhum valor */
  }
}



/* Insere o elemento "Valor" na arvore "arvore". Devolve 1 se 
   deu tudo certo, devolve 0 se deu pau em alguma coisa.
   (por exemplo, se a arvore nao existe, ou se esse valor ja 
   existe na arvore).
*/
int ArvBInsere(ArvB **arvore, int valor) {
  int ins;
  ArvB *novaarvore;

  if ( *arvore == NULL ) 
    return 0;
  
  if (ArvBBusca(*arvore,valor)) 
    return 0;

  ins = ArvBInsereInterno(arvore, &novaarvore,valor);
  if ( ins != NenhumValor )
    *arvore = ArvBNovoNoh(*arvore,novaarvore,(*arvore)->ordem,ins);

  return 1;
}



/* Busca o Valor 'valor' e retorna a sua altura na árvore.
   Caso não achar o 'valor', faz *altura = 0
*/
void ArvBBuscaAltura(ArvB *arvore, int valor, int *altura) {
  int i;

  (*altura)++;

  for (i=0; ((i < arvore->elems) && (valor > arvore->info[i])); i++);
  
  if ((i < arvore->elems) && (arvore->info[i] == valor))
    return; /* Encontramos o valor no nesta folha */

  if (arvore->filhos[i] == NULL)
    (*altura)=0; /* chegamos à folha e não encontramos o valor */
  else 
    ArvBBuscaAltura(arvore->filhos[i],valor,altura);

}


/* Busca o valor "Valor" na arvore "arvore". 
   A funcao deve retornar 0 se o valor nao existir na arvore ou se 
   ocorrer algum tipo de Pau. Caso o valor esteja na arvore, a funcao
   deve retornar o nivel no qual o valor se encontra (a raiz 
   possui nivel 1
*/
int ArvBBusca(ArvB *arvore, int valor) {
  int h=0;

  ArvBBuscaAltura(arvore,valor,&h);
  return h;
}


/* Remove o valor "valor" da arvore "arvore".
   retorna 0 caso o valor nao exista, ou caso de algum pau
   (como passarem uma arvore nula).
   retorna 1 caso tenha tido sucesso.
*/
int ArvBRemove(ArvB **arvore, int valor) { 
  return 0;
}

/* author: Gustavo Sverzut Barbieri (http://www.gustavobarbieri.com.br) */