/*         CCF 130   -    Trabalho 2   * B-TREE *

      _______________________________________________________________

     |                                                               |

     | Implementar a consulta e a insercao de uma B-Tree.            |

     | As chaves deverao consistir de caracteres de A a Z.           |

     | Cada noh tera M chaves.                                       |

     | As chaves serao lidas de um arquivo c:/temp/chaves.txt        |

     |_______________________________________________________________|



         Carlos Henrique Silva Galdino - 14256

         Fernanda Maria Villela Reis - 15583      */





# include <stdio.h>

# include <stdlib.h>

# include <math.h>

# include <string.h>

const int M = 2;


//Estrutura da arvore:

struct arv {
       int folha;

       char info[4];  //Contem os caracteres das chaves

       int n; //Numero atual de chaves no noh

       struct arv *filhos[5];  //Ponteiros para os filhos

       };



typedef struct arv *PONT_ARV;



//Prototipos das funcoes

FILE *abre_arquivo ();        //Abre o arquivo

PONT_ARV pesquisa_BTree (char, PONT_ARV arv);



int main()

{

        int i=0;  //Auxiliares
        char M;

        FILE *arq = abre_arquivo();
                char caracter;

        PONT_ARV raiz = malloc(sizeof(struct arv));
        PONT_ARV aux;
        for (i = 0; i < 4; i++) {
            raiz->filhos[i] = NULL;
        }
        raiz->folha = 0;


        system ("color 5f");

        printf("\n\n\n   =-=-=  B - T R E E  =-=-=\n\n");  //Imprimindo menu


        i = 0;

        do

        {   //Le caracter de um arquivo

            caracter = getc(arq);

            printf ("%c", caracter);
            if (caracter != ',') {
                raiz->info[i] = caracter;

                i++;
            }

         } while(caracter != EOF && i < 4);
         fclose(arq);

        printf ("\n\n\tEntre com a chave que deseja procurar: ");

        scanf ("%c", &M);
        aux = pesquisa_BTree(M,raiz);
        for (i = 0; i < 4; i++)
            printf("\n%d - %c", i, aux->info[i]);
        if (aux->info[0] == M)
            printf("\nachei");
        else
            printf("\nnao achei");
        for (i = 0; i < 4; i++)
            printf("\n\nno da arvore: %c", raiz->info[i]);

        printf ("\n\n");

        system ("pause");



}



//Funcao que abre um arquivo

FILE *abre_arquivo () {

        FILE *arq;

        if(!(arq = fopen("teste.txt","r")))  //Abrindo arquivo

        {

            printf("\n\n\tErro ao abrir arquivo!!!\n");

            system ("pause");

            exit(1);

        }

        return arq;

}



//Funcao que busca um numero na arvore B-Tree

PONT_ARV pesquisa_BTree(char chave, PONT_ARV arv) {

      int i;

      if (arv != NULL) {

           for (i = 1; ((i <= arv->n) && (arv->info[i-1] < chave)); i++)

           if (i > (arv->n) || (arv->info[i-1] > chave))

              return pesquisa_BTree(chave, arv->filhos[i-1]);

           else

               return arv;

      }

      else

          return NULL;

}